The basic operation of the composite pattern is easily grasped. Composite is another wrapper pattern that involves one object rerouting method calls to another object with the same interface.

Graphed, it looks nearly identical to the state pattern. Remember that with state, a wrapping object relays method calls to any one of a number of objects with the same interfaces, depending on its "state."

With composite, rather than relaying the calls to one internal object, the wrapping object relays the calls to ALL of them.

If state involves a one-to-one-of-many relationship, composite involves a straight-up one-to-many relationship. When the wrapper jumps(), all the objects that it wraps jump() too.

This operation is useful because--in coding as in life--it can be convenient to treat a group of things like one thing.

CompositeWakeable: A Simple Example

Remember my decision that module-specific collateral material would come up in a pop-up window when the user requests it. And the further decision to make alert 2/5th modules: of the five strategies in a module, an alert composed only two, an IWakeable instance and an ILoadable instance. Other than background-drawing code for the pop-up window, an alert amounted to just these two objects.

As soon as I began tailoring actual alerts, I found that I wanted to stack alerts on top of one another: a text alert on top of a text alert (emphatic paragraphs), a picture alert with a text alert (a caption) underneath, a video sandwiched between a picture and some text, etc.

It was nothing to whip up a MultipleAlert class that took in plural alerts in its constructor and aligned them vertically. The problem was dealing with the now submerged strategies of each module, _loadable and _wakeable.

Just as it listened for selection events, my Mediator class listened for new alerts, loading and waking them. However, it was written for one alert at a time, not multiple simultaneous alerts. And I wanted it that way. For the sake of letting-be and eventual adding-on, it was better to force novel complications inside the new class, MultipleAlert.

Clearly, loadable and wakeable needed to remain one thing for the Mediator, while also being a group of things. The obvious solution was the Composite pattern, with its many-in-one structure.

The first step was to populate composite versions of each strategy in Multiple Alert:

Now let's look at CompositeWakeable. A typical composite, this one offers a method for adding and referring to its children.

The rest of the composite's methods repeat those its children:

The one-to-many method is the defining operation of the Composite pattern:

Now, when the Mediator wakes CompositeWakeable inside MultipleAlert, it wakes up all the alerts gathered inside it.

Note that the CompositeWakeable is not exactly the same as its children, even though they share methods. The child probably won't implement addWakeables, or might only implement a silent-fail dummy method. The reverse might be true, too--the composite might sport dummy methods that don't really apply to it:

There are cases where this method could be another one-to-many wrapping. Waking, however, is not one of them. Just as BaseNavigable takes callbacks for goto() and gotoPronto(), BaseWakeable takes locally defined callbacks for wake() and sleep(). So uniform wakes are improbable and multiple wake setting unnecessary.

Composite: Folders within Folders

Believe it or not, we have not even touched the most powerful part of the Composite pattern, the part that dramatically lifts the pattern above and beyond its fellow wrappers.

So far we have been considering the simplest case of a composite, where a composite includes leaf children, end of story.

Now, what if one of composite's children was itself a composite? A whole branching tree might grow out of a single composite:

Imagine the top of this inverted tree calling a commonly-implemented method like wake(). Wakings would cascade down the entire tree, at first encompassing more branching composites, and finally waking all that is wakeable.

After I read the Composite chapter in Head First Design Patterns, I recognized immediately that the composite was structured like any navigation system or any folder-and-file system, with some nodes terminating a line, other nodes leading to more nodes.

This structure is of course quite pedestrian, so its mere rediscovery didn't explain why my tongue was hanging out. No, it was that the pattern suggested ways to soft-code this familiar structure so that it could be built and manipulated fluidly.

A Not So Simple Example

I began thinking about a possible background loading queue after getting only a few pages into the Head First Composite chapter.

This possibility had been like the many possibilities that flicker in the back of a coder's mind. It seemed like a pleasant prospect to be there, but it involved crossing not one but many rivers, all equally wide and alien to me...so even my daydreams had not even left the yard.

Knowing composite gave me ambition. Perhaps I could write a loading queue that wasn't dry, brittle spaghetti.

My initial guess was that was organizing candidates into folder-like groups, then organizing these groups into folder-like hierarchies, could make the queue segmented and modular enough to react intelligently to user input.

I knew that that the solution would not be a cookie-cutter example of the pattern. Unique factors abounded:

