import java.util.Iterator;

/**
 * Created on 30.12.2006
 */

/**
 * Dieses Interface beschreibt die Schnittstelle eines AVL-Baums zum Speichern
 * von vergleichbaren Werten. Ein AVL-Baum ist ein binaerer Suchbaum, bei dem
 * die Hoehe der Aeste eines Teilbaumes nich maximal um eins unterscheidet, also
 * jeder Knoten ausgeglichen ist
 * 
 * @author Marc Woerlein (Woerlein@informatik.uni-erlangen.de)
 * 
 * @param <E>
 *            der Typ der zu speichernden Werte. Diese muessen untereinander
 *            vergleichbar sein.
 * 
 */
public interface AVLInterface<E extends Comparable<E>> extends Iterable<E> {

	/**
	 * Diese Klasse stellt einen Knoten im AVLBaum dar.
	 * 
	 * @author Marc Woerlein (Woerlein@informatik.uni-erlangen.de)
	 * 
	 * @param <Typ>
	 *            der im Knoten zu speichernde Typ. Dieser muss fuer einen
	 *            allgemeinen Binaerbaum nicht untereinander Vergleichbar sein.
	 */
	public class Knoten<Typ> {

		/** im Knoten gespeicherter Wert */
		public Typ value;

		/** hoehe des Knotens in Baum */
		public int height;

		/** Elternknoten */
		public Knoten<Typ> parent = null;

		/** linkes Kind */
		public Knoten<Typ> left = null;

		/** rechtes Kind */
		public Knoten<Typ> right = null;

		/**
		 * erzeugt einen Knoten fuer den uebergebenen Wert
		 * 
		 * @param value
		 */
		public Knoten(Typ value) {
			this.value = value;
		}

		/**
		 * trennt den Knoten von seinem Elternknoten ab
		 */
		private void unlink() {
			if (parent != null) {
				if (parent.left == this) {
					parent.left = null;
				} else {
					parent.right = null;
				}
				parent = null;
			}
		}

		/**
		 * fuegt den uebergebenen Knoten als linkes Kind an.
		 * <p>
		 * Dafuer enfernt es den alten Knoten und passt die Hoehe dieses Knotens
		 * an. Elternhoehen werden NICHT aktuallisiert und muessen seperat
		 * angepasst werden!
		 * 
		 * @param left
		 *            der neue Knoten, oder <code>null</code> zum loeschen
		 */
		public void setLeft(Knoten<Typ> left) {
			if (this.left != null) {
				// alten linken Knoten aushaengen
				this.left.parent = null;
				this.left = null;
				// Hoehe anpassen
				height = (right == null ? 0 : right.height + 1);
			}

			if (left != null) {
				// neuen Knoten aus alten Baum aushaengen
				left.unlink();
				// neuen linken Knoten einhaengen
				left.parent = this;
				this.left = left;
				// Hoehe anpassen
				height = (height <= left.height ? left.height + 1 : height);
			}
		}

		/**
		 * fuegt den uebergebenen Knoten als rechtes Kind an.
		 * <p>
		 * Dafuer enfernt es den alten Knoten und passt die Hoehe dieses Knotens
		 * an. Elternhoehen werden NICHT aktuallisiert und muessen seperat
		 * angepasst werden!
		 * 
		 * @param right
		 *            der neue Knoten, oder <code>null</code> zum loeschen
		 */
		public void setRight(Knoten<Typ> right) {
			if (this.right != null) {
				// alten rechten Knoten aushaengen
				this.right.parent = null;
				this.right = null;
				// Hoehe anpassen
				height = (left == null ? 0 : left.height + 1);
			}

			if (right != null) {
				// neuen Knoten aus alten Baum aushaengen
				right.unlink();
				// neuen rechten Knoten einhaengen
				right.parent = this;
				this.right = right;
				// Hoehe anpassen
				height = (height <= right.height ? right.height + 1 : height);
			}
		}

		/**
		 * @return die Balance (linke Hoehe - rechte Hoehe) des Knotens
		 */
		public int balance() {
			final int linkeHoehe = (left == null ? -1 : left.height);
			final int rechteHoehe = (right == null ? -1 : right.height);
			return linkeHoehe - rechteHoehe;
		}

		/**
		 * @return <code>true</code>, wenn die eigenen Hoehe zu der der
		 *         Kinder passt
		 */
		public boolean heightKonsistent() {
			final int linkeHoehe = (left == null ? -1 : left.height);
			final int rechteHoehe = (right == null ? -1 : right.height);
			return height == Math.max(linkeHoehe, rechteHoehe) + 1;
		}

		/**
		 * ueberprueft rekursiv, ob der Teilbaum der an diesem Knoten haengt,
		 * konsistent Aufgebaut ist.
		 * 
		 * @param parent
		 *            der eigentliche Vorgaenger des Knotens
		 * @param checkMore
		 *            sagt, das neben den Verzeigerung auch die Hoehen und
		 *            Balancen ueberprueft werden sollen
		 * @return <code>true</code>, wenn der Teilbaum Konsistent ist
		 */
		public boolean subBaumKonsistent(Knoten<Typ> parent, boolean checkMore) {
			return this.parent == parent
					&& (left == null || left.subBaumKonsistent(this, checkMore))
					&& (right == null || right.subBaumKonsistent(this,
							checkMore))
					&& (!checkMore || (Math.abs(balance()) < 2 && heightKonsistent()));
		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see java.lang.Object#toString()
		 */
		public String toString() {
			return value.toString() + "(" + height + "/" + balance() + ")";
		}
	}

	/**
	 * @return den Wurzelkonten des Baumes, oder <code>null</code> bei einem
	 *         leeren Baum
	 */
	public Knoten<E> getRoot();

	/**
	 * Diese Methode sucht nach dem Knoten, mit dem uebergebenen Wert. Wenn es
	 * keinen Knoten gibt, der den Wert enthaellt, wird der Knoten, an den der
	 * gesuchte Wert angehaengt gehoert, zurueck geliefert.
	 * 
	 * @param value
	 *            der zu suchende/einzufuegende/zuloeschende Wert
	 * @return den Baumknoten, mit dem gesuchten Wert, oder dessen potentiellen
	 *         Vater
	 */
	public Knoten<E> getNode(E value);

	/**
	 * @return Anzahl der im Baum gespeicherten Werte
	 */
	public int size();

	/**
	 * schaut ob der Suchbaum leer ist
	 * 
	 * @return <code>true</code>, wenn der Suchbaum leer ist ansonsten
	 *         <code>false</code>
	 */
	public boolean isEmpty();

	/**
	 * loescht alle Werte aus dem Baum, so das er danach leer ist
	 */
	public void clear();

	/**
	 * schaut nach, ob der uebergebene Wert schon in den Baum eingefuegt wurde
	 * 
	 * @param value
	 *            der zu suchende Wert
	 * @return <code>true</code>, wenn der Wert schon im Baum enthalten ist,
	 *         ansonsten <code>false</code>
	 */
	public boolean contains(E value);

	/**
	 * fuegt einen neuen Wert in den AVL-Baum ein
	 * 
	 * @param value
	 *            der einzufuegende Wert
	 * @return <code>true</code>, wenn der Wert neu eingefuegt wurde und
	 *         <code>false</code>, wenn der Wert schon vorher im Baum war
	 */
	public boolean add(E value);

	/**
	 * entfernt den uebergebenen Wert aus dem AVL-Baum
	 * 
	 * @param value
	 *            der zu loeschende Wert
	 * @return <code>true</code>, wenn der Wert aus dem Baum entfernt wurde
	 *         und <code>false</code>, wenn der Wert vorher nicht im Baum war
	 */
	public boolean remove(E value);

	// NEUE METHODEN

	/**
	 * einfache Rotation der Wurzel x eines Teilbaumes nach rechts
	 * 
	 * @param x
	 * @return die neue Wurzel des Teilbaumes
	 */
	public Knoten<E> rotateRight(Knoten<E> x);

	/**
	 * einfache Rotation der Wurzel x eines Teilbaumes nach links
	 * 
	 * @param x
	 * @return die neue Wurzel des Teilbaumes
	 */
	public Knoten<E> rotateLeft(Knoten<E> x);

	/**
	 * doppelte Rotation der Wurzel x eines Teilbaumes nach rechts
	 * 
	 * @param x
	 * @return die neue Wurzel des Teilbaumes
	 */
	public Knoten<E> doubleRight(Knoten<E> x);

	/**
	 * doppelte Rotation der Wurzel x eines Teilbaumes nach links
	 * 
	 * @param x
	 * @return die neue Wurzel des Teilbaumes
	 */
	public Knoten<E> doubleLeft(Knoten<E> x);

	/**
	 * rebalanciert den Baum ab dem Knoten x nach oben
	 * 
	 * @param x
	 *            der Knoten dessen Kind sich veraendert hat
	 * @param left
	 *            zeigt an ob am linken (<code>true</code>) oder am rechten (<code>false</code>)
	 *            Ast von x eine Veraenderung statt gefunden hat.
	 * @param grown
	 *            sagt, ob der veraenderte Teilbaum vergroessert (<code>true</code>)
	 *            oder verkleinert (<code>false</code>) wurde.
	 */
	public void rebalance(Knoten<E> x, boolean left, boolean grown);

	/**
	 * ermittelt die aktuelle Hoehe des Suchbaumes, also die Laenge des
	 * laengsten Pfades von der Wurzel zu einem Blatt
	 * 
	 * @return die (aktuelle) Hoehe des Baumes, oder -1 beim leeren Baum
	 */
	public int height();

	/**
	 * @return das kleinste gespeicherte Element
	 */
	public E first();

	/**
	 * @return das groesste gespeicherte Element
	 */
	public E last();

	/**
	 * @return einen Iterator der sortiert ueber alle gespeicherten Werte
	 *         iteriert.
	 */
	public Iterator<E> iterator();
}