The Composite pattern allows you to compose objects that have the same base type into tree-like structures in which parent nodes contain child nodes of the same type. In other words, that kind of tree-like structure forms part-whole hierarchies. What is a part-whole hierarchy? It's a hierarchical structure that contains both compositions of objects (containers) and individual objects as leaf nodes (primitives). Each composite has other nodes that could be either leaf nodes or other composites. That kind of relationship repeats itself within the hierarchy recursively. Since every composition or leaf node shares the same base type, the same operations can be applied over each of them without type-checking on the client side. A client can ignore the differences between a composition and a leaf node to operate them. An example of a composite object structure at runtime is illustrated in Figure 13-1.

Figure 13-1. A typical Composite object structure

A static structure of the Composite pattern is illustrated as a class diagram in Figure 13-2.

Figure 13-2. A class diagram illustrates the conceptural structure of the Composite pattern.

The base interface is the Component that defines operations that are shared by both the Leaf and the Composite classes.

There are some operations that are meaningful to only the Composite class, such as add:Component, remove:Component, and getChild:int. The Leaf class doesn't implement those methods for an obvious reason (in fact, it does but just an empty implementation). Why don't we put those methods in the Composite class only? We don't want clients to tell which kinds of nodes they are dealing with at runtime and to expose the internal details of the composite structure to clients as well. That's why even though operations make sense only to the Composite class; we also declare them in the base interface so every type of node share the same things. That way we can let clients treat any one of them uniformly.

Each node represents either a leaf node or a composite node. The main difference between the Leaf node and the Composite node is that a Leaf node doesn't contain any children of the same type but Composite does. Composite contains children of the same base type. Since both the Leaf and Composite classes share the same interfaces, any operation that is targeted for the Component type can be safely applied to each of them. Clients don't need to care about type-checking with a bunch of if- else, switch-case statements to determine the exact type of the object that is being worked on.

Let's back up to the top level of the hierarchy. The grandparent of all these nodes is treated as a reference to an instance of the Component class. If there are any changes to the internal structure, there is no client code that needs to be changed.

At the ultimate parent node, the whole aggregate structure can be referred to as their common base type, Component. Clients don't need to know any traversal strategy to use it, as a traversal or enumeration strategy is either provided by a composite structure or accessed through an external/internal iterator (see the Iterator pattern, Chapter 14).

You would naturally think about using the pattern when

In Chapter 2, we briefly discussed using an abstract tree structure to maintain user-created (drawn) strokes. In the next few sections, we are going to discuss how to implement the pattern in the TouchPainter app to achieve that.

Let's go back to our Mark composite structure that was defined in Chapter 2. We have a base Mark protocol that acts as a base type of both of our individual Dot, Vertex, and Stroke types. Instances of Dot are drawable on a view, while Stroke's child Vertex objects are used only for helping to connect lines together within the same stroke.

Clients that know how to construct a tree of Mark composite structures will add instances of Vertex to a Stroke instance and add the Stroke instance to the grandparent of the scribble. For adding drawable dots, the clients need to add individual instances of Dot to the grandparent. Their relationships are illustrated in Figure 13-3.

Figure 13-3. A class diagram of a Composite structure shows the class relationships of Dot and Vertex as leaf node classes as well as Stroke as a container class.

Vertex implements only the location property. Dot subclasses Vertex and adds color and size because Vertex doesn't need color and size but Dot does. A visualized runtime structure of a Mark tree is shown in Figure 13-4.

Figure 13-4. An object structure of a Composite contains Stroke, Dot, and Vertex objects.

aStroke can contain either Dot (aDot) or Vertex objects (aVertex) at runtime. So a Stroke object can be a parent of all kinds of Marks or a composition of a real stroke that is made out of Vertex objects and drawn on the screen as a whole group.

Let's cut some code for the Mark protocol as shown in Listing 13-1.

@protocol Mark <NSObject>

@property (nonatomic, retain) UIColor *color;
@property (nonatomic, assign) CGFloat size;
@property (nonatomic, assign) CGPoint location;
@property (nonatomic, readonly) NSUInteger count;
@property (nonatomic, readonly) id<Mark> lastChild;

