package fha.inf3.avltree;

import java.util.*;

import fha.inf3.tree.*;
/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
* adapted to BinarySearchTree interface D. Gruntz
*/
public class AVLSearchTree implements BinarySearchTree {

	/** The tree root. */
	private Node root;

	public BinarySearchTreeNode getRoot(){
		return root;
	}

	/**
	* Test if the tree is logically empty.
	* @return true if empty, false otherwise.
	*/
	public boolean isEmpty() {
		return root == null;
	}

	public int size(){
		return size(root);
	}
	
	private static int size(Node p){
		if(p==null)return 0;
		else return 1 + size(p.left) + size(p.right);
	}
	
	public int height(){
		return height(root);
	}
	
	/**
	* Return the height of node t, or -1, if null.
	*/
	private static int height(Node t) {
		return t == null ? -1 : t.height;
	}

	/**
	* Find an item in the tree.
	* @param x the item to search for.
	* @return the matching item or null if not found.
	*/
	public Object search(Comparable key) {
		return search(root, key);
	}

	/**
	* Internal method to find an item in a subtree.
	* @param x is item to search for.
	* @param t the node that roots the tree.
	* @return node containing the matched item.
	*/
	private Object search(Node t, Comparable x) {
		while(t != null)
			if(x.compareTo(t.key) < 0)
				t = t.left;
			else if(x.compareTo(t.key) > 0)
				t = t.right;
			else
				return t.element;    // Match

		return null;   // No match
	}

	/**
	* Insert into the tree; duplicates are ignored.
	* @param x the item to insert.
	*/
	public void insert(Comparable key, Object element) {
		root = insert(root, key, element);
	}

	/**
	* Internal method to insert into a subtree.
	* @param x the item to insert.
	* @param t the node that roots the tree.
	* @return the new root.
	*/
	private Node insert(Node p, Comparable key, Object element) {
		if(p == null)
			p = new Node(key, element);
		else {
			int c = key.compareTo(p.key);
			if(c < 0) {
				p.left = insert(p.left, key, element);
				if(height(p.left) - height(p.right) == 2)
					if(height(p.left.left) > height(p.left.right))
						p = rotateR(p);
					else
						p = rotateLR(p);
			}
			else if(c > 0) {
				p.right = insert(p.right, key, element);
				if(height(p.right) - height(p.left) == 2)
					if(height(p.right.right) > height(p.right.left))
						p = rotateL(p);
					else
						p = rotateRL(p);
			}
			else
				p.element = element;
		}
		p.height = Math.max(height(p.left), height(p.right)) + 1;
		return p;
	}

	/**
	* Remove from the tree. Nothing is done if x is not found.
	* @param x the item to remove.
	*/
	public void remove (Comparable key){
		root = remove(root, key);	
	}
	
	/**
	* Internal method to remove out of a subtree.
	* @param key the item to remove.
	* @param p the node that roots the tree.
	* @return the new root.
	*/
	private Node remove(Node p, Comparable key){
		if (p == null) {
			return null;
		}
		int c = p.key.compareTo(key);
		if (c == 0) {
			if (p.left != null && p.right != null) {
				Node biggest = findBiggest(p.left);
				p.left = remove(p.left, biggest.key);
				p.key = biggest.key;
				p.element = biggest.element;
			}
			else if (p.left != null) {
				p = p.left;
			}
			else if (p.right != null) {
				p = p.right;
			}
			else {
				return null;
			}
		}
		else if (c < 0) {
		 	p.right = remove(p.right, key);
		}
		else {
			p.left = remove(p.left, key);
		}
		p = checkRotation(p);
		p.height = Math.max(height(p.left), height(p.right))+1;
		return p;
	}
	
	private Node findBiggest(Node p) {
		Node tmp = p;
		while (tmp.right != null) {
			tmp = tmp.right;
		}
		return tmp;
	}
	
	private Node checkRotation(Node p) {
		Node tmp = p;
		if (height(p.left) - height(p.right) == 2) {
			if (height(p.left.left) - height(p.left.right) == 1) {
				tmp = rotateR(p);
			}
			else {
				tmp =rotateLR(p);
			}
		}
		else if (height(p.right) - height(p.left) == 2) {
			if (height(p.right.right) - height(p.right.left) == 1) {
				tmp = rotateL(p);
			}
			else {
				tmp = rotateRL(p);
			}
		}
		return tmp;
	}
	
	/**
	* Rotate binary tree node with left child.
	* For AVL trees, this is a single rotation for case 1.
	* Update heights, then return new root.
	*/
	private static Node rotateR(Node k2) {
		Node k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;
		k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
		k1.height = Math.max(height(k1.left), k2.height) + 1;
		return k1;
	}

	/**
	* Rotate binary tree node with right child.
	* For AVL trees, this is a single rotation for case 4.
	* Update heights, then return new root.
	*/
	private static Node rotateL(Node k1) {
		Node k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;
		k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
		k2.height = Math.max(height(k2.right), k1.height) + 1;
		return k2;
	}

	/**
	* Double rotate binary tree node: first left child
	* with its right child; then node k3 with new left child.
	* For AVL trees, this is a double rotation for case 2.
	* Update heights, then return new root.
	*/
	private static Node rotateLR(Node k3) {
		k3.left = rotateL(k3.left);
		return rotateR(k3);
	}

	/**
	* Double rotate binary tree node: first right child
	* with its left child; then node k1 with new right child.
	* For AVL trees, this is a double rotation for case 3.
	* Update heights, then return new root.
	*/
	private static Node rotateRL(Node k1) {
		k1.right = rotateR(k1.right);
		return rotateL(k1);
	}


	// Test program
	public static void main(String [ ] args) {
		//AVLSearchTree t = new AVLSearchTree();
		//final int NUMS = 4000;
		//final int GAP  =   37;

		//System.out.println("Checking... (no more output means success)");

		//for(int i = GAP; i != 0; i = (i + GAP) % NUMS)
		//	t.insert(new Integer(i), new Integer(i));

		//for(int i = 1; i < NUMS; i++)
		//if(((Integer)(t.search(new Integer(i)))).intValue() != i)
		//	System.out.println("Find error1!");
		
		AVLSearchTree aTree = new AVLSearchTree();
		System.out.println("AVLSearchTree");
		aTree.showHeight(aTree, 10000, 100000);
		MyBinarySearchTree bTree = new MyBinarySearchTree();
		System.out.println("BinarySearchTree");
		bTree.showHeight(10000, 100000);
	}
	
	public void showHeight(BinarySearchTree t, int teil, int max) {
		Random rand = new Random();
		for(int i = 0; i < max; i++) {
			Integer INT = new Integer(rand.nextInt());
			t.insert(INT, INT);
			if (i != 0 && i%teil == 0) {
				System.out.println("n = " + i + "\t\tHoehe = " + t.height() + "\t\tHoehe / log2(n) = " + (Math.log(this.height()/Math.log(2))));
			}
		}
	}
}

class Node implements BinarySearchTreeNode {
	Comparable key;
	Object element;
	Node left, right;
	int height;

	Node(Comparable key){this(key, null);}
	Node(Comparable key, Object element){
		this.key = key; this.element = element;
	}
	Node(Comparable key, Object element, Node left, Node right){
		this(key, element); this.left = left; this.right = right;
	}
	
	public Object getKey(){return key;}
	public BinarySearchTreeNode getLeft(){return left;}
	public BinarySearchTreeNode getRight(){return right;}
}