Chapter 16. The Composite Pattern
Frequently, programmers develop systems in which a component may be either an individual object or a collection of objects. The Composite pattern is designed to accommodate both cases. You can use the Composite to build part-whole hierarchies or to construct data representations of trees. In summary, a composite is a collection of objects, any one of which may be either a composite or just a primitive object. In tree nomenclature, some objects may be nodes with additional branches and some may be leaves.
The problem that develops is the dichotomy between having a single, simple interface to access all the objects in a composite and the ability to distinguish between nodes and leaves. Nodes have children and can have children added to them, whereas leaves do not at the moment have children, and in some implementations they may be prevented from having children added to them.
Some authors have suggested creating a separate interface for nodes and leaves where a leaf could have the methods, such as the following.
public string getName();
public float getValue();
And a node could have these additional methods.
public ArrayList elements();
public Node getChild(string nodeName);
public void add(Object obj);
public void remove(Object obj);
This then leaves us with the programming problem of deciding which elements will be which when we construct the composite. However, Design Patterns suggests that each element should have the same interface whether it is a composite or a primitive element. This is easier to accomplish, but we are left with the question of what the getChild operation should accomplish when the object is actually a leaf.
C# can make this quite easy for us, since every node or leaf can return an ArrayList of the child nodes. If there are no children, the count property returns zero. Thus, if we simply obtain the ArrayList of child nodes from each element, we can quickly determine whether it has any children by checking the count property.
Just as difficult is the issue of adding or removing leaves from elements of the composite. A nonleaf node can have child-leaves added to it, but a leaf node cannot. However, we would like all of the components in the composite to have the same interface. We must prevent attempts to add children to a leaf node, and we can design the leaf node class to raise an error if the program attempts to add to such a node.
An Implementation of a Composite
Let’s consider a small company that began with a single person. He was, of course, the CEO, although he may have been too busy to think about it at first. Then he hired a couple of people to handle the marketing and manufacturing. Soon each of them hired some additional assistants to help with advertising, shipping, and so forth, and they became the company’s first two vice-presidents. As the company’s success increased, the firm continued to grow until it had the organizational chart in Figure 16-1.
Figure 16-1. A typical organizational chart
Computing Salaries
If the company is successful, each of these company members receives a salary, and we could at any time ask for the cost of the control span of any employee to the company. We define this control cost as the salary of that person and those of all subordinates. Here is an ideal example for a composite.
• The cost of an individual employee is simply his or her salary (and benefits).
• The cost of an employee who heads a department is his or her salary plus those of subordinates.
We would like a single interface that will produce the salary totals correctly whether the employee has subordinates or not.
float getSalaries(); //get salaries of all
At this point, we realize that the idea of all Composites having the same standard method names in their interface is probably unrealistic. We’d prefer that the public methods be related to the kind of class we are actually developing. So rather than have generic methods like getValue, we’ll use getSalaries.
The Employee Classes
We could now imagine representing the company as a Composite made up of nodes: managers and employees. It would be possible to use a single class to represent all employees, but since each level may have different properties, it might be more useful to define at least two classes: Employees and Bosses. Employees are leaf nodes and cannot have employees under them. Bosses are nodes that may have employee nodes under them.
We’ll start with the AbstractEmployee class and derive our concrete Employee classes from it.
public interface AbstractEmployee {
float getSalary(); //get current salary
string getName(); //get name
bool isLeaf(); //true if leaf
void add(string nm, float salary); //add subordinate
void add(AbstractEmployee emp); //add subordinate
IEnumerator getSubordinates(); //get subordinates
AbstractEmployee getChild(); //get child
float getSalaries(); //get sum of salaries
}
In C# we have a built-in enumeration interface called IEnumerator. This interface consists of these methods.
bool MoveNext(); //False if no more left
object Current() //get current object
void Reset(); //move to first
So we can create an AbstractEmployee interface that returns an Enumerator. You move through an enumeration, allowing for the fact that it might be empty, using the following approach.
e.Reset();
while (e.MoveNext()) {
Emp = (Employee)e.Current();
//..do computation..
}
This Enumerator may, of course, be empty and can thus be used for both nodes and leaves of the composite.
Our concrete Employee class will store the name and salary of each employee and allow us to fetch them as needed.
public class Employee :AbstractEmployee {
protected float salary;
protected string name;
protected ArrayList subordinates;
//------
public Employee(string nm, float salary) {
subordinates = new ArrayList();
name = nm;
salary = salry;
}
//------
public float getSalary() {
return salary;
}
//------
public string getName() {
return name;
}
//------
public bool isLeaf() {
return subordinates.Count == 0;
}
//------
public virtual AbstractEmployee getChild() {
return null;
}
The Employee class must have concrete implementations of the add, remove, getChild, and subordinates classes. Since an Employee is a leaf, all of these will return some sort of error indication. The subordinates method could return a null, but programming will be more consistent if subordinates returns an empty enumeration.
public IEnumerator getSubordinates() {
return subordinates.GetEnumerator ();
}
The add and remove methods must generate errors, since members of the basic Employee class cannot have subordinates. We throw an Exception if you call these methods in the basic Employee class.
public virtual void add(string nm, float salary) {
throw new Exception(
"No subordinates in base employee class");
}
//------
public virtual void add(AbstractEmployee emp) {
throw new Exception(
"No subordinates in base employee class");
}
The Boss Class
Our Boss class is a subclass of Employee and allows us to store subordinate employees as well. We’ll store them in an ArrayList called subordinates and return them through an enumeration. Thus, if a particular Boss has temporarily run out of Employees, the enumeration will just be empty.
public class Boss:Employee {
public Boss(string name, float salary):base(name,salary) {}
//------
public override void add(string nm, float salary) {
AbstractEmployee emp = new Employee(nm,salary);
subordinates.Add (emp);
}
//------
public override void add(AbstractEmployee emp){
subordinates.Add(emp);
}
//------
If you want to get a list of employees of a given supervisor, you can obtain an Enumeration of them directly from the ArrayList. Similarly, you can use this same ArrayList to return a sum of salaries for any employee and his or her subordinates.
public float getSalaries() {
float sum;
AbstractEmployee esub;
//get the salaries of the boss and subordinates
sum = getSalary();
IEnumerator enumSub = subordinates.GetEnumerator() ;
while (enumSub.MoveNext()) {
esub = (AbstractEmployee)enumSub.Current;
sum += esub.getSalaries();
}
return sum;
}
Note that this method starts with the salary of the current Employee and then calls the getSalaries() method on each subordinate. This is, of course, recursive, and any employees who have subordinates will be included. A diagram of these classes is shown in Figure 16-2.
Figure 16-2. The AbstractEmployee class and how Employee and Boss are derived from it
Building the Employee Tree
We start by creating a CEO Employee and then add his or her subordinates and their subordinates, as follows.
private void buildEmployeeList() {
prez = new Boss("CEO", 200000);
marketVP = new Boss("Marketing VP", 100000);
prez.add(marketVP);
salesMgr = new Boss("Sales Mgr", 50000);
advMgr = new Boss("Advt Mgr", 50000);
marketVP.add(salesMgr);
marketVP.add(advMgr);
prodVP = new Boss("Production VP", 100000);
prez.add(prodVP);
advMgr.add("Secy", 20000);
//add salesmen reporting to sales manager
for (int i = 1; i<=5; i++){
salesMgr.add("Sales" + i.ToString(),
rand_sal(30000));
}
prodMgr = new Boss("Prod Mgr", 40000);
shipMgr = new Boss("Ship Mgr", 35000);
prodVP.add(prodMgr);
prodVP.add(shipMgr);
for (int i = 1; i<=3; i++){
shipMgr.add("Ship" + i.ToString(), rand_sal(25000));
}
for (int i = 1; i<=4; i++){
prodMgr.add("Manuf" + i.ToString(), rand_sal(20000));
}
}
Once we have constructed this Composite structure, we can load a visual TreeView list by starting at the top node and calling the addNode() method recursively until all the leaves in each node are accessed.
private void buildTree() {
EmpNode nod;
nod = new EmpNode(prez);
rootNode = nod;
EmpTree.Nodes.Add(nod);
addNodes(nod, prez);
}
To simplify the manipulation of the TreeNode objects, we derive an EmpNode class that takes an instance of Employee as an argument.
public class EmpNode:TreeNode {
private AbstractEmployee emp;
public EmpNode(AbstractEmployee aemp ):
base(aemp.getName ()) {
emp = aemp;
}
//-----
public AbstractEmployee getEmployee() {
return emp;
}
}
The final program display is shown in Figure 16-3.
Figure 16-3. The corporate organization shown in a TreeView control
In this implementation, the cost (sum of salaries) is shown in the bottom bar for any employee you click on. This simple computation calls the getChild() method recursively to obtain all the subordinates of that employee.
private void EmpTree_AfterSelect(object sender,
TreeViewEventArgs e) {
EmpNode node;
node = (EmpNode)EmpTree.SelectedNode;
getNodeSum(node);
}
//------
private void getNodeSum(EmpNode node) {
AbstractEmployee emp;
float sum;
emp = node.getEmployee();
sum = emp.getSalaries();
lbSalary.Text = sum.ToString ();
}
Self-Promotion
We can imagine cases where a simple Employee would stay in his current job but have new subordinates. For example, a Salesman might be asked to supervise sales trainees. For such a case, it is convenient to provide a method in the Boss class that creates a Boss from an Employee. We just provide an additional constructor that converts an employee into a boss.
public Boss(AbstractEmployee emp):
base(emp.getName() , emp.getSalary()) {
Doubly Linked Lists
In the preceding implementation, we keep a reference to each subordinate in the Collection in each Boss class. This means that you can move down the chain from the president to any employee, but there is no way to move back up to find out who an employee’s supervisor is. This is easily remedied by providing a constructor for each AbstractEmployee subclass that includes a reference to the parent node.
public class Employee :AbstractEmployee {
protected float salary;
protected string name;
protected AbstractEmployee parent;
protected ArrayList subordinates;
//------
public Employee(AbstractEmployee parnt,
string nm, float salry) {
subordinates = new ArrayList();
name = nm;
salary = salry;
parent = parnt;
}
Then you can quickly walk up the tree to produce a reporting chain.
private void btShowBoss_Click(object sender, System.EventArgs e) {
EmpNode node;
node = (EmpNode)EmpTree.SelectedNode;
AbstractEmployee emp = node.getEmployee ();
string bosses = "";
while(emp != null) {
bosses += emp.getName () +"
";
emp = emp.getBoss();
}
MessageBox.Show (null, bosses,"Reporting chain");
}
See Figure 16-4.
Figure 16-4. The tree list display of the composite with a display of the parent nodes on the right
Consequences of the Composite Pattern
The Composite pattern allows you to define a class hierarchy of simple objects and more complex composite objects so they appear to be the same to the client program. Because of this simplicity, the client can be that much simpler, since nodes and leaves are handled in the same way.
The Composite pattern also makes it easy for you to add new kinds of components to your collection as long as they support a similar programming interface. On the other hand, this has the disadvantage of making your system overly general. You might find it harder to restrict certain classes where this would normally be desirable.
A Simple Composite
The intent of the Composite pattern is to allow you to construct a tree of various related classes, even though some have different properties than others and some are leaves that do not have children. However, for very simple cases, you can sometimes use just a single class that exhibits both parent and leaf behavior. In the SimpleComposite example, we create an Employee class that always contains the ArrayList subordinates. This collection of employees will either be empty or populated, and this determines the nature of the values that you return from the getChild and remove methods. In this simple case, we do not raise errors and always allow leaf nodes to be promoted to have child nodes. In other words, we always allow execution of the add method.
While you may not regard this automatic promotion as a disadvantage, in systems where there are a very large number of leaves, it is wasteful to keep a Collection initialized and unused in each leaf node. In cases where there are relatively few leaf nodes, this is not a serious problem.
Composites in .NET
In .NET, you will note that the Node object class we use to populate the TreeView is in fact just such a simple Composite pattern. You will also find that the Composite describes the hierarchy of Form, Frame, and Controls in any user interface program. Similarly, toolbars are containers, and each may contain any number of other containers.
Any container may then contain components such as buttons, check boxes, and TextBoxes, each of which is a leaf node that cannot have further children. They may also contain ListBoxes and grids that may be treated as leaf nodes or that may contain further graphical components. You can walk down the Composite tree using the Controls collection.
Other Implementation Issues
Ordering components. In some programs, the order of the components may be important. If that order is somehow different from the order in which they were added to the parent, then the parent must do additional work to return them in the correct order. For example, you might sort the original collection alphabetically and return a new sorted collection.
Caching results. If you frequently ask for data that must be computed from a series of child components, as we did here with salaries, it may be advantageous to cache these computed results in the parent. However, unless the computation is relatively intensive and you are quite certain that the underlying data have not changed, this may not be worth the effort.
Thought Questions
1. A baseball team can be considered an aggregate of its individual players. How could you use a Composite to represent individual and team performance?
2. The produce department of a supermarket needs to track its sales performance by food item. Suggest how a Composite might be helpful.
