import java.util.ArrayList;
import java.util.List;
import java.util.UUID;
import java.util.function.Function;

/**
 * Implementiert den abstrakten Datentypen Binärer Suchbaum zur Speicherung von
 * Elementen, deren Klassen das Comparable-Interface implementieren. Der binäre
 * Suchbaum enthält einen Zeiger auf den Wurzelknoten.
 *
 * @param <E>
 *          Der Typ des zu speichernden Elements.
 */
public class BinTree<E extends Comparable<E>> {

  public static class EmptyTreeException extends RuntimeException {
    public EmptyTreeException() {
    }
  }

  /**
   * Jeder Knoten Node enthält das zu speichernde Element element sowie Zeiger
   * parent, left und right auf den Elternknoten, den linken Kindknoten und den
   * rechten Kindknoten. Falls ein Knoten keine Eltern oder keine Kinder hat, so
   * zeigen die entsprechenden Zeiger auf null.
   */
  public class Node implements Comparable<E> {
    E element;
    Node left;
    Node right;
    Node parent;

    public Node(E e) {
      this.element = e;
    }

    @Override
    public int compareTo(E o) {
      return this.element.compareTo(o);
    }

    public void setLeft(Node child) {
      this.left = child;
      if (child != null) {
        child.parent = this;
      }
    }

    public void setRight(Node child) {
      this.right = child;
      if (child != null) {
        child.parent = this;
      }
    }

    @Override
    public String toString() {
      return String.valueOf(this.element);
    }
  }

  // Die Wurzel des binären Suchbaums
  private Node root;

  public BinTree() {
  }

  /**
   * Gibt das Maximum im binären Suchbaum zurück.
   *
   * @return das Maximum oder eine EmptyTreeException, wenn der Suchbaum leer
   *         ist
   * @throws EmptyTreeException
   */
  public E maximum() throws EmptyTreeException {
    if (this.root == null) {
      throw new EmptyTreeException();
    }
    return maximum(this.root).element;
  }

  private Node maximum(Node node) {
    if (node.right != null) {
      return maximum(node.right);
    }
    return node;
  }

  /**
   * Überprüft, ob das Element 'element' im binären Suchbaum enthalten ist.
   *
   * @param element
   *          das gesuchte Element
   * @return Gibt genau dann true zurück, wenn das gesuchte Element im Suchbaum
   *         gefunden wurde.
   */
  public boolean contains(E element) {
    // TODO: Code hier einfügen

    return false;
  }

  /**
   * Fügt das Element 'element' in den binären Suchbaum ein, falls es nicht
   * bereits enthalten ist.
   *
   * @param element
   *          das einzufügende Element
   * @return Gibt genau dann true zurück, wenn das Element eingefügt wurde.
   */
  public boolean insert(E element) {
    // TODO: Code hier einfügen

    return false;
  }

  /**
   * Gibt den symmetrischen Nachfolger des Knotens 'node' zurück. Der
   * symmetrische Nachfolger ist der Knoten mit dem kleinsten Element im rechten
   * Teilbaum des Knotens 'node'. Falls der rechte Teilbaum des Knotens 'node'
   * leer ist, so soll eine EmptyTreeException geworfen werden.
   *
   * @param node
   *          der Knoten für den der symmetrische Nachfolger gesucht wird
   * @return Liefert den symmetrischen Nachfolger bzw. falls der rechte Teilbaum
   *         des Knotens node leer ist, wird eine EmptyTree-Exception geworfen.
   *
   * @throws EmptyTreeException
   */
  public Node successor(Node node) throws EmptyTreeException {
    // TODO: Code hier einfügen

    return null;
  }

  /**
   * Löscht den Knoten mit dem Element 'element' aus dem binären Suchbaum.
   * Beim Löschen soll die Symmetrischer-Nachfolger-Methode angewendet werden,
   * d.h., falls der Knoten mit dem Element 'element' zwei Kinder hat, so wird
   * er durch seinen symmetischen Nachfolger ersetzt.
   *
   * @param element
   *          das zu löschende Element
   * @return Die Methode soll genau dann true zurückgeben, wenn ein Knoten mit
   *         dem Element 'element' entfernt wurde
   */
  public boolean delete(E element) {
    // TODO: Code hier einfügen

    return false;
  }

  /**
   * Führt eine In-Order-Traversierung des binären Suchbaums durch und wendet
   * dabei auf jedes Element den Lambda-Ausdruck 'lambda' an. Bei einer
   * In-Order- Traversierung wird beginnend bei der Wurzel zuerst der linke
   * Teilbaum durchlaufen, dann der aktuelle Knoten besucht und schließlich der
   * rechte Teilbaum durchlaufen. Auf diese Weise werden alle Knoten des Baums
   * in einer eindeutigen Reihenfolge besucht. Die Methode wendet den
   * Lambda-Ausdruck 'lambda' in der Reihenfolge auf die Elemente des Baums an,
   * in der ihre Knoten besucht werden. Die Ergebnisse werden als Liste
   * zurückgegeben.
   *
   * @param lambda
   *          Der Lambda-Ausdruck lambda wird auf jedes Element des Baums
   *          angewandt.
   * @return Die Ergebnisse werden als Liste zurückgegeben.
   */
  public <T> List<T> inorder(Function<E, T> lambda) {
    // TODO: Code hier einfügen

    return new ArrayList<>();
  }

