Binary search trees - Data Structures and Problem Solving Using Java - page 746

1 /**
2 * This is the implementation of the TreeSetIterator.
3 * It maintains a notion of a current position and of
4 * course the implicit reference to the TreeSet.
5 */
6 private class TreeSetIterator implements Iterator<AnyType>
7 {
8 private int expectedModCount = modCount;
9 private int visited = 0;
10 private Stack<AANode<AnyType>> path = new Stack<AANode<AnyType>>( );
11 private AANode<AnyType> current = null;
12 private AANode<AnyType> lastVisited = null;
13
14 public TreeSetIterator( )
15 {
16 if( isEmpty( ) )
17 return;
18
19 AANode<AnyType> p = null;
20 for( p = root; p.left != nullNode; p = p.left )
21 path.push( p );
22
23 current = p;
24 }
25
26 public boolean hasNext( )
27 {
28 if( expectedModCount != modCount )
29 throw new ConcurrentModificationException( );
30
31 return visited < size( );
32 }
33
34 public AnyType next( )
35 { /* Figure 19.75 */ }
36
37 public void remove( )
38 { /* Figure 19.76 */ }
39 }
figure 19.74
TreeSetIterator inner class skeleton
If we have not removed the last item in the iteration, then we have to reset
the stack, because rotations may have rearranged the tree. This is done at lines
20-36. Line 35 is needed because we do not want current to be on the stack.
We finish by providing an implementation of the TreeMap class. A TreeMap
is simply a TreeSet in which we store key/value pairs; in fact, a similar