package javacodebook.collections.tree;

import java.util.*;

/**
 *  Ein Baum besteht aus vielen Knoten, die jeweils einen Elternknoten haben und
 *  mehrere Kindknoten haben können. Es gibt genau einen Wurzelknoten, von dem
 *  alle Kindknoten abgehen.
 *  Die Klasse Node repräsentiert einen solchen Knoten. Das Programm, dass den
 *  Baum verwendet, kann ausgehend vom Wurzelknoten den gesamten Baum erreichen.
 */
public class Node {

    //Das eigentliche Objekt mit der Information
    private Object nodeObject;
    //Der Elternknoten
    private Node parent;
    //Die Liste der Kindknoten
    private ArrayList children = new ArrayList();

    /** Erzeugt einen neuen Knoten mit dem angegebenen Objekt als Inhalt. */
    public Node(Object nodeObject) {
        this.nodeObject = nodeObject;
    }

    /** Gibt das Informations-Objekt dieses Knotens zurück */
    public Object getNodeObject() {
        return nodeObject;
    }

    /** Gibt diesem Knoten ein anderes Informations-Objekt */
    public void setNodeObject(Object nodeObject) {
        this.nodeObject = nodeObject;
    }

    /** Gibt den Elternknoten zurück */
    public Node getParent() {
        return parent;
    }

    /** Setzt den Elternknoten */
    public void setParent(Node parent) {
        this.parent = parent;
    }

    /**
     * Fügt einen Kindknoten hinzu. Beim Kindknoten wird der Elternknoten
     * gesetzt.
     */
    public void addChild(Node childNode) {
        children.add(childNode);
        childNode.setParent(this);
    }

    /** Liste aller Kinder dieses Knotens */
    public Node[] getChildren() {
        Node[] childArray = new Node[children.size()];
        children.toArray(childArray);
        return childArray;
    }

    /** Ermittelt die Anzahl der Kindknoten */
    public int getChildCount() {
        return children.size();
    }

    /** Ermöglicht den Zugriff auf Kindknoten über den Index */
    public Node getChildAt(int index) {
        if(index < 0 || index > children.size())
            throw new ArrayIndexOutOfBoundsException("Zu wenig Kindknoten");
        return (Node)children.get(index);
    }

    /** Entfernt einen Kindknoten */
    public boolean removeChild(Node child) {
        return children.remove(child);
    }

    /** Entfernt diesen Knoten inkl. aller seiner Kindknoten aus dem Baum */
    public boolean remove() {
        return parent.removeChild(this);
    }

    /**
     * Der Pfad eines Knotens enthält alle Knoten bis zum Wurzelknoten. Damit
     * lässt sich eine genaue Positionsbestimmung innerhalb der Baumhierarchie
     * durchführen. Es wird ein Array zurückgegeben, in dem das erste Element
     * der aktuelle Knoten und das letzte Elemente der Wurzelknoten ist.
     */
    public Node[] getPath() {
        Node current = this;
        LinkedList list = new LinkedList();
        while(current.getParent() != null) {
            list.addLast(current);
            current = current.getParent();
        }
        Node[] path = new Node[list.size()];
        list.toArray(path);
        return path;
    }

    /** Hilfsmethode zur Ausgabe der Knotenposition */
    public void printPath() {
        Node[] path = getPath();
        for(int i = path.length-1; i >= 0; i--) {
            for(int j = 1; j < path.length - i; j++)
                System.out.print("  ");
            System.out.println(path[i].getNodeObject());
        }
    }

    /**
     * Ermittelt die Hierarchieebene des Knotens, ausgehend vom Wurzelknoten,
     * der sich auf Ebene 0 befindet.
     */
    public int getLevel() {
        return getPath().length;
    }

    /** Ermittelt ausgehend von einem beliebigen Knoten den Wurzelknoten */
    public Node getRoot() {
        Node node = this;
        while(node.getParent() != null)
            node = node.getParent();
        return node;
    }

