// TreeExample.java SJ

import fi.joensuu.cs.tra.*;
import java.util.LinkedList;

public class TreeExample {

	public static void main(String[] args) {

		Tree<Integer> tree = exampleTree();

		System.out.println("In pre-order:");
		preorderPrint(tree);

		System.out.println("In by-level order:");
		printByLevel(tree);

		System.out.println("Paths:");
		for (int i = 1; i < 16; i++) {
            //LinkedList<TreeNode> P = searchPath(tree, new Integer(i));
            LinkedList<TreeNode> P = searchPath2(tree, new Integer(i));
            if (P == null)
                System.out.println("No path to node " + i);
            else {
                System.out.print("Path to node " + i + " : ");
                for (TreeNode n : P)
                    System.out.print(n.getElement() + " ");
                System.out.println();
            }
		}

		
	} // main()


	// builds a small pre-ordered tree
	public static Tree<Integer> exampleTree() {
		Tree<Integer> tree = new Tree<Integer>();

		TreeNode<Integer> n, m, l = null, k;

		/* result tree:

			1
		  //\\
		 /|  |\
		/ |  | \
	   2  6 10  14_____________
	  / \ |  |  |  \  \  \  \  \
	  3 5 8 11  15 16 17 18 19 20
			 |
			12
		*/

		// root
		n = new TreeNode<Integer>(1);
		tree.setRoot(n);

		// left child of root
		m  = new TreeNode<Integer>(2);
		n.setLeftChild(m);

		// other children of root
		for (int i = 6 ; i <= 14 ; i+=4) {
			l = new TreeNode<Integer>(i);
			m.setRightSibling(l);
			m = l;
		}

		// children of 2
		m = tree.getRoot().getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(3));
		m.getLeftChild().setRightSibling(new TreeNode<Integer>(5));

		// child of 6
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(8));

		// child of 10
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(11));
		// grandchild of 10
		m = m.getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(12));

		// children of 14
		m = new TreeNode<Integer>(15);
		l.setLeftChild(m);
		for (int i = 16 ; i <= 20 ; i++) {
			l = new TreeNode<Integer>(i);
			m.setRightSibling(l);
			m = l;
		}

		System.out.println("        1");
		System.out.println("      //\\\\");
		System.out.println("     /|  |\\");
		System.out.println("    / |  | \\");
		System.out.println("   2  6 10  14_____________");
		System.out.println("  / \\ |  |  |  \\  \\  \\  \\  \\");
		System.out.println("  3 5 8 11  15 16 17 18 19 20");
		System.out.println("         |");
		System.out.println("        12");
		System.out.println();

		return tree;

	} // exampleTree()


    // recursive traversal (print) in pre-order
	public static void preorderPrint(Tree T) {
		if (T.getRoot() != null)
			preorderPrintBranch(T.getRoot());
		System.out.println();
	} // preorderPrint()


	public static void preorderPrintBranch(TreeNode n) {
		System.out.print(n.getElement() + " ");
		TreeNode child = n.getLeftChild();
		while (child != null) {
			preorderPrintBranch(child);
			child = child.getRightSibling();
		}
	} // preorderPrintBranch()


	// traversal (print) by level
	public static void printByLevel(Tree T) {
		LinkedQueue<TreeNode> Q = new LinkedQueue<TreeNode>();
		if (T.getRoot() != null)
			Q.offer(T.getRoot());

		while (! Q.isEmpty()) {
			TreeNode n = Q.poll();
			System.out.print(n.getElement() + " ");
			n = n.getLeftChild();
			while (n != null) {
				Q.offer(n);
				n = n.getRightSibling();
			}
		}
		System.out.println();
	} // printByLevel()


    // search from non-ordered tree without recursion
    // depth first search until finds the given element
	// Haku järjestämättömästä treesta
    // Returns path to given node as a list, or null if node not found
    // Uses stack (list)
	public static LinkedList<TreeNode> searchPath(Tree T, Object x) {
		LinkedList<TreeNode> L = new LinkedList<TreeNode>();
		TreeNode n;
		if (T.getRoot() != null)
			L.add(T.getRoot());

		while (! L.isEmpty()) {
			n = L.getLast();

			// is it here?
			if (n.getElement().equals(x))
				break;

			// go left down if possible
			else if (n.getLeftChild() != null)
				L.add(n.getLeftChild());

            // otherwise go right,  or up until we can go rigth
			else {
				while ((! L.isEmpty()) &&
					   (L.getLast().getRightSibling() == null))
					L.removeLast();
                // if we found a node which has right sibling in the list
                // replace last of the list with tis right sibling
				if (! L.isEmpty())
					L.addLast(L.removeLast().getRightSibling());
			} // else

		} // while !L.isEmpty

		if (L.isEmpty())
			L = null;

		return L;

	} // searchPath()

    // search from non-ordered tree with recursion
    // Returns path to given node as a list, or null if node not found
	public static LinkedList<TreeNode> searchPath2(Tree T, Object x) {
        return searchPath2(T.getRoot(), x);
    }

    public static LinkedList<TreeNode> searchPath2(TreeNode n, Object x) {
        if (n == null)  // null found, no node here
            return null;

        else if (n.getElement().equals(x)) {    // found, end of path
            LinkedList<TreeNode> L = new LinkedList<TreeNode>();
            L.add(n);
            return L;

        } else {
            LinkedList<TreeNode> L = null;
            TreeNode c = n.getLeftChild();  // iteration of children
            while (c != null) {             
                L = searchPath2(c, x);
                if (L != null) {    // found from below, add n to list
                    L.addFirst(n);
                    return L;
                }
                c = c.getRightSibling();
            }
            return null; // not found
        }
        
    }   // searchPath2


} // class TreeExample