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

1 public AnyType next( )
2 {
3 if( !hasNext( ) )
4 throw new NoSuchElementException( );
5
6 AnyType value = current.element;
7 lastVisited = current;
8
9 if( current.right != nullNode )
10 {
11 path.push( current );
12 current = current.right;
13 while( current.left != nullNode )
14 {
15 path.push( current );
16 current = current.left;
17 }
18 }
19 else
20 {
21 AANode<AnyType> parent;
22
23 for( ; !path.isEmpty( ); current = parent )
24 {
25 parent = path.pop( );
26
27 if( parent.left == current )
28 {
29 current = parent;
30 break;
31 }
32 }
33 }
34
35 visited++;
36 return value;
37 }

figure 19.75
next method for
TreeSetIterator

observation will hold for HashMap , relative to HashSet . Thus we implement the
package-visible abstract class MapImpl , which can be constructed from any Set
(or Map ). TreeMap and HashMap will extend MapImpl , providing implementations
of the abstract methods. The class skeleton for MapImpl is shown in Figures
19.77 and 19.78.
One data member, the underlying set theSet , is declared at line 10. The
key/value pairs are represented by a concrete implementation of the Map.Entry
class; this implementation is partially supplied by the abstract Pair class that
extends MapImpl (at lines 52-72). In TreeMap this Pair class is extended further