package edu.utoledo.nlowe.CustomDataTypes.Iterator;

import edu.utoledo.nlowe.CustomDataTypes.CustomStack;
import edu.utoledo.nlowe.CustomDataTypes.KeyValuePair;
import edu.utoledo.nlowe.CustomDataTypes.BinaryTreeNode;

/**
 * Created by nathan on 12/4/15
 */
public class PostorderBinaryTreeIterator<K extends Comparable<K>, V> extends BinaryTreeIterator<K, V>
{
    /**
     * The traversal stack. The value of the KVP is true if we have already
     * visited the right subtree of the node in question
     */
    protected final CustomStack<KeyValuePair<BinaryTreeNode<K, V>, Boolean>> traversalStack;

    public PostorderBinaryTreeIterator(BinaryTreeNode<K, V> head)
    {
        super(head);
        traversalStack = new CustomStack<>();
    }

    private void moveLeftmost()
    {
        while (nextNode != null)
        {
            traversalStack.push(new KeyValuePair<>(nextNode, false));
            nextNode = nextNode.getLeftBranch();
        }
    }

    @Override
    public KeyValuePair<K, V> next()
    {
        if(traversalStack.size() == 0)
        {
            moveLeftmost();
        }

        // If there is no right branch, or we already visited it, we can "visit" this node
        if(traversalStack.peek().getKey().getRightBranch() == null || traversalStack.peek().getValue())
        {
            return traversalStack.pop().getKey().getPayload();
        }else{
            // Go to the leftmost branch on the right subtree
            traversalStack.peek().setValue(true);
            nextNode = traversalStack.peek().getKey().getRightBranch();
            moveLeftmost();

            return next();
        }
    }
}

@@ -739,26 +739,646 @@
 ck%3C%3E();%0A    
-%7D%0A
+    traversalStack.push(new KeyValuePair%3C%3E(head, false));%0A%0A        spider();%0A    %7D%0A%0A    /**%0A     * Moves the next node pointer left as far as possible then%0A     * right once if possible until we reach a leaf%0A     */%0A    private void spider()%0A    %7B%0A        moveLeftmost();%0A%0A        while (nextNode.getRightBranch() != null)%0A        %7B%0A            traversalStack.peek().setValue(true);%0A            nextNode = nextNode.getRightBranch();%0A            traversalStack.push(new KeyValuePair%3C%3E(nextNode, false));%0A            moveLeftmost();%0A        %7D%0A    %7D%0A%0A    /**%0A     * Moves the next node pointer as far left as possible%0A     */
 %0A    private
@@ -1427,16 +1427,32 @@
 nextNode
+.getLeftBranch()
  != null
@@ -1455,32 +1455,81 @@
 null)%0A        %7B%0A
+            nextNode = nextNode.getLeftBranch();%0A
             trav
@@ -1586,57 +1586,8 @@
 ));%0A
-            nextNode = nextNode.getLeftBranch();%0A
     
@@ -1668,76 +1668,118 @@
     
-if(traversalStack.size() == 0)%0A        %7B%0A            moveLeftmost();
+KeyValuePair%3CK, V%3E result = traversalStack.pop().getKey().getPayload();%0A%0A        if(traversalStack.size() %3E 0)
 %0A   
@@ -1779,26 +1779,25 @@
  0)%0A        
-%7D%0A
+%7B
 %0A        // 
@@ -1797,91 +1797,60 @@
     
-// If there is no right branch, or we already visited it, we can %22visit%22 this node%0A
+    nextNode = traversalStack.peek().getKey();%0A%0A    
     
@@ -1908,19 +1908,20 @@
 h() 
-=
+!
 = null 
-%7C%7C 
+&& !
 trav
@@ -1950,26 +1950,16 @@
 alue())%0A
-        %7B%0A
         
@@ -1966,74 +1966,17 @@
     
-return traversalStack.pop().getKey().getPayload();%0A        %7Delse%7B%0A
+%7B%0A       
     
@@ -1984,61 +1984,71 @@
     
-   
 // Go 
-to the leftmost branch on the right subtree%0A
+right next since we haven't visited the right branch%0A    
     
@@ -2097,32 +2097,36 @@
 e);%0A            
+   
+ 
 nextNode = trave
@@ -2185,61 +2185,340 @@
     
-moveLeftmost();%0A
+    traversalStack.push(new KeyValuePair%3C%3E(nextNode, false));%0A%0A                // If the node we're scheduled to visit next isn't a leaf, find the next leaf%0A                spider();%0A            %7D
 %0A      
+  %7D%0A
       
-return next();%0A        %7D
+  else%0A        %7B%0A            // Nothing left, we're done%0A            nextNode = null;%0A        %7D%0A%0A        return result;
 %0A   

Fix Postorder