Composite

From Wikibooks, open books for an open world
Jump to: navigation, search

Bridge Computer Science Design Patterns
Composite
Decorator

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 repertory. 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.

Composite pattern in UML.
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.

Implementation in C#
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();
        }
    }
}
Implementation in Common Lisp

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)))
Implementation in Java

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.).

  1. /** "Component" */
    
  2. interface Graphic {
    
  3.     // Prints the graphic.
    
  4.     public void print();
    
  5. }
    
  1. /** "Composite" */
    
  2. import java.util.List;
    
  3. import java.util.ArrayList;
    
  4. class CompositeGraphic implements Graphic {
    
  5.     // Collection of child graphics.
    
  6.     private List<Graphic> mChildGraphics = new ArrayList<Graphic>();
    
  7.     // Prints the graphic.
    
  8.     public void print() {
    
  9.         for (Graphic graphic : mChildGraphics) {
    
  10.             graphic.print();
    
  11.         }
    
  12.     }
    
  13.     // Adds the graphic to the composition.
    
  14.     public void add(Graphic graphic) {
    
  15.         mChildGraphics.add(graphic);
    
  16.     }
    
  17.     // Removes the graphic from the composition.
    
  18.     public void remove(Graphic graphic) {
    
  19.         mChildGraphics.remove(graphic);
    
  20.     }
    
  21. }
    
  1. /** "Leaf" */
    
  2. class Ellipse implements Graphic {
    
  3.     // Prints the graphic.
    
  4.     public void print() {
    
  5.         System.out.println("Ellipse");
    
  6.     }
    
  7. }
    
  1. /** Client */
    
  2. public class Program {
    
  3.     public static void main(String[] args) {
    
  4.         // Initialize four ellipses
    
  5.         Ellipse ellipse1 = new Ellipse();
    
  6.         Ellipse ellipse2 = new Ellipse();
    
  7.         Ellipse ellipse3 = new Ellipse();
    
  8.         Ellipse ellipse4 = new Ellipse();
    
  9.         // Initialize three composite graphics
    
  10.         CompositeGraphic graphic = new CompositeGraphic();
    
  11.         CompositeGraphic graphic1 = new CompositeGraphic();
    
  12.         CompositeGraphic graphic2 = new CompositeGraphic();
    
  13.         // Composes the graphics
    
  14.         graphic1.add(ellipse1);
    
  15.         graphic1.add(ellipse2);
    
  16.         graphic1.add(ellipse3);
    
  17.         graphic2.add(ellipse4);
    
  18.         graphic.add(graphic1);
    
  19.         graphic.add(graphic2);
    
  20.         // Prints the complete graphic (four times the string "Ellipse").
    
  21.         graphic.print();
    
  22.     }
    
  23. }
    
Implementation in PHP
<?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();
Implementation in Python
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()
Implementation in Ruby
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


Clipboard

To do:
Add more illustrations.


Bridge Computer Science Design Patterns
Composite
Decorator


You have questions about this page?
Ask it here:


Create a new page on this book: