Understanding the Composite Pattern
 
Published: 23 Jan 2007
Abstract
If you want to see an exciting and dynamic use of Treeview controls, read this article where we see the composite at work. If you remember your first year of computer science, you will remember terms like breadth first, spanning trees, binary trees, depth-first search and so on. The composite pattern gives us an exremely approachable way to manage trees on the processing side. This tutorial shows you how to hook up your treeviews to the tree structure which Composite presents.
by David Simmonds
Feedback
Average Rating: 
Views (Total / Last 10 Days): 35545/ 45

Introduction

What happens with Composite Pattern?

In the Composite pattern, every participant is referred to as a component. By providing a common interface which components adhere to, we ensure that we can interact with all participants in a uniform way.

The need for uniform interaction is due to the fact that we also have composite-participants and leaf-participants. A leaf is the smallest indivisible component in the pattern. You could think of leaves as being "atomic."

A Composite is simply a component which knows how to aggregate other components by adding and removing other components to and from itself. It knows how to account for them and also knows how to forward messages to each of its components. Any message to a composite will end up with delegation to its aggregated components.

We do not care how each component gets its job done. We simply pass messages to a component at any level of the hierarchy we choose. Most times the message is passed to a component at the top which can be a leaf or composite. If it is a composite, then it automatically forwards the instructions to be carried out to each of its member components. Each component will in turn figure out whether it is a composite or a leaf. If it is a leaf, then it carries out basic operations on itself and returns the result if necessary or simply updates itself. If it is a composite, then it forwards messages to each of its member components in turn. All this transparency is achieved because we treat each component equally. In effect, we are saying to each component, “Take responsibility for yourself. You must figure out whether you are an individual (Leaf) or a group (Composite).” Leaves operate on themselves and represent themselves. Composites pass on the instructions coming from the top to their components (which again might be leaves or composites). In this way, we have a self traversing structure which internally takes responsibility for ensuring that every member is properly instructed or updated.  At the top, we do not care who we are talking to. We know our instructions will be carried out properly regardless.

In the electoral example, each component gets an instruction to return the vote-count for candidates in the constituency. The ballot paper is a leaf and represents the smallest indivisible unit of information in the voting process. In pattern-talk, each vote will get an instruction to return a vote-count. It returns 1 for the person who got that vote and 0 for other candidates. An instruction to the constituency to count itself is forwarded to its aggregated polling stations. The polling station also knows that it is a composite, not a leaf. It therefore forwards vote-count requests to its aggregates, the ballot-papers.

Notice one thing though. In the electoral example, we have a leafy-composite situation. The component (constituency) which aggregates polling stations is itself a leaf. This is necessary since the determination of which party has won and so will provide the cabinet and Prime minister is decided not by a popular vote count, but by a seat count (in the US an Electoral College count). The PM can get 48% of the popular vote-count, but because her party wins the most seats (at the constituency level) she wins the elections and her party goes into power.

The example has been simplified somewhat. Ballots are counted in boxes and sometimes they are spoiled and count for nothing. In large constituencies, there are polling stations within polling divisions. In some countries there are more than two parties and coalitions are formed between several parties. Also, on a ballot where you are able to vote for several positions and propositions at the same time, the ballot itself becomes a composite and the vote on each issue becomes the leaf. But let us keep the example simple for now.

Intent seen through O/S & Applications

Windows XP scans the user's menus to see which menu branch has a recently installed program that shows the operation of the pattern. The individual programs which can be run are leaves while the branches of the sub-menus represent composites.

Scenario - Sample Code

The sample code shows the integration of the composite pattern with a windows form control which is a natural fit for showing composite leaf/branch structures: The treeview control. Of course, the aspects related to the treeview fall into the category of extra-pattern issues, but at least you get to see real-life integration with language features.

So what does it do? It allows you to model in a tree structure all the available rooms which can be booked in a resort area. Since Jamaica has four major resort areas, it allows you to add the four of them. These resort areas behave like composite items. It also allows you to add other composites, such as Hotels and hotel floors. Leaf structures are represented in the sample code by Villas and Rooms. These are the actual entities in which you would spend the night. You cannot really spend the night in a hotel, can you? You would spend the night in a hotel room.

In the sample, Resorts, Hotels and Floors inherit from the composite abstract class called CompositeAccomodation. Rooms and Villas inherit from the Leaf abstract class called Quarters.

The Gof pointed out that there is a hard decision to make in terms of allowing the Leaf abstract class to fully inherit the Component abstract class. This is the fact that we should not be able to add components to a leaf. The design decision made here is to inherit all the methods of the component class, so that leaves do in fact have a remove-component and add-component method. In the leaf class we simply throw an exception when these methods are called. If the client needs to know that it has made a mistake in attempting to add to a leaf, it can catch these exceptions and further process them. Otherwise, the attempt to add to the leaf is simply ignored.

The Meat of the Matter

UML – General

Figure 1

UML  – Sample Code

Figure 2

Participants – Sample Code

 

Component - Accomodation

Inherit class defines the behaviors which must be inherited and overridden in both the composite and leaf participants. It usually includes behaviors such as add-component and remove-component which add and remove children component from the said component class. This is an interacting interface since clients will interact with both composites and leaves posing as components.

Composite – CompositeAccomodation (ResortArea, Hotel, Floor)

This is able to add children to it. It aggregates a datastruture which can keep a reference to multiple child-components. It accepts instructions from the client to perform operations, but really passes these on to all of its children one by one (which may pass on these instructions to their children in cases where they themselves have children). It depends on its children to do the empirical work.

When thinking about the children of a composite, it is very important that you not mix up the concept of a child with the concept of a leaf. A child can be a composite which itself has children.

Leaf – Quarters (HotelRoomSingle, HotelRoomDouble, Villa)

This is not able to add children to itself. In this code sample, if child-related operations are attempted, an exception is thrown. It performs the operations which its parent-component (a composite) has passed on to it. It may pass results back up to its parent (including passing itself back as a result) or perform the operation on itself.

Client – Client_Rooms

Client will interact with composites and the leaves they are “composed” of uniformly, through their component interface. Clients know what they are adding to or removing from because the client has chosen this direct interaction. But with regard to the really important aspect of the pattern, which is the traversal of the tree structure to any depth required to find all components, the client really does not know the type of class it is dealing with at any point and does not really care.

Component

The component simply governs behavior. It is a MustInherit (abstract) class which defines the behaviors that the composites and components must implement and so defines the behaviors which the client will expect to be available.

Listing 1

Public MustInherit Class Accomodation    'equivalent of Component in the pattern
  Public PossibleNoOccupants As Integer
  Public Booked As Boolean
  Public AccomodationKey As String
  Public AccomodationType As HotelIndustryType
  Protected Sub New(ByVal AccName As String,  … )
  ' Constructor
     AccomodationKey = AccName
  End Sub
  ' Allows you to add rooms (a child component) to the
  '   current component. 
    Public MustOverride Function AddAccomodation
                      (AccomodationToAdd As Accomodation)
    ' Allows you to remove rooms (a child component) 
    '     from the current component. 
    Public MustOverride Function RemoveAccomodation
           (ByVal RemoveableAccomodation As Accomodation)
  Public Overridable Function CalculateOccupancy
                          (ByVal Occupancy As IntegerAs Long 
    Dim ActualOccupancy As Integer
    Dim PossibleOccupancy As Integer
 
  ' This method call is EXTREMELY DECEPTIVE in its simplicity.
  '  Because of the transparency
  '  of composites and leaves and the fact that composites
  '  delegate operations to their child-components so 
  '  transparently. It shows the flexibility, power and 
  '  transparency of the pattern VERY NICELY.
  Dim OccupancyFigures As OccupancyObject =  
             DetermineOccupancyFigures(New OccupancyObject)
 
  ActualOccupancy = OccupancyFigures.OccupiedBeds
 PossibleOccupancy = OccupancyFigures.UnOccupiedBeds +
                           OccupancyFigures.OccupiedBeds
  ' See the composite and leaf classes for the actual 
  '   (and very elegant) implementation of this function
  Public MustOverride Function DetermineOccupancyFigures
        (OccupancyFigures As OccupancyObject) As OccupancyObject
  ' Searches all the children of this component for the first
  '   unbooked room with the required number of occupants 
  '   passed to it 
  Public MustOverride Function FindAvailableAccomodation
          (Occupancy As IntegerAs Accomodation
End Class

Composite

All of the composite’s behavior is inherited from the component class. But among all these functions, there are two types of functions which the composite class implements. The first set of functions is child management function. These functions perform operations on the datastructure (Hashtable) by adding and removing children from it.

The other class of functions implemented in the composite class is the operational functions which are domain specific. In this case, those functions are specific to the hotel industry. The composite is a real buck passer and simply passes the instruction to the children components which it holds in its hash table. So, in these functions you will see a lot of "For Each" statements in these functions as it loops through each child and allows each child to perform the required operation.

Listing 2

' Equivalent of composite in the pattern
Public MustInherit Class CompositeAccomodation                  
       Inherits Accomodation
   Public Sub New(ByVal ComponentName As String, ByVal 
                           ParentNode As TreeNode)
   ' Constructor
     MyBase.New(ComponentName, ParentNode)
   End Sub
   ' Holds a reference to all the child components
   Public AccomodationCollection As New Hashtable
Public Overrides Function AddAccomodation
                        (AccomodationToAdd As Accomodation)            
   ' Adds a child component to itself
    AccomodationCollection.Add
                (AccomodationToAdd.AccomodationKey, 
                 AccomodationToAdd)
   End Function
   Public Overloads Overrides Function BookAccomodation
             (ByVal BookAble As Accomodation) As Integer
   ' Be careful with this function. this function does not scan
   '    the child-accomodations to FIND a suitable accomodation. 
   '    It scans all child accomodations and books ALL of them.
      Dim VisitorsBookedFor As Integer
      For Each SuitableAccomodation As Accomodation In 
                         Me.AccomodationCollection
        VisitorsBookedFor += SuitableAccomodatn.BookAccomodation
      Next
    End Function
  Public Overrides Function DetermineOccupancyFigures
         (ByVal OccObject As OccupancyObject) As OccupancyObject
    For Each OccupiableAccomodation As Accomodation In 
                             Me.AccomodationCollection
      OccupiableAccomodation.DetermineOccupncyFigures(OccObject)
    Next
    Return OccObject
  End Function
' This is one of the actual classes which will be instantiated
'  and used as the client. with all the behaviours of a 
'  composite class.
Public Class HotelFloor
       Inherits CompositeAccomodation
  Public Sub New(FloorNumber As Integer, ParentNode As TreeNode)
    ' Initializes all the extra-pattern state
    '   (they have no bearing on the pattern operation)
    MyBase.New(FloorNumber.ToString, ParentNode)
    Me.AccomodationType = HotelIndustryType.Floor
    Me.DisplayNode.ImageIndex = HotelIndustryType.Floor
  End Sub
End Class

Leaf

Child management functions, which are implemented in the composite class, are simply empty functions which throw exceptions in their leaf counterparts. Aside from those functions, the leaf simply implements the domain-specific operations which its composite parent keeps passing to it.

Listing 3

' Equivalent of leaf in the pattern
Public MustInherit Class Quarters                    
       Inherits Accomodation
  Public Sub New (    …   )
    MyBase.New(ComponentName, ParentNode)
    Me.PossibleNoOccupants = NoOccupants
  End Sub
  Public Overrides Function AddAccomodation 
               (AccomodationToAdd As Accomodation) As Object
    Throw New BadChildOpException
                (BadChildOpException.Operation.AddChildToChild)
  End Function
Public Overloads Overrides Function BookAccomodation
               (ByVal RequiredOccupancy As Integer) As Boolean
    If Me.Booked = False And Me.PossibleNoOccupants 
                          <= RequiredOccupancy Then
       Me.Booked = True
       Return True
    Else
       Return False
      End If
        End Function
  Public Overrides Function FindAvailableAccomodation
            (RequiredOccupancy As IntegerAs Accomodation
    If Not Me.Booked And 
              Me.PossibleNoOccupants >= RequiredOccupancy Then
       Return Me
    End If
  End Function
  Public Overrides Function DetermineOccupancyFigures
       (OccupancyFigures As OccupancyObject) As OccupancyObject
    If Me.Booked Then
      OccupancyFigures.OccupiedBeds += Me.PossibleNoOccupants
    Else
      OccupancyFigures.UnOccupiedBeds += Me.PossibleNoOccupants
    End If
  End Function
End Class
' This is one of the actual classes which will be instantiated 
'   and used with all the behaviours of a leaf class.
Public Class HotelRoomSingle
       Inherits Quarters
  Public Sub New(RoomNumber As Integer, ParentNode As TreeNode)
    MyBase.New(RoomNumber.ToString, ParentNode, 1)
    Me.AccomodationType = HotelIndustryType.Villa
    Me.DisplayNode.ImageIndex = HotelIndustryType.Villa
  End Sub
End Class

Client

The client in this case is the form. Clicking on relevant menu objects of the context menu will add components and remove them. Clicking also fires some of the hotel-based functions.

Listing 4

Private Sub Form1_Load( … ) Handles MyBase.Load
  Dim Jamaica As New Composite.ResortArea
                ("Jamaica", tvwHotelRooms)
  Dim JamaicanResorts As TreeNode = Jamaica.DisplayNode
 
  Dim OchoRios As New Composite.ResortArea
                 ("OchoRios", JamaicanResorts)
  Dim MontegoBay As New Composite.ResortArea
                 ("MontegoBay", JamaicanResorts)
  OchoRios.DisplayNode.Tag = OchoRios
  MontegoBay.DisplayNode.Tag = MontegoBay
End Sub
Private Function GetCurrentAccomodation() As Accomodation
' General purpose function which takes the currently selected 
'   node of the Treeview and returns the Accomodation object
'   which is tied to it.
' Think of this as a sort of helper function which is  
'   partially extra-pattern. 
  Dim ResultingAccomodation As Accomodation = 
        CType(tvwHotelRooms.SelectedNode.Tag, Accomodation)
  Return ResultingAccomodation
End Function
Private Sub mnuBook_Click Handles mnuBook.Click
        WIPAccomodation = GetCurrentAccomodation()
        WIPAccomodation.BookAccomodation()
End Sub
Private Sub mnuAddHotel_Click Handles mnuAddHotel.Click
  WIPAccomodation = GetCurrentAccomodation()
  WIPAccomodation.AddAccomodation(New Composite.Hotel 
                                       (“NameofHotel"))
End Sub
Private Sub mnuAdd1Room_Click Handles mnuAdd1Room.Click
  WIPAccomodation = GetCurrentAccomodation()
  WIPAccomodation.AddAccomodation(New Leaf.HotelRoomSingle(…)
End Sub
Opportunities for and Costs of - Adaptation and Extension

You can add components and clients extremely easily so that extension is truly a breeze. You simply add the new class and inherit appropriately from Composite or Leaf classes. Add the extra-pattern behavior (such as an icon which visually represents the component) and initialize this extra behavior in an appropriate constructor. Document this extra class so that client-coders know that they should make use of it and you are off and running.

Interface issues

The component is an interacting interface and can be implemented as either an interface or a Must-Inherit (abstract class). Practically though, the component is likely to have a fair amount of state which would benefit from the sharing of a constructor. So it is best implemented as a must-inherit class. In fact, in this example, we see where part of the constructor is the addition of a TreeNode class to the nodes collection of an existing treenode. If it were implemented as an interface, then the code for TreeNode manipulation would be spread over many classes and be quite messy and hard to maintain.

Namespace/Scope/Accessor issues

There are no great issues here to be dealt with, except that for ease of understanding by people who maintain your code, participant-classes should be factored into their own assemblies based on component, composite and leaf classes. This makes for ease of maintainability.

Common mistakes in Pattern Literature/Pitfalls to avoid

The pattern is extremely operational, meaning that if you do not implement it properly, you will know the first time you test the code. Besides, there is not that much to get wrong.

So, it is very unlikely that you will end up doing something which prevents you from achieving the extensibility desired.

Advanced Issues

Useful variations

1a        Chameleon-Composite

Composites allow components to switch between composites and leaves.

1b        Classic-Composite

Components end their life the way they started. Leaves continue to be leaves throughout, while composites continue to be composites throughout.

2a        Leafy-Composite

Every component is a leaf and will perform the primitive, low-level operations on it in addition to forwarding messages to its children to perform similar operations

2b        Leaf-on-Branch Composite

Composites do not have primitive functions and simply forward processing instructions to their child components (typical case).

3a        Electoral-College-Composite

Some composites behave as leaves at the level above it and composites to the level below it as in the election vote-counting system. This may seem obvious and readers may think it is the typical case, but what we are saying is that in this scheme, the highest levels of composites are affected empirically by the lowest level leaves. Another good example of this is in the electoral-college system of voting, where you can lose the popular vote but still become president.

3b        Popular-Vote-Composite

Every single leaf and mid-level composite filters up to the highest level and is counted there.

4a        Birth-Cert composite

Leaves know who their parents are and can reference their parent in performing their operations. One could argue that you could achieve the same results by passing a “my-parent” token to the children as you traverse them, but how do you access the grand-parent when you need to?

4b        Foster-Child Composite

Advanced Discussion

I suggest that you apply the following order and principles when working on composite projects.

·         Allow the client to control invocation of the addition and removal logic.

·         Get the additions and then the removals right.

Then deal with the each Implementation-specific functionality, one at a time.

So, if we are dealing with find-accomodation, deal with find-accomodation across component, composite and leaf. Then move on to deal with bookings across component, composite and leaf. Finally, move on to unbooking across component, composite and leaf

Deal with subsidiary functions first. So for example, deal with the find-accomodation first. This is used before you can do the booking, so in the same way that we would be guided by general software development principles to deal with it first (composing bigger functionality from primitive functions), similarly, would we do it here.

Test the solution thoroughly. Remember you are not done coding until you have tested and this holds true for every software project.

Now you will notice that Composite can be a real pain to test, since you have to repeatedly create composites and leaves before you can test operations on them. And depending on the number of functionalities you have to test, this can be horrendous.

My suggestion is to create the object-hierarchy of test-data and include a routine which uses some persistence mechanism to persist-to-disk and restore the hierarchy (possibly with an option to restore from several backups). You can then make changes to it, tweak it, add test cases and remove extraneous stuff. In-between tests, you persist the object-hierarchy. This not only saves you time and frustration (plus allowing other developers to code and test the solution simultaneously), but it also helps you to ensure consistency in the tests.

Composite/Treeview/XML: a natural fit

Composite is one of the most elegant and intuitive patterns. Later on when we look at the Interpreter pattern, you will see where it can save you from knowing a lot of XPATH. I load the XML file straight into a composite object-hierarchy which is linked to a treeview, do all the processing in the Composite hierarchy (including searching) and then store the results back into XML.

Downloads

[Download Sample]

Note: Open the project using either Microsoft Visual Studio 2003 .NET or Microsoft Visual Studio 2005 (After conversion), right click a node and select a function from the pop-up menu to work with the application.

Conclusion

In this article you have seen the theory behind composite pattern with a help of a Visual Basic project.



User Comments

No comments posted yet.

Product Spotlight
Product Spotlight 





Community Advice: ASP | SQL | XML | Regular Expressions | Windows


©Copyright 1998-2024 ASPAlliance.com  |  Page Processed at 2024-03-28 9:01:09 AM  AspAlliance Recent Articles RSS Feed
About ASPAlliance | Newsgroups | Advertise | Authors | Email Lists | Feedback | Link To Us | Privacy | Search