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 Function getName() As String public Function getValue() As String
and a node could have the additional methods:
public Function elements() As Collection public Function getChild(nodeName As String) As Node public Sub add(obj As Object) public Sub remove(obj As Object);
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.
VB can make this quite easy for us, since every node or leaf can return a Collection of the child nodes. If there are no children, the count property returns zero. Thus, if we simply obtain the Collection 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.
Let's consider a small company. It may have started with a single person who got the business going. 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 continued, the firm continued to grow until it has the organizational chart in Figure 17-1.
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.
public Function getSalaries() As Single
At this point, we realize that the idea of all Composites having the same standard method names in their interface is probably naïve. 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.
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.
'Class AbstractEmployee 'Interface for all Employee classes '--------- Public Function getSalary() As Single End Function '--------- Public Function getName() As String End Function '--------- Public Function isLeaf() As Boolean End Function '--------- Public Sub add(nm As String, salary As Single) End Sub '--------- Public Sub addEmp(emp As AbstractEmployee) End Sub '--------- Public Function getSubordinates() As Subords End Function '--------- Public Sub remove(emp As AbstractEmployee) End Sub '---------- Public Function getChild(nm As String) As AbstractEmployee End Function '--------- Public Function getSalaries() As Single End Function '--------- Public Sub init(name As String, salary As Single) End Sub
Our concrete Employee class will store the name and salary of each employee and allow us to fetch them as needed.
'Class Employee 'implementation of AbstractEmployee interface Implements AbstractEmployee Private nm As String Private salary As String Private subordinates As Subords '-------- Private Function AbstractEmployee_getChild(nm As String) _ As AbstractEmployee Set AbstractEmployee_getChild = Null End Function '-------- Private Function AbstractEmployee_getName() As String AbstractEmployee_getName = nm End Function '-------- Private Function AbstractEmployee_getSalaries() As Single AbstractEmployee_getSalaries = salary End Function '-------- Private Function AbstractEmployee_getSalary() As Single AbstractEmployee_getSalary = salary End Function '-------- Private Sub AbstractEmployee_init(name As String, _ money As Single) nm = name salary = money Set subordinates = New Subords End Sub '-------- Private Function AbstractEmployee_isLeaf() As Boolean AbstractEmployee_isLeaf = True End Function '-------- Private Sub AbstractEmployee_remove(emp As AbstractEmployee) Err.Raise vbObjectError + 513, , & _ "No subordinates in base employee class" End Sub '-------- Private Sub Class_Initialize() nm = "" salary = 0 End Sub
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. For example, subordinates could return null, but programming will be more consistent if it returns an empty enumeration.
Private Function AbstractEmployee_getSubordinates() _ As Subords Set AbstractEmployee_getSubordinates = subordinates End Function
The add and remove methods must generate errors, since members of the basic Employee class cannot have subordinates.
Private Sub AbstractEmployee_add(nm As String, _ salary As Single) Err.Raise vbObjectError + 513, , & _ "No subordinates in base employee class" End Sub '-------- Private Sub AbstractEmployee_addEmp(emp As _ AbstractEmployee) Err.Raise vbObjectError + 513, , & _ "No subordinates in base employee class" End Sub
VB does not provide an enumeration class that contains its own internal pointer to move through a list. So we create a simple class that contains a collection and an index to move through that collection. The advantage of using this class, here called Subords, is that you can search down through the composite tree without having to maintain indexes outside of each instance of the Collection that you search through.
'Class Subords 'A simple enumeration of a collection Private subNames As Collection 'the collection Private index As Integer 'the internal index '----- Public Sub moveFirst() index = 1 End Sub '----- Public Function hasMoreElements() hasMoreElements = index <= subNames.count End Function '----- Public Function nextElement() As Object Set nextElement = subNames(index) index = index + 1 End Function '----- Private Sub Class_Initialize() Set subNames = New Collection index = 1 End Sub '----- Public Sub add(obj As Object) subNames.add obj End Sub '----- Public Function element(i As Integer) As Object Set element = subNames(i) End Function '----- Public Function count() As Integer count = subNames.count End Function
Using the Subords class, we can simply call the hasMoreElements method and the nextElement method to move through a collection without having to use and maintain an index ourselves.
Our Boss class is a subclass of Employee and allows us to store subordinate employees as well. We'll store them in a Collection 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. We'll make this Boss class contain an instance of Employee, which will then return the name and salary information. The Boss class itself will handle the subordinate list.
'Class Boss 'A Boss implementation of AbstractEmployee 'which allows subordinates Implements AbstractEmployee Private emp As AbstractEmployee 'keeps employee data Private subordinates As Subords 'list of subordinates '-------- Private Sub AbstractEmployee_add(nm As String, _ salary As Single) Dim newEmp As AbstractEmployee Set newEmp = New Employee newEmp.init nm, salary subordinates.add newEmp End Sub '-------- Private Sub AbstractEmployee_addEmp(emp As _ AbstractEmployee) subordinates.add emp End Sub '--------- Private Function AbstractEmployee_getName() As String AbstractEmployee_getName = emp.getName End Function '-------- Private Function AbstractEmployee_getSalary() As Single AbstractEmployee_getSalary = emp.getSalary End Function '-------- Private Function AbstractEmployee_getSubordinates() _ As Subords Set AbstractEmployee_getSubordinates = subordinates End Function '-------- Private Sub AbstractEmployee_init(name As String, _ salary As Single) Set emp = New Employee emp.init name, salary Set subordinates = New Subords End Sub '-------- Private Function AbstractEmployee_isLeaf() As Boolean AbstractEmployee_isLeaf = False End Function
If you want to get a list of employees of a given supervisor, you can obtain an Enumeration of them directly from the Subords collection. Similarly, you can use this same Collection to returns a sum of salaries for any employee and his subordinates.
Private Function AbstractEmployee_getSalaries() As Single Dim sum As Single, esub As AbstractEmployee 'get the salaries of the boss and subordinates sum = emp.getSalary subordinates.moveFirst While subordinates.hasMoreElements Set esub = subordinates.nextElement sum = sum + esub.getSalaries Wend AbstractEmployee_getSalaries = sum End Function
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 17-2.
We start by creating a CEO Employee and then add his or her subordinates and their subordinates, as follows.
Private Sub buildEmployeeList() Dim i As Integer Dim marketVP As AbstractEmployee Dim salesMgr As AbstractEmployee Dim advMgr As AbstractEmployee, emp As AbstractEmployee Dim prodVP As AbstractEmployee, prodMgr As AbstractEmployee Dim shipMgr As AbstractEmployee Set prez = New Boss prez.init "CEO", 200000 Set marketVP = New Boss marketVP.init "Marketing VP", 100000 prez.addEmp marketVP Set salesMgr = New Boss salesMgr.init "Sales Mgr", 50000 Set advMgr = New Boss advMgr.init "Advt Mgr", 50000 marketVP.addEmp salesMgr marketVP.addEmp advMgr Set prodVP = New Boss prodVP.init "Production VP", 100000 prez.addEmp prodVP advMgr.add "Secy", 20000 'add salesmen reporting to sales manager For i = 1 To 5 salesMgr.add "Sales" & Str$(i), rand_sal(30000) Next i Set prodMgr = New Boss prodMgr.init "Prod Mgr", 40000 Set shipMgr = New Boss shipMgr.init "Ship Mgr", 35000 prodVP.addEmp prodMgr prodVP.addEmp shipMgr For i = 1 To 3 shipMgr.add "Ship" & Str$(i), rand_sal(25000) Next i For i = 1 To 4 prodMgr.add "Manuf" & Str$(i), rand_sal(20000) Next i End Sub
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 Sub addNodes(nod As Node, ByVal emp As AbstractEmployee) Dim col As Subords, i As Integer, newNode As Node Dim newEmp As AbstractEmployee, cnt As Integer Dim index As Integer Set col = emp.getSubordinates index = nod.index 'get node's index col.moveFirst While col.hasMoreElements Set newEmp = col.nextElement Set newNode = empTree.Nodes.add(index, tvwChild) newNode.Text = newEmp.getName newNode.Expanded = True addNodes newNode, newEmp Wend End Sub
The final program display is shown in Figure 17-3.
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 Sub empTree_Click() Dim newEmp As AbstractEmployee 'finds the salary of the selected employee and 'all the subordinates Set newEmp = prez.getChild(empTree.SelectedItem) lblSalary.Caption = Str$(newEmp.getSalaries) End Sub
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.
Private Sub AbstractEmployee_makeBoss(newBoss As _ AbstractEmployee) Set emp = newBoss End Sub
In this implementation, we have all the classes (Employee and Boss) implement the AbstractEmployee interface. However, so we can treat each object as one having the methods of an AbstractEmployee, we have to include the makeBoss methods in the AbstractEmployee interface. Then we have to add this method to the Employee class as well, raising an error if it is called inadvertently.
Private Sub AbstractEmployee_makeBoss( _ emp As AbstractEmployee) Err.Raise vbObjectError + 514, , "Employee is not a boss" End Sub
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.
Private Sub AbstractEmployee_init(parnt As AbstractEmployee, _ name As String, money As Single) Set parent = parnt hasParent = True nm = name salary = money Set subordinates = New Subords End Sub
Then you can quickly walk up the tree to produce a reporting chain.
Public Sub setBoss(empl As AbstractEmployee) Dim nm As String Set emp = empl Do nm = emp.getName empList.AddItem nm Set emp = emp.getBoss Loop Until emp.getName = nm End Sub
See Figure 17-4.
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.
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 Collection employees. 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.
In VB, 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, Checkboxes, 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.
In VB7 we do not need to use the Subords class because we have a built-in enumeration interface called IEnumerator. This interface consists of these methods.
Function MoveNext() as Boolean 'False if no more left Function Current() as Object 'get current object Sub 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 = Ctype(e.Current, Employee) '...do computation.. End While
This Enumerator may, of course, be empty and can thus be used for both nodes and leaves of the composite. Here is our AbstractEmployee interface.
Public Interface AbstractEmployee Inherits IEnumerable 'Interface for all Employee classes Function getSalary() As Single Function getName() As String Function isLeaf() As Boolean Overloads Sub add(ByVal nm As String, _ ByVal salary As Single) Overloads Sub add(ByVal emp As AbstractEmployee) Function getSubordinates() As IEnumerator Sub remove(ByVal emp As AbstractEmployee) Function getChild(ByVal nm As String) _ As AbstractEmployee Function getSalaries() As Single End Interface
Since VB7 allows polymorphism, we have two polymorphic versions of the add method. Note that VB7 syntax requires that we specifically declare them using the Overloads keyword.
The other major change we make for VB7 is that we can throw an exception if a program tries to add or remove an Employee from an Employee class when that employee is not a Boss and has no subordinates.
Public Overridable Overloads Sub add( _ ByVal nm As String,_ ByVal salary As Single) _ Implements AbstractEmployee.add Throw New Exception("No subordinates") End Sub '------ Public Overridable Overloads Sub add( _ ByVal emp As AbstractEmployee) _ Implements AbstractEmployee.add Throw New Exception("No subordinates") End Sub
In our VB6 version of the composite, we had to completely implement every method of the AbstractEmployee interface in both the Employee and the Boss class. In VB7 we can derive the Boss from the Employee class and only implement the methods that differ. VB7's syntax does require that we specifically declare the fact that we are overriding these methods, as shown below.
Public Overloads Overrides Sub add( _ ByVal nm As String, ByVal salary As Single) Dim newEmp As AbstractEmployee newEmp = New Employee(nm, salary) subordinates.add(newEmp) End Sub '-------- Public Overloads Overrides Sub add( _ ByVal emp As AbstractEmployee) subordinates.add(emp) End Sub
The Enumerator we use in our Boss and Employee classes to enumerate employees is a member of the ArrayList class. Classes that can return an IEnumerator are said to implement the IEnumerable interface. However, the advantage here is that we can create an empty ArrayList in the Employee class and never allow additions to the array. However, we need not handle requests for an enumeration of subordinates separately because the enumeration will always be empty.
For this reason, we do not have to create separate versions of the getSalaries method for Employees and Bosses because if the enumeration of subordinates is empty, the method will simply return the salary of the current employee.
Public Function getSalaries() As Single _ Implements AbstractEmployee.getSalaries Dim sum As Single Dim esub As AbstractEmployee Dim enumSub As IEnumerator 'get the salaries of the boss and subordinates sum = getSalary enumSub = subordinates.getEnumerator While enumSub.moveNext esub = CType(enumSub.current, AbstractEmployee) sum = sum + esub.getSalaries End While Return sum End Function
In our VB6 version of the composite, we had a specific makeBoss method to create a Boss from an employee. We can do that in VB7 with a second, overloaded version of the constructor.
Public Sub New(ByVal name As String, _ ByVal salary As Single) MyBase.New(name, salary) subordinates = New ArrayList() End Sub '----- Public Sub New(ByVal emp As Employee) MyBase.New(emp.getName, emp.getSalary) End Sub
When you click on an element of the tree view, you can catch the afterSelect event.
Protected Sub EmpTree_AfterSelect( _ ByVal sender As Object, _ ByVal e As System.WinForms.TreeViewEventArgs) Dim node As EmpNode node = CType(EmpTree.SelectedNode, EmpNode) getNodeSum(node) End Sub
Then you can compute the salary recursively.
Private Function getNodeSum(ByVal node As EmpNode)_ As Single Dim emp As AbstractEmployee Dim sum As Single emp = node.getEmployee sum = emp.getSalaries lbSalary.Text = sum.Format("n", Nothing) End Function
Note that the label text is generated using the Single variable object's Format method.
The final Composite program for VB7 is shown in Figure 17-5.
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.
A baseball team can be considered an aggregate of its individual players. How could you use a composite to represent individual and team performance?
The produce department of a supermarket needs to track its sales performance by food item. Suggest how a composite might be helpful.