  // ///////////
  // Hilfsmethoden zum Testen der Funktionalität
  // ///////////

  protected boolean checkBinTree() {
    return checkBinTree(this.root);
  }

  protected boolean checkBinTree(Node n) {
    if (n != null) {
      if (n.left != null) {
        if (n.element.compareTo(n.left.element) < 0 || n.left.parent != n) {
          return false;
        }
      } else if (n.right != null) {
        if (n.element.compareTo(n.right.element) >= 0 || n.right.parent != n) {
          return false;
        }
      }
    }
    return true;
  }

  public static void main(String argv[]) throws EmptyTreeException {

    BinTree<Integer> intTree = new BinTree<>();

    for (int i = 0; i < 10; i++) {
      int element = (int) (Math.pow(-1, i) * i);
      System.out.println("Insert: " + element);
      if (!intTree.insert(element)) {
        System.out.println("\tFehler: Element " + element
            + " konnte nicht eingefügt werden.");
      }

      if (!intTree.checkBinTree()) {
        System.out.println("\tFehler: Kein binärer Suchbaum.");
      }
    }

    for (int i = 0; i < 10; i++) {
      int element = (int) (Math.pow(-1, i) * i);
      System.out.println("Search: " + element);

      boolean found = intTree.contains(element);
      if (!found) {
        System.out.println("\tFehler: Element " + element
            + " wurde nicht gefunden.");
      }
    }

    boolean found = intTree.contains(20);
    if (found) {
      System.out
          .println("Fehler: Element gefunden, sollte aber nicht vorhanden sein");
    }

    try {
      System.out.println("Maximum: " + intTree.maximum());
    } catch (EmptyTreeException e) {
      System.out.println("\tFehler: Baum ist leer");
    }

    System.out.println("Inorder traversierung: "
        + intTree.inorder(p -> p).toString());
    System.out.println("Binärdarstellung: "
        + intTree.inorder(p -> Integer.toBinaryString(p + 10)).toString());

    if (intTree.root != null) {
      int duplicate = intTree.root.element;
      System.out.println("Insert: " + duplicate);
      if (intTree.insert(duplicate)) {
        System.out.println("\tFehler: Duplikat " + duplicate
            + " wurde eingefügt.");
      }

      if (!intTree.checkBinTree()) {
        System.out.println("\tFehler: Kein binärer Suchbaum.");
      }
    }

    for (int i = 0; i < 10; i++) {
      int element = (int) (Math.pow(-1, i) * i);
      System.out.println("Delete: " + element);
      if (!intTree.delete(element)) {
        System.out.println("\tFehler: Element " + element
            + " konnte nicht gelöscht werden.");
      }
      if (!intTree.checkBinTree()) {
        System.out.println("\tFehler: Kein binärer Suchbaum.");
      }
      System.out.println("\tInorder-traversierung: "
          + intTree.inorder(p -> p).toString());

      found = intTree.contains(element);
      if (found) {
        System.out
            .println("\tFehler: Element gefunden, sollte aber nicht vorhanden sein");
      }
    }

    BinTree<String> stringTree = new BinTree<>();
    List<String> allStrings = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
      String element = UUID.randomUUID().toString().substring(0, 8);
      System.out.println("Insert: " + element);
      if (!stringTree.insert(element)) {
        System.out.println("\tFehler: Element " + element
            + " konnte nicht eingefügt werden.");
      }

      allStrings.add(element);

      if (!stringTree.checkBinTree()) {
        System.out.println("\tFehler: Kein binärer Suchbaum.");
      }
    }

    for (int i = 0; i < 10; i++) {
      String element = allStrings.get(i);
      System.out.println("Delete: " + element);
      if (!stringTree.delete(element)) {
        System.out.println("\tFehler: Element " + element
            + " konnte nicht gelöscht werden.");
      }
      if (!stringTree.checkBinTree()) {
        System.out.println("\tFehler: Kein binärer Suchbaum.");
      }
      System.out.println("\tInorder-traversierung: "
          + stringTree.inorder(p -> p.toLowerCase()).toString());

      found = stringTree.contains(element);
      if (found) {
        System.out
            .println("\tFehler: String gefunden, der nicht mehr vorhanden sein sollte.");
      }
    }

    System.out.println("Fertig.");
  }
}