/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

/*
 * ÉìÕ¹Ê÷
 * »ùÓÚBSTreeµÄÀ©³ä
 */

package dsa;

public class SplayTree extends BSTree implements Dictionary {
   /**************************** ¹¹Ôì·½·¨ ****************************/
   public SplayTree() { super(); }
   public SplayTree(BinTreePosition r) { super(r); }
   public SplayTree(BinTreePosition r, Comparator c) { super(r, c); }

   /**************************** ´Êµä·½·¨£¨¸²¸Ç¸¸ÀàBSTree£© ****************************/
   //Èô´ÊµäÖÐ´æÔÚÒÔkeyÎª¹Ø¼üÂëµÄÌõÄ¿£¬Ôò·µ»ØÆäÖÐµÄÒ»¸öÌõÄ¿£»·ñÔò£¬·µ»Ønull
   public Entry find(Object key) {
      if (isEmpty()) return null;
      BSTreeNode u = binSearch((BSTreeNode)root, key, C);
      root = moveToRoot(u);
      return (0 == C.compare(key, u.getKey())) ? (Entry)u.getElem() : null;
   }

   //²åÈëÌõÄ¿(key, value)£¬²¢·µ»Ø¸ÃÌõÄ¿
   public Entry insert(Object key, Object value) {
      Entry e = super.insert(key, value);//µ÷ÓÃ¸¸Àà·½·¨Íê³É²åÈë
      root = moveToRoot(lastV);//ÖØÐÂÆ½ºâ»¯
      return e;
   }

   //Èô´ÊµäÖÐ´æÔÚÒÔkeyÎª¹Ø¼üÂëµÄÌõÄ¿£¬Ôò½«Õª³ýÆäÖÐµÄÒ»¸ö²¢·µ»Ø£»·ñÔò£¬·µ»Ønull
   public Entry remove(Object key) {
      Entry e = super.remove(key);//µ÷ÓÃ¸¸Àà·½·¨Íê³ÉÉ¾³ý
      if (null != e && null != lastV)  root = moveToRoot(lastV);//ÖØÐÂÆ½ºâ»¯
      return e;
   }

   /**************************** ¸¨Öú·½·¨ ****************************/
   //´Ó½Úµãz¿ªÊ¼£¬×ÔÉÏ¶øÏÂÖØÐÂÆ½ºâ»¯
   protected static BinTreePosition moveToRoot(BinTreePosition z) {
      while (z.hasParent())
         if (!z.getParent().hasParent())
            if (z.isLChild()) z = zig(z);
            else                    z = zag(z);
         else if (z.isLChild())
            if (z.getParent().isLChild()) z = zigzig(z);
            else                                      z = zigzag(z);
         else if (z.getParent().isLChild()) z = zagzig(z);
         else                                      z = zagzag(z);
      return z;
   }

   //vÎª×óº¢×Ó
   //Ë³Ê±ÕëÐý×ªv£¬Ê¹Ö®ÉÏÉýÒ»²ã£¨ÉìÕ¹Ê÷£©
   //·µ»ØÐÂµÄ×ÓÊ÷¸ù
   protected static BinTreePosition zig(BinTreePosition v) {
      if (null != v && v.isLChild()) {//v±ØÐëÓÐ¸¸Ç×£¬¶øÇÒ±ØÐëÊÇ×óº¢×Ó
         BinTreePosition p = v.getParent();//¸¸Ç×
         BinTreePosition g = p.getParent();//×æ¸¸
         boolean asLChild = p.isLChild();//¸¸Ç×ÊÇ·ñ×æ¸¸µÄ×óº¢×Ó
         v.secede();//Õª³öv£¨ÓÚÊÇpµÄ×óº¢×ÓÎª¿Õ£©
         BinTreePosition c = v.getRChild();//½«vµÄÓÒº¢×Ó
         if (null != c) p.attachL(c.secede());//×÷ÎªpµÄ×óº¢×Ó
         p.secede();//Õª³ö¸¸Ç×
         v.attachR(p);//½«p×÷ÎªvµÄÓÒº¢×Ó
         if (null != g)//Èô×æ¸¸´æÔÚ£¬Ôò½«v×÷ÎªÆäº¢×Ó
            if (asLChild)  g.attachL(v);
            else              g.attachR(v);
      }
      return v;
   }

