/*
 * @(#)SegmentTreePostorderIterator.java  1.0  2010-12-25
 *
 * Copyright (c) 2000-2010 Werner Randelshofer, Immensee, Switzerland.
 * All rights reserved.
 *
 * You may not use, copy or modify this file, except in compliance with the
 * license agreement you entered into with Werner Randelshofer.
 * For details see accompanying license terms.
 */
package ch.randelshofer.segmenttree;

import java.util.Hashtable;
import java.util.Stack;
/**
 * Implementation of segment tree postorder iterator.
 */
public class SegmentTreePostorderIterator implements SegmentTreeIterator {
	private Hashtable<SegmentNode,Boolean> visited = null;
	private Stack<SegmentNode> s = null;
	
	/**
	 * Creates the iterator
	 * @param t - segment tree on which to iterate
	 * @return iterator
	 */
    public static SegmentTreePostorderIterator IteratorInitialize(SegmentTree t) {
		if (t.getRoot()==null) {
			System.err.println("Tree not initialized");
			return null;
		}
		return new SegmentTreePostorderIterator(t.getRoot());
	}
    /**
	 * Creates iterator which will start from specific node
	 * @param n start node
	 * @return iterator
	 */
	public static SegmentTreePostorderIterator IteratorInitialize(SegmentNode n) {
		if (n ==null) {
			System.err.println("Tree not initialized");
			return null;

		}
		return new SegmentTreePostorderIterator(n); 
	}
	
	public SegmentTreePostorderIterator(SegmentNode start) {
		this.s = new Stack<SegmentNode>();
		this.visited = new Hashtable<SegmentNode, Boolean>();

		s.push(start);
		
	}
	
	/**
	 * Returns true if unvisited node exists
	 */
	
	public boolean hasNext() {
		return !s.isEmpty();
	}

	/**
	 * Next tree node pointed by iterator
	 * @return next tree node
	 */
	public SegmentNode next() {
		if (s.isEmpty()) return null;
		SegmentNode res = null;
		while (!s.isEmpty()) {
			SegmentNode t = s.peek();
			if (visited.containsKey(t)) {
				//visit t
				res = t;
				s.pop();
				break;
			} else {
				visited.put(t, true);
				if (t.rightSon() != null ) {
					s.push(t.rightSon());
					
				}
				if (t.leftSon()  != null ) {
					s.push(t.leftSon());
				}
			}
		}
		return res;
	}

}
