/* 
   more agreesively oop version of binary search trees
*/

interface Node<TY extends Comparable<TY>>
{
    int size();  // number if nodes in tree
    boolean empty(); // if (n.empty()) replaces if (n==null)
    vertex<TY> insert(TY x);  // always use as in n=n.insert(x)
    boolean search(TY x);     // is x in tree?
    Node<TY> delete(TY x);    // always use as in n=n.delete(x)
    Node<TY> delmax(vertex<TY> modnode);  // delete largest, replaces modnode
    int depth();   // height (length of longest branch)
    boolean bst(TY min, TY max); // tree if tree is a binary search tree
    void accept(treegraph TG, int l, int lb, int rb); //graphical integration
    int getheight();  // simply returns height
    int calcbalance(); // return relative balance, <0 means left heavy
                       // >0 means right heavy
    void LL();
    void RR();
}//Node interface

// nil replaces null as the empty tree, base case of methods
class nil<TY extends Comparable<TY>> implements Node<TY>
{
    public int size() { return 0; }
    public boolean empty() { return true; }
    public vertex<TY> insert(TY x) { return new vertex<TY>(x); }
    public boolean search(TY x) { return false; } // not found
    public Node<TY> delete(TY x) { return this; }
    public Node<TY> delmax(vertex<TY> modnode) { return this; }
    public int depth() { return 0; }
    public boolean bst(TY min, TY max) { return true; }
    public void accept(treegraph TG, int l, int lb, int rb)
       {TG.draw(this,l,lb,rb);}

    public int getheight() { return 0; }
    public int calcbalance() { return 0; }
    public void LL() {}
    public void RR() {}
}//nil

// vertex containing info, left, right, recursive case of methods.
class vertex<TY extends Comparable<TY>> implements Node<TY>
{
    protected TY item; // data stored in vertex
    protected Node<TY> left; // could be nil or vertex
    protected Node<TY> right;
    // read access to protected values:
    public Node<TY> left() { return left; }
    public Node<TY> right() { return right; }
    public TY head() { return item; } // name "head" required by treegraph

    public vertex(TY x) { item=x; left=right=new nil<TY>(); }//constructor

    public boolean empty() { return false; }
    public int size() { return 1 + left.size() + right.size(); }
    public int depth()
    {
	int ld = left.depth(), rd = right.depth();
	if (ld>rd) return ld+1; else return rd+1;
    }
    public boolean bst(TY min, TY max)
    {
	return (min==null || min.compareTo(item)<0) &&
	    (max==null || max.compareTo(item)>0) &&
	    left.bst(min,item) && right.bst(item,max);
    }

    public boolean search(TY x)
    {
	int c = item.compareTo(x);
	return (c==0) || (c>0 && left.search(x)) || (c<0 && right.search(x));
    }

    public vertex<TY> insert(TY x)
    {
	int c = item.compareTo(x);
	if (c>0) left = left.insert(x);
	else if (c<0) right = right.insert(x);
	balance();
	return this; // no duplicates inserted
    }

    // modnode points to node whose item needs to be changed to
    // either the largest of the left, or smallest on the right.
    // initial value of modnode should be null. It is assumed that
    // there are no duplicates

     // called from delete    
    public Node<TY> delmax(vertex<TY> modnode)
    {
	if (!right.empty()) 
	    { 
		right=right.delmax(modnode); 
		balance();
		return this; 
	    }
	// this is the largest/rightmost vertex of subtree
	modnode.item = item;  // transfer information to node above
	return left; // left subtree moves up (replaces current node)
    }

    // always call n = n.delete(x)
    public Node<TY> delete(TY x)
    {
        int c = item.compareTo(x);
	if (c>0) { left = left.delete(x); balance(); return this; }
	else if (c<0) { right = right.delete(x); balance(); return this; }
	//assuming c==0, node to be deleted is found
	if (!left.empty())
	    { 
		left=left.delmax(this); // this node is the modnode.
		balance();
		return this;
	    }
	else 
	    {
		return right; // replace this node with right subtree
	    }
    }//delete

    public void accept(treegraph TG, int l, int lb, int rb)
       {TG.draw(this,l,lb,rb);}

    //////////////////////// AVL IMPLEMENTATION ////////////////////
    protected int height = 1;

    public int getheight() { return height; }
    public int calcbalance() // sets height too, non-recursive!
    {
	int lh = left.getheight(), rh = right.getheight();
	if (lh>rh) height = lh+1; else height=rh+1;
	return right.getheight() - left.getheight();
    }

    // rotations
    public void LL()
    {
	if (left.empty()) return;
	vertex<TY> lvert = ((vertex<TY>)left);
	TY tmp = item;
	Node<TY> r0 = right;
	item = lvert.item;
	left = lvert.left;
	right = new vertex<TY>(tmp,lvert.right,r0);
	calcbalance();
    }

    public void RR()
    {
	if (right.empty()) return;
	vertex<TY> rvert = ((vertex<TY>)right);
	TY tmp = item;
	Node<TY> l0 = left;
	item = rvert.item;
	right = rvert.right;
	left = new vertex<TY>(tmp,l0,rvert.left);
	calcbalance();
    }

    protected void balance()
    {
	int bal = calcbalance();
	if (bal < -1) // left subtree too tall - LL or LR
	    {
		int lb = left.calcbalance();
		if (lb<=0) // left hevy -single rotation
		    LL();
		else // double rotation   (LR)
		    {
			left.RR();
			LL();
		    }
	    }
	else if (bal>1) // right subtree too tall, RR or RL
	    {
		int rb = right.calcbalance();
		if (rb>=0) // right-heavy - single rotation
		    RR();
		else
		    {
			right.LL();     //(RL)
			RR();
		    }
	    }
    } // balance


    protected vertex(TY i, Node<TY> l, Node<TY> r) // special constructor
	{ item=i; left=l; right=r; calcbalance(); }
}//vertex class


public class modernavl
{
    public static void main(String[] args)
    {
      treegraph W = new treegraph(1024,768);
      nil<Integer> NIL = new nil<Integer>(); // shared empty tree instance
      Node<Integer> T = NIL;
      int[] A = {8,4,12,6,2,10,14,11};
      for(int x:A) T=T.insert(x);
      W.drawtree(T);
      try{Thread.sleep(1000);} catch(Exception e) {} // 5 sec delay
      T = T.delete(12);
      W.drawtree(T);
      T = T.delete(8);
      try{Thread.sleep(1000);} catch(Exception e) {} // 5 sec delay
      W.drawtree(T);
      T = T.insert(15); 
      try{Thread.sleep(1000);} catch(Exception e) {} // 5 sec delay
      W.drawtree(T);
T = T.insert(16);
      try{Thread.sleep(2000);} catch(Exception e) {} // 5 sec delay
      W.drawtree(T);
      T = T.insert(18); T = T.insert(20); T=T.insert(22); T=T.insert(23);
      T=T.insert(24); T=T.insert(26);      
      try{Thread.sleep(2000);} catch(Exception e) {} // 5 sec delay
      W.drawtree(T);
      W.display.drawString("Do you like my tree?",20,W.YDIM-50);
      try{Thread.sleep(5000);} catch(Exception e) {} // 5 sec delay
    }  // main
}//modern