public class AVLDictionary implements LocatorDictionary {
	StringComparator c;
	LinkedBinaryTree tree;
	
	public AVLDictionary(Comparator cmp) {
		c = (StringComparator) cmp;
		tree = new LinkedBinaryTree();
	}
	
	public int size() {
		return tree.size()-1;
	}
	
	public boolean isEmpty() {
		return tree.isEmpty();
	}
	
	public boolean isExternal(Position p) {
		return tree.isExternal(p);	
	}
	
	public Position findPosition(Object k, Position p) {
		if(tree.isExternal(p))
			return p;
		if(c.isLessThan(((AVLItem)p.element()).key(), k))
			return findPosition(k, tree.leftChild(p));
		else if(c.isGreaterThan(((AVLItem)p.element()).key(), k)) 
			return findPosition(k, tree.rightChild(p));
		return p;
	}
	
	public Position find(Object k) {
		return findPosition(k, tree.root());		
	}
	
	public int height(Position p) {
		if(tree.isExternal(p))
			return 0;
		return ((AVLItem)p.element()).height();
	}
	
	public boolean isBalanced(Position z) {
		return Math.abs(height(tree.leftChild(z)) - height(tree.rightChild(z)))<=1;
	}
	
	public void setHeight(Position z) {
		((AVLItem)z.element()).setHeight(1+Math.max(height(tree.leftChild(z)),
													height(tree.rightChild(z))));
	}
	
	public Position tallerChild(Position p) {
		if(height(tree.leftChild(p)) >= height(tree.rightChild(p)))
			return tree.leftChild(p);
		return tree.rightChild(p);
	}
	
	public Position restructure(Position x) {
		Position y = tree.parent(x);
		Position z = tree.parent(y);
		Position upper = tree.parent(z);
		Position t0, t1, t2, t3;
		Position a, c;
		Position b=null;
		
		if( (tree.rightChild(z)==y) && (tree.rightChild(y)==x) ) 
		{
			a = z;
			b = y;
			t1 = tree.leftChild(b);
			((Node) t1).setParent((Node)z);
			((Node) z).setRight((Node)t1);
			((Node) a).setParent((Node)b);
			((Node) b).setLeft((Node)a);
			((Node) b).setParent((Node)upper);
		}
		else if( (tree.leftChild(z)==y) && (tree.leftChild(y)==x) )
		{
			b = y;
			c = z;
			t2 = tree.rightChild(b);
			((Node) t2).setParent((Node)z);
			((Node) z).setLeft((Node)t2);
			((Node) b).setRight((Node)c);
			((Node) c).setParent((Node)b);
			((Node) b).setParent((Node)upper);
		}
		else if( (tree.rightChild(z)==y) && (tree.leftChild(y)==x) )
		{
			a = z;
			c = y;
			b = x;
			t1 = tree.leftChild(b);
			t2 = tree.rightChild(b);
			((Node) t1).setParent((Node)z);
			((Node) z).setRight((Node)t1);
			((Node) t2).setParent((Node)y);
			((Node) y).setLeft((Node)t2);
			((Node) a).setParent((Node)b);
			((Node) c).setParent((Node)b);
			((Node) b).setLeft((Node)a);
			((Node) b).setRight((Node)c);
			((Node) b).setParent((Node)upper);
		}
		else if( (tree.leftChild(z)==y) && (tree.rightChild(y)==x) )
		{
			a = y;
			b = x;
			c = z;
			t2 = tree.leftChild(b);
			t1 = tree.rightChild(b);
			((Node) t2).setParent((Node)y);
			((Node) y).setRight((Node)t2);
			((Node) t1).setParent((Node)z);
			((Node) z).setLeft((Node)t1);
			((Node) a).setParent((Node)b);
			((Node) c).setParent((Node)b);
			((Node) b).setLeft((Node)a);
			((Node) b).setRight((Node)c);
			((Node) b).setParent((Node)upper);
		}
		if(upper!=null) {
			if(tree.rightChild(upper) == z)
				((Node) upper).setRight((Node)b);
			else
				((Node) upper).setLeft((Node)b);
		}
		else
			tree.root = b;
		return b;
	}
	
	public void balance(Position z) {
		while(!tree.isRoot(z)) {
			z = tree.parent(z);
			setHeight(z);
			if(!isBalanced(z)) {
				Position x = tallerChild(tallerChild(z));
				z = restructure(x);
				setHeight(tree.leftChild(z));
				setHeight(tree.rightChild(z));
				setHeight(z);
			}
		}
	}
	
	public Position insert(Object k, Object o) {
		Position newPosition = find(k);
		tree.expandExternal(newPosition);
		tree.replace(newPosition, new AVLItem(k, o, 1));
		balance(newPosition);
		return newPosition;
	}
	
	public Object remove(Position p) {
		AVLItem returnElement;

		if(tree.isExternal(p)) 
			return null;
			
		returnElement = new AVLItem (((AVLItem)p.element()).key(),
					     ((AVLItem)p.element()).element(),
					     ((AVLItem)p.element()).height());
		if(tree.isExternal(tree.leftChild(p)))
			p = tree.leftChild(p);
		else if(tree.isExternal(tree.rightChild(p)))
			p = tree.rightChild(p);
		else {
			Position swapPos = p;
			p = tree.rightChild(swapPos);
			do
				p = tree.leftChild(p);
			while(tree.isInternal(p));
			replaceKey(swapPos, 
					   ((AVLItem)(tree.parent(p)).element()).key());
			replaceElement(swapPos,
					   ((AVLItem)(tree.parent(p)).element()).key());
		}
		Position z = sibling(p);
		tree.removeAboveExternal(p);
		balance(z);
		return returnElement;
	}
	
	public Object replaceKey(Position l, Object k) {
		Object temp = ((AVLItem)l.element()).key();
		((AVLItem)l.element()).setKey(k);
		return temp;
	}
	
	public Object replaceElement(Position l, Object e) {
		Object temp = ((AVLItem)l.element()).element();
		((AVLItem)l.element()).setElement(e);
		return temp;
	}
	
	public Position sibling(Position p) {
		if(tree.isRoot(p))
			return null;
		Position parent = tree.parent(p);
		if(tree.leftChild(parent) == p)
			return ((Node) parent).getRight();
		return ((Node) parent).getLeft();
	}
}