//Ali Soleimani
//CS3
//Binary Tree class.  Uses self-balancing AVL trees.

import java.util.*;

public class BinaryTree implements BinaryTreeInterface {

  // Add newElement into the proper place in the tree
  // Allows duplicate elements to be added!
  public void addElement(OrderedObject newElement) {
    if(root==null) root=new TreeNode(null, newElement);
    else addHelper(root, newElement);
    numberElements++;
  }

  // Returns if an object that reports equality to
  // object elem is contained in the tree
  public boolean contains(OrderedObject elem) {
    TreeNode current=root;
    while(current!=null) {                   //While we still are in the tree:
      if((current.data).equals(elem)) return true;   //We found it.
      else { if(elem.lessThan(current.data)) current=current.left; else current=current.right;}
    }                                     //Follow the appropriate path.
    return false;                             //Not found.
  }
  
  // Allows for iteration through the tree
  // Creates an ordered array of the tree at the instant it is run.
  // Since I am using AVL trees, I decided that dynamically getting the next
  // element from the tree was a bad idea, because of all the rotations, swapping, etc. going on.
  public java.util.Enumeration elements() {
    
    class myEnum implements Enumeration {
      int i;
      Stack myStack;
      myEnum() {        //Uses a temp stack to iterate through the elements and add them to myStack
	myStack = new Stack();                 //Standard inits
	Stack tempStack = new Stack();
	i=0;
	TreeNode cur=root;
	while(!tempStack.empty() || cur != null) {   //Add elements to myStack in reverse order.
	  while(cur!=null) {
	    tempStack.push(cur);
	    cur=cur.right;
	  }
	  cur=(TreeNode)tempStack.pop();
	  myStack.push(cur.data);
	  cur=cur.left;
	}
      }
      public boolean hasMoreElements() {
	return !myStack.empty();
      }
      public Object nextElement() {
	if(!myStack.empty()) return myStack.pop();
	else throw new NoSuchElementException();
      }
    }
    return new myEnum();
  }
  
  // Returns true if the tree is empty
  public boolean isEmpty() {
    return (root==null);
  }
  
  // Removes all elements from the tree
  public void removeAllElements() {
    root=null;
    numberElements=0;
  }

  // Removes the first of object that reports
  // equals(obj) to be true from the tree
  // returns true if some instance was removed, false
  // if no such instance was found.
  public boolean removeElement(OrderedObject obj) {
    if(root==null) return false;        //Return 0 if tree is empty
    TreeNode current=root;
    while(current!=null && (! ((current.data).equals(obj)) ) ) {
      if(obj.lessThan(current.data)) current=current.left; else current=current.right;
    }
    if(current != null) {
      if(current.left != null && current.right != null) delSwap(current);
      TreeNode sublink = (current.left != null) ? (current.left) : (current.right);
      TreeNode par = current.parent;
      if(par!=null) {                  //We are deleting a subtree; root ptr is irrelevant.
	//Fix pointers above current.
	Side from = new Side();        //From holds the subtree we deleted from.
	from.data=(par.right==current);
	if(par.left == current) par.left = sublink;
	else par.right=sublink;
	if(sublink!=null) sublink.parent = par;    //Fix sublink parent pointers.
	//Fix parent balance.
	current = null;   //Kill current and let it be deleted.
	while(par!=null) par=delHelper(par, from);      //Call delHelper on deleted's parent, etc.
      }
      else {                    //We are deleting the root. Only one subtree.
	if(current.right!=null) {root=current.right; current.right= null; root.parent = null;}
	else
	  if (current.left!=null) {root=current.left; current.left = null; root.parent = null;}
	  else root=null;
	current=null;   //Kill current
      }
      numberElements--;
      return true;           //We did find/delete the element.
    }
    else return false;                  //Data not found.
  }
  
  // Returns how many elements are in the tree
  public int size() {
    return numberElements;
  }

  //---------------------------------------------------------------//

  TreeNode root;
  int numberElements;

  class TreeNode {
    TreeNode parent;
    TreeNode left;
    TreeNode right;
    int balanced;
    OrderedObject data;

    TreeNode() {balanced=0;};
    TreeNode(TreeNode p, OrderedObject info) {
      balanced=0;
      parent=p;
      data=info;
    };
  }
  
  class Side {
    boolean data;
  }
  
  //---------------------------------------------------------------//

  public BinaryTree() {
    numberElements=0;
  }