   //vÎªÓÒº¢×Ó
   //ÄæÊ±ÕëÐý×ªv£¬Ê¹Ö®ÉÏÉýÒ»²ã£¨ÉìÕ¹Ê÷£©
   //·µ»ØÐÂµÄ×ÓÊ÷¸ù
   protected static BinTreePosition zag(BinTreePosition v) {
      if (null != v && v.isRChild()) {//v±ØÐëÓÐ¸¸Ç×£¬¶øÇÒ±ØÐëÊÇÓÒº¢×Ó
         BinTreePosition p = v.getParent();//¸¸Ç×
         BinTreePosition g = p.getParent();//×æ¸¸
         boolean asLChild = p.isLChild();//¸¸Ç×ÊÇ·ñ×æ¸¸µÄ×óº¢×Ó
         v.secede();//Õª³öv£¨ÓÚÊÇpµÄ×óº¢×ÓÎª¿Õ£©
         BinTreePosition c = v.getLChild();//½«vµÄ×óº¢×Ó
         if (null != c) p.attachR(c.secede());//×÷ÎªpµÄÓÒº¢×Ó
         p.secede();//Õª³ö¸¸Ç×
         v.attachL(p);//½«p×÷ÎªvµÄ×óº¢×Ó
         if (null != g)//Èô×æ¸¸´æÔÚ£¬Ôò½«v×÷ÎªÆäº¢×Ó
            if (asLChild)  g.attachL(v);
            else              g.attachR(v);
      }
      return v;
   }

   //vÎª×óº¢×Ó£¬¸¸Ç×Îª×óº¢×Ó
   //Ë³Ê±ÕëÐý×ªv£¬Ê¹Ö®ÉÏÉýÁ½²ã£¨ÉìÕ¹Ê÷£©
   //·µ»ØÐÂµÄ×ÓÊ÷¸ù
   protected static BinTreePosition zigzig(BinTreePosition v) {
      if (null != v && v.isLChild() && v.hasParent() && v.getParent().isLChild()) {
         BinTreePosition p = v.getParent();//¸¸Ç×
         BinTreePosition g = p.getParent();//×æ¸¸
         BinTreePosition s = g.getParent();//Ôø×æ¸¸
         boolean asLChild = g.isLChild();//×æ¸¸ÊÇ·ñÔø×æ¸¸µÄ×óº¢×Ó
         g.secede();
         p.secede();
         v.secede();
         BinTreePosition c;//ÁÙÊ±±äÁ¿£¬¸¨Öúº¢×ÓµÄÒÆ¶¯
         c = p.getRChild(); if (null != c)   g.attachL(c.secede());//pµÄÓÒº¢×Ó×÷ÎªgµÄ×óº¢×Ó
         c = v.getRChild(); if (null != c)   p.attachL(c.secede());//vµÄÓÒº¢×Ó×÷ÎªpµÄ×óº¢×Ó
         p.attachR(g);//g×÷ÎªpµÄÓÒº¢×Ó
         v.attachR(p);//p×÷ÎªvµÄÓÒº¢×Ó
         if (null != s)//ÈôÔø×æ¸¸´æÔÚ£¬Ôò½«v×÷ÎªÆäº¢×Ó
            if (asLChild)  s.attachL(v);
            else              s.attachR(v);
      }
      return v;
   }

   //vÎªÓÒº¢×Ó£¬¸¸Ç×ÎªÓÒº¢×Ó
   //Ë³Ê±ÕëÐý×ªv£¬Ê¹Ö®ÉÏÉýÁ½²ã£¨ÉìÕ¹Ê÷£©
   //·µ»ØÐÂµÄ×ÓÊ÷¸ù
   protected static BinTreePosition zagzag(BinTreePosition v) {
      if (null != v && v.isRChild() && v.hasParent() && v.getParent().isRChild()) {
         BinTreePosition p = v.getParent();//¸¸Ç×
         BinTreePosition g = p.getParent();//×æ¸¸
         BinTreePosition s = g.getParent();//Ôø×æ¸¸
         boolean asLChild = g.isLChild();//×æ¸¸ÊÇ·ñÔø×æ¸¸µÄ×óº¢×Ó
         g.secede();
         p.secede();
         v.secede();
         BinTreePosition c;//ÁÙÊ±±äÁ¿£¬¸¨Öúº¢×ÓµÄÒÆ¶¯
         c = p.getLChild(); if (null != c)   g.attachR(c.secede());//pµÄ×óº¢×Ó×÷ÎªgµÄÓÒº¢×Ó
         c = v.getLChild(); if (null != c)   p.attachR(c.secede());//vµÄ×óº¢×Ó×÷ÎªpµÄÓÒº¢×Ó
         p.attachL(g);//g×÷ÎªpµÄ×óº¢×Ó
         v.attachL(p);//p×÷ÎªvµÄ×óº¢×Ó
         if (null != s)//ÈôÔø×æ¸¸´æÔÚ£¬Ôò½«v×÷ÎªÆäº¢×Ó
            if (asLChild)  s.attachL(v);
            else              s.attachR(v);
      }
      return v;
   }

