import java.util.*;

public class PrefixTreeBreadthFirstIterator implements Iterator<Character> {
	//Data
	Vector<LinkedList<Character>> levels;	//Vector of levels
	Iterator<Character> it;
	int level;

	//Constructor
	public PrefixTreeBreadthFirstIterator(PrefixTree tree) {
		levels = new Vector<LinkedList<Character>>();
		breadthFirstTraversal(tree);
		reset();
	}

	//Private method
 	private void breadthFirstTraversal(PrefixTree tree) {
		LinkedList<PrefixTree> currentLevel = new LinkedList<PrefixTree>();
		if(!tree.isEmpty()) currentLevel.addLast(tree);
		while(!currentLevel.isEmpty()) {
			LinkedList<Character> data = new LinkedList<Character>();
  			LinkedList<PrefixTree> nextLevel = new LinkedList<PrefixTree>();
  			Iterator<PrefixTree> it = currentLevel.iterator();
  			while(it.hasNext()) {
				PrefixTree t = it.next();
				data.addLast(t.character());
				PrefixTree[] child = t.child();
				for(int i = 0; i < child.length; i++)
					if(t.child[i] != null)
						nextLevel.addLast(t.child[i]);
   			}
   			levels.add(data);
   			level++;
       		currentLevel = nextLevel;	
    	}
 	}

	//Methods
	public int numberOfLevels() { return levels.size(); }
	public LinkedList<Character> getData(int level) { return levels.get(level); }

	//Iterator methods
	public boolean hasNext() {
		if(it.hasNext()) return true;
		level++;
		if(level < levels.size()) {
			it = levels.get(level).iterator();
			return true;
		}
		return false;
 	}
	public Character next() {
		if(!hasNext()) throw new NoSuchElementException();
		return it.next();
	}
	public void remove() { throw new UnsupportedOperationException(); }
	public void reset() { level = 0; it = levels.get(0).iterator(); }
}