Page 1 of 1

Data Structures- Trees, Stacks, and the Iterator Pattern Rate Topic: -----

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10568
  • View blog
  • Posts: 39,131
  • Joined: 27-December 08

Posted 21 November 2010 - 03:40 PM

Data Structures- Trees, Stacks, and the Iterator Pattern

In this tutorial, we will be shifting gears from recursion to implementing an Iterator for a Tree. If you haven't already done so, I would highly recommend reading up on my previous tutorial on Recursion, Stacks, and Trees, as it covers a lot of the foundation for the Iterator Pattern here. The reason for this shift is because implementing an Iterator for a Tree nicely ties together a lot of the concepts we have talked about with Stacks and Tree Models. In addition, designing an Iterator is a key part of implementing the Collection interface, and this is not necessarily the most straight-forward for Trees like it is for Lists and Sets. Also, the concepts presented in this tutorial are applicable to Tree parsing in general.

So to start, we will want to have our Iterator calss implementing the Iterator interface which accepts the Tree it will be iterating over in the constructor. Just like the Call Stack is the underlying structure for when we utilize recursion, a Stack will be the backbone of our Iterator. However, I will be using a custom Stack implementation- a StackMap. Specifically, I will be storing a StackMap<TreeNode<E>, Integer> so I can control the iteration through the Tree. With recursion, calls are pushed onto the Call Stack, then popped off when the call completes. The StackMap allows us to better control when Nodes are pushed and popped for iteration with the Iterator. For specific information on the StackMap, see my StackMap snippet.
class TreeIterator<E> implements Iterator<E>{

	     //used to store TreeNodes in depth-first ordering
	     //as well as their positions in the parent TreeNode
         private StackMap<TreeNode<E>, Integer> callStack;

         //the Tree we are iterating over
         private Tree<E> tree;

         //used to flag that another element has been returned
         //and prevent the remove() method from trying to remove the
         //same element twice
		 private boolean returnedNext;

		 //used to flag that the iteration has been started
		 //to differentiate between when the StackMap is empty
		 //after the Tree has been completely traversed
		 private boolean returnedRoot;

         public TreeIterator(Tree<E> tree){
              this.tree = tree;
              callStack = new StackMap<TreeNode<E>, Integer>();

              returnedNext = true;
              returnedRoot = false;
         }

       //the Iterator methods we will be implementing
        public boolean hasNext(){}
        public E next(){}
        public void remove(){} 
}




Now let's outline our logic some before beginning. To start, we will push the root Node onto the StackMap when we instantiate the Iterator. When the next() method is called, the current element on the StackMap will be returned, and the next element will be pushed onto the Stack in depth-first order. When a Node has no more children to be pushed onto the Stack (ie., we have hit the bottom), it will be popped from the StackMap and go back upto the parent Node.

So how will the hasNext() method work? Basically, it checks to see if the Stack is empty to determine whether or not there is another element. Remember, we push an element onto the StackMap, then return that element when next() is called. So by the time the StackMap is empty, we have traversed the entire Tree.
         //There are more elements to iterate through iff the Stack isn't empty
         //Otherwise, we have traversed through all the elements in the Tree
         public boolean hasNext(){ return !(callStack.isEmpty() && returnedRoot);}




The next() method utilizes the StackMap data structure to back the Iterator. Basically, we start by pushing the root Node onto the StackMap. On each subsequent call of next(), we examine the top element on the StackMap. If it has children, then we push its first child onto the CallStack. If the top element doesn't have any more children, then we pop it and go to the next element on the StackMap. We repeat this process until we find a Node that has more children, or until we have run through all the elements on the StackMap.
  /** 
   * @return: The next element in the Tree, null if there are no more elements
   **/
         public E next(){

         		//if there isn't another element to iterate over
         		//then return null
         		if(!hasNext())
         			return null;

				//otherwise, flag that we've returned the next
				//element in the Tree
				returnedNext = true;

				/***
				 * if the callStack is empty and we haven't pushed the
				 * root Node already (hasNext() takes this into account)
				 * then we will push the root Node and mark that we have done so
				 * as to prevent iterating over the Tree multiple times with one
				 * Iterator
				 ***/
         		if(callStack.isEmpty()){
         			callStack.push(tree.getRoot(),0);
         			returnedRoot = true;
         		}

				//otherwise
         		else{

         			//start by examining the current element
         			TreeNode<E> temp = callStack.peek().getKey();
         			int value = callStack.peek().getValue();

					//if it has a child Node, then push it onto the callStack
					if(temp != null && temp.numberChildren() > 0)
						callStack.push(temp.get(0),0);

					//otherwise, go up levels in the callStack until we hit a Node that has another
					//child to add
					else{
						callStack.pop();
						temp = callStack.peek().getKey();
						while(value >= temp.numberChildren()-1 && callStack.size() > 1){
							value = callStack.pop().getValue();
							temp = callStack.peek().getKey();
						}

						if(!callStack.isEmpty() && value < temp.numberChildren()-1){
							callStack.push(temp.get(value+1), value+1);
						}

						//if we get to the root Node, we've traversed the entire tree
						//so we flag returnedNext as false so remove() won't do anything
						//and return null, as there are no more elements to iterate over
						else if(temp == tree.getRoot() && returnedRoot){
							returnedNext = false;
							return null;
						}


					}
         		} //end else

				return callStack.peek().getKey().getValue();
         }




As for the remove() method, what it does is remove the element last returned by next() from the Tree. It starts by examining the top element on the StackMap, popping it from the StackMap. We then remove any children from that Node, and remove that Node from the current StackMap's head element. This is very similar to removing an element from a Linked List. We then push the element we popped back onto the CallStack, decrementing its value by 1 to compensate for the fact that it is no longer in the Tree. We do this, as the next() method will then process this element normally and proceed onto the next element in the Tree.

The special case we have is when we try to remove the root Node of the Tree. When this happens, we just clear the Tree and the StackMap.
         public void remove(){
         	
 			//if we haven't returned another element from next() 
 			//or there aren't any more elements in the callStack
 			//then terminate this method call
         	if(!returnedNext || callStack.isEmpty()){
         		return;
         	}

			//if the element we are trying to remove is the Root
			//of the Tree, then we'll just clear the Tree and the 
			//callStack
			if(callStack.peek().getKey() == tree.getRoot()){
				tree.clear();
				callStack.pop();
			}
			
			//otherwise
			else{
				
				//pop the top element and get the current its value
				TreeNode<E> temp = callStack.peek().getKey();
				int value = callStack.pop().getValue();

				//remove the element we popped from the Tree
				callStack.peek().getKey().remove(temp);
				
				//and remove its children so they won't be 
				//returned by the next() method
				temp.getConnections().clear();
				
				//now push it back onto the callStack
				//decrementing its value to account for the fact
				//that its former parent Node now has one fewer children
				callStack.push(temp, value-1);
			}


			returnedNext = false;
     }



Is This A Good Question/Topic? 0
  • +

Page 1 of 1