Design a deep iterator

Related: LeetCode 341 - Flatten Nested List Iterator
Design a deep iterator - 包子IT面试培训
Alis: Nested Iterator
Write a deep iterator to iterate through a list of objects or integer which could be another list or integer. For example, this collection contains Integer or another collection. L means it is a collection that contains either integer or another L.

                                     ----> 5

                                     |

               ---- 3 -> 4  -> L  -> 6

              |

1 -> 2 -> L -> 7-> 8

We would expect an iterator to loop through it will print out 1, 2, 3, 4, 5, 6, 7, 8

Key: stack of iterator.
In java, the idiom of iterator is that u always call hasNext before next.
==>So in next(), there is no need to call hasNext(), which just causes worse performance.
https://github.com/kowshik/big-o/blob/master/java/src/collections/DeepIterator.java
public class DeepIterator<T> implements Iterator<T> {
// A reference to the item which will be returned during
// the next call to next().
private T nextItem;
private final Stack<Iterator<?>> stack = new Stack<Iterator<?>>();

public DeepIterator(Collection<?> collection) {
if (collection == null) {
throw new NullPointerException("Can't iterate over a null collection.");
}
stack.push(collection.iterator());
}

@Override
@SuppressWarnings("unchecked")
public boolean hasNext() {
if (nextItem != null) {
return true;
}

while (!stack.isEmpty()) {
Iterator<?> iter = stack.peek();
if (iter.hasNext()) {
Object item = iter.next();
if (item instanceof Collection<?>) {
stack.push(((Collection<?>) item).iterator());
} else {
nextItem = (T) item;
return true;
}
} else {
stack.pop();
}
}

return false;
}

@Override
public T next() {
if (hasNext()) { // change to if(nextItem!=null)
T toReturn = nextItem;
nextItem = null;
return toReturn;
}

throw new NoSuchElementException();
}

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

public class DeepIterator implements Iterator {
    private Stack iteratorStack = new Stack();
    private Integer top = null;

    public DeepIterator(Iterable iterable){
        this.iteratorStack.push(iterable.iterator());
    }

    @Override
    public boolean hasNext() {
        if(this.top != null) return true;

        while(!this.iteratorStack.isEmpty()) {
            Iterator tmpIterator = this.iteratorStack.peek();

            if(tmpIterator.hasNext()){
                Object tmp = tmpIterator.next();
                if(tmp instanceof Integer){
                    this.top = (Integer) tmp;
                    return true;
                } else if(tmp instanceof Iterable){
                    this.iteratorStack.push(((Iterable) tmp).iterator());
                } else {
                    throw new RuntimeException("Unsupported data type. ");
                }
            } else {
                this.iteratorStack.pop();
            }
        }
        return false;
    }

    @Override
    public Integer next() throws NoSuchElementException {
        if(hasNext()){
            Integer tmp = this.top;
            this.top = null;
            return tmp;
        }

        throw new NoSuchElementException();
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("This is not supported right now.");
    }
}

http://dongfeiwww.com/design/pattern/2014/07/23/design-pattern/

    public boolean hasNext() {
       if (itrs.isEmpty()) {
           return false;
       }
       Iterator<Object> curIter = itrs.peek();
       while (curIter.hasNext()) {
           Object nextObj = curIter.next();
           if (obj instanceof ArrayList) {
               if ((ArrayList(obj)).size() == 0) { //
                   continue;
               } else {
                   itrs.push((ArrayList(obj)).iterator()); // not needed to use recrusive
                   return hasNext();
               }
           } else {
               curValue = (Object)nextObj;
               return true;
           }
           
       }
       itrs.pop();
       return hasNext();
    }

http://www.mitbbs.com/article_t/JobHunting/32583985.html
http://buttercola.blogspot.com/2015/11/linkedin-deep-iterator.html

eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6
这个data structure的interface是这样的

public interface Data<T> {
    // Does this Data hold a collection?
    public boolean isCollection();
    // Returns the collection contained by     // this Data, or null if it is a single element
    public Collection<Data<T>> getCollection();
    // Returns the single element contained     //by this Data, or null if it is  collection
    public T getElement();
}

public class DeepIterator implements Iterator<Data> {

    private Stack<Iterator<Data>> stack = new Stack<>();

    private Data top = null;

     

    public DeepIterator(List<Data> input) {

        stack.push(input.iterator());

    }

     

    @Override

    public boolean hasNext() {

        if (this.top != null) {

            return true;

        }

         

        while (!stack.isEmpty()) {

            Iterator<Data> it = stack.peek();

             

            if (it.hasNext()) {

                Data curr = it.next();

                if (!curr.isCollection()) {

                    top = curr.getElement();

                    return true;

                } else {

                    stack.push(curr.getCollection.iterator());

                }

            } else {

                stack.pop();

            }

        }

         

        return false;

    }

     

    @Override

    public Integer next() {

        if (top != null) {

            Integer result = top;

            top = null;

            return result;

        } else {

            return null;

        }

    }

}

第1题：level sum，算是deep iterator的变种。一个多重nested array，例如{a,{b,c 
},{{d},e}}，返回level sum = a + 2 * (b + c) + 3 * d + 2 * e。 
Read full article from Design a deep iterator - 包子IT面试培训