1) Loadables don't come out of the package in tidy groups. Each one needs to be harvested from a module in a Composite-like hierarchy of modules.

2) Different groups of loadables might easily share individual loadables.

3) The status of streaming loadables might revert from isReady==true to isReady==false as they lost their buffer, so a constant reference to them had to be maintained.

At this point, I knew that my queue would be a composite, but I didn't know what species of leaf-node would be the building block.

Triple-Layer Cake: The SortIteratorComposite

The answer only crystallized when I re-read the Head First chapter on another pattern, Iterator.

The Iterator pattern is strongly linked to the Composite pattern. This is the problem it solves: Suppose you are writing code that explores a composite, asking: what's up with your children? Since composites might use different ways to access its children, the code you're writing would need to account for the differences.

A pain, unless...each composite had the identical manner of accessing or iterating over its children.

No BaseIterator class should ever exist. Rather the Iterator pattern boils down to a minimal interface:

An iterator can implement these methods promiscuously. The canonical example has nothing to do with composites. Suppose some code is eating through data values. It doesn't know if what it's eating is an object hash or an array...and it doesn't need to know if everything it eats though has an interator. Then, all it has to do is ask the iterator hasNext() and then (if it does) take next().

While reading about Iterator, prompted by a leap of intuition (or random mental mash-up?), I made a second guess: The building blocks of my composite hierarchy would not compose iterators, they could actually BE iterators. Composite iterators would ask their children hasNext() (any unloaded loadables?). If the children had children, they would pass the question along, but if they were actual leaf iterators, they would ask themselves the question. Any true response would stop the process and be passed up the tree, while a false response would only be passed up if the whole tree had been traversed.

A structure crystallized in my head fully formed, but naming it was tough. It was a funny composite, because it was composed of iterators...and it was a funny iterator, because it sorted among its children (loaded?)...and it was a funny sort, because it stopped sorting with a positive result. FindComposite and FilterComposite sounded too vague, so I unhappily settled on SortIteratorComposite.

SortIteratorComposite has the usual extra composite method: addChild. It also the one-to-many version of Iterator's key method, hasNext.

In the direct case, a CompositeSortIterator might have a bunch of real iterators for children. When its hasNext method is called, it starts by running through the children and asking each if it hasNext. If one returns true, it returns true, too.

In the indirect case, a CompositeSortIterator might have a couple of fellow CompositeSortIterators among its children. But since the composite patterns makes the one and the many equivalent, the parent composite does not care either way, treating all children equally and calling hasNext regardless. In the case where the child is another composite, the hasNext just gets pushed farther down the line.

If, at an actual, non-composite iterator, true is returned, that value then gets pushed up the tree, as each interrupted hasNext completes. If you've never wrestled with recursion before, this graph might clarify the sequence.

You might be wondering how the top composite, once a positive bubbles up, gets a next() value from some iterator at the bottom of the tree.

