/**
 * 
 */
package dataStructures1112;

/**
 * @author Daniel
 *
 */
public class BSTInOrderIterator<K,V> implements Iterator<Entry<K,V>> {

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	
	
    private Stack<BSTNode<K,V>> st;
	
	private BSTNode<K,V> root;
	
	
	public BSTInOrderIterator(BSTNode<K,V> node){
		this.st = new StackInList<BSTNode<K,V>>();
		this.root = node;
		this.rewind();
	}

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

	@Override
	public Entry<K,V> next() throws NoSuchElementException {
		
		if(!this.hasNext())
			throw new NoSuchElementException();
		BSTNode<K,V> next = st.pop();
		this.pushPathToMinimum(next.getRight());
		return next.getEntry();
	}

	@Override
	public void rewind() {
	    this.pushPathToMinimum(root);
	}
	
	private void pushPathToMinimum(BSTNode<K,V> node) {
		  
		  while(node != null)
		  {
		   st.push(node);
		   node = node.getLeft();
		  }
		  
		 }

}