Design Patterns : Elements of Reusable Object-Oriented Software

Design Patterns: Elements of Reusable Object-Oriented Software 
81 
Figure 2.13: Iterator class and subclasses 
The Iterator interface provides operations First, Next, and IsDone forcontrolling 
the traversal. The ListIterator class implements First topoint to the first element 
in the list, and Next advances the iteratorto the next item in the list. IsDone 
returns whether or not the listpointer points beyond the last element in the list. 
CurrentItemdereferences the iterator to return the glyph it points to. 
AnArrayIterator class would do similar things but on anarray of glyphs. 
Now we can access the children of a glyph structure without knowingits 
representation: 
Glyph* g; 
Iterator* i = g->CreateIterator(); 
for (i->First(); !i->IsDone(); i->Next()) { 
Glyph* child = i->CurrentItem(); 
// do something with current child 
} 

---

Design Patterns: Elements of Reusable Object-Oriented Software 
82 
CreateIterator returns a NullIterator instance by default. ANullIterator is a 
degenerate iterator for glyphs that have nochildren, that is, leaf glyphs. 
NullIterator's IsDone operationalways returns true. 
A glyph subclass that has children will override CreateIterator toreturn an 
instance of a different Iterator subclass. 
Which
subclass depends on the structure 
that stores the children. If theRow subclass of Glyph stores its children in a 
list_children, then its CreateIterator operation would looklike this: 
Iterator* Row::CreateIterator () { 
return new ListIterator(_children); 
} 
Iterators for preorder and inorder traversals implement theirtraversals in terms 
of glyph-specific iterators. The iterators forthese traversals are supplied the 
root glyph in the structure theytraverse. They call CreateIterator on the glyphs 
in the structure anduse a stack to keep track of the resulting iterators. 
For example, class PreorderIterator gets the iterator fromthe root glyph, 
initializes it to point to its first element, and thenpushes it onto the stack: 
void PreorderIterator::First () { 
Iterator* i = _root->CreateIterator(); 
if (i) { 
i->First(); 
_iterators.RemoveAll(); 
_iterators.Push(i); 
} 
} 
CurrentItem would simply call CurrentItem on theiterator at the top of the stack: 
Glyph* PreorderIterator::CurrentItem () const { 
Return _iterators.Size() > 0 ? _iterators.Top()->CurrentItem() : 0;
} 
The Next operation gets the top iterator on the stack andasks its current item 
to create an iterator, in an effort to descendthe glyph structure as far as possible 
(this is a preordertraversal, after all). Next sets the new iterator to thefirst 
item in the traversal and pushes it on the stack. ThenNext tests the latest iterator; 
if its IsDoneoperation returns true, then we've finished traversing the 
currentsubtree (or leaf) in the traversal. In that case, Next popsthe top iterator 
off the stack and repeats this process until it findsthe next incomplete traversal, 
if there is one; if not, then we havefinished traversing the structure. 

---