import java.util.Iterator;
import java.util.*;

public class AVLBaum<E extends Comparable<E>> implements AVLInterface<E> {

	/** die Wurzel des Baumes */
	private Knoten<E> root;

	/** die Anzahl an gespeicherten Elementen */
	private int size;

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#getRoot()
	 */
	public Knoten<E> getRoot() {
		return root;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#getNode(E)
	 */
	public Knoten<E> getNode(E value) {
		// Schleppzeiger zum Speichern des gewuenschten Vorgaengers
		Knoten<E> schlepp = null;
		Knoten<E> node = root;
		while (node != null) {
			// Schleppzeiger weitersetzen
			schlepp = node;
			final int result = node.value.compareTo(value);
			if (result == 0) {
				// gesuchter Knoten gefunden
				return node;
			} else if (result > 0) {
				// auf der linken Seite weiter suchen
				node = node.left;
			} else {
				// auf der rechten Seite weiter suchen
				node = node.right;
			}
		}
		// Knoten nicht gefunden, Schleppzeiger zeigt auf potenziellen
		// Vorgaenger
		return schlepp;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#size()
	 */
	public int size() {
		return size;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#isEmpty()
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#clear()
	 */
	public void clear() {
		root = null;
		size = 0;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#contains(E)
	 */
	public boolean contains(E value) {
		// Wenn der Baum nicht leer und der Wert gueltig ist,
		// muss ueberprueft werden, ob der Wert im Baum gefunden wurde.
		return root != null && value != null
				&& getNode(value).value.compareTo(value) == 0;
	}

	/**
	 * haengt den neuen Knoten an die Stelle des alten Knoten im Baum
	 * 
	 * @param alt
	 * @param neu
	 * @return <code>true</code>, wenn der Knoten links angefuegt wurde
	 */
	private boolean swap(Knoten<E> alt, Knoten<E> neu) {
		// alten Knoten aus dem Baum entfernen
		// Vaterreferenz wird beim Ersetzen zurueckgesetzt
		alt.setLeft(null);
		alt.setRight(null);
		if (alt == root) {
			// Wurzel ersetzen
			root = neu;
			return false;
		} else if (alt.parent.left == alt) {
			// links ersetzen
			alt.parent.setLeft(neu);
			return true;
		} else {
			// rechts ersetzen
			alt.parent.setRight(neu);
			return false;
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#add(E)
	 */
	public boolean add(E value) {
		// pruefen, ob der Wert schon enthalten ist
		if (value == null) {
			return false;
		}
		final Knoten<E> n = getNode(value);
		if (n != null && n.value.compareTo(value) == 0) {
			return false;
		}
		// wenn nicht, an entsprechendem Knoten einfuegen
		final Knoten<E> neu = new Knoten<E>(value);
		if (n == null) {
			// Baum war vorher leer
			root = neu;
		} else if (n.value.compareTo(value) < 0) {
			n.setRight(neu);
			// Ausbalancieren: Teilbaum ist rechts gewachsen
			rebalance(n, false, true);
		} else {
			n.setLeft(neu);
			// Ausbalancieren: Teilbaum ist links gewachsen
			rebalance(n, true, true);
		}
		size++;

		// Q: Baum ist leer oder von der Wurzel ab strukturell konsistent
		// TODO: momentan ohne Balance- und Hoehenpruefung
		assert root == null || root.subBaumKonsistent(null, true);
		return true;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see AVLInterface#remove(E)
	 */
	public boolean remove(E value) {
		// pruefen, ob der Wert schon enthalten ist
		if (value == null) {
			return false;
		}
		final Knoten<E> node = getNode(value);
		if (node == null || node.value.compareTo(value) != 0) {
			return false;
		}

		final Knoten<E> parent = node.parent;
		// wenn ja, loesche diesen
		if (node.left == null) {
			// haenge rechten Ast anstelle des zu loeschenden Knotens
			// funktioniert auch fuer Blaetter
			final boolean left = swap(node, node.right);
			// Ausbalancieren: Teilbaum ist <code>left</code> geschrumpft
			rebalance(parent, left, false);
		} else if (node.right == null) {
			// haenge linken Ast anstelle des zu loeschenden Knotens
			final boolean left = swap(node, node.left);
			// Ausbalancieren: Teilbaum ist <code>left</code> geschrumpft
			rebalance(parent, left, false);
		} else {
			// innerer Knoten mit zwei Aesten
			// suche kleinsten Knoten auf der rechten Seite
			Knoten<E> a = node.right;
			while (a.left != null) {
				a = a.left;
			}
			// ziehe den Wert nach oben
			node.value = a.value;

			final Knoten<E> parenta = a.parent;
			// und loesche den anderen Knoten, der nur einen rechten Ast hat
			final boolean left = swap(a, a.right);
			// Ausbalancieren: Teilbaum a ist <code>left</code> geschrumpft
			rebalance(parenta, left, false);
		}
		size--;

		// Q: Baum ist leer oder von der Wurzel ab strukturell konsistent
		// TODO: momentan ohne Balance- und Hoehenpruefung
		assert root == null || root.subBaumKonsistent(null, true);
		return true;
	}

	public Knoten<E> rotateRight(Knoten<E> x) {

	    if ((x == null) || (x.left == null)) {
		return null;
	    }

	    Knoten<E> save1 = x.left.right;
	    Knoten<E> save2 = x.left;
	    Knoten<E> parent = x.parent;
	    
	    if (parent != null) {
		if (parent.left == x) {
		    x.setLeft(save1);
		    save2.setRight(x);
		    parent.setLeft(save2);
		    return parent.left;
		}
		else {
		    x.setLeft(save1);
		    save2.setRight(x);
		    parent.setRight(save2);
		    return parent.right;
		}
	    }
	    else {
		x.setLeft(save1);
		save2.setRight(x);
		root = save2;
		return root;
	    }
	}

	public Knoten<E> rotateLeft(Knoten<E> x) {
	    
	    if ((x == null) || (x.right == null)) {
		return null;
	    }

	    Knoten<E> save1 = x.right.left;
	    Knoten<E> save2 = x.right;
	    Knoten<E> parent = x.parent;

	    if (parent != null) {
		if (parent.left == x) {
		    x.setRight(save1);
		    save2.setLeft(x);
		    parent.setLeft(save2);
		    return parent.left;
		}
		else {
		    x.setRight(save1);
		    save2.setLeft(x);
		    parent.setRight(save2);
		    return parent.right;
		}
	    }
	    else {
		x.setRight(save1);
		save2.setLeft(x);
		root = save2;
		return root;
	    }
	}

	public Knoten<E> doubleRight(Knoten<E> x) {

	    if ((x == null) || (x.left == null)) {
		return null;
	    }
	    
	    rotateLeft(x.left);
	    return rotateRight(x);
	}

	public Knoten<E> doubleLeft(Knoten<E> x) {

	    if ((x == null) || (x.right == null)) {
		return null;
	    }

	    Knoten<E> save = rotateRight(x.right);
	    return rotateLeft(x);
	}

	public void rebalance(Knoten<E> x, boolean left, boolean grown) {

	    if (x == null) {
		return;
	    }

	    x.height = heightHelp(x);
	    if (Math.abs(x.balance()) <= 1) {
		rebalance(x.parent, false, false);
	    }
	    else {
		if (x.balance() > 1) {
		    if (x.left.balance() < 0) {
			Knoten<E> save = doubleRight(x);
			rebalance(save.parent, false, false);
		    }
		    else {
			Knoten<E> save = rotateRight(x);
			rebalance(save.parent, false, false);
		    }
		}
		else {
		    if (x.right.balance() <= 0) {
			Knoten<E> save = rotateLeft(x);
			rebalance(save.parent, false, false);
		    }
		    else {
			Knoten<E> save = doubleLeft(x);
			rebalance(save.parent, false, false);
		    }
		}
	    }

	}

	public int height() {
	
	    return heightHelp(getRoot());
	}

	private int heightHelp(Knoten<E> wurzel) {

	    int hoehe;
	    int hoeheLinks = -1;
	    int hoeheRechts = -1;

	    if (wurzel == null) {
		return 0;
	    }
	    if (wurzel.left != null) {
		hoeheLinks = heightHelp(wurzel.left);
	    }
	    if (wurzel.right != null) {
		hoeheRechts = heightHelp(wurzel.right);
	    }
	    if (hoeheRechts >= hoeheLinks) {
		hoehe = hoeheRechts + 1;
	    }
	    else {
		hoehe = hoeheLinks + 1;
	    }
	    return hoehe;
	}

	public E first() {

	    Knoten<E> buffer = getRoot();
	    while (buffer.left != null) {
		buffer = buffer.left;
	    }
	    return buffer.value;
	}

	public E last() {

	    Knoten<E> buffer = getRoot();
	    while (buffer.right != null) {
		buffer = buffer.right;
	    }
	    return buffer.value;
	}

	public Iterator<E> iterator() {

	    return new AVLIterator();
	}

	private LinkedList<E> liste(Knoten<E> wurzel, LinkedList<E> list) {

	    if (wurzel != null) {
		liste(wurzel.left, list);
		list.add(wurzel.value);
		liste(wurzel.right, list);
	    }
	    return list;
	}

	private class AVLIterator implements Iterator<E> {

	    Iterator<E> it;
	    LinkedList<E> liste;
	    E letztes;

	    public AVLIterator() {

		liste = new LinkedList<E>();
		it = liste(AVLBaum.this.getRoot(), liste).iterator();
	    }

	    public boolean hasNext() {

		return it.hasNext();
	    }

	    public E next() throws NoSuchElementException {

		if (hasNext()) {
		    letztes = it.next();
		    return letztes;
		}
		else {
		    throw new NoSuchElementException();
		}
	    }

	    public void remove() throws IllegalStateException {

		if (letztes != null) {
		    AVLBaum.this.remove(letztes);
		    letztes = null;
		}
		else {
		    throw new IllegalStateException();
		}
	    }
	}

	public String toString() {

		return this.getClass().getSimpleName() + "(" + size() + ")";
	}

/*	public void toString(Knoten<E> root) {

	    if (root != null) {
		System.out.print("Wert: " + root + " Vater: " + root.parent + " linkes Kind: " + root.left + " rechtes Kind: " + root.right);
		System.out.println();
		toString(root.left);
		toString(root.right);
	    }
	}

	public static void main(String[] args) {

		AVLBaum<Integer> c = new AVLBaum<Integer>();
		for (int i = 1; i <= 13; i++) {
		    c.add(i);
		}
		c.add(0);
		c.remove(9);
		c.remove(11);
		c.toString(c.getRoot());
		c.add("W"); c.add("Y"); c.add("S"); c.add("G"); c.add("U");
		c.doubleRight(c.getNode("Y"));
		c.toString(c.getRoot());
		System.out.println();
		c.rotateRight(c.getNode("W"));
		c.toString(c.getRoot());
		System.out.println();
		c.rotateLeft(c.getNode("S"));
		c.toString(c.getRoot());
	}*/

}