- (void) addMark:(id <Mark>) mark;
- (void) removeMark:(id <Mark>) mark;
- (id <Mark>) childMarkAtIndex:(NSUInteger) index;

@end

Mark has three properties, color, size, and location. They should be common for any kinds of Marks that are drawable on the screen. In our original class diagrams, there are two methods declared in the Mark type, addMark:mark and removeMark:mark. They seem to make sense only to the Stroke class, as a Dot instance doesn't have any composition at all. The reason composite operations are declared in the top-level abstract interface is that we don't want clients to do any runtime check to know whether a Mark instance is a Stroke in order to add or remove children. Our goal is to make every node the same to clients to use. This uniformity becomes obviously important, for example, if you need to write a method that takes a parameter of Mark and adds/removes other Mark objects to/from it. The method shouldn't need to know whether the Mark of interest is a Stroke or Vertex (or Dot).

Now, here we go with our Vertex class, as shown Listing 13-2.

#import "Mark.h"

@interface Vertex : NSObject <Mark>
{
  @protected
  CGPoint location_;
}

@property (nonatomic, retain) UIColor *color;
@property (nonatomic, assign) CGFloat size;
@property (nonatomic, assign) CGPoint location;
@property (nonatomic, readonly) NSUInteger count;
@property (nonatomic, readonly) id<Mark> lastChild;

- (id) initWithLocation:(CGPoint) location;
- (void) addMark:(id <Mark>) mark;
- (void) removeMark:(id <Mark>) mark;
- (id <Mark>) childMarkAtIndex:(NSUInteger) index;

@end

It's a good practice to re-declare properties/methods that the subclass overrides. Even though Vertex seems to implement all properties declared in the Mark protocol, only the location property is real. The location_ member variable is declared as @protected as it will be used by at least one subclass later. The rest of the properties do nothing (dummies), as shown in Listing 13-3.

#import "Vertex.h"


@implementation Vertex
@synthesize location=location_;
@dynamic color, size;

- (id) initWithLocation:(CGPoint) aLocation
{
  if (self = [super init])
  {
    [self setLocation:aLocation];
  }

  return self;
}

// default properties do nothing
- (void) setColor:(UIColor *)color {}
- (UIColor *) color { return nil; }
- (void) setSize:(CGFloat)size {}
- (CGFloat) size { return 0.0; }

// Mark operations do nothing
- (void) addMark:(id <Mark>) mark {}

- (void) removeMark:(id <Mark>) mark {}
- (id <Mark>) childMarkAtIndex:(NSUInteger) index { return nil; }
- (id <Mark>) lastChild { return nil; }
- (NSUInteger) count { return 0; }


@end

Vertex@synthesizes only the location property and @dynamiccolor and size. @dynamic tells the compiler that we provide our own accessor methods for color and size. Although the compiler may not complain about it if we take the @dynamic directive off, it's still a good practice to keep that as it will make your life easier when you come back to the code later. The initWithLocation: method simply assigns the aLocation value to the Vertex's location property and returns itself. Other composite methods declared in Mark are dummies.

Dot subclasses Vertex and provides a few more implementations for the Mark protocol, as shown in Listing 13-4.

#import "Vertex.h"

@interface Dot : Vertex
{
  @private
  UIColor *color_;
  CGFloat size_;
}

@property (nonatomic, retain) UIColor *color;
@property (nonatomic, assign) CGFloat size;

@end

Dot needs to @synthesize only the size and color properties, as Vertex already covers a lot of stuff that is good enough for Dot as well. Dot's implementation is shown in Listing 13-5.

#import "Dot.h"


@implementation Dot
@synthesize size=size_, color=color_;

- (void) dealloc
{
  [color_ release];
  [super dealloc];
}

@end

We are done with Vertex and Dot. Let's move forward to Stroke, our composite class, as shown in Listing 13-6.

#import "Mark.h"

@interface Stroke : NSObject <Mark>
{
  @private
  UIColor *color_;
  CGFloat size_;
  NSMutableArray *children_;
}


