Composite
The composite design pattern reduces the cost of an implementation that handles data represented as a tree. When an application does a process on a tree, usually the process has to handle the iteration on the components, the move on the tree and has to process the nodes and the leafs separately. All of this creates a big amount of code. Suppose that you have to handle a file system repository. Each folders can contain files or folders. To handle this, you have an array of items that can be file or folder. The files have a name and the folders are arrays. Now you have to implement a file search operation on the whole folder tree. The pseudo-code should look like this:
method searchFilesInFolders(rootFolder, searchedFileName) is
input: a list of the content of the rootFolder.
input: the searchedFileName that should be found in the folders.
output: the list of encountered files.
Empty the foundFiles list
Empty the parentFolders list
Empty the parentIndices list
currentFolder := rootFolder
currentIndex := 0
Add rootFolder to parentFolders
while parentFolders is not empty do
if currentIndex is out of currentFolder then
currentFolder := last item of parentFolders
Remove the last item of parentFolders
currentIndex := last item of parentIndices + 1
Remove the last item of parentIndices
else if the item at the currentIndex of the currentFolder is a folder then
currentFolder := the folder
Add currentFolder to parentFolders
Add currentIndex to parentIndices
currentIndex := 0
otherwise
if the name of the file is equal to the searchedFileName then
Add the file to foundFiles
Increment currentIndex
Return the foundFiles
In the previous code, each iteration of the same while loop is a process of one node or leaf. At the end of the process, the code move to the position of the next node or leaf to process. There are three branches in the loop. The first branch is true when we have processed all the children of the node and it moves to the parent, the second goes into a child node and the last process a leaf (i.e. a file). The memory of the location should be stored to go back in the tree. The problem in this implementation is that it is hardly readable and the process of the folders and the files is completely separate. This code is heavy to maintain and you have to think to the whole tree each moment. The folders and the files should be called the same way so they should be objects that implements the same interface.
- Component
- is the abstraction for all components, including composite ones.
- declares the interface for objects in the composition.
- (optional) defines an interface for accessing a component's parent in the recursive structure, and implements it if that's appropriate.
- Leaf
- represents leaf objects in the composition.
- implements all Component methods.
- Composite
- represents a composite Component (component having children).
- implements methods to manipulate children.
- implements all Component methods, generally by delegating them to its children.
So now the implementation is rather like this:
interface FileSystemComponent is
method searchFilesInFolders(searchedFileName) is
input: the searchedFileName that should be found in the folders.
output: the list of encountered files.
class File implementing FileSystemComponent is
method searchFilesInFolders(searchedFileName) is
input: the searchedFileName that should be found in the folders.
output: the list of encountered files.
if the name of the file is equal to the searchedFileName then
Empty the foundFiles list
Add the file to foundFiles
Return the foundFiles
otherwise
Return an empty list
class Folder implementing FileSystemComponent is
field children is
The list of the direct children.
method searchFilesInFolders(searchedFileName) is
input: the searchedFileName that should be found in the folders.
output: the list of encountered files.
Empty the foundFiles list
for each child in children
Call searchFilesInFolders(searchedFileName) on the child
Add the result to foundFiles
Return the foundFiles
As you can see, a component can be an individual object and also can be a collection of objects. A Composite pattern can represent both the conditions. In this pattern, one can develop tree structures for representing part-whole hierarchies.
Examples
The best example of use of this pattern is the Graphical User Interface. The widgets of the interface are organized in a tree and the operations (resizing, repainting...) on all the widgets are processed using the composite design pattern.
Cost
This pattern is one of the least expensive patterns. You can implement it each time you have to handle a tree of data without worrying. There is no bad usage of this pattern. The cost of the pattern is only to handle the children of a composite but this cost would be required and more expensive without the design pattern.
Creation
You have to create an almost empty interface and implement the management of the composite children. This cost is very low.
Maintenance
You can't get caught in the system. The only relatively expensive situation occurs when you have to often change the operations applied to the whole data tree.
Removal
You should remove the pattern when you remove the data tree. So you just remove all in once. This cost is very low.
Advices
- Put the composite and component terms in the name of the classes to indicate the use of the pattern to the other developers.
Implementations
Various examples of the composite pattern.
using System;
using System.Collections.Generic;
namespace Composite
{
class Program
{
interface IGraphic
{
void Print();
}
class CompositeGraphic : IGraphic
{
private List<IGraphic> child = new List<IGraphic>();
public CompositeGraphic(IEnumerable<IGraphic> collection)
{
child.AddRange(collection);
}
public void Print()
{
foreach(IGraphic g in child)
{
g.Print();
}
}
}
class Ellipse : IGraphic
{
public void Print()
{
Console.WriteLine("Ellipse");
}
}
static void Main(string[] args)
{
new CompositeGraphic(new IGraphic[]
{
new CompositeGraphic(new IGraphic[]
{
new Ellipse(),
new Ellipse(),
new Ellipse()
}),
new CompositeGraphic(new IGraphic[]
{
new Ellipse()
})
}).Print();
}
}
}
The following example, written in Common Lisp, and translated directly from the Java example below it, implements a method named print-graphic, which can be used on either an ellipse, or a list whose elements are either lists or ellipses.
(defstruct ellipse) ;; An empty struct.
;; For the method definitions, "object" is the variable,
;; and the following word is the type.
(defmethod print-graphic ((object null))
NIL)
(defmethod print-graphic ((object cons))
(print-graphic (first object))
(print-graphic (rest object)))
(defmethod print-graphic ((object ellipse))
(print 'ELLIPSE))
(let* ((ellipse-1 (make-ellipse))
(ellipse-2 (make-ellipse))
(ellipse-3 (make-ellipse))
(ellipse-4 (make-ellipse)))
(print-graphic (cons (list ellipse-1 (list ellipse-2 ellipse-3)) ellipse-4)))
The following example, written in Java, implements a graphic class, which can be either an ellipse or a composition of several graphics. Every graphic can be printed. In Backus-Naur form,
Graphic ::= ellipse | GraphicList
GraphicList ::= empty | Graphic GraphicList
It could be extended to implement several other shapes (rectangle, etc.) and methods (translate, etc.).
import java.util.List;
import java.util.ArrayList;
/** "Component" */
interface Graphic {
//Prints the graphic.
public void print();
}
/** "Composite" */
class CompositeGraphic implements Graphic {
//Collection of child graphics.
private final List<Graphic> childGraphics = new ArrayList<>();
//Adds the graphic to the composition.
public void add(Graphic graphic) {
childGraphics.add(graphic);
}
//Prints the graphic.
@Override
public void print() {
for (Graphic graphic : childGraphics) {
graphic.print(); //Delegation
}
}
}
/** "Leaf" */
class Ellipse implements Graphic {
//Prints the graphic.
@Override
public void print() {
System.out.println("Ellipse");
}
}
/** Client */
class CompositeDemo {
public static void main(String[] args) {
//Initialize four ellipses
Ellipse ellipse1 = new Ellipse();
Ellipse ellipse2 = new Ellipse();
Ellipse ellipse3 = new Ellipse();
Ellipse ellipse4 = new Ellipse();
//Creates two composites containing the ellipses
CompositeGraphic compositGraphic2 = new CompositeGraphic();
compositGraphic2.add(ellipse1);
compositGraphic2.add(ellipse2);
compositGraphic2.add(ellipse3);
CompositeGraphic compositGraphic3 = new CompositeGraphic();
compositGraphic3.add(ellipse4);
//Create another graphics that contains two graphics
CompositeGraphic compositGraphic = new CompositeGraphic();
compositGraphic.add(compositGraphic2);
compositGraphic.add(compositGraphic3);
//Prints the complete graphic (Four times the string "Ellipse").
compositGraphic.print();
}
}
The following example, written in Java, implements a graphic class, which can be either an ellipse or a composition of several graphics. Every graphic can be printed. In algebraic form,
Graphic = ellipse | GraphicList
GraphicList = empty | Graphic GraphicList
It could be extended to implement several other shapes (rectangle, etc.) and methods (translate, etc.).
/** "Component" */
interface Graphic {
// Prints the graphic.
public void print();
}
/** "Composite" */
import java.util.List;
import java.util.ArrayList;
class CompositeGraphic implements Graphic {
// Collection of child graphics.
private List<Graphic> mChildGraphics = new ArrayList<Graphic>();
// Prints the graphic.
public void print() {
for (Graphic graphic : mChildGraphics) {
graphic.print();
}
}
// Adds the graphic to the composition.
public void add(Graphic graphic) {
mChildGraphics.add(graphic);
}
// Removes the graphic from the composition.
public void remove(Graphic graphic) {
mChildGraphics.remove(graphic);
}
}
/** "Leaf" */
class Ellipse implements Graphic {
// Prints the graphic.
public void print() {
System.out.println("Ellipse");
}
}
/** Client */
public class Program {
public static void main(String[] args) {
// Initialize four ellipses
Ellipse ellipse1 = new Ellipse();
Ellipse ellipse2 = new Ellipse();
Ellipse ellipse3 = new Ellipse();
Ellipse ellipse4 = new Ellipse();
// Initialize three composite graphics
CompositeGraphic graphic = new CompositeGraphic();
CompositeGraphic graphic1 = new CompositeGraphic();
CompositeGraphic graphic2 = new CompositeGraphic();
// Composes the graphics
graphic1.add(ellipse1);
graphic1.add(ellipse2);
graphic1.add(ellipse3);
graphic2.add(ellipse4);
graphic.add(graphic1);
graphic.add(graphic2);
// Prints the complete graphic (four times the string "Ellipse").
graphic.print();
}
}
<?php
/** "Component" */
interface Graphic
{
/**
* Prints the graphic
*
* @return void
*/
public function printOut();
}
/**
* "Composite" - Collection of graphical components
*/
class CompositeGraphic implements Graphic
{
/**
* Collection of child graphics
*
* @var array
*/
private $childGraphics = array();
/**
* Prints the graphic
*
* @return void
*/
public function printOut()
{
foreach ($this->childGraphics as $graphic) {
$graphic->printOut();
}
}
/**
* Adds the graphic to the composition
*
* @param Graphic $graphic Graphical element
*
* @return void
*/
public function add(Graphic $graphic)
{
$this->childGraphics[] = $graphic;
}
/**
* Removes the graphic from the composition
*
* @param Graphic $graphic Graphical element
*
* @return void
*/
public function remove(Graphic $graphic)
{
if (in_array($graphic, $this->childGraphics)) {
unset($this->childGraphics[array_search($graphic, $this->childGraphics)]);
}
}
}
/** "Leaf" */
class Ellipse implements Graphic
{
/**
* Prints the graphic
*
* @return void
*/
public function printOut()
{
echo "Ellipse";
}
}
/** Client */
//Initialize four ellipses
$ellipse1 = new Ellipse();
$ellipse2 = new Ellipse();
$ellipse3 = new Ellipse();
$ellipse4 = new Ellipse();
//Initialize three composite graphics
$graphic = new CompositeGraphic();
$graphic1 = new CompositeGraphic();
$graphic2 = new CompositeGraphic();
//Composes the graphics
$graphic1->add($ellipse1);
$graphic1->add($ellipse2);
$graphic1->add($ellipse3);
$graphic2->add($ellipse4);
$graphic->add($graphic1);
$graphic->add($graphic2);
//Prints the complete graphic (four times the string "Ellipse").
$graphic->printOut();
class Component(object):
def __init__(self, *args, **kw):
pass
def component_function(self): pass
class Leaf(Component):
def __init__(self, *args, **kw):
Component.__init__(self, *args, **kw)
def component_function(self):
print "some function"
class Composite(Component):
def __init__(self, *args, **kw):
Component.__init__(self, *args, **kw)
self.children = []
def append_child(self, child):
self.children.append(child)
def remove_child(self, child):
self.children.remove(child)
def component_function(self):
map(lambda x: x.component_function(), self.children)
c = Composite()
l = Leaf()
l_two = Leaf()
c.append_child(l)
c.append_child(l_two)
c.component_function()
module Component
def do_something
raise NotImplementedError
end
end
class Leaf
include Component
def do_something
puts "Hello"
end
end
class Composite
include Component
attr_accessor :children
def initialize
self.children = []
end
def do_something
children.each {|c| c.do_something}
end
def append_child(child)
children << child
end
def remove_child(child)
children.delete child
end
end
composite = Composite.new
leaf_one = Leaf.new
leaf_two = Leaf.new
composite.append_child(leaf_one)
composite.append_child(leaf_two)
composite.do_something
