/**
 * 
 */
package dataStructures;

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

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

	/**
	 * 
	 */
	public BSTInorderIterator(BSTNode<K, V> root) {

		this.root = root;
		rewind();
	}

	@Override
	public boolean hasNext() {

		return (!path.isEmpty());
	}

	@Override
	public Entry<K, V> next() throws NoSuchElementException {

		if (!hasNext())
			throw new NoSuchElementException();

		BSTNode<K, V> node = path.pop();
		Entry<K, V> entryToReturn = node.getEntry();
		// Se tem filho direito, achar o m’nimo desse filho e empilhar
		if (node.getRight() != null)
			minNode(node.getRight());

		return entryToReturn;
	}

	@Override
	public void rewind() {

		path = new StackInList<BSTNode<K, V>>();
		minNode(root);
	}

	/**
	 * Realiza o percurso atŽ ao n— cuja chave tem o valor m’nimo. Empilha os
	 * n—s por onde vai passando atŽ chegar ao fim.
	 * 
	 * @param node
	 *            N— de partida.
	 * @return N— cujo valor da chave Ž m’nimo.
	 */
	private void minNode(BSTNode<K, V> node) {

		while (node != null) {
			path.push(node);
			node = node.getLeft();
		}
	}
}