package plp.collection;

public class AVL {
    
    private AVL left;
    private AVL right;
    private Comparable data;
    private int height;
    private int size;

    public AVL() {
	this(null, null, null);
    }

    private void updateValues() {
	if (isEmpty()) {
	    height = size = 0;
	} else {
	    height = 1 + Math.max(left.height, right.height);
	    size = left.size + right.size + 1;	
	}
    }

    private void changeLinks(AVL left, Comparable data, AVL right) {
	this.left = left;
	this.data = data;
	this.right = right;
	updateValues();
    }

    private AVL(AVL left, Comparable data, AVL right) {
	changeLinks(left, data, right);
    }
    
    private void rightRotation() {
	AVL ll = left.left;
	Comparable ldata = left.data;
	left.changeLinks(left.right, data, right);
	changeLinks(ll, ldata, left);
    }

    private void leftRotation() {
	AVL rr = right.right;
	Comparable rdata = right.data;
	right.changeLinks(left, data, right.left);
	changeLinks(right, rdata, rr);
    }

    private void balance() {
	if (isEmpty()) {
	    return;
	}
	if (left.height == right.height + 2) {
	    if (left.right.height == left.left.height + 1) {
		left.leftRotation();
	    }
	    rightRotation();
	} else if (right.height == left.height + 2) {
	    if (right.left.height == right.right.height + 1) {
		right.rightRotation();
	    }
	    leftRotation();
	} else {
	    updateValues();
	}
    }

    public void insert(Comparable dataToInsert) 
	throws AVLInsertionException
    {
	try {
	    insertAux(dataToInsert);
	} catch (AVLException e) {
	    throw new AVLInsertionException(this, dataToInsert);
	}
    }

    private AVL chooseNode(Comparable data) 
	throws AVLEmptyException
    {
	if (isEmpty()) {
	    throw new AVLEmptyException(this);
	} else {
	    int cmp = data.compareTo(this.data);
	    if (cmp == 0) {
		return this;
	    } else {
		return (cmp > 0 ? right : left);
	    }
	}
    }

    private void insertAux(Comparable dataToInsert) 
	throws AVLInsertionException
    {
	try {
	    AVL c = chooseNode(dataToInsert);
	    if (c == this) {
		throw new AVLInsertionException(this, dataToInsert);
	    } else {
		c.insert(dataToInsert);
		balance();
	    }
	} catch (AVLEmptyException e) {
	    changeLinks(new AVL(), dataToInsert, new AVL());
	} 
    }
    
    public void remove(Comparable dataToRemove) 
	throws AVLRemoveException 
    {
	try {
	    removeSearchNode(dataToRemove);
	} catch (AVLRemoveException e) {
	    throw new AVLRemoveException(this, dataToRemove);
	}
    }	

    private void removeSearchNode(Comparable dataToRemove) 
	throws AVLRemoveException 
    {
	try {
	    AVL c = chooseNode(dataToRemove);
	    if (c == this) {
		if (left.isEmpty()) {
		    changeLinks(right.left, right.data, right.right);
		} else {
		    left.removeSearchLeaf(this);
		}
	    } else {
		c.removeSearchNode(dataToRemove);
	    }
	    balance();
	} catch (AVLEmptyException e) {
	    throw new AVLRemoveException(this, dataToRemove);
	}
    } 

    private void removeSearchLeaf(AVL nodeToRemove) {
	if (right.isEmpty()) {
	    nodeToRemove.data = data;
	    changeLinks(left.left, left.data, left.right);
	} else {
	    right.removeSearchLeaf(nodeToRemove);
	}
	balance();
    }

    public boolean isEmpty() {
	return left == null;
    }

    public int size() {
	return size;
    }

    public boolean member(Comparable data) {
	try {
	    AVL c = chooseNode(data);
	    return (c == this || c.member(data));
	} catch (AVLEmptyException e) {
	    return false;
	}
    }

    /*
      It is not necessary to use an auxilliary function in order to get
      the right AVL as the exception will always occur at the root.
    */

    public Comparable data(int rank) 
	throws AVLRankException
    {
	if (rank >= size) {
	    throw new AVLRankException(this, rank);
	} else if (rank == left.size) {
	    return this.data;
	} else if (rank < left.size) {
	    return left.data(rank);
	} else {
	    return right.data(rank - left.size - 1);
	}
    }

    public Comparable max() 
	throws AVLRankException
    {
	return data(size - 1);
    }

    public Comparable min() 
	throws AVLRankException
    {
	return data(0);
    }

    private int dfsAux(Comparable [] array, int index) {
	if (isEmpty()) {
	    return index;
	}
	index = left.dfsAux(array, index);
	array[index++] = data;
	return right.dfsAux(array, index);
    }

    public Comparable [] dfs() {
	Comparable [] array = new Comparable[size()];
	dfsAux(array, 0);
	return array;
    }

    public String toString() {
	String s = "";
	if (isEmpty()) {
	    s = "EMPTY\n";
	} else {
	    s += data + "(height = " + height + " size = " + size + ")\n";
	    s += left;
	    s += right;
	}
	return s;
    }
}