public abstract class ForestWalk {
	public static <T> void breadthFirst(Forest<T> wood, ForestCursor<T> start, Operation<? super T> op) {
		Queue<ForestCursor<T>> q = new LinkedQueue<ForestCursor<T>>();
		for(ForestCursor<T> root = start; root != null; root = wood.toJunior(root)) {
			q.enqueue(root);
		}
		while (q.size() > 0) {
			ForestCursor<T> current = q.dequeue();
			ForestCursor<T> next = wood.toElderSon(current);
			while (next != null) {
				q.enqueue(next);
				next = wood.toJunior(next);
			}
			op.performOn(wood.getElement(current));
		}
	}
	
	public static <T> void inOrder(Forest<T> wood, ForestCursor<T> start, Operation<? super T> op) {
		if (start != null) {
			inOrder(wood, wood.toElderSon(start), op);
			op.performOn(wood.getElement(start));
			ForestCursor<T> next = wood.toElderSon(start);
			if (next != null) {
				next = wood.toJunior(next);
				while (next != null) {
					inOrder(wood, next, op);
					next = wood.toJunior(next);
				}
			}
			for(ForestCursor<T> edge = wood.toJunior(start); edge != null; edge = wood.toJunior(edge)) {
				inOrder(wood, edge, op);
			}
		}
	}

	public static <T> void preOrder(Forest<T> wood, ForestCursor<T> start, Operation<? super T> op) {
		if (start != null) {
			op.performOn(wood.getElement(start));
			preOrder(wood, wood.toElderSon(start), op);
			preOrder(wood, wood.toJunior(start), op);
		}
	}

	public static <T> void postOrder(Forest<T> wood, ForestCursor<T> start, Operation<? super T> op) {
		if (start != null) {
			postOrder(wood, wood.toElderSon(start), op);
			op.performOn(wood.getElement(start));
			postOrder(wood, wood.toJunior(start), op);
		}
	}
	
	public static void main(String [] args) {
		class ForestPrinter implements Operation<String> {

			@Override
			public void performOn(String item) {
				System.out.print(item + " ");
			}
		}
		Forest<String> t = new LinkedForest<String>(
						           new LinkedForest<String>(
						               new LinkedForest<String>(new LinkedForest<String>(), "2", new LinkedForest<String>("x")),
						               "*", new LinkedForest<String>("3")
						           ),
						           "+",
						           new LinkedForest<String>("root_brother")
							   );
		System.out.println(t.toString());
		ForestPrinter print = new ForestPrinter();
		System.out.print("Breadth-first walk: ");
		breadthFirst(t, t.root(), print);
		System.out.println();
		
		System.out.print("In order walk: ");
		inOrder(t, t.root(), print);
		System.out.println();
		
		System.out.print("Pre-order walk: ");
		preOrder(t, t.root(), print);
		System.out.println();
		
		System.out.print("Post-order walk: ");
		postOrder(t, t.root(), print);
	}

}