/**
 * AlgoDat SS00, Aufgabe 53
 * Testklasse fuer LinkedBinaryTree
 * 
 * @author Christian Semrau
 * <a href="mailto:gsemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */
class ChS_Aufg53 extends LinkedBinaryTree{

    // Isses nicht seltsam? Da sollen wir einen Suchbaum schreiben,
    // der Elemente vom Typ Object enthaelt, und auf einmal sollen
    // wir ganze Zahlen (int) einfuegen?! Schlimmer noch: Wie ermittelt
    // man die natuerliche Reihenfolge beliebiger Objekte, wie es in
    // Aufgabe 52 erforderlich ist?
    // Eine Loesung ist die Verwendung des Interfaces Comparable,
    // das seit JDK 1.2 existiert und es ermoeglicht, unbekannte
    // Objekte zu vergleichen, sofern sie nur dieses Interface
    // implementieren. Statt also Object-Variablen zu speichern,
    // speichern wir Comparable-Variablen.

    // Unter JDK 1.2 implementiert Integer das Comparable-Interface,
    // in vorigen Versionen natuerlich nicht, da das Interface nicht
    // existierte. Leider hab ich in meiner IDE nur das JDK 1.1.6,
    // daher musste ich meine eigene Mantelklasse basteln, die
    // Comparable implementiert. Wer das JDK 1.2 verwenden kann,
    // der kann ruhig diese innere Klasse entfernen, dann wird wieder
    // die normale java.lang.Integer verwendet.

    static class Integer implements Comparable{
        public int value;
        public Integer(int v){
            value = v;
        }
        // Vergleicht this mit obj, das Ergebnis ist kleiner als 0,
        // wenn this kleiner ist als obj, es ist groesser als 0,
        // wenn this groesser ist als obj, und gleich 0,
        // wenn this gleich obj ist
        public int compareTo(Object obj){
            // Setzt voraus, dass obj vom Typ Integer ist
            return value-((Integer)obj).value;
        }
        // Vergleicht zwei Objekte auf Gleichheit, wird von meinen 
        // Klassen nicht genutzt
        public boolean equals(Object obj){
            return (obj!=null) && (obj instanceof Integer)
            && (value==((Integer)obj).value);
        }
        // fuer Ausgabe der Durchlaufungmethoden
        public String toString(){
            return ""+value;
        }
    }
    
    // hier gehts nun endlich los
    // --------------------------

public static void main(String[] args) {
    LinkedBinaryTree tree;

    tree = new LinkedBinaryTree();
    System.out.println("Aufbau mit insert");
    perInsert(tree);
    ausgabe(tree);
    System.out.println();

    tree = new LinkedBinaryTree();
    // Dieses \" ist ein Steuercode, mit dem man ein " ausgeben kann,
    // mit einem einfachen " wird ja die Zeichenkette geschlossen,
    // genauso kann man mit \\ einen einfachen \ ausgeben.
    System.out.println("Aufbau \"zu Fuss\"");
    zuFuss(tree);
    ausgabe(tree);
}

static void ausgabe(LinkedBinaryTree tree){
    // Ausgabe ueber die Durchlaufmethoden
    System.out.println("Preorder:  "+tree.traversePreorder());
    System.out.println("Inorder:   "+tree.traverseInorder());
    System.out.println("Postorder: "+tree.traversePostorder());
    System.out.println("Levelorder:"+tree.traverseLevelorder());
    System.out.println();

    // Ausgabe ueber die Iteratoren
    System.out.print(  "PreIter:   ");
    for(Iterator it = tree.iteratorPreorder(); it.hasNext();)
        System.out.print(it.next()+" ");
    System.out.println();
    System.out.print(  "InIter:    ");
    for(Iterator it = tree.iteratorInorder(); it.hasNext();)
        System.out.print(it.next()+" ");
    System.out.println();
    System.out.print(  "PostIter:  ");
    for(Iterator it = tree.iteratorPostorder(); it.hasNext();)
        System.out.print(it.next()+" ");
    System.out.println();
    System.out.print(  "LevelIter: ");
    for(Iterator it = tree.iteratorLevelorder(); it.hasNext();)
        System.out.print(it.next()+" ");
    System.out.println();
} // ausgabe()

static public void perInsert(LinkedBinaryTree tree) {

    // Dies ist die Reihenfolge, in der die Knoten eingefuegt werden
    // muessen, um den Baum aus Aufgabe 54 zu erhalten.

    tree.insert(new Integer(5));
    tree.insert(new Integer(3));
    tree.insert(new Integer(2));
    tree.insert(new Integer(4));
    tree.insert(new Integer(7));
    tree.insert(new Integer(8));
}

static public void zuFuss(LinkedBinaryTree tree) {
    TreeNode le, ri;

    // der Baum wird von unten aufgebaut
    // wenn der Baum umfangreicher wird, braucht man u.U. noch eine
    // weitere Hilfsvariable
    le = new TreeNode(new Integer(2), null, null);
    ri = new TreeNode(new Integer(4), null, null);
    le = new TreeNode(new Integer(3), le, ri);
    ri = new TreeNode(new Integer(8), null, null);
    ri = new TreeNode(new Integer(7), null, ri);
    tree.root = new TreeNode(new Integer(5), le, ri);
}

} // ChS_Aufg53