  private boolean addHelper(TreeNode tree, OrderedObject info) {  //Recursively adds/rebalances the AVL tree.
    if(info.lessThan(tree.data) && tree.left!=null) {
      if(addHelper(tree.left, info)!=false) {       //Move down the tree.
	tree.balanced--;                   //If subtree grew, correct balance.
	if(tree.balanced==0) return false;       //No change in height; return 0.
	if(tree.balanced==-1) return true;      //Change in height; return 1.
	return(leftBalance(tree));          //Icky!  Rebalance this node.
      }
      else return false;                   //If the subtree didn't grow, this node is unchanged.
    }
    
    if(info.lessThan(tree.data)) {            //When we can insert into an empty left subtree:
      tree.left = new TreeNode(tree, info);  //Create the tree
      tree.balanced--;                      //Make the node balanced if it had a right subtree,
      return (tree.balanced==-1);}          //left high if it was a leaf node.  We can't
                                           //unbalance the tree, but we might increase height.
    if(tree.right != null) {
      if(addHelper(tree.right, info) != false) {           //Move down the right subtree.  Same as above case.
	tree.balanced++;
	if(tree.balanced==0) return false;
	if(tree.balanced==1) return true;
	return(rightBalance(tree));
      }
      else return false;
    }
    
    else {
      tree.right= new TreeNode(tree, info); //When we can insert into an empty right subtree:
      tree.balanced++;                      //Same as above case.
      return tree.balanced == 1;}
  }
  
  private void leftRotate(TreeNode pivot) {     //Rotates a subtree to the left.
    TreeNode rotator=pivot.right;
    pivot.right=rotator.left;
    rotator.left=pivot;
    if(pivot.right != null) (pivot.right).parent=pivot;                 //Fix parent pointers.
    rotator.parent=pivot.parent;
    pivot.parent=rotator;
    if((rotator.parent)!=null) {                 //If we aren't at the root node,
      if(((rotator.parent).left)==pivot) rotator.parent.left=rotator;
      else rotator.parent.right=rotator;    //Fix the parent pointer.
    }
    else root=rotator;                            //Otherwise, fix the root pointer.
  }


  /*delHelper is a recursive function which moves up the tree starting immediately after
    deletion.  Since we are using an AVL tree, the deleted node can have at most a single
    subnode, which simplifies our job. */
  TreeNode delHelper(TreeNode original, Side side) {
    TreeNode next = original.parent;              //Hold place of parent node.
    //When the original tree is balanced to start out:
    if(original.balanced == 0) {
      if(side.data) original.balanced--;
      else original.balanced++;                                    //Rebalance
      return null;                                        //No upper nodes unbalanced
    }
    //When the original tree will not be unbalanced by the deletion:
    if( ((original.balanced == -1) && !side.data) || ((original.balanced == 1) && side.data)) {
      original.balanced = 0;                          //Rebalance
      if(next!=null) {side.data = (next.right == original); return next;}    //Set the side flag.
      else return null;                                   //At root node.  Stop loop.
    }
    //When the original tree will be unbalanced.
    TreeNode opposite = (side.data ? (original.left) : (original.right));
    
    //When the subtree that wasn't deleted from is balanced:
    if(opposite.balanced == 0) {
      original.balanced = (side.data ? -1 : 1);
      opposite.balanced = (side.data ? 1 : -1);
      if(side.data) rightRotate(original);
      else leftRotate(original);  //Rotate inside.
      return null;                                       //Above balance unaffected.
    }
    
    //When the subtree that wasn't deleted from is inside-heavy:
    int inside=(side.data ? 1 : -1);
    if(opposite.balanced == inside) {
      if(next != null) side.data = (next.right == original);
      original.balanced = (((side.data ? opposite.right : opposite.left).balanced==-inside) ? -inside : 0);
      opposite.balanced = (((side.data ? opposite.right : opposite.left).balanced==inside) ? -inside : 0);
      (side.data ? opposite.right : opposite.left).balanced=0;
      if(side.data) leftRotate(opposite);
      else rightRotate(opposite);   //Rotate outwards.
      if(side.data) rightRotate(original);
      else leftRotate(original);   //Rotate inwards.
      return next;
    }
    
    //When the subtree that wasn't deleted from is outside-heavy:
    if(opposite.balanced == -inside) {
      original.balanced = opposite.balanced = 0;   //Everything balanced.
      if(next!=null) side.data = (next.right == original);
      if(side.data) rightRotate(original);
      else leftRotate(original);   //Rotate inwards.
      return next;
    }
    return null;
  }
  
  private void rightRotate(TreeNode pivot) {    //Rotates a subtree to the right.
    TreeNode rotator=pivot.left;
    pivot.left=rotator.right;
    rotator.right=pivot;
    if(pivot.left != null) (pivot.left).parent=pivot;                  //Fix parent pointers.
    rotator.parent=pivot.parent;
    pivot.parent=rotator;
    if((rotator.parent)!=null) {                 //If we aren't at the root node,
      if(((rotator.parent).left)==pivot) rotator.parent.left=rotator;
      else rotator.parent.right=rotator;    //Fix the parent pointer.
    }
    else root=rotator;                            //Otherwise, fix the root pointer.
  }

