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);
        }
    }
}