For a few years now I have been striving to understand a yet undocumented Good Design which I discovered while writing some tree handling code. The problem was simple. I wanted to make some code (client code) which could traverse the nodes of a tree in my domain model. This article describes how I solved this problem six years ago and what six years in the think tank does to an idea.
This is a no brainer of course except that I felt that it seemed futile to create code which was hard wired to the inner workings of my domain model since the code really wanted to be reusable. Trees are everywhere in our lives. From file systems to XML DOM structures, hierarchies are everywhere and need to be traversed.
Swing has a component that can traverse all kinds of trees. It is enough that you implement a TreeModel, although the TreeModel class itself counts a few extra methods than is required for the pure data modeling. And of course I didn't have the smarts to look in the JDK if anyone had solved my problem before, so I went ahead and discovered the same things that were " common knowledge".
What I did discover is that in order to navigate any tree you need to be able to answer four simple questions
Swing's TreeModel solves the problem in a slightly different way, (no " T getParent(T)") but the important fact remains that if you implement an interface containing those four methods, you can write tree agnostic code which traverses trees in any way you want.
Let's call my interface TreeAbstraction:
public T getRoot(); public T getParentOf(T o); public int getChildCount(T o); public T getChildOf(T o, int index);
It is of course possible that getChildCount and getChildOf should be changed to one method returning a list or an iterator. I think it makes no difference other than that Lists clean up the interface. Also this interface requires models to have index based access of their children, which may also not be feasible for all conceivable hierarchical structures. List, Set or Collection or even Iterator may be more "correct".
Wonderful. So I set out and created a large set of classes supporting this tree traversal methodology: I wrote code which could iterate over the nodes in-order, actually implementing the Iterator interface. I had a notion of " views" layered on top of the hierarchy so that I could iterate over only parts of a tree (for example only the subelements of _this_ item). I added " view mathematics" so I could iterate over an aggregation of several views, subtraction of views, and so on. And on top of this I wrote useful code (JSP tag libraries) which could do all of this as long as it was handed those four methods.
And of course we ended up creating many different TreeAbstraction implementations for several hierarchical domain models we had.
The end result is client code (iterators, views, tag libraries) which can operate on many different types of hierarchical domain models (file systems, DOM trees, etc.). I think that's is quite cool.
I have tried to explain this concept to many people so if you've already lost, no problem. Go back to the beginning and start over. It is important that you understand the concept of the TreeAbstraction. If it's your second time round, try continuing. :-)
As I stated in the introduction, I have strived for many years to understand this Good Design I created, and wondered wether or not it was a design pattern itself or if it was just an application of a design pattern. Recently I have come to understanding that it is a pattern in its own right in the same way that Iterator is a design pattern.
The Iterator pattern allows client code to traverse a number of of items without the client code knowing how the items are organised.
Likewise, my TreeAbstraction allows client code to traverse a number of items in a hierarchy without the client code knowing how items are organised.
Hence I propose a new Design Pattern which encompasses both Iterator, TreeAbstraction and possibly others which:
"allows client code to traverse conceptually similar object structures without knowing how those object structures are implemented"
It has in fact taken me six years to write that statement down, and it feels really good.
Now, the way I have implemented this pattern (whatever it will be called) is driven by the forces of the client code and the domain model not knowing about each other or even that there will be anything tying them together. Iterator on the other hand as it is implemented in Java is provided right there in the List interface. This goes against the forces driving this pattern, since I don't want client code having to know that it is a List or anything, I just want to be able to traverse this list, I want an iterator, not a List r an Iterable! In my opinion, Lists and so forth are proliferating to the very extreme and this may well turn out to be a Bad Thing(tm).
The point is that Iterator is part of the Collections API and since everyone is accustomed to retrieving an iterator by way of its factory method in the Set or List, it is quite uncommon to see it in other places where it would be natural to provide iterators. For example org.w3c.dom does not provide a simple Iterator of the an item's child nodes as one might have learned to expect from List, but rather you need to pass your Node, to a DocumentTraversal class and from there you get a complex NodeIterator which contains seven (!) methods.
So let's continue along a complete Design Pattern, generalizing it ever so slightly along the way:
Name: Conceptual Abstraction
Type: Behavioural
Intent:
Allow client code to manipulate conceptually similar object structures without knowing how those object structures are implemented
Problem:
Two types of hierarchies exist and I would like to write code which can be reused for both types of hierarchies. File and Node both implement their own type of hierarchy using different method names and semantics. File.getParentFile returns a File's parent, while Node.getParentNode returns a Node's parent. Client code would like to be able to traverse the hierarchy without knowing the type of hierarchy.
Forces:
Context:
The client code has a reference to an object but knows not if it is a Node or a File, and it wants to get that object's parent:
Object item = // node or file Object parent = ???
Example:
1. Define the operations required for hierarchy traversal:
Object getRoot(); Object getParentOf(Object); List getChildrenOf(Object);
2. Implement concrete classes for FileHierarchy and NodeHierarchy:
File getParentOf(File f) {
return f.getParentFile();
}
...
Node getParentOf(Node n) {
return n.getParent();
}
Resulting Context:
Client code uses an instance of FileHierarchy or NodeHierarchy depending on if it is talking to a File or Node hierarchy:
Object item = // node or file Hierarchy h = ... Object parent = h.getParentOf(n);
Solution:
Create an abstraction which encapsulates the operations that are required to manipulate the conceptual structure, and create implementations of that abstraction for each implementation of the conceptual structure.
Define an interface which establishes the contract required to be able to manipulate the conceptual structure. The methods of the interface will typically take a generic type in as a parameter and return the same generic type.
The concrete implementations would describe how to perform all of these operations on a specific type of domain object model, by delegating to the appropriate methods in the domain object themselves.
Clients that have a handle to a domain object can pass the domain object to a concrete implementation of this abstraction to perform some operation, for example navigation.
___________________________________
Note how I have generalized the design pattern by noting how it refers to " operations" and not merely "navigation". If I wanted to write client code that inserted items into an existing structure then it would be as simple as to add "addItemAfter(Object)" in the abstraction. That way, client code could at leisure modify the structure without knowing how the structure does it.
*Phew* that took a few hours! (Not to say years!) Have fun with it!