// PuuEsim.java SJ

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

public class PuuEsim {

	public static void main(String[] args) {

		Tree<Integer> puu = exampleTree();

		System.out.println("Esijärjestyksessä:");
		preorderPrint(puu);

		System.out.println("Tasoittain:");
		printByLevel(puu);

		System.out.println("Polut:");
		for (int i = 1; i < 16; i++) {
            //LinkedList<TreeNode> P = searchPath(puu, new Integer(i));
            LinkedList<TreeNode> P = searchPath2(puu, new Integer(i));
            if (P == null)
                System.out.println("Ei polkua solmuun " + i);
            else {
                System.out.print("Polku solmuun " + i + " : ");
                for (TreeNode n : P)
                    System.out.print(n.getElement() + " ");
                System.out.println();
            }
		}

		
	} // main()


	// rakentaa pienen esijärjestetyn yleisen puun
	public static Tree<Integer> exampleTree() {
		Tree<Integer> puu = new Tree<Integer>();

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

		/* rakennetaan tällainen puu:

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

		// juuri
		n = new TreeNode<Integer>(1);
		puu.setRoot(n);

		// juuren vasemmanpuoleisin lapsi
		m  = new TreeNode<Integer>(2);
		n.setLeftChild(m);

		// juuren muut lapset
		for (int i = 6 ; i <= 14 ; i+=4) {
			l = new TreeNode<Integer>(i);
			m.setRightSibling(l);
			m = l;
		}

		// 2:n lapset
		m = puu.getRoot().getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(3));
		m.getLeftChild().setRightSibling(new TreeNode<Integer>(5));

		// 6:n lapsi
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(8));

		// 10:n lapsi
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(11));
		// 10:n lapsenlapsi
		m = m.getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(12));

		// 14:n lapset
		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 puu;

	} // exampleTree()


	// Tulostus esijärjestyksessä rekursiivisesti
	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()


	// Tulostus tasoittain
	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()


	// Haku järjestämättömästä puusta
	// Hakee syvyyssuunnassa koko puun kunnes löytää annetun alkion
	// Palauttaa polun ko. solmuun listana, tai null jollei
	// solmua löydy
    // Käyttää apurakenteena pinoa (listaa)
	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();

			// katsotaan josko onnistaisi
			if (n.getElement().equals(x))
				break;

			// mennään vasemmalle alas jos päästään
			else if (n.getLeftChild() != null)
				L.add(n.getLeftChild());

			// muuten mennään oikealle, tai ylös kunnes päästään oikealle
			else {
				while ((! L.isEmpty()) &&
					   (L.getLast().getRightSibling() == null))
					L.removeLast();
				// jos löytyi solmu jonka oikea veli on olemassa
				// korvataan listan viimeinen ko. solmulla
				if (! L.isEmpty())
					L.addLast(L.removeLast().getRightSibling());
			} // else

		} // while !L.isEmpty

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

		return L;

	} // searchPath()

	// Haku järjestämättömästä puusta
    // rekursiivinen versio
	// Palauttaa polun ko. solmuun listana, tai null jollei
	// solmua löydy
	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)  // tyhjä solmu, ei polkua täällä
            return null;

        else if (n.getElement().equals(x)) {    // löytyi, polun pää
            LinkedList<TreeNode> L = new LinkedList<TreeNode>();
            L.add(n);
            return L;

        } else {
            LinkedList<TreeNode> L = null;
            TreeNode c = n.getLeftChild();  // lasten läpikäynti
            while (c != null) {             
                L = searchPath2(c, x);
                if (L != null) {    // löytyi alempaa, lisätään n polkuun
                    L.addFirst(n);
                    return L;
                }
                c = c.getRightSibling();
            }
            return null; // ei löytynyt
        }
        
    }   // searchPath2


} // class PuuEsim