package com.freetymekiyan.algorithms.level.medium;

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

/**
 * Given a nested list of integers, implement an iterator to flatten it.
 * <p>
 * Each element is either an integer, or a list -- whose elements may also be integers or other lists.
 * <p>
 * Example 1:
 * Given the list [[1,1],2,[1,1]],
 * <p>
 * By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:
 * [1,1,2,1,1].
 * <p>
 * Example 2:
 * Given the list [1,[4,[6]]],
 * <p>
 * By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
 * <p>
 * Tags: Stack, Design
 * Similar Problems: (M) Flatten 2D Vector, (M) Zigzag Iterator
 */
public class FlattenNestedListIterator {

    /**
     * This is the interface that allows for creating nested lists.
     * You should not implement it, or speculate about its implementation
     */
    public interface NestedInteger {

        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        public boolean isInteger();

        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        public Integer getInteger();

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        public List<NestedInteger> getList();
    }

    public class NestedIterator implements Iterator<Integer> {

        private Deque<NestedInteger> stack = new ArrayDeque<>();

        public NestedIterator(List<NestedInteger> nestedList) {
            flattenList(nestedList);
        }

        @Override
        public Integer next() {
            return hasNext() ? stack.pop().getInteger() : null;
        }

        @Override
        public boolean hasNext() {
            while (!stack.isEmpty()) {
                if (stack.peek().isInteger()) {
                    return true;
                }
                flattenList(stack.pop().getList());
            }
            return false;
        }

        private void flattenList(List<NestedInteger> list) {
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
    }

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
}

@@ -708,16 +708,59 @@
 %0A * %3Cp%3E%0A
+ * Company Tags: Google, Facebook, Twitter%0A
  * Tags:
@@ -837,16 +837,33 @@
 Iterator
+, (M) Mini Parser
 %0A */%0Apub
@@ -1641,24 +1641,617 @@
 t();%0A    %7D%0A%0A
+    /**%0A     * Stack.%0A     * Flatten by pushing a list of nested lists onto stack in reverse order.%0A     * So that we can get them in original order.%0A     * For hasNext(), first check if stack is empty.%0A     * If it is empty, return false.%0A     * If it is not, check whether the top is an integer.%0A     * If it is an integer, return true.%0A     * If it is a list, pop the list and add all elements to stack from back to front.%0A     * %3Cp%3E%0A     * If the nested integer wraps an empty list, hasNext() should return false.%0A     * So we must unwrap nested integer in hasNext() to make sure.%0A     */%0A
     public c
@@ -2348,29 +2348,8 @@
 tack
- = new ArrayDeque%3C%3E()
 ;%0A%0A 
@@ -2407,24 +2407,64 @@
 stedList) %7B%0A
+            stack = new ArrayDeque%3C%3E();%0A
             
@@ -2470,20 +2470,16 @@
  flatten
-List
 (nestedL
@@ -2707,24 +2707,80 @@
 isEmpty()) %7B
+ // Must put in hasNext(), otherwise cannot pass %22%5B%5B%5D%5D%22.
 %0A           
@@ -2890,20 +2890,16 @@
  flatten
-List
 (stack.p
@@ -2958,32 +2958,193 @@
 lse;%0A        %7D%0A%0A
+        /**%0A         * Push list of nested integers to stack in REVERSE order.%0A         * So that when popping out of stack, it's the correct order.%0A         */%0A
         private 
@@ -3155,20 +3155,16 @@
  flatten
-List
 (List%3CNe

update flatten nested list iterator