@property (nonatomic, retain) UIColor *color;
@property (nonatomic, assign) CGFloat size;
@property (nonatomic, assign) CGPoint location;
@property (nonatomic, readonly) NSUInteger count;
@property (nonatomic, readonly) id<Mark> lastChild;

- (void) addMark:(id<Mark>) mark;
- (void) removeMark:(id<Mark>) mark;
- (id<Mark>) childMarkAtIndex:(NSUInteger) index;

@end

As Stroke is a composite class, unlike Vertex and Dot, it does need to implement all the methods and properties declared in the Mark protocol, as shown in Listing 13-7.

#import "Stroke.h"

@implementation Stroke

@synthesize color=color_, size=size_;
@dynamic location;

- (id) init
{
  if (self = [super init])
  {
    children_ = [[NSMutableArray alloc] initWithCapacity:5];
  }

  return self;
}

- (void) setLocation:(CGPoint)aPoint
{
  // it doesn't set any arbitrary location
}

- (CGPoint) location
{
  // return the location of the first child
  if ([children_ count] > 0)
  {
    return [[children_ objectAtIndex:0] location];

}

  // otherwise returns the origin
  return CGPointZero;
}

- (void) addMark:(id <Mark>) mark
{
  [children_ addObject:mark];
}

- (void) removeMark:(id <Mark>) mark
{
  // if mark is at this level then
  // remove it and return
  // otherwise, let every child
  // search for it
  if ([children_ containsObject:mark])
  {
    [children_ removeObject:mark];
  }
  else
  {
    [children_ makeObjectsPerformSelector:@selector(removeMark:)
                               withObject:mark];
  }
}

// needs to be added to draft
- (id <Mark>) childMarkAtIndex:(NSUInteger) index
{
  if (index >= [children_ count]) return nil;

  return [children_ objectAtIndex:index];
}


// a convenience method to return the last child
- (id <Mark>) lastChild
{
  return [children_ lastObject];
}

// returns number of children
- (NSUInteger) count
{
  return [children_ count];
}


- (void) dealloc
{
  [color_ release];
  [children_ release];
  [super dealloc];
}

@end

