package com.ankurdave.part;

import scala.Tuple2;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArtIterator implements Iterator<Tuple2<byte[], Object>> {
    private ArrayList<Node> elemStack = new ArrayList<Node>();
    private ArrayList<Integer> idxStack = new ArrayList<Integer>();
    private int pos = 0;
    private boolean _hasNext;

    public ArtIterator(Node root) {
        if (root != null) {
            elemStack.add(root);
            idxStack.add(0);
            maybeAdvance();
        }
    }

    @Override public boolean hasNext() {
        return _hasNext;
    }

    @Override public Tuple2<byte[], Object> next() {
        if (_hasNext) {
            Leaf leaf = (Leaf)elemStack.get(pos);
            byte[] key = leaf.key;
            Object value = leaf.value;

            // Mark the leaf as consumed
            idxStack.set(pos, 1);

            maybeAdvance();
            return new Tuple2<byte[], Object>(key, value);
        } else {
            throw new NoSuchElementException("end of iterator");
        }
    }

    @Override public void remove() {
        throw new UnsupportedOperationException();
    }

    // Postcondition: if _hasNext is true, the top of the stack must contain a leaf
    private void maybeAdvance() {
        // Pop exhausted nodes
        while (pos >= 0 && elemStack.get(pos).exhausted(idxStack.get(pos))) {
            pos -= 1;
            if (pos >= 0) {
                // Move on by advancing the exhausted node's parent
                idxStack.set(pos, idxStack.get(pos) + 1);
            }
        }
        _hasNext = (pos >= 0);

        if (_hasNext) {
            // Descend to the next leaf node element
            while (true) {
                if (elemStack.get(pos) instanceof Leaf) {
                    // Done - reached the next element
                    break;
                } else {
                    // Advance to the next child of this node
                    ArtNode cur = (ArtNode)elemStack.get(pos);
                    idxStack.set(pos, cur.nextChildAtOrAfter(idxStack.get(pos)));
                    Node child = cur.childAt(idxStack.get(pos));

                    // Push it onto the stack
                    pos += 1;
                    while (elemStack.size() <= pos) elemStack.add(null);
                    elemStack.set(pos, child);
                    while (idxStack.size() <= pos) idxStack.add(-1);
                    idxStack.set(pos, 0);
                }
            }
        }
    }
}

@@ -33,20 +33,28 @@
 ort 
-scala.Tuple2
+java.util.ArrayDeque
 ;%0Aim
@@ -68,25 +68,21 @@
 va.util.
-ArrayList
+Deque
 ;%0Aimport
@@ -144,23 +144,38 @@
 ption;%0A%0A
-public 
+import scala.Tuple2;%0A%0A
 class Ar
@@ -242,25 +242,21 @@
 private 
-ArrayList
+Deque
 %3CNode%3E e
@@ -275,20 +275,21 @@
 ew Array
-List
+Deque
 %3CNode%3E()
@@ -302,25 +302,21 @@
 private 
-ArrayList
+Deque
 %3CInteger
@@ -341,12 +341,13 @@
 rray
-List
+Deque
 %3CInt
@@ -358,63 +358,8 @@
 %3E();
-%0A    private int pos = 0;%0A    private boolean _hasNext;
 %0A%0A  
@@ -442,19 +442,20 @@
 emStack.
-add
+push
 (root);%0A
@@ -475,19 +475,20 @@
 dxStack.
-add
+push
 (0);%0A   
@@ -585,24 +585,36 @@
  return 
-_hasNext
+!elemStack.isEmpty()
 ;%0A    %7D%0A
@@ -675,32 +675,33 @@
         if (
-_
 hasNext
+()
 ) %7B%0A        
@@ -724,39 +724,37 @@
 (Leaf)elemStack.
-get(pos
+peek(
 );%0A            b
@@ -877,24 +877,37 @@
 dxStack.
-set(pos,
+push(idxStack.pop() +
  1);%0A%0A  
@@ -1214,24 +1214,29 @@
  if 
-_hasNext is true
+the stack is nonempty
 , th
@@ -1354,24 +1354,36 @@
  while (
-pos %3E= 0
+!elemStack.isEmpty()
  && elem
@@ -1388,23 +1388,21 @@
 emStack.
-get(pos
+peek(
 ).exhaus
@@ -1414,23 +1414,21 @@
 dxStack.
-get(pos
+peek(
 ))) %7B%0A  
@@ -1441,42 +1441,90 @@
     
-pos -= 1;%0A            if (pos %3E= 0
+elemStack.pop();%0A            idxStack.pop();%0A%0A            if (!elemStack.isEmpty()
 ) %7B%0A
@@ -1616,25 +1616,21 @@
 dxStack.
-set(pos, 
+push(
 idxStack
@@ -1630,23 +1630,20 @@
 dxStack.
-get(pos
+pop(
 ) + 1);%0A
@@ -1670,60 +1670,41 @@
   %7D%0A
-        _hasNext = (pos %3E= 0);%0A%0A        if (_hasNext
+%0A        if (!elemStack.isEmpty()
 ) %7B%0A
@@ -1813,23 +1813,21 @@
 emStack.
-get(pos
+peek(
 ) instan
@@ -2061,23 +2061,21 @@
 emStack.
-get(pos
+peek(
 );%0A     
@@ -2098,25 +2098,21 @@
 dxStack.
-set(pos, 
+push(
 cur.next
@@ -2135,23 +2135,20 @@
 dxStack.
-get(pos
+pop(
 )));%0A   
@@ -2202,15 +2202,13 @@
 ack.
-get(pos
+peek(
 ));%0A
@@ -2278,130 +2278,23 @@
     
-pos += 1;%0A                    while (elemStack.size() %3C= pos) elemStack.add(null);%0A                    elemStack.set(pos, 
+elemStack.push(
 chil
@@ -2317,23 +2317,16 @@
         
-while (
 idxStack
@@ -2330,79 +2330,13 @@
 ack.
-size() %3C= pos) idxStack.add(-1);%0A                    idxStack.set(pos, 
+push(
 0);%0A

Use Deque instead of custom stacks