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>
 * Company Tags: Google, Facebook, Twitter
 * Tags: Stack, Design
 * Similar Problems: (M) Flatten 2D Vector, (M) Zigzag Iterator, (M) Mini Parser
 */
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();
    }

    /**
     * Stack.
     * Flatten by pushing a list of nested lists onto stack in reverse order.
     * So that we can get them in original order.
     * For hasNext(), first check if stack is empty.
     * If it is empty, return false.
     * If it is not, check whether the top is an integer.
     * If it is an integer, return true.
     * If it is a list, pop the list and add all elements to stack from back to front.
     * <p>
     * If the nested integer wraps an empty list, hasNext() should return false.
     * So we must unwrap nested integer in hasNext() to make sure.
     */
    public class NestedIterator implements Iterator<Integer> {

        private Deque<NestedInteger> stack;

        public NestedIterator(List<NestedInteger> nestedList) {
            stack = new ArrayDeque<>();
            flatten(nestedList);
        }

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

        @Override
        public boolean hasNext() {
            while (!stack.isEmpty()) { // Must put in hasNext(), otherwise cannot pass "[[]]".
                if (stack.peek().isInteger()) {
                    return true;
                }
                flatten(stack.pop().getList());
            }
            return false;
        }

        /**
         * Push list of nested integers to stack in REVERSE order.
         * So that when popping out of stack, it's the correct order.
         */
        private void flatten(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();
 */
}

@@ -153,16 +153,60 @@
 t;%0A%0A/**%0A
+ * 341. Flatten Nested List Iterator%0A * %3Cp%3E%0A
  * Given
@@ -1722,216 +1722,459 @@
   * 
-Flatt
+Think about the methods.%0A     * Normally hasNext() checks whether we have reached the 
 en
+d
  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 fals
+checking against the collection size.%0A     * But we don't have a size here, we don't know how many nested levels are there.%0A     * We step forward one integer at a time.%0A     * So how about we put the nested integer into a dynamic collection and check whether it's empty or not?%0A     * Then next() only needs to check hasNext() first and return the next valu
 e.%0A 
@@ -2183,343 +2183,593 @@
   * 
-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 sur
+Another common sense is that this kind of recursive calls are normally modelled with Stack. So let's try it.%0A     * %3Cp%3E%0A     * Flatten a nested list by pushing its items onto stack in reverse order.%0A     * So that we can get them in the original order.%0A     * For hasNext(), we must account for the case when the top is a nested list with an empty nested list:%0A     * %7C Since we return one integer at a time, we should make the next integer ready on top of the stack.%0A     * %7C When the top is a list, we must flatten it until the top is an integer to make sure there are more to iterat
 e.%0A 
@@ -2782,24 +2782,31 @@
 %0A    public 
+static 
 class Nested
@@ -3256,166 +3256,64 @@
 ty()
-) %7B // Must put in hasNext(), otherwise cannot pass %22%5B%5B%5D%5D%22.%0A                if (stack.peek().isInteger()) %7B%0A                    return true;%0A                %7D
+ && !stack.peek().isInteger()) %7B // Special case %22%5B%5B%5D%5D%22.
 %0A   
@@ -3390,21 +3390,32 @@
  return 
-false
+!stack.isEmpty()
 ;%0A      
@@ -3942,9 +3942,8 @@
 );%0A */%0A%7D
-%0A

update 341. Flatten Nested List Iterator with detialed thought process and easier code