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:

// Composite.h

class Component
{
public:
	virtual ~Component() {}
	virtual void AddComponent(Component *component) {}       // empty default implementation
	virtual void RemoveComponent(Component *component) {}    // empty default implementation
	virtual Component *GetChild(int index) {}                // empty default implementation
	void SetParent(Component *component);
	Component *GetParent();
	virtual void Print() = 0;                                // the abstract operation
protected:
	Component() : m_parent(nullptr) {}                       // default parent is null
	Component *m_parent;
};

class Composite : public Component
{
public:
	~Composite() override {}
	void AddComponent(Component *component) override;
	void RemoveComponent(Component *component) override;
	Component *GetChild(int index) override;
	void Print() override;
protected:
	Composite() {}
	std::vector<Component*> m_components;                    // a list of components 
};

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:

// Composite.cpp

void Composite::AddComponent(Component *component)
{
	component->SetParent(this);
	m_components.push_back(component);
}

void Composite::RemoveComponent(Component *component)
{
	std::vector<Component*>::iterator it = m_components.begin();
	while (it != m_components.end())
	{
		if (*it == component)
		{
			m_components.erase(it);
			break;
		}
		it++;
	}
}

Component *Composite::GetChild(int index)
{
	if (index < m_components.size())
		return m_components[index];
	else
		return nullptr;
}

void Composite::Print()
{	
	for (Component *component : m_components)
	{
		if (m_parent)
		{
			int i = 1;
			Component *parent = m_parent;
			while (parent = parent->GetParent())
				i++;
			while (i--)
				std::cout << "     ";
		}
		
		std::cout << "    ";
		component->Print();
	}
}

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:

// Composite.h

class ToDoItem : public Component
{
public:
	~ToDoItem() override {}
	ToDoItem(std::string task) : m_task(task) {}
	void Print() override;
private:
	const std::string m_task;
};

class ToDoList : public Composite
{
public:
	ToDoList(std::string list_name) : m_list_name(list_name) {}
	void Print() override;
private:
	const std::string m_list_name;
};

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:

// Composite.cpp

void ToDoList::Print()
{
	std::cout << "* " << m_list_name << ":" << std::endl;
	
	Composite::Print();
}

void ToDoItem::Print()
{
	std::cout << "- " << m_task << std::endl;
}

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

// main.cpp

#include "Composite.h"

int main(int argc, char **argv)
{
	Component *shopping_list = new ToDoList("do shoppping");
	
	Component *item1_1 = new ToDoItem("buy socks");
	Component *item1_2 = new ToDoItem("buy shirts");
	Component *item1_3 = new ToDoItem("buy towels");
	Component *item1_4 = new ToDoItem("buy pens");
	Component *item1_5 = new ToDoItem("buy phone charger");
	
	Component *food_list = new ToDoList("buy food");
	
	Component *item2_1 = new ToDoItem("buy soup");
	Component *item2_2 = new ToDoItem("buy pasta");
	Component *item2_3 = new ToDoItem("buy orange juice");
	Component *item2_4 = new ToDoItem("buy chicken");
	
	Component *grocery_list = new ToDoList("buy groceries");
	
	Component *item3_1 = new ToDoItem("buy potatoes");
	Component *item3_2 = new ToDoItem("buy onions");
	Component *item3_3 = new ToDoItem("buy tomatoes");
	Component *item3_4 = new ToDoItem("buy pickles");
	
	grocery_list->AddComponent(item3_1);
	grocery_list->AddComponent(item3_2);
	grocery_list->AddComponent(item3_3);
	grocery_list->AddComponent(item3_4);
	
	food_list->AddComponent(item2_1);
	food_list->AddComponent(item2_2);
	food_list->AddComponent(item2_3);
	food_list->AddComponent(item2_4);
	food_list->AddComponent(grocery_list);
	
	shopping_list->AddComponent(item1_1);
	shopping_list->AddComponent(item1_3);
	shopping_list->AddComponent(item1_4);
	shopping_list->AddComponent(item1_5);
	shopping_list->AddComponent(food_list);
	
	shopping_list->Print();

	return 0;
}

The output of the test code is the following:

* do shoppping:
    - buy socks
    - buy towels
    - buy pens
    - buy phone charger
    * buy food:
         - buy soup
         - buy pasta
         - buy orange juice
         - buy chicken
         * buy groceries:
              - buy potatoes
              - buy onions
              - buy tomatoes
              - buy pickles

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:

// Composite.h

class Visitor;

class Component
{
public:
        // other members as before...

	virtual void Accept(Visitor *visitor) = 0;

        // other members as before...
};

class Composite : public Component
{
public:
	// other members as before...

	void Accept(Visitor *visitor) override; 

        // other members as before...
};

class ToDoItem : public Component
{
public:
        // other members as before...

	void Accept(Visitor *visitor) override;
	std::string &GetItemName() { return m_task; }
private:
	std::string m_task;
};

class ToDoList : public Composite
{
public:
        // other members as before...

	void Accept(Visitor *visitor) override;
	std::string &GetListName() { return m_list_name; }
private:
	std::string m_list_name;
};

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

// Composite.cpp

void Composite::Accept(Visitor *visitor)
{
	for (Component *component : m_components)
		component->Accept(visitor);
}

void ToDoList::Accept(Visitor *visitor)
{
	visitor->Visit(this); 
	
	Composite::Accept(visitor);
}

void ToDoItem::Accept(Visitor *visitor)
{
	visitor->Visit(this); 
}

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

// Visitor.h

#include "string"

class ToDoItem;
class ToDoList;

class Visitor
{
public:
	virtual ~Visitor() {}
	virtual void Visit(ToDoItem *component) = 0;    // visit ToDoItem objects (leaves)
	virtual void Visit(ToDoList *composite) = 0;    // visit ToDoList objects (composites)
protected:
	Visitor() {}
};

class AddTextVisitor : public Visitor
{
public:
	AddTextVisitor(const std::string &item_text, const std::string &list_text) : m_item_text(item_text), m_list_text(list_text) {}
	void Visit(ToDoItem *component) override;
	void Visit(ToDoList *composite) override;
private:
	std::string m_item_text;
	std::string m_list_text;
};

// Visitor.cpp

#include "Visitor.h"
#include "Composite.h"

void AddTextVisitor::Visit(ToDoItem *component)
{
	component->GetItemName().append(m_item_text);
}

void AddTextVisitor::Visit(ToDoList *composite)
{
	composite->GetListName().append(m_list_text);
}

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:

// main.cpp

#include "Composite.h"
#include "Visitor.h"

int main(int argc, char **argv)
{
        // same as before...
	
	shopping_list->Print();
	
	shopping_list->Accept(new AddTextVisitor("!", "..."));  // watch out for memory leaks of course
	
	shopping_list->Print();

	return 0;
}

The output is the following:

* do shoppping:
    - buy socks
    - buy towels
    - buy pens
    - buy phone charger
    * buy food:
         - buy soup
         - buy pasta
         - buy orange juice
         - buy chicken
         * buy groceries:
              - buy potatoes
              - buy onions
              - buy tomatoes
              - buy pickles

* do shoppping...:
    - buy socks!
    - buy towels!
    - buy pens!
    - buy phone charger!
    * buy food...:
         - buy soup!
         - buy pasta!
         - buy orange juice!
         - buy chicken!
         * buy groceries...:
              - buy potatoes!
              - buy onions!
              - buy tomatoes!
              - buy pickles!