package collections;

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

/**
 * This class provides a flattening iterator over a Collection<?>.
 * i.e. In its constructor, the class takes in a Collection<?> object
 * which may nest either a Collection<?> object or an object of type T.
 * Also, it is expected that the nested Collection<?> objects will not
 * reference their container Collection<?> objects as this will lead
 * to a loop. But they can nest other Collection<?> objects. The class
 * then iterates through elements in the given Collection<?> object,
 * returning the values in the leaves of the nested structure one-by-one
 * upon each call to next().
 *
 *
 * Example: This deep iterator can be used to iterate over a vector that
 *          either contains a vector of integers, or just plain integers,
 *          or both. Lets assume that the Collection<?> passed has the
 *          following structure:
 *
 *                           [int_a, vector_1, int_d, vector_2, int_h]
 *                                     /                 \
 *                                    /                   \
 *                               [int_b, int_c]        [int_e, vector_3]
 *                                                                /
 *                                                               /
 *                                                         [int_f, int_g]
 *
 *          The iterator returns the leaves in order viz.: int_a, int_b,
 *          int_c, int_d, int_e, int_f, int_g, int_h.
 */

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 Stack<Iterator<?>> stack = new Stack<Iterator<?>>();

	public DeepIterator(Collection<?> 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()) {
			T toReturn = nextItem;
			nextItem = null;
			return toReturn;
		}

		throw new NoSuchElementException();
	}

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

@@ -207,19 +207,16 @@
 tion%3C?%3E.
-%0A *
  i.e. In
@@ -219,16 +219,19 @@
 . In its
+%0A *
  constru
@@ -277,19 +277,16 @@
 %3E object
-%0A *
  which m
@@ -299,16 +299,19 @@
 t either
+%0A *
  a Colle
@@ -349,19 +349,16 @@
  type T.
-%0A *
  Also, i
@@ -375,24 +375,27 @@
 ted that the
+%0A *
  nested Coll
@@ -420,19 +420,16 @@
 will not
-%0A *
  referen
@@ -452,32 +452,35 @@
 er Collection%3C?%3E
+%0A *
  objects as this
@@ -489,19 +489,16 @@
 ill lead
-%0A *
  to a lo
@@ -530,32 +530,35 @@
 er Collection%3C?%3E
+%0A *
  objects. The cl
@@ -560,19 +560,16 @@
 he class
-%0A *
  then it
@@ -622,16 +622,19 @@
 n%3C?%3E
+%0A *
  object,
 %0A * 
@@ -629,19 +629,16 @@
  object,
-%0A *
  returni
@@ -731,19 +731,21 @@
 xt().%0A *
+ 
 %0A *
+ 
 %0A * Exam
@@ -813,27 +813,18 @@
 that
-%0A *         
  either
+%0A *
  con
@@ -874,28 +874,16 @@
 ntegers,
-%0A *         
  or both
@@ -895,16 +895,19 @@
 s assume
+%0A *
  that th
@@ -936,28 +936,16 @@
  has the
-%0A *         
  followi
@@ -964,37 +964,12 @@
 :%0A *
+ 
 %0A *
-                          
  %5Bin
@@ -1010,160 +1010,16 @@
 t_h%5D
-%0A *                                     /                 %5C%0A *                                    /                   %5C%0A *                              
+ / %5C / %5C
  %5Bin
@@ -1033,23 +1033,16 @@
 t_c%5D
-       
  %5Bint_e,
  vec
@@ -1037,16 +1037,19 @@
  %5Bint_e,
+%0A *
  vector_
@@ -1054,202 +1054,12 @@
 r_3%5D
-%0A *                                                                /%0A *                                                               /%0A *                                                        
+ / /
  %5Bin
@@ -1072,28 +1072,20 @@
 nt_g%5D%0A *
+ 
 %0A *
-         
  The ite
@@ -1141,20 +1141,8 @@
 t_b,
-%0A *         
  int
@@ -1151,16 +1151,19 @@
 , int_d,
+%0A *
  int_e, 
@@ -1359,16 +1359,22 @@
 private 
+final 
 Stack%3CIt
@@ -1468,16 +1468,131 @@
 tion) %7B%0A
+%09%09if (collection == null) %7B%0A%09%09%09throw new NullPointerException(%0A%09%09%09%09%09%22Can't iterate over a null collection.%22);%0A%09%09%7D%0A%0A
 %09%09stack.

Fix deep iterator.