Design Patterns : Elements of Reusable Object-Oriented Software

Accessing Scattered Information 
Many kinds of analysis require examining the text character bycharacter. The text 
we need to analyze is scattered throughout ahierarchical structure of glyph objects. 
To examine text in such astructure, we need an access mechanism that has knowledge 
about thedata structures in which objects are stored. Some glyphs might storetheir 
children in linked lists, others might use arrays, and stillothers might use more 
esoteric data structures. Our access mechanismmust be able to handle all of these 
possibilities. 
An added complication is that different analyses access information indifferent 
ways. 
Most
analyses will traverse the text frombeginning to end. But some do the 
opposite
—
a reverse search, forexample, needs to progress through the text backward 
rather thanforward. Evaluating algebraic expressions could require an 
inordertraversal. 
So our access mechanism must accommodate differing data structures, andwe must 
support different kinds of traversals, such as preorder,postorder, and inorder. 
Encapsulating Access and Traversal 
Right now our glyph interface uses an integer index to let clientsrefer to children. 
Although that might be reasonable for glyph classesthat store their children in 
an array, it may be inefficient forglyphs that use a linked list. An important 
role of the glyphabstraction is to hide the data structure in which children 
arestored. That way we can change the data structure a glyph class useswithout 
affecting other classes. 
Therefore only the glyph can know the data structure it uses. Acorollary is that 
the glyph interface shouldn't be biased toward onedata structure or another. It 

---

Design Patterns: Elements of Reusable Object-Oriented Software 
79 
shouldn't be better suited to arraysthan to linked lists, for example, as it is 
now. 
We can solve this problem and support several different kinds oftraversals at 
the same time. We can put multiple access and traversalcapabilities directly in 
the glyph classes and provide a way to chooseamong them, perhaps by supplying 
an enumerated constant as aparameter. The classes pass this parameter around during 
a traversalto ensure they're all doing the same kind of traversal. They have topass 
around any information they've accumulated during traversal. 
We might add the following abstract operations to Glyph's interface tosupport 
this approach: 
void First(Traversal kind) 
void Next() 
bool IsDone() 
Glyph* GetCurrent() 
void Insert(Glyph*) 
Operations First, Next, and IsDonecontrol the traversal. First initializes the 
traversal. Ittakes the kind of traversal as a parameter of typeTraversal, an 
enumerated constant with valuessuch as CHILDREN (to traverse the glyph's immediate 
childrenonly), PREORDER (to traverse the entire structure inpreorder), POSTORDER, 
and INORDER.Next advances to the next glyph in the traversal, andIsDone reports 
whether the traversal is over or not.GetCurrent replaces theChild operation; it 
accesses the current glyph in thetraversal. Insert replaces the old operation; 
it insertsthe given glyph at the current position.An analysis would use the 
following C++ code to do a preordertraversal of a glyph structure rooted at g: 
Glyph* g; 
for (g->First(PREORDER); !g->IsDone(); g->Next()) { 
Glyph* current = g->GetCurrent(); 
// do some analysis 
} 
Notice that we've banished the integer index from the glyph interface.There's 
no longer anything that biases the interface toward one kindof collection or 
another. We've also saved clients from having toimplement common kinds of 
traversals themselves. 
But this approach still has problems. For one thing, it can't supportnew traversals 
without either extending the set of enumerated valuesor adding new operations. 
Say we wanted to have a variation on preordertraversal that automatically skips 

---