/**
 * in dieser (abstrakten) Klasse ist die Einfuegeoperation fuer AVL-Baeume (unvollstaendig) 
 * gemaess dem 12. Aufgabenblatt 'Alogrithmen und Datenstrukturen' implementiert.
 *  
 * @param <K> Typ der gespeicherten Schluesselwerte
 */
public abstract class AbstractAVLTree<K extends Comparable<K>> {
	/** der Wurzelknoten des Baums */
	AVLNode<K> root;
	
	/**
	 * Konstruktor
	 */
	public AbstractAVLTree() {
		root = new AVLNode<K>(null);
	}
	
	/**
	 * fuegt einen Schluessel in den Baum ein (falls dieser noch nicht enthalten war)
	 * 
	 * @param key Schluesselwert der eingefuegt werden soll
	 */
	public void insertKey(K key) {
		recursiveInsert(root, key);
	}
	
	/**
	 * bestimmt die innere Pfadlaenge des Baumss
	 * 
	 * @return innere Pfadlaenge des Baums
	 */
	public int getInternalPathLength() {
		TreeStatisticsCalculator<K> treeStatistics = 
			new TreeStatisticsCalculator<K>();
		this.applyVisitor(treeStatistics);
		return treeStatistics.getInternalPathLength();
	}
	
	/**
	 * fuegt rekursiv einen neuen Knoten in den AVL-Baum ein
	 * Faelle beachtet werden muessen:
	 * 
	 * Fall 1: T=NIL
	 * 
	 * T:         *
	 * 
	 * Fall 2:
	 * 
	 * T:         k
	 *           / \
	 *          O   O
	 *         / \ / \
	 *        .........
	 *        
	 * Fall 3: T.key > k
	 * 
	 * T:         O
	 *           / \
	 *          O   O
	 *         / \ / \
	 *        .k.......
	 *        
	 * Fall 4: T.key < k
	 * 
	 * T:         O
	 *           / \
	 *          O   O
	 *         / \ / \
	 *        .......k.
	 *  
	 * @param node Wurzel des Teilbaums, in den der Schluessel eingefuegt werden soll
	 * @param key der einzufuegende Schluesselwert
	 * @return true, falls die Einfuegeoperation den Baum erhoeht hat
	 */
	protected boolean recursiveInsert(AVLNode<K> node, K key) {
		// 1. Fall: T = NIL : ersetze T durch neuen Knoten
		if( node.getKey()==null ) {
			node.setKey(key);
			node.setLeft(new AVLNode<K>(null));
			node.setRight(new AVLNode<K>(null));
			return true;
		}
		// 2. Fall: key(T) = key: nichts zu tun
		else if( node.getKey().compareTo(key)==0 ) {
			return false;
		}
		// 3. Fall: key(T) < key: fuege rekursiv in rechten Teilbaum ein
		else if( node.getKey().compareTo(key)<0 ) {
			boolean higher = recursiveInsert(node.getRight(), key);
			return rebalanceRightAfterInsertion(node, higher);
		}
		// 4. Fall: key(T) > key: fuege rekursiv in linken Teilbaum ein 
		else {
			boolean higher = recursiveInsert(node.getLeft(), key);
			return rebalanceLeftAfterInsertion(node, higher);
		}
	}

