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

		throw new NoSuchElementException();
	}

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

@@ -207,16 +207,19 @@
 tion%3C?%3E.
+%0A *
  i.e. In
@@ -222,19 +222,16 @@
 . In its
-%0A *
  constru
@@ -277,16 +277,19 @@
 %3E object
+%0A *
  which m
@@ -302,19 +302,16 @@
 t either
-%0A *
  a Colle
@@ -349,16 +349,19 @@
  type T.
+%0A *
  Also, i
@@ -382,19 +382,16 @@
 that the
-%0A *
  nested 
@@ -420,16 +420,19 @@
 will not
+%0A *
  referen
@@ -455,35 +455,32 @@
 er Collection%3C?%3E
-%0A *
  objects as this
@@ -489,16 +489,19 @@
 ill lead
+%0A *
  to a lo
@@ -537,27 +537,24 @@
 ollection%3C?%3E
-%0A *
  objects. Th
@@ -560,16 +560,19 @@
 he class
+%0A *
  then it
@@ -625,19 +625,16 @@
 n%3C?%3E
-%0A *
  object,
  ret
@@ -629,16 +629,19 @@
  object,
+%0A *
  returni
@@ -734,21 +734,19 @@
 xt().%0A *
- 
 %0A *
- 
 %0A * Exam
@@ -814,18 +814,27 @@
 that
+%0A *         
  either
-%0A *
  con
@@ -880,24 +880,36 @@
 in integers,
+%0A *         
  or both. Le
@@ -917,19 +917,16 @@
 s assume
-%0A *
  that th
@@ -955,16 +955,28 @@
  has the
+%0A *         
  followi
@@ -991,20 +991,45 @@
 ture:%0A *
- 
 %0A *
+                          
  %5Bint_a,
@@ -1066,16 +1066,160 @@
 t_h%5D
- / %5C / %5C
+%0A *                                     /                 %5C%0A *                                    /                   %5C%0A *                              
  %5Bin
@@ -1233,16 +1233,23 @@
 t_c%5D
+       
  %5Bint_e,
 %0A * 
@@ -1244,19 +1244,16 @@
  %5Bint_e,
-%0A *
  vector_
@@ -1258,12 +1258,202 @@
 r_3%5D
- / /
+%0A *                                                                /%0A *                                                               /%0A *                                                        
  %5Bin
@@ -1470,12 +1470,20 @@
 %5D%0A *
- 
 %0A *
+         
  The
@@ -1535,24 +1535,36 @@
 nt_a, int_b,
+%0A *         
  int_c, int_
@@ -1565,19 +1565,16 @@
 , int_d,
-%0A *
  int_e, 
@@ -1941,22 +1941,16 @@
 ception(
-%0A%09%09%09%09%09
 %22Can't i
@@ -1987,17 +1987,16 @@
 %22);%0A%09%09%7D%0A
-%0A
 %09%09stack.

Fix comment