   //vÎª×óº¢×Ó£¬¸¸Ç×ÎªÓÒº¢×Ó
   //Ë³Ê±ÕëÐý×ªv£¬Ê¹Ö®ÉÏÉýÁ½²ã£¨ÉìÕ¹Ê÷£©
   //·µ»ØÐÂµÄ×ÓÊ÷¸ù
   protected static BinTreePosition zigzag(BinTreePosition v) {
      if (null != v && v.isLChild() && v.hasParent() && v.getParent().isRChild()) {
         BinTreePosition p = v.getParent();//¸¸Ç×
         BinTreePosition g = p.getParent();//×æ¸¸
         BinTreePosition s = g.getParent();//Ôø×æ¸¸
         boolean asLChild = g.isLChild();//×æ¸¸ÊÇ·ñÔø×æ¸¸µÄ×óº¢×Ó
         g.secede();
         p.secede();
         v.secede();
         BinTreePosition c;//ÁÙÊ±±äÁ¿£¬¸¨Öúº¢×ÓµÄÒÆ¶¯
         c = v.getLChild(); if (null != c)   g.attachR(c.secede());//vµÄ×óº¢×Ó×÷ÎªgµÄÓÒº¢×Ó
         c = v.getRChild(); if (null != c)   p.attachL(c.secede());//vµÄÓÒº¢×Ó×÷ÎªpµÄ×óº¢×Ó
         v.attachL(g);//g×÷ÎªvµÄ×óº¢×Ó
         v.attachR(p);//p×÷ÎªvµÄÓÒº¢×Ó
         if (null != s)//ÈôÔø×æ¸¸´æÔÚ£¬Ôò½«v×÷ÎªÆäº¢×Ó
            if (asLChild)  s.attachL(v);
            else              s.attachR(v);
      }
      return v;
   }

   //vÎªÓÒº¢×Ó£¬¸¸Ç×Îª×óº¢×Ó
   //Ë³Ê±ÕëÐý×ªv£¬Ê¹Ö®ÉÏÉýÁ½²ã£¨ÉìÕ¹Ê÷£©
   //·µ»ØÐÂµÄ×ÓÊ÷¸ù
   protected static BinTreePosition zagzig(BinTreePosition v) {
      if (null != v && v.isRChild() && v.hasParent() && v.getParent().isLChild()) {
         BinTreePosition p = v.getParent();//¸¸Ç×
         BinTreePosition g = p.getParent();//×æ¸¸
         BinTreePosition s = g.getParent();//Ôø×æ¸¸
         boolean asLChild = g.isLChild();//×æ¸¸ÊÇ·ñÔø×æ¸¸µÄ×óº¢×Ó
         g.secede();
         p.secede();
         v.secede();
         BinTreePosition c;//ÁÙÊ±±äÁ¿£¬¸¨Öúº¢×ÓµÄÒÆ¶¯
         c = v.getRChild(); if (null != c)   g.attachL(c.secede());//vµÄÓÒº¢×Ó×÷ÎªgµÄ×óº¢×Ó
         c = v.getLChild(); if (null != c)   p.attachR(c.secede());//vµÄ×óº¢×Ó×÷ÎªpµÄÓÒº¢×Ó
         v.attachR(g);//g×÷ÎªvµÄÓÒº¢×Ó
         v.attachL(p);//p×÷ÎªvµÄ×óº¢×Ó
         if (null != s)//ÈôÔø×æ¸¸´æÔÚ£¬Ôò½«v×÷ÎªÆäº¢×Ó
            if (asLChild)  s.attachL(v);
            else              s.attachR(v);
      }
      return v;
   }
}