	/**
	 * rebalanciert einen linken Teilbaum nach einer Einfuegeoperation
	 * 
	 * Fall 4.1: kein Hoehenunterschied durch die Einfuegeoperation (nichts zu tun)
	 *           (ansonsten einer der Faelle 2-4)
	 * 
	 * Fall 4.2: linker und rechter Teilbaum hatten die gleiche Tiefe und der
	 *           linke waechst nun um 1
	 * 
	 * T:       O
	 *         / \
	 *        /   \
	 *       /\   /\
	 *      /  \ /__\
	 *      ####             <- diese Ebene wurde im linken Teilbaum neu eingefuegt 
	 *      
	 * Fall 4.3: linker Teilbaum kleiner und waechst nun auf die gleiche Hoehe wie 
	 *           der rechte Teilbaum
	 * 
	 * T:       O
	 *         / \
	 *        /   \
	 *       /\   /\
	 *      /  \ /  \
	 *      ####/____\        <- diese Ebene wurde im linken Teilbaum neu eingefuegt
	 *      
	 *  Fall 4.4.1: der linke Teilbaum ist zu stark gewachsen (um eine Ebende) 
	 *  
	 *  T:       O
	 *          / \
	 *         /   \
	 *        /     \
	 *       /       \
	 *      O        /\
	 *     / \      /  \
	 *    /   \    /    \
	 *   O    /\  /______\
	 *  / \  /__\
	 *  ###                   <- diese Ebene wurde im linken Teilbaum neu eingefuegt
	 *  
	 *  Fall 4.4.2: der linke Teilbaum ist zu stark gewachsen (um eine Ebende)
	 *  
	 *  T:        O
	 *           / \
	 *          /   \
	 *         /     \
	 *        /       \
	 *       /         \
	 *      O          /\
	 *     / \        /  \
	 *    /   \      /    \
	 *   /\    O    /      \
	 *  /  \  / \  /________\ 
	 * /____\/\ /\
	 *      #######           <- diese Ebene wurde im linken Teilbaum neu eingefuegt 
	 *
	 *
	 * @param node Wurzelknoten des zu Rebalancierenden Baums
	 * @param higher flag das angibt, ob der Baum durch die Einfuegeoperation 
	 *        seine Hoehe veraendert hat
	 * @return true, falls der rebalancierte Baum hoeher geworden ist als vor der 
	 *         Einfuegeoperation 
	 */
	protected boolean rebalanceLeftAfterInsertion(AVLNode<K> node, boolean higher) {
		// Fall 4.1: higher=false
		if( higher==false )
			return false;
		else {
			// Fall 4.2: higher=true && bal[T]=0
			if( node.getBalance()==0 ) {
				node.setBalance(-1);
				return true;
			}
			// Fall 4.3: higher=true && bal[T]=1
			else if( node.getBalance()==1 ) {
				node.setBalance(0);
				return false;
			}
			// Fall 4.4: higher=true && bal[T]=-1
			else {
				// Fall 4.4.1: bal[left[T]]=-1
				if( node.getLeft().getBalance()==-1 ) {
					rightRotate(node);
					node.setBalance(0);
					node.getRight().setBalance(0);
					return false;
				}
				// Fall 4.4.2: bal[left[T]]=1
				else {
					int oldBalance = node.getLeft().getRight().getBalance();
					leftRightDoubleRotation(node);
					int newLeftBalance  = 0;
					int newRightBalance = 0;
					switch( oldBalance ) {
					case 0:
						// newLeftBalance=newRightBalance=0
						break;
					case -1:
						newLeftBalance  = 0;
						newRightBalance = 1; 
						break;
					case 1:
						newLeftBalance  = -1;
						newRightBalance =  0; 
						break;
					}
					node.getLeft().setBalance(newLeftBalance);
					node.getRight().setBalance(newRightBalance);
					node.setBalance(0);
					return false;
				}
				
			}
		}
	}


	/**
	 * rebalanciert einen rechten Teilbaum nach einer Einfuegeoperation
	 * 
	 * @param node Wurzelknoten des zu Rebalancierenden Baums
	 * @param higher flag das angibt, ob der Baum durch die Einfuegeoperation seine Hoehe 
	 *        veraendert hat
	 * @return true, falls der rebalancierte Baum hoeher geworden ist als vor der 
	 *         Einfuegeoperation 
	 */
	abstract protected boolean rebalanceRightAfterInsertion(AVLNode<K> node, boolean higher);
	
	/**
	 * fuehrt eine Rechts-Links-Doppelrotation um einen gegebenen Knoten durch
	 * 
	 * @param node Knoten, um den gedreht werden soll
	 */
	protected void rightLeftDoubleRotation(AVLNode<K> node) {
		rightRotate(node.getRight());
		leftRotate(node);
	}


	/**
	 * fuehrt eine Links-Rechts-Doppelrotation um einen gegebenen Knoten durch
	 * 
	 * @param node Knoten, um den gedreht werden soll
	 */
	protected void leftRightDoubleRotation(AVLNode<K> node) {
		leftRotate(node.getLeft());
		rightRotate(node);
	}

	/**
	 * fuehrt eine Links-Rotation um einen gegebenen Knoten durch
	 * 
	 * @param node Knoten, um den gedreht werden soll
	 */
	protected void leftRotate(AVLNode<K> node) {
		AVLNode<K> leftNode = 
			new AVLNode<K>(node.getKey());
		leftNode.setLeft(node.getLeft());
		leftNode.setRight(node.getRight().getLeft());
		node.setKey(node.getRight().getKey());
		node.setRight(node.getRight().getRight());
		node.setLeft(leftNode);
	}
	
	/**
	 * fuehrt eine Rechts-Rotation um einen gegebenen Knoten durch
	 * 
	 * @param node Knoten, um den gedreht werden soll
	 */
	protected void rightRotate(AVLNode<K> node) {
		AVLNode<K> rightNode = 
			new AVLNode<K>(node.getKey());
		rightNode.setRight(node.getRight());
		rightNode.setLeft(node.getLeft().getRight());
		node.setKey(node.getLeft().getKey());
		node.setLeft(node.getLeft().getLeft());
		node.setRight(rightNode);
	}


	/**
	 * applies given visitor to the root node
	 * @param v
	 */
	public void applyVisitor(TreeVisitor<K> v) {
		root.accept(v);
	}
}