Composite Design Pattern

According to the GoF book, the intent of the Composite pattern is to “compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly.” In other words this pattern allows us to create tree data structures whose elements can be objects or collections of objects, and lets us interact with the structure’s elements without knowing if the specific element is a single object or a composition of objects. Let’s have a look at the class diagram for the pattern:

An abstract base class defines an interface common to all Components: Leaf and Composite derives from it, and it is this interface that lets clients treat all elements of the structure uniformly. The Leaf class represents single object, also called primitives and implements the operations declared in the base class by executing them directly; a Composite is a composition of objects and has a list of child Components. It implements an operation by forwarding it to all of its children (sub-components), and performing some additional work before and/or after forwarding. A Composite is itself a Component so it implements the same interface and is indistinguishable from a simple component from a client’s perspective. There can be different Leaf classes, and different Composite classes. We can refactor the common functionality out of the single Composite sub classes into an abstract Composite base class that implements the child related methods and the data structure that contains the children. Using this pattern we can create tree structures in which every node is a Leaf or a Composite:

Methods to add/remove components and to access a composite’s subcomponents are generally declared in the Component base class/interface. This seems wrong, since a Leaf doesn’t contain children components and shouldn’t be forced to implement methods that it doesn’t use or need. This is a trade-off in order to be able to treat single objects and composites the same way. Generally the solution is to provide a default implememtation in the Component class that does nothing, or that throws an exception, so if such an operation is called on a Component that is not a Composite that operation fails (silently or not). The alternative is to declare the methods in the Composite class and have only composites implement the behavior, but in this case we would need to cast a Component down to a Composite in order to access it, and we would lose the transparency that the pattern provides in letting us treat all elements as Component. In a following example I choose the first approach, and provide a default empty implementation for the child related methods in the Component base abstract class that the Composite class overrides.

The Composite Pattern: an example

As an example, consider a list of tasks to be carried out during the day. Each task is a single thing that has to be done, but we can break up something to do into more sub tasks: for example a task could be “buy groceries”, and it could be split into some sub tasks like “buy onions” and “buy pickels”, and so forth. The “buy groceries” task could be part of a more general task, “buy food”. So we start to see that a task can be a single task or a list of tasks, so let’s put it into code, starting from the Component and Composite base classes:

The Component abstract base class declares the child related methods and gives them a default empty implementation (see the discussion about transparency above); it also declares an abstract operation Print(), that prints the task at hand. Every component can also have a reference to its parent (if it’s the root component the parent is null), this allows us to go up the tree hierarchy. The parent’s reference is set when a component is added to another component with the AddComponent() method. The Composite class, as we saw, abstracts the common functionality of a Composite and implements the child related methods:

As we saw, the Composite class implements the Print() method by forwarding of the operation to the child components, performing some additional work before. Here, the parent’s reference is used to find out which level of the hierarchy we’re in, in order to format the output of the Print() method correctly (we indent the output the more as we go deep into the tree structure). This implementation, as we’ll see, is called from the specific composite subclass in order to carry out the forwarding to the children (common behavior to all composites). Let’s have a look at the ToDoItem (Leaf) and ToDoList (ConcreteComposite) classe definitions and their implementations:

These classes contain a string to hold the name of the task/list of tasks to do and a contructor to set them. The ToDoItem class implements Print() by printing its string directly, while ToDoList class prints its string, then calls the Composite base class implementation to print the string of all the sub components:

Let’s test the code by creating a simple shopping list:

The output of the test code is the following:

Using the Visitor pattern to traverse the tree structure

Tthe Visitor pattern lets us add new operations to our components. As we saw in this post, If the hierarchy doesn’t change frequently, a Visitor is a handy way of adding new behaviour to our classes (if we add new type of components to the hierarchy frequently maybe adding new operation as virtual functions in the Component base class is the way to go). An interesting feature of the Visitor pattern is the ability to get back type information that we lose when we use all elements in the structure as abstract Components. Suppose we want to perform some action that is specific to the concrete component subclass. In our example, suppose we want to add some text to the string that identifies the task, but we want to differentiate whether the actual Component is a Leaf (a ToDoItem) or a Composite (a ToDoList). Using  a dynamic_cast is costly, and adding  a data member that specifies the concrete type in the base class, and then performing  a static_cast isn’t very OO. Visitor pattern to the rescue: adding an abstract Accept() method to the Component base class lets us pass to the element a class implementing the Visitor interface, which declares a Visit() method:

The Accept() method is declared as a pure virtual function in the Component abstract base class and is overriden in the Composite class and in the ToDoItem and ToDoList concrete classes. I also added two getter methods to retrieve the name of the task/list of tasks. The methods perform the same operation ( they retrieve the string containing the name of the task), but in order to demonstrate how the Visitor pattern can help us retrieve lost type informations I gave the functions different names and put them into the different concrete implementation classes (in real code, if we wanted to get the name of the task, we’d probably refactor the name into the Component base class and set it into the Component’s constructor, and provide the Component base class with a non virtual public getter method, but bear with me for this example). The Accept() method simply calls the Visitor’s Visit method, passing a pointer to the concrete type ( as usual, a Composite forward the Accept() request to all its children after carrying out the operation itself):

The Visit() method is overloaded on the concrete component type in the components’ hierarchy:

Doing so allows us to perform a different operation based on the different concrete type of the element in the hierarchy. In our example we create an AddTextVisitor which simply appends some text to the task’s string and some other text to the string in the task lists:

The output is the following: