package com.interview.misc;

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Given a nested list of integers, implement an iterator to flatten it.
 * Each element is either an integer, or a list -- whose elements may also be integers or other lists.
 * Example 1:
 * Given the list [[1,1],2,[1,1]],
 * By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
 *
 * https://leetcode.com/problems/flatten-nested-list-iterator/
 */
public class NestedIterator implements Iterator<Integer> {

    private final Deque<NestedInteger> stack;
    private NestedInteger current;
    private final Deque<Integer> positionStack;
    private int position = 0;

    public NestedIterator(List<NestedInteger> nestedList) {
        NestedInteger ni = new NestedIntegerImpl(nestedList);
        current = ni;
        this.stack = new LinkedList<>();
        this.positionStack = new LinkedList<>();
    }

    @Override
    public Integer next() {
        return current.getList().get(position++).getInteger();
    }

    @Override
    public boolean hasNext() {
        if (position < current.getList().size()) {
            NestedInteger i = current.getList().get(position);
            if (i.isInteger()) {
                return true;
            } else {
                stack.offerFirst(current);
                positionStack.offerFirst(position + 1);
                current = i;
                position = 0;
                return hasNext();
            }
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            current = stack.pollFirst();
            position = positionStack.pollFirst();
            return hasNext();
        }
    }
}

class NestedIntegerImpl extends NestedInteger {

    private List<NestedInteger> list;
    NestedIntegerImpl(List<NestedInteger> list) {
        this.list = list;
    }

    @Override
    public boolean isInteger() {
        return false;
    }

    @Override
    public Integer getInteger() {
        return null;
    }

    @Override
    public List<NestedInteger> getList() {
        return list;
    }
}


abstract class NestedInteger {
    abstract boolean isInteger();
    abstract Integer getInteger();
    abstract List<NestedInteger> getList();
}
@@ -129,11 +129,79 @@
 st;%0A
-%0A/*
+import java.util.Stack;%0A%0A/**%0A * Date 04/17/2017%0A * @author Tushar Roy%0A 
 *%0A *
@@ -678,32 +678,26 @@
 %3E %7B%0A
-%0A
     
-private final Deque
+Stack%3CIterator
 %3CNes
@@ -711,129 +711,60 @@
 ger%3E
+%3E
  stack
-;%0A    private NestedInteger current;%0A    private final Deque%3CInteger%3E positionStack;%0A    private int position = 0;%0A
+ = new Stack%3C%3E();%0A    Integer nextVal = null;
 %0A   
@@ -832,178 +832,172 @@
     
-NestedInteger ni = new NestedIntegerImpl(nestedList
+stack.push(nestedList.iterator()
 );%0A    
+%7D%0A%0A
     
-current = ni;%0A        this.stack = new LinkedList%3C%3E();%0A        this.positionStack = new LinkedList%3C%3E
+@Override%0A    public Integer next() %7B%0A        if (!hasNext()) %7B%0A            throw new IllegalArgumentException
 ();%0A    
 %7D%0A%0A 
@@ -996,280 +996,195 @@
     
-%7D%0A%0A
     
-@Override%0A    public Integer next() %7B%0A        return current.getList().get(position++).getInteger();%0A    %7D%0A%0A    @Override%0A    public boolean hasNext() %7B%0A        if (position %3C current.getList().size()) %7B%0A            NestedInteger i = current.getList().get(position)
+%7D%0A        Integer val = nextVal;%0A        nextVal = null;%0A        return val;%0A    %7D%0A%0A    @Override%0A    public boolean hasNext() %7B%0A        if (nextVal != null) %7B%0A            return true
 ;%0A  
@@ -1193,82 +1193,89 @@
     
+%7D%0A
     
-if (i.isInteger()) %7B%0A                return true;%0A            %7D else %7B
+    while (!stack.isEmpty()) %7B%0A            boolean pushedIntoStack = false;
 %0A   
@@ -1287,187 +1287,169 @@
     
-    stack.offerFirst(current);%0A                positionStack.offerFirst(position + 1);%0A                current = i;%0A                position = 0;%0A                return hasNext();
+Iterator%3CNestedInteger%3E itr = stack.peek();%0A            if (itr.hasNext()) %7B%0A                NestedInteger ni = itr.next();%0A                if (ni.isInteger()) %7B
 %0A   
@@ -1457,26 +1457,24 @@
         
-%7D%0A
         
 %7D else %7B
@@ -1469,52 +1469,39 @@
     
-%7D else %7B%0A            if (stack.isEmpty()) %7B%0A
+nextVal = ni.getInteger();%0A    
     
@@ -1515,28 +1515,27 @@
      return 
-fals
+tru
 e;%0A         
@@ -1541,528 +1541,242 @@
     
-%7D%0A
     
-        current = stack.pollFirst();%0A            position = positionStack.pollFirst();%0A            return hasNext();%0A        %7D%0A    %7D%0A%7D%0A%0Aclass NestedIntegerImpl extends NestedInteger %7B%0A%0A    private List%3CNestedInteger%3E list;%0A    NestedIntegerImpl(List%3CNestedInteger%3E list) %7B%0A        this.list = list;
+%7D else %7B%0A                    pushedIntoStack = true;%0A                    stack.push(ni.getList().iterator());%0A                %7D
 %0A    
-%7D%0A%0A
     
-@Override%0A    public boolean isInteger() %7B%0A        return false;
+    %7D%0A            if (!pushedIntoStack) %7B
 %0A    
-%7D%0A%0A
+  
     
-@Override%0A    public Integer getInteger() %7B%0A        return null;%0A
+      stack.pop();%0A        
     %7D%0A
-%0A
     
-@Override%0A    public List%3CNestedInteger%3E getList() %7B
+    %7D
 %0A   
@@ -1787,20 +1787,21 @@
  return 
-list
+false
 ;%0A    %7D%0A
@@ -1807,23 +1807,17 @@
 %0A%7D%0A%0A
-%0Aabstract class
+interface
  Nes
@@ -1833,25 +1833,16 @@
 r %7B%0A    
-abstract 
 boolean 
@@ -1858,25 +1858,16 @@
 ();%0A    
-abstract 
 Integer 
@@ -1888,17 +1888,8 @@
     
-abstract 
 List

update nested integer