import cs_1c.FHs_treeNode;
import cs_1c.FHsearch_tree;

public class FHsplayTree<E extends Comparable< ? super E > >
extends FHsearch_tree<E>
{
   public boolean insert(E x)
   {
      int compareResult;
      FHs_treeNode tempNode;

      if (mRoot == null)
      {
         mSize++;
         mRoot = new FHs_treeNode(x, null, null);
         return true;
      }

      tempNode = splay(mRoot, x);

      compareResult = x.compareTo(mRoot.data);

      if ( compareResult < 0 )
      {
         FHs_treeNode newNode = new FHs_treeNode(x, tempNode.lftChild, mRoot);
         mRoot = newNode;
         mSize++;
         return true;
      }
      else if ( compareResult > 0 )
      {
         FHs_treeNode newNode = new FHs_treeNode(x, mRoot, tempNode.rtChild);
         mRoot = newNode;
         mSize++;
         return true;
      }
      else
         return false; // duplicate
   }

   public boolean remove( E x )
   {
      FHs_treeNode newRoot;

      if (mRoot == null)
      {
         return false;
      }

      newRoot = splay(mRoot, x);

      if (mRoot != x)
         return false;
      if (mRoot.lftChild == null)
         newRoot = mRoot.rtChild;

      else
      {
         newRoot = mRoot.lftChild;
         newRoot = splay(newRoot, x);
         newRoot.rtChild = mRoot.rtChild;
      }

      mRoot = newRoot;
      return true;
   }

   public E showRoot()
   {
      if (mRoot == null)
         return null;
      return mRoot.data;
   }

   FHs_treeNode<E> splay( FHs_treeNode<E> root, E x )
   {
      FHs_treeNode rtTree = null;
      FHs_treeNode lftTree = null;
      FHs_treeNode rtTreeMin = null;
      FHs_treeNode lftTreeMax = null;
      int compareResult;

      while (root != null)
      {
         compareResult = x.compareTo(root.data);

         if (compareResult < 0)
         {
            if (root.lftChild == null)
               break;

            //Zig Zig left
            if (x.compareTo(root.lftChild.data) < 0)
            {
               root = rotateWithLeftChild(root);
               if (root.lftChild == null)
                  break;
            }

            rtTreeMin.lftChild = root;
            rtTreeMin = root;
            root = root.lftChild;
         }

         else if (compareResult > 0)
         {
            if (root.rtChild == null)
               break;

            //Zig Zig right
            if (x.compareTo(root.rtChild.data) < 0)
            {
               root = rotateWithRightChild(root);
               if (root.lftChild == null)
                  break;
            }

            lftTreeMax.rtChild = root;
            lftTreeMax = root;
            root = root.rtChild;
         }
         else
            break;
      }

      if (lftTree != null)
      {
         lftTreeMax.lftChild = root.lftChild;
         root.lftChild = lftTree;
      }

      if (rtTree != null)
      {
         rtTreeMin.rtChild = root.rtChild;
         root.rtChild = rtTree;
      }
      return root;
   }

   FHs_treeNode<E> rotateWithLeftChild( FHs_treeNode<E> k2 )
   {
      FHs_treeNode<E> k1 = k2.lftChild;
      k2.lftChild = k1.rtChild;
      k1.rtChild = k2;
      return k1;
   }

   FHs_treeNode<E> rotateWithRightChild( FHs_treeNode<E> k2 )
   {
      FHs_treeNode<E> k1 = k2.rtChild;
      k2.rtChild = k1.lftChild;
      k1.lftChild = k2;
      return k1;
   }

   protected FHs_treeNode<E> find( FHs_treeNode<E> root, E x )
   {
      if (mRoot == null)
         return null;
      FHs_treeNode retRoot = splay (mRoot, x);
      if (retRoot.data == x)
         return retRoot;
      return null;
   }
}