  private boolean leftBalance(TreeNode tree) {    //Balances a left-overheavy subtree.
    TreeNode leftsub= (tree.left);   //We know it exists since tree is left-heavy.

    switch(leftsub.balanced) {   //Check to see where the imbalance was created.
      
    case -1:                           //When we added on the left subtree of left subtree,
      tree.balanced=0;              //Both the old and new top nodes will be balanced.
      leftsub.balanced=0;
      rightRotate(tree);       //Do a single rotation
      return false;                //The top node height did not grow as a result of the add.
      
    case 1:                    //When we added on the right subtree of left subtree,
      TreeNode rightsub= (leftsub.right);    //We know we _have_ a right subtree.
      switch(rightsub.balanced) {                //Check the right subtree's balance:
      case -1:                        //When it started left-heavy:
	tree.balanced = 1;           //Root node will end up right-heavy.
	leftsub.balanced=0;          //Left subtree will end up balanced.
	rightsub.balanced=0;         //Right subtree will end up balanced.
	break;
      case 0:                         //When we just added the right subtree,
	tree.balanced=leftsub.balanced=rightsub.balanced=0;
	break;                        //Everything ends up balanced.
      case 1:                         //When it started right-heavy:
	tree.balanced = 0;           //Root will be balanced
	leftsub.balanced = -1;       //Leftsub will be left-heavy
	rightsub.balanced = 0;       //Rightsub will be balanced.
	break;
      }
      leftRotate(leftsub);            //Do a left rotation to move imbalance to outer subtree.
      rightRotate(tree);              //Do a right rotation to correct imbalance.
      return false;                       //Root node height does not increase due to new node.
    }
    return false;
  }
  
  private boolean rightBalance(TreeNode tree) {   //Balances a right-overheavy subtree.
    TreeNode rightsub= (tree.right);   //We know it exists since tree is left-heavy.
    
    switch(rightsub.balanced) {   //Check to see where the imbalance was created.
      
    case 1:                           //When we added on the right subtree of right subtree,
      tree.balanced=0;              //Both the old and new top nodes will be balanced.
      rightsub.balanced=0;
      leftRotate(tree);        //Do a single rotation
      return false;                //The top node height did not grow as a result of the add.
      
    case -1:                    //When we added on the left subtree of right subtree,
      TreeNode leftsub= (rightsub.left);    //We know we _have_ a left subtree.
      switch(leftsub.balanced) {                //Check the right subtree's balance:
      case -1:                         //When it started left-heavy:
	tree.balanced = 0;            //Root node will end up right-heavy.
	leftsub.balanced=0;           //Left subtree will end up balanced.
	rightsub.balanced=1;          //Right subtree will end up balanced.
	break;
      case 0:                          //When we just added the left subtree (it's balanced)
	tree.balanced=leftsub.balanced=rightsub.balanced=0;
	break;                         //Everything ends up balanced
      case 1:                          //When it started right-heavy:
	tree.balanced = -1;           //Root will be left-heavy;
	leftsub.balanced = 0;         //Leftsub will be balanced
	rightsub.balanced = 0;        //Rightsub will be balanced.
	break;
      }
      rightRotate(rightsub);            //Do a right rotation to move imbalance to outer subtree.
      leftRotate(tree);              //Do a left rotation to correct imbalance.
      return false;                       //Root node height does not increase due to new node.
    }
    return false;
  }
  
  private void delSwap(TreeNode original) {        //Swaps a node in preparation for deletion.
    TreeNode finaln = original.right;            //original has both subtrees
    while(finaln.left != null) finaln=finaln.left;
    TreeNode oldRight=original.right;           //Define temp pointers.
    TreeNode oldLeft=original.left;
    TreeNode oldParent=original.parent;
    original.left = null;                           //Fix original pointers.
    original.right = finaln.right;
    if(finaln.parent != original) original.parent = finaln.parent;  //Avoid self-reference
    else original.parent=finaln;
    finaln.left = oldLeft;                           //Fix final pointers.
    if(oldRight != finaln) finaln.right = oldRight;
    else finaln.right=original;
    finaln.parent = oldParent;
    if((original.parent).left == finaln) (original.parent).left = original;
    else (original.parent).right = original;
    if(original.right != null) (original.right).parent = original; //Fix parent ptrs of children of swapped.
    if(finaln.left != null) (finaln.left).parent = finaln;
    if(finaln.right != null) (finaln.right).parent = finaln;
    if(finaln.parent != null) {         //If the top node has a parent, fix its pntrs.
      if((finaln.parent).left == original) (finaln.parent).left = finaln;
      else (finaln.parent).right = finaln;
    }
    else root=finaln;                    //If the parent pointer is NULL, fix the root ptr.
  }
}