    /** Sucht den Knoten zu einem Objekt im Baum, ausgehend von dem angegebenen
     *  Knoten abwärts.
     *  Wird das Objekt nicht im Baum gefunden, so wird null zurückgegeben.
     */
    public static Node findNode(Node startNode, Object searchObject) {
        //Container für das Suchergebnis. Es wird ein Node-Array der Länge 1
        //verwendet, da nur der erste gefundene Knoten zurückgegeben werden soll.
        Node[] resultNode = new Node[1];
        //Die Suche wird immer beim Wurzelknoten begonnen
        findNode(startNode, searchObject, resultNode);
        //Wenn der Knoten in der privaten findNode()-Methode gefunden wurde,
        //ist resultNode jetzt nicht mehr null
        return resultNode[0];
    }

    /** Rekursive Suche im Baum. Ausgehend vom Wurzelknoten wird so lange
     *  gesucht, bis der Knoten gefunden wird, der das gesuchte Objekt enthält,
     *  oder bis alle Knoten einmal untersucht wurden.
     *  Wird das Objekt in einem Knoten gefunden, so wird eine Referenz auf
     *  diesen Knoten im Array resultNode gespeichert (Ein Objekt würde nicht
     *  ausreichen, da die Objektreferenz geändert würde und die obenstehende
     *  findNode()-Methode dass nicht merken kann).
     */
    private static void findNode(Node node, Object searchObject, Node[] resultNode) {
        if(node.getNodeObject().equals(searchObject)) {
            resultNode[0] = node;
            return;
        }
        else {
            Node[] children = node.getChildren();
            for(int i = 0; i < children.length; i++)
                findNode(children[i], searchObject, resultNode);
        }
    }
}

--- Neue Klasse ---

package javacodebook.collections.tree;

/**
 * Ein Beispiel für die Anwendung der Baumstruktur.
 */
public class TreeExample {

    public static void main(String[] args) {

        //Baum erzeugen und mit Katalogdaten füllen. Zuerst wird ein
        //Wurzelknoten erzeugt, an den dann beliebig viele Knoten angefügt
        //werden können.
        Node root = new Node("Kategorien");
        fillTree(root);
        printTree(root);
        //Suchen eines Objekts im Baum mit der Methode findNode(). Hier wird
        //auch der TreePath gezeigt, der über die Methode getPath() ausgelesen
        //werden kann.
        System.out.println();
        Node x = root.findNode(root, "TFT Monitor");
        System.out.println("Suche nach TFT Monitor liefert folgenden Knoten");
        x.printPath();

    }

    private static void fillTree(Node root) {
        //Produkt-Kategorie erzeugen und an den Wurzelknoten anfügen
        Node category = new Node("Hardware");
        root.addChild(category);
        //Produktgruppe erzeugen und an die Produktkategorie anfügen
        Node group = new Node("Mainboards");
        category.addChild(group);
        //Produkt erzeugen und an die Produktgruppe anfügen
        Node product = new Node("Sockel 2341 ABC");
        group.addChild(product);
        product = new Node("Sockel 33");
        group.addChild(product);
        product = new Node("Slot UX");
        group.addChild(product);
        group = new Node("Monitore");

        //Neue Kategorie erzeugen und ... s.o.
        category.addChild(group);
        product = new Node("17\" Monitor");
        group.addChild(product);
        product = new Node("19\" Monitor");
        group.addChild(product);
        product = new Node("TFT Monitor");
        group.addChild(product);
        category = new Node("Software");
        root.addChild(category);
        group = new Node("Betriebssysteme");
        category.addChild(group);
        product = new Node("Fenster 96");
        group.addChild(product);
        product = new Node("Fenster 99");
        group.addChild(product);
        product = new Node("Linux");
        group.addChild(product);
    }

    /** Ausgabe des Baums in einer Rekursion */
    private static void printTree(Node node) {
        //Für alle Kinder des aktuellen Knotens überprüfen, ob sie auch Kinder
        //haben, und für diese die Methode ebenfalls aufrufen
        Node[] children = node.getChildren();
        for(int i = 0; i < children.length; i++) {
            //Einrücken von Elemente je nach Level
            for(int j = 1; j < children[i].getLevel(); j++)
                System.out.print("  ");
            //Aktuellen Kindknoten ausgeben
            System.out.println(children[i].getNodeObject());
            //Kinder des aktuellen Kindknotens überprüfen
            if(children[i].getChildCount() > 0)
                printTree(children[i]);
        }
    }

}