Page 1 of 1

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

#1 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,120
  • 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;
     }


This post has been edited by macosxnerd101: 12 May 2017 - 07:59 AM


Is This A Good Question/Topic? 1
  • +

Replies To: Data Structures- Trees, Stacks, and the Iterator Pattern

#2 Kannelbulle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 12-May 17

Posted 12 May 2017 - 06:56 AM

Hello. Although it's quite some time after the tutorial was posted, I have 2 issues:
- code snippet for stack implementation doesn't work any longer
- why is value of a node being compared with number of children? In previous tutorial there was no mention about what value is for, hence I suppose it's simply what the node should represent. Hence, is there any assumption for using it to traverse back the tree? And even compare it with number of children?
(snippet 3 lines 32-46)
Please clarify if possible :)
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,120
  • Joined: 27-December 08

Posted 12 May 2017 - 08:06 AM

I've fixed the link for the StackMap snippet.

As for your question, the TreeIterator is controlling a depth-first traversal of the tree. The next() method essentially visits the next TreeNode in the depth-first ordering. So if a node is a leaf, we should backtrack. This is the reason for checking that a TreeNode has children.
Was This Post Helpful? 0
  • +
  • -

#4 Kannelbulle  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 12-May 17

Posted 12 May 2017 - 08:24 AM

Thanks for the update!

I understand the problem of going back "up" the tree, however I do not se why there is a comparison with value. It seems like all that matters is if parent node has any more children to traverse, but why value comparison?
It seems like either it's a way to flag a node if it had left child traversed, it's first walk-through it, or it had both children traversed. But as I see value is in your stack implementation simply some kind of number stored.

To be more specific :
while(value >= temp.numberChildren()-1 && callStack.size() > 1){ // why compare value with children? 
44
                          value = callStack.pop().getValue();
45
                          temp = callStack.peek().getKey();
46
                      }
47
 
48
                      if(!callStack.isEmpty() && value < temp.numberChildren()-1){ // why does value matter here? 
49
                          callStack.push(temp.get(value+1), value+1);
50
                      }



If i'm correct value should matter in any way while traversing. Only the number of children yet untraversed.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,120
  • Joined: 27-December 08

Posted 12 May 2017 - 10:03 AM

Quote

It seems like all that matters is if parent node has any more children to traverse, but why value comparison?


Not quite. Yes, it is important if a parent node has more children to traverse. If it does have more children, which child should I visit next? The value works as a bookmark, telling me which of the parent's children the current node is. This helps me determine the next child to visit.

In a traditional DFS implementation, we have a node. Then for each of the node's children, we recurse on that child. The underlying call stack supporting the recursion and the loop index allows us to keep track of which child to visit next. Here, we are lacking the loop index (hence, the value variable); and the StackMap is the "underlying call stack," so to speak.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1