[ Data Structures with Java ] Section 18.4 : The STree Iterator

Preface : 
Iterators have basic operations that allow a program to scan the elements in a collection and access their values. They also allow removal of an element as an update operation. The iterator methods are hasNext(), next() and remove(). Our task is to implement these methods as well as implement the STree class method iterator() that creates an Iterator object and gives it an initial value. 

The STree Iterator : 
In Section 17.2, we introduced an iterative inorder scan of a binary tree. The algorithm used a stack to store node references when we descended down a path to locate the next element. Popping the stack allowed us to reverse steps and move up the path. The design simulated the recursive version of the inorder scan. With the STree iterator, we implement an iterative traversal of the elements using the STNode parent field. 
- The Private Variables and Constructor of the STree Iterator Class 
Like the LinkedList iterator, we constructor the STree iterator using an inner class, IteratorImpl, that implements the Iterator interface. The private portion of IteratorImpl includes the variable nextNode, which references the next node in the inorder traversal of the tree. Its counterpart, lastReturned, references the last node whose value is returned by next(). This variable designates the node that is deleted by the iterator remove() method. The integerexpectedModCount is an inner class variable that corresponds to the value of modCount in the STree class. Comparing the two allows the iterator to determine whether an unexpected change occurred in the tree. For instance, the program may insert a new element using the STree class add(). This invalidates an iterator. The only way we can update the tree during an iterator scan is to call the iterator method remove(). Below is the implementation of the constructor of class IteratorImple : 

- IteratorImpl inner class inside STree class: Constructor and private variables

view plaincopy to clipboardprint?

1.     private class IteratorImpl implements Iterator{  
2.         // set expectedModCount to the number of list changes   
3.         // at the time of iterator creation  
4.         private int expectedModCount = modCount;  
5.         // node of the last value returned by next() if that  
6.         // value was deleted by the iterator method remove().  
7.         private STNode lastReturned = null;  
8.         // node whose value is returned a subsequent call to next;  
9.         private STNode nextNode = null;  
10.           
11.         IteratorImpl(){  
12.             nextNode = root;  
13.             if(nextNode!=null)  
14.                 while(nextNode.left!=null)  
15.                     nextNode = nextNode.left;  
16.         }  
17. ...  
18. }  

The constructor initializes nextNode to point at the minimum element in the tree. Find the element by starting at the root and traversing the chain of left subtrees. The process stops at a node with a null left subtree. This become the first node the iterator visits in the inorder scan. 

The STree Iterator Public Method : 
The STree method iterator() simply creates and returns an IteratorImpl object. The iterator is positioned at the minimum element whose value is the leftmost node in the tree. To follow up, lets check the implementation of methods in class IteratorImpl. 
- Implementing next() 
To implement the method next(), we must execute a series of iterative steps that move use from the current node to the next node in order. We do not look at the left branch of the current tree node, because it contains smaller values that we have already visited. We must either descend down the right subtree or move up the tree. We summarize the possibilities with the following rules : 

If the right subtree is not empty, obtain the next node in order by moving to the right child and then moving left until we encounter a null subtree.

If the right subtree is empty, obtain the next node in order by following a chain of parent references until we find a parent, P, for which our current node, nodePtr, is a left child. Node P is the next node in order. When this situation occurs, all the nodes on the left subtree of P have been visited, and it is time to visit P

The implementation of next() follows these two rules even when the method extracts the value of the last node. In the following implementation, the private method checkIteratorState() verifies that the value of expectedModCount in the inner class IteratorImpl equals the value of modCount in the STree class. If the values are not equal, an unexpected change has occurred in the tree and an exception is thrown : 

- Implementation of class IteratorImpl : (Except method remove())

view plaincopy to clipboardprint?

1. private class IteratorImpl implements Iterator{  
2.     // set expectedModCount to the number of list changes   
3.     // at the time of iterator creation  
4.     private int expectedModCount = modCount;  
5.     // node of the last value returned by next() if that  
6.     // value was deleted by the iterator method remove().  
7.     private STNode lastReturned = null;  
8.     // node whose value is returned a subsequent call to next;  
9.     private STNode nextNode = null;  
10.       
11.     IteratorImpl(){  
12.         nextNode = root;  
13.         if(nextNode!=null)  
14.             while(nextNode.left!=null)  
15.                 nextNode = nextNode.left;  
16.     }  
17.       
18.     protected void checkIteratorState(){  
19.         if(expectedModCount!=modCount) throw new ConcurrentModificationException("Concurrent Modification Exception!");  
20.     }  
21.       
22.     @Override  
23.     public boolean hasNext() {  
24.         return nextNode!=null;  
25.     }  
26.   
27.     @Override  
28.     public T next() {  
29.         checkIteratorState();  
30.         if(nextNode==null)  
31.             throw new NoSuchElementException();  
32.         lastReturned = nextNode;  
33.         STNode p;  
34.         if(nextNode.right!=null) {  
35.             nextNode = nextNode.right;  
36.             while(nextNode.left!=null) nextNode = nextNode.left;  
37.         } else {  
38.             p = nextNode.parent;  
39.             while(p!=null && p.right == nextNode) {  
40.                 nextNode = p;  
41.                 p = nextNode.parent;  
42.             }  
43.             nextNode = p;  
44.         }  
45.         return lastReturned.nodeValue;  
46.     }  
47.   
48.     @Override  
49.     public void remove() {  
50.         throw new java.lang.UnsupportedOperationException();              
51.     }  
52.   
53. }