/**
 * 
 */
package dataStructures;

/**
 * @author Ricardo Gaspar Nr. 35277
 * @author Hugo Ant—nio Nr. 34334 Turno P2 Docente Vasco Amaral
 */
public class BSTBreadthFirstIterator<K, V> implements Iterator<Entry<K, V>> {

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	
	protected BSTNode<K, V> root;
	protected Queue<BSTNode<K, V>> q;

	/**
	 * 
	 */
	public BSTBreadthFirstIterator(BSTNode<K, V> root) {
		this.root = root;
		rewind();
	}

	@Override
	public boolean hasNext() {
		return !q.isEmpty();
	}

	@Override
	public Entry<K, V> next() throws NoSuchElementException {
		if (!hasNext())
			throw new NoSuchElementException();
		BSTNode<K, V> node = q.dequeue();
		enqueueNode(node.getLeft());
		enqueueNode(node.getRight());

		return node.getEntry();
	}

	@Override
	public void rewind() {
		q = new QueueInList<BSTNode<K, V>>();
		q.enqueue(root);

	}

	/**
	 * Adiciona um dado n— ˆ fila.
	 * 
	 * @param node
	 *            N— a adicionar.
	 */
	private void enqueueNode(BSTNode<K, V> node) {
		if (node != null)
			q.enqueue(node);
	}
}