package iterator.exprtwo;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Set;
import java.util.HashSet;
import enumeration.Op;

public interface Expr {
	public int evaluate();
	public Iterator<Object> preorderIterator();
	public Iterator<Object> postorderIterator();
	public Iterator<Object> breadthIterator();
}

abstract class AbsExpr implements Expr {
	public abstract int evaluate();
	public Iterator<Object> preorderIterator() {
		PreorderIterator i = new PreorderIterator();
		i.addNode(this);
		return i;
	}
	public Iterator<Object> postorderIterator() {
		PostorderIterator i = new PostorderIterator();
		i.addNode(this);
		return i;
	}
	public Iterator<Object> breadthIterator() {
		BreadthIterator i = new BreadthIterator();
		i.addNode(this);
		return i;
	}
	abstract Object acceptPreOrder(PreorderIterator i);
	abstract Object acceptPostOrder(PostorderIterator i);
	abstract Object acceptBreadth(BreadthIterator i);
}

class Const extends AbsExpr {
	private final int v;
	public Const(int v) {
		this.v = v;
	}
	public int evaluate() {
		return v;
	}
	Object acceptPreOrder(PreorderIterator i) {
		return v;
	}
	Object acceptPostOrder(PostorderIterator i) {
		i.markVisited(this);
		return v;
	}
	Object acceptBreadth(BreadthIterator i) {
		i.markVisited(this);
		return v;
	}
}

class BinOp extends AbsExpr {
	private final AbsExpr l;
	private final AbsExpr r;
	private final Op op;
	public BinOp(AbsExpr l, Op op, AbsExpr r) {
		if ((l == null) || (op == null) || (r == null)) {
			throw new IllegalArgumentException();
		}
		this.op = op;
		this.l = l;
		this.r = r;
	}
	public int evaluate() {
		return op.eval(l.evaluate(), r.evaluate());
	}
	Object acceptPreOrder(PreorderIterator i) {
		i.addNode(r);
		i.addNode(l);
		return op;
	}
	Object acceptPostOrder(PostorderIterator i) {
		i.markVisited(this);
		if (i.visited(r)) {
			return op;
		} else {
			i.addNode(this);
			if (i.visited(l))
				return r.acceptPostOrder(i);
			else
				return l.acceptPostOrder(i);
		}
	}
	Object acceptBreadth(BreadthIterator i) {
		if (i.visited(this)) {
			i.addNode(l);
			i.addNode(r);
			return i.next();
		} else {
			i.markVisited(this);
			i.addNode(this);
			return op;
		}
	}
}

class PreorderIterator implements Iterator<Object> {
	private Stack<AbsExpr> s = new Stack<AbsExpr>();
	public boolean hasNext() {
		return ! s.empty();
	}
	void addNode(AbsExpr e) {
		s.push(e);
	}
	public Object next() {
		if (hasNext())
			return (s.pop()).acceptPreOrder(this);
		throw new NoSuchElementException();
	}
	public void remove() {
		throw new UnsupportedOperationException();
	}
}

class PostorderIterator implements Iterator<Object> {
	private Set<AbsExpr> v = new HashSet<AbsExpr>();
	private Stack<AbsExpr> s = new Stack<AbsExpr>();
	public boolean hasNext() {
		return ! s.empty();
	}
	boolean visited(AbsExpr e) {
		return v.contains(e);
	}
	void markVisited(AbsExpr e) {
		v.add(e);
	}
	void addNode(AbsExpr e) {
		s.push(e);
	}
	public Object next() {
		if (hasNext())
			return (s.pop()).acceptPostOrder(this);
		throw new NoSuchElementException();
	}
	public void remove() {
		throw new UnsupportedOperationException();
	}
}

class BreadthIterator implements Iterator<Object> {
	private Set<AbsExpr> v = new HashSet<AbsExpr>();
	private List<AbsExpr> l = new ArrayList<AbsExpr>();
	public boolean hasNext() {
		return ! l.isEmpty();
	}
	boolean visited(AbsExpr e) {
		return v.contains(e);
	}
	void markVisited(AbsExpr e) {
		v.add(e);
	}
	void addNode(AbsExpr e) {
		l.add(e);
	}
	public Object next() {
		if (hasNext()) {
			AbsExpr e = l.get(0);
			l.remove(0);
			return e.acceptBreadth(this);
		}
		throw new NoSuchElementException();
	}
	public void remove() {
		throw new UnsupportedOperationException();
	}
}