Remember that hasNext is logically called before next (Got any? I'll take that). Also remember that, if true is ultimately returned, hasNext has already blazed the recursive trails down the composite tree. So if breadcrumbs are left, a top-level next() can simply retrace its successive steps to find the ultimate next() result.

This is easily done. For each composite, store the last examined child (the selected folder, as it were) in a curLeaf variable:

Afterward, SortIteratorComposite can recursively dig through various composites until it finds an actual iterator, then get the real next().

Notice that what is ultimately returned is neither a composite iterator nor an actual iterator, but the result of a next() call on an actual iterator (in this case, an unloaded loadable). This is non-standard, because the next() should return either a SortIteratorComposite or a SortIterator, not an untyped object.

I coded the SortIteratorComposite this way because I wanted next() to return an actual result, not a first positive-testing leaf iterator. And the elegance of this extra-level recursion appealed to me at the time. When I open up its package again, however, I'll make next() return the iterator, and have whatever calls next() take the extra step of extracting the actual next() value. That way, the ISortIteratorComposite interface can be implemented throroughly, and any type errors caught by the compiler.

So what about these actual Object-returning iterators? They will either implement the ISortIterableComposite interface or subclass this base class:

Reflect on the fact that I haven't mentioned an actual SortIterable yet. The entire structure has been built, but the actual work of grouping, filtering and returning loadables has been entirely deferred to various SortIterables. That's great, because we can change the logics without changing the overarching structure. What's even greater is that an eclectic set of logics can be brought under one roof.

SortIterableComposite in Practice: The Queue

My Downloader class is a bit of an oxen. He loads whatever a SortIterableComposite in his superclass tells him to load:

When he's hungry for a load, he just grunts next():

So what should be loaded first? The "thinking" of the SortIteratorComposite is determined by the logic and the order of its child iterators. The most important iterators would be those that react to the most basic user input, module selection. Let's stipulate first that a selected module should go to the head of the line. Here is characteristic method of the SelfIterator:

Well, that was over almost too quickly. Let's now write a ChildrenIterator to download the selected module's children. If the user is interested in a module, chances are, she's interested in its children, too. Here is its hasNext:

Now, after children, siblings should be checked for loads as well. So I wrote a SiblingIterator class as well.

The next step was to roll all these module-selection-sensitive iterators into one FamilyIterator class:

Now let's get this party started. For its first child, Downloader's top-level iterator adds an instance of FamilyIterator:

Uniquely, Downloader keeps a separate reference to familyIterator, so it can tell what "family" is a stake when a new selection is made:

Cool, no? With only a few simple SortIterator classes written, I already have a background loading queue that responds immediately to a new selection, directing its efforts first at the selected module, then its children, then its siblings.

It gets better. What if the whole family is completely loaded? Should Downloader rest? I think not. Here is the TreeSortIterator, which uses the moduleTree class to walk through the entire module tree looking for modules with unloaded loads:

This iterator gets its own folder after the family iterator:

The structure of Downloader's deep-thinking, rapidly built iterator can be graphed like this:

Can you believe how simple it is to built different trees and thus different downloading logics? With the change of a single line, the priorities of SiblingIterator and ChildrenIterator could be switched, or one of them could go in the same folder as the TreeSortIterator...or another SortIterator subclass can be added, anywhere.

Consider also that the ordering could be changed almost as easily run-time as it can be changed compiled time, so whole prioritizing schemes could be deployed in response to run-time factors: bandwidth, user selections, user history, etc.

Polymorphism in Composite

The composite depends on an strict interface conformity to ensure equivalence between the one that really is one, and the one-seeming one that really is many. So patterns-experienced coders will have noticed that my implementation of the ISortIteratorComposite interface has been incomplete and inconsistent.

Cleaning that up is on my TODO list. I mention it now because patterns are often based on particular interface manipulations, and when you struggle with an interface, your strggle might be typical for that pattern.

In my case, I was never quite sure about the autonomy of the units within the whole composite tree. For instance, ISortIterableComposite has a setFilter method. That method takes a filter function parameter:

And since the setFilter function is a one-to-many in a composite, setting the filter here cascades down the tree, affecting the result of all the hasNext methods in the many SortIterators we've reviewed. I desired that, because I though the filter/finding criteria might shift...but is it kosher for one unit in a tree parameterize and alter the behavior of another unit?

Another problem I had was getting rid of iterators that would lose their relevance. Why should Downloader's iterator keep going through a DeepLinkIterator (which offered successive loads enabling a deep-link navigation), which is long dead by the time a user selects their first module?

The solution was a TempIterator, awarded first place among the iterators:

This composite would handle urgent, non-selection-based series of loads that could be added dynamically and retired permanently. Here is the adding:

The retiring required more subtlety. Most iterators aren't going to be on first-name basis with Downloader or even their parent composites. So they can't well retire themselves. They could, however, reset an "active" property, and the composite parent could retire the child on the basis of that property.

Here is the active setter in TempIterator, a subclass of SortIterator:

And here is how a TempIteratorComposite prunes a TempIterator:

Now for an example of an actual pruning. The Mediator listens for alerts, and alerts usually come in series. When the user puts a series in play, the Mediator gets an iterator from AlertSeries and gives it to Downloader:

When user actions take the series out of play, the Mediator resets its active property:

Now, the next time Downloader's iterator calls hasNext(), it--or a downstream TempIteratorComposite--will prune alertsIterator. If any alerts remain unloaded, they will remain unloaded, which is righteous, because user-browsed collateral material should not be part of normal background loading.

Like the cascading filter parameter, this worked out for me...but I remained paranoid, because again, by creating a whole "Temp" branch of the composite tree, I wasn't sure if I was exploiting polymorphism or bending an interface. Should one composite and all its children act at variance with the rest of the tree?

Question like these dog me when I work with Composite...but the rewards are eye-popping, so I'll keep at it.

Tags: patterns · code1 Comment