package edu.utoledo.nlowe.CustomDataTypes.Iterator;

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

/**
 * An iterator that traverses a tree in pre-order
 */
public class PreorderBinaryTreeIterator<K extends Comparable<K>, V> extends BinaryTreeIterator<K, V>
{
    protected final CustomStack<BinaryTreeNode<K, V>> traversalStack;

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

    @Override
    public boolean hasNext()
    {
        return nextNode != null && traversalStack.size() > 0;
    }

    @Override
    public KeyValuePair<K, V> next()
    {
        // "Visit" this node
        KeyValuePair<K, V> payload = nextNode.getPayload();
        traversalStack.push(nextNode);

        if(nextNode.getLeftBranch() != null)
        {
            // Go left next, if we can
            nextNode = nextNode.getLeftBranch();
        }
        else if(nextNode.getRightBranch() != null)
        {
            // go right next, if we can
            nextNode = nextNode.getRightBranch();
        }
        else
        {
            do
            {
                // Try to go up and right. If we can't we're done iterating
                nextNode = traversalStack.pop().getRightBranch();
            }while (traversalStack.size() > 0 && nextNode == null);
        }

        return payload;
    }
}

@@ -374,16 +374,148 @@
 K, V%3E%0A%7B%0A
+    /**%0A     * The traversal stack%0A     *%0A     * The value is %3Ccode%3Etrue%3C/code%3E when a node's right branch has been visited%0A     */%0A
     prot
@@ -538,16 +538,29 @@
 omStack%3C
+KeyValuePair%3C
 BinaryTr
@@ -571,16 +571,26 @@
 de%3CK, V%3E
+, Boolean%3E
 %3E traver
@@ -746,120 +746,64 @@
     
-%7D%0A%0A
     
-@Override%0A    public boolean hasNext()%0A    %7B%0A        return nextNode != null && traversalStack.size() %3E 0
+traversalStack.push(new KeyValuePair%3C%3E(head, false))
 ;%0A  
@@ -803,24 +803,26 @@
 e));%0A    %7D%0A%0A
+%0A%0A
     @Overrid
@@ -958,47 +958,8 @@
 d();
-%0A        traversalStack.push(nextNode);
 %0A%0A  
@@ -1030,31 +1030,34 @@
  // 
-Go left next, if we can
+Visit the left branch next
 %0A   
@@ -1094,32 +1094,102 @@
 etLeftBranch();%0A
+            traversalStack.push(new KeyValuePair%3C%3E(nextNode, false));%0A
         %7D%0A      
@@ -1262,32 +1262,35 @@
  // 
-go right next, if we can
+visit the right branch next
 %0A   
@@ -1348,137 +1348,665 @@
     
-%7D%0A        else%0A        %7B%0A            do%0A            %7B%0A                // Try to go up and right. If we can't we're done iterating
+    traversalStack.peek().setValue(true);%0A            traversalStack.push(new KeyValuePair%3C%3E(nextNode, false));%0A        %7D%0A        else%0A        %7B%0A            // go Up and find a node that we haven't visted the right branch of%0A            do%0A            %7B%0A                nextNode = traversalStack.pop().getKey();%0A            %7Dwhile(%0A                traversalStack.size() %3E 0 &&%0A                (%0A                        traversalStack.peek().getKey().getRightBranch() == null %7C%7C%0A                        traversalStack.peek().getValue()%0A                )%0A            );%0A%0A            if(traversalStack.size() %3E 0)%0A            %7B%0A                // Go right next
 %0A   
@@ -2041,26 +2041,36 @@
 ersalStack.p
-op
+eek().getKey
 ().getRightB
@@ -2094,44 +2094,214 @@
     
-%7Dwhile (traversalStack.size() %3E 0 &&
+    traversalStack.peek().setValue(true);%0A                traversalStack.push(new KeyValuePair%3C%3E(nextNode, false));%0A            %7D%0A            else%0A            %7B%0A                // We're done%0A               
  nex
@@ -2311,16 +2311,28 @@
 de =
-=
  null
-)
 ;
+%0A            %7D
 %0A   

Fix Preorder