import java.util.Iterator;

public abstract class Forest<T> implements Iterable<T> {
	public abstract int size();
	public boolean isEmpty() {
		return size() == 0;
	}
	public Iterator<T> inOrderIterator() {
		return new InOrderIterator(this);
	}
	public Iterator<T> preOrderIterator() {
		return new PreOrderIterator(this);
	}
	public Iterator<T> postOrderIterator() {
		return new PostOrderIterator(this);
	}
	public Iterator<T> breadthFirstIterator() {
		return new BreadthFirstIterator(this);
	}
		
	public abstract ForestCursor<T> root();
	public abstract ForestCursor<T> toElderSon(ForestCursor<T> c);
	public abstract ForestCursor<T> toJunior(ForestCursor<T> c);
	public abstract T getElement(ForestCursor<T> c);
	
	private void toString(StringBuffer buf, String indent, ForestCursor<T> c) {
		if (c == null) {
			return;
		}
		buf.append(indent);
		buf.append(getElement(c).toString());
		buf.append(System.getProperty("line.separator"));
		toString(buf, indent + "  ", toElderSon(c));
		for(ForestCursor<T> f = toJunior(c); f != null; f = toJunior(f)) {
			toString(buf, indent, f);
		}
	}
	
	@Override
	public String toString() {
		StringBuffer buf = new StringBuffer();
		toString(buf, "", root());
		return buf.toString();
	}
	
	@Override
	public Iterator<T> iterator() {
		return preOrderIterator();
	}

	private abstract class ForestIterator implements Iterator<T> {
		protected Iterator<T> ordered_items_;
		
		@Override
		public boolean hasNext() {
			return this.ordered_items_.hasNext();
		}

		@Override
		public T next() {
			return this.ordered_items_.next();
		}

		@Override
		public void remove() {
			this.ordered_items_.remove();
		}
		
	}

	private class InOrderIterator extends ForestIterator {
		public InOrderIterator(Forest<T> tree) {
			final Queue<T> ordered_items = new BufferQueue<T>(tree.size());
			ForestWalk.inOrder(tree, tree.root(), new Operation<T>() {
				@Override
				public void performOn(T item) {
					ordered_items.enqueue(item);
				}
			});
			this.ordered_items_ = ordered_items.iterator();
		}
	}
	private class PreOrderIterator extends ForestIterator {
		public PreOrderIterator(Forest<T> tree) {
			final Queue<T> ordered_items = new BufferQueue<T>(tree.size());
			ForestWalk.preOrder(tree, tree.root(), new Operation<T>() {
				@Override
				public void performOn(T item) {
					ordered_items.enqueue(item);
				}
			});
			this.ordered_items_ = ordered_items.iterator();
		}
	}
	private class PostOrderIterator extends ForestIterator {
		public PostOrderIterator(Forest<T> tree) {
			final Queue<T> ordered_items = new BufferQueue<T>(tree.size());
			ForestWalk.postOrder(tree, tree.root(), new Operation<T>() {
				@Override
				public void performOn(T item) {
					ordered_items.enqueue(item);
				}
			});
			this.ordered_items_ = ordered_items.iterator();
		}
	}
	private class BreadthFirstIterator extends ForestIterator {
		public BreadthFirstIterator(Forest<T> tree) {
			final Queue<T> ordered_items = new BufferQueue<T>(tree.size());
			ForestWalk.breadthFirst(tree, tree.root(), new Operation<T>() {
				@Override
				public void performOn(T item) {
					ordered_items.enqueue(item);
				}
			});
			this.ordered_items_ = ordered_items.iterator();
		}
	}
}