Stroke has its own children_ as an instance of NSMutableArray to keep track of its child Mark nodes. In its init method, it initializes an instance of NSMutableArray with the arbitrary capacity of five (it doesn't hurt to make it a little bigger, though).

The location property is not @synthesized because a Stroke object doesn't provide a location value directly but from its first child. If the Stroke object doesn't have any children, the location accessor method will return CGPointZero that refers to the origin of the screen.

The addMark: (id <Mark>) mark method forwards the mark parameter to children_ with the message call addObject:mark. removeMark: (id <Mark>) mark is a little tricky. It first searches for the mark parameter at the children_ level. If there is none, then it will forward the search operation to each child node with the message makeObjectsPerformSelector:@selector(removeMark:) withObject:mark, so the search will keep going recursively until it reaches the last child of the tree. Every Mark object implements the removeMark: method, so there is no concern for us whether a particular child node is a Stroke, Vertex, or anything else before sending the message out.

childMarkAtIndex:, lastChild, and count methods simply return from similar methods in children_ (NSMutableArray).

The way a client can construct a Mark composite structure is shown in Listing 13-8.

// ...

Dot *newDot = [[[Dot alloc] init] autorelease];
Stroke *parentStroke = [[[Stroke alloc] init] autorelease];

[parentStroke addMark:newDot];

// ...

Vertex *newVertex = [[[vertex alloc] init] autorelease];
Stroke *newStroke = [[[Stroke alloc] init] autorelease];

[newStroke addMark:newVertex];

[parentStroke addMark:newStroke];

// ...

Individual Dot objects can be added to parentStroke as leaf nodes. parentStroke can also take composite Stroke objects that manage their own Vertex children, of which the purpose is to let the drawing algorithm draw connected lines.

In our TouchPaint app, there is a CanvasViewController that handles some basic drawing operations with touches. Touch event operations in the controller construct a main composite Mark structure that contains all individual, drawable dots as well as strokes that contain other non-drawable vertices, to form connected lines. CanvasViewController's view, called CanvasView, will present (draw) a complete Mark structure on the screen.

Figure 13-5 illustrates an actual dot and stroke drawing situation.

Figure 13-5. An actual sequence of drawing a dot and a stroke with Quartz 2D

We can add a drawing operation like drawWithContext:(CGContextRef)context to the Mark protocol so every node can draw itself according to its specific purpose. The one in Dot will go like that shown in Listing 13-9.

- (void) drawWithContext:(CGContextRef)context
{
  CGFloat x = self.location.x;
  CGFloat y = self.location.y;
  CGFloat frameSize = self.size;
  CGRect frame = CGRectMake(x, y, frameSize, frameSize);

  CGContextSetFillColorWithColor (context,[self color CGColor]);
  CGContextFillEllipseInRect(context, frame);
}

With an active context, an ellipse (a dot) can be drawn in the context with location, color, and size.

However, a vertex provides only a particular location in a stroke. So a Vertex object will add a point to a line only in the context (well, the Quartz 2D function in fact does add a line to a point) with its own location (coordinates), as shown in Listing 13-10.

- (void) drawWithContext:(CGContextRef)context
{
  CGFloat x = self.location.x;
  CGFloat y = self.location.y;

  CGContextAddLineToPoint(context, x, y);
}

For a Stroke object, it needs to move the context to the first point of its children, and then it wraps up the whole line drawing operation with the Quartz 2D functions CGContextSetStrokeColorWithColor and CGContextStrokePath, as shown in Listing 13-11.

- (void) drawWithContext:(CGContextRef)context
{
  CGContextMoveToPoint(context, self.location.x, self.location.y);

  for (id <Mark> mark in children_)
  {
    [mark drawWithContext:context];
  }

  CGContextSetStrokeColorWithColor(context,[self.color CGColor]);
  CGContextStrokePath(context);
}

The primary challenge when designing the Mark protocol is to come up with a minimal set of operations to provide open-ended functionality. Performing surgery on the Mark protocol and its subclasses for each new functionality is both invasive and error-prone. Eventually, the classes get harder to understand, extend, and reuse. So the key is to focus on a sufficient set of primitives for a simple and coherent interface.

In the chapter about the Visitor pattern (Chapter 15), we will explore how both the Composite and the Visitor patterns work together to create powerful yet flexible solutions for many problems related to tree structures.

In the Cocoa Touch framework, UIViews are organized as a composite structure. Each instance of UIView can have other instances of UIViews to form a unified tree structure. It lets clients treat individual UIView objects and compositions of UIViews uniformly.

The UIViews in a window are internally structured into a view tree. At the root of the hierarchy is a UIWindow object and its content view. Other UIViews that are added to it become subviews of it. Each of them can have other views and becomes the superview of its view children. A UIView object can have only one superview and zero or more subviews. Figure 13-6 illustrates this relationship.

Figure 13-6. A visual structure of the UIView

Their relationships can be viewed from a different perspective as illustrated in a hierarchical diagram in Figure 13-7.

Figure 13-7. A hierarchical structure of the UIView

The view composite structure plays a part in both drawing and event handling. When a superview is asked to render itself for display, the message will be handled in the superview before its subviews. The message will be propagated to other subviews throughout the whole tree. Since they are all of the same type, UIView, they can be treated uniformly, and a branch of a UIView hierarchy can be treated as a unified view.

The unified view is also used as a responder chain for event handling and action messages. The drawing message is passed down the structure from superviews to their subviews, as are any event handling messages. The responder chain in the Cocoa Touch framework is the implementation of the Chain of Responsibility pattern (see Chapter 17).

The Composite pattern's main intent is for each node in a tree structure to share the same abstraction interface. So the whole structure can be used as a unified abstraction structure without exposing its internal representation. Any operation on each node (either leaf or composite) can be operated with the same interfaces that are defined in a protocol or abstraction base class.

New operations applied on the structure can be used with the Visitor pattern (Chapter 17) to have visitors "visit" each node for further processing without modifying the existing composite structure.

An internal representation of a composite structure is not supposed to be exposed to clients, so the Composite pattern is always used with the Iterator pattern to enumerate each individual item in a composite object. We will discuss the Iterator pattern and related design issues in the next chapter.