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
- private class IteratorImpl implements Iterator{
-
-
- private int expectedModCount = modCount;
-
-
- private STNode lastReturned = null;
-
- private STNode nextNode = null;
-
- IteratorImpl(){
- nextNode = root;
- if(nextNode!=null)
- while(nextNode.left!=null)
- nextNode = nextNode.left;
- }
- ...
- }
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())
- private class IteratorImpl implements Iterator{
-
-
- private int expectedModCount = modCount;
-
-
- private STNode lastReturned = null;
-
- private STNode nextNode = null;
-
- IteratorImpl(){
- nextNode = root;
- if(nextNode!=null)
- while(nextNode.left!=null)
- nextNode = nextNode.left;
- }
-
- protected void checkIteratorState(){
- if(expectedModCount!=modCount) throw new ConcurrentModificationException("Concurrent Modification Exception!");
- }
-
- @Override
- public boolean hasNext() {
- return nextNode!=null;
- }
-
- @Override
- public T next() {
- checkIteratorState();
- if(nextNode==null)
- throw new NoSuchElementException();
- lastReturned = nextNode;
- STNode p;
- if(nextNode.right!=null) {
- nextNode = nextNode.right;
- while(nextNode.left!=null) nextNode = nextNode.left;
- } else {
- p = nextNode.parent;
- while(p!=null && p.right == nextNode) {
- nextNode = p;
- p = nextNode.parent;
- }
- nextNode = p;
- }
- return lastReturned.nodeValue;
- }
-
- @Override
- public void remove() {
- throw new java.lang.UnsupportedOperationException();
- }
-
- }
