include/AD/trees/splay.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef splay_trees_h
  26 #define splay_trees_h
  27
  28 /////////////////////////////////////////////////////////////////////////////
  29 //  Class |SplayTree| implements, of course, splay trees.  Splay trees
  30 //  are due to Sleator and Tarjan (JACM 1985.)
  31 /////////////////////////////////////////////////////////////////////////////
  32 #include <AD/trees/trees.h>
  33
  34 template <class K, class V>
  35    class SplayTree : public BinaryTree<K,V> {
  36       SplayTree(const SplayTree& t);
  37
  38       Bool found;         // have we found the key???
  39       int  last_compare;  // last comparison result
  40       TrNode<K,V> * P;    // target of splaying
  41
  42       enum Direction { N, L, R };
  43       int           splay (int, TrNode<K,V> *&, const K&, Bool inf = false);
  44       TrNode<K,V> * concat(TrNode<K,V> *, TrNode<K,V> *);
  45
  46    public:
  47
  48       ////////////////////////////////////////////////////////////////////
  49       // Constructors and destructor
  50       ////////////////////////////////////////////////////////////////////
  51       inline  SplayTree() {}
  52       inline ~SplayTree() {}
  53
  54       ////////////////////////////////////////////////////////////////////
  55       // New mutators
  56       ////////////////////////////////////////////////////////////////////
  57       BinaryNode * lookup(const K&) const;
  58       BinaryNode * insert(const K&, const V&);
  59       Bool remove(const K&);
  60    };
  61
  62 //////////////////////////////////////////////////////////////////////////
  63 //  Implemetation of the template methods
  64 //////////////////////////////////////////////////////////////////////////
  65
  66 //////////////////////////////////////////////////////////////////////////
  67 //  Lookup a key
  68 //////////////////////////////////////////////////////////////////////////
  69 template <class K, class V>
  70    BinaryNode * SplayTree<K,V>::lookup(const K& key) const
  71    {  ////////////////////////////////////////////////////////////////////
  72       // Get around the fact that lookup() is a const member function
  73       ////////////////////////////////////////////////////////////////////
  74       SplayTree<K,V> * self = (SplayTree<K,V> *)this;
  75
  76       self->found = false;
  77       self->splay(N,(TrNode<K,V>*&)self->tree_root,key);
  78       self->tree_root = P;
  79       return found ? tree_root : 0;
  80    }
  81
  82 //////////////////////////////////////////////////////////////////////////
  83 //  Insert a key
  84 //////////////////////////////////////////////////////////////////////////
  85 template <class K, class V>
  86    BinaryNode * SplayTree<K,V>::insert(const K& key, const V& value)
  87    {  found = false;
  88       splay(N,(TrNode<K,V> *&)tree_root,key);
  89       if (found) {
  90          P->value = value;
  91          tree_root = P;
  92          return P;
  93       } else {
  94          TrNode<K,V> * T = new TrNode<K,V>(key,value);
  95          if (P) {
  96             if (last_compare > 0) {  // new cell to the right
  97                if (! P->is_right_threaded()) {
  98                   T->R = P->R; T->clear_rthread();
  99                   P->set_rthread();
 100                   BinaryNode * R;
 101                   for (R = P->R; ! R->is_left_threaded(); R = R->L);
 102                   R->set_lthread(); R->L = T;
 103                }
 104                T->clear_lthread();
 105                T->L = P;
 106                P->R = T;
 107             } else {                 // new cell to the left
 108                if (! P->is_left_threaded()) {
 109                   T->L = P->L; T->clear_lthread();
 110                   P->set_lthread();
 111                   BinaryNode * L;
 112                   for (L = P->L; ! L->is_right_threaded(); L = L->R);
 113                   L->set_rthread(); L->R = T;
 114                }
 115                T->clear_rthread();
 116                T->R = P;
 117                P->L = T;
 118             }
 119          }
 120          tree_root = T;
 121          count++;
 122          return T;
 123       }
 124    }
 125
 126 //////////////////////////////////////////////////////////////////////////
 127 // Delete a key
 128 //////////////////////////////////////////////////////////////////////////
 129 template <class K, class V>
 130    Bool SplayTree<K,V>::remove(const K& key)
 131    {  found = false;
 132       splay(N,(TrNode<K,V>*&)tree_root,key);
 133       if (! found) return false;
 134       //////////////////////////////////////////////////////////
 135       // Unlink threads
 136       //////////////////////////////////////////////////////////
 137       BinaryNode * L = (BinaryNode*)prev(P);
 138       BinaryNode * R = (BinaryNode*)next(P);
 139       if (L) L->R = R;
 140       if (R) R->L = L;
 141       //////////////////////////////////////////////////////////
 142       // remove node
 143       //////////////////////////////////////////////////////////
 144       L = P->L; R = P->R;
 145       delete P;
 146       //////////////////////////////////////////////////////////
 147       // Splay left side to make right child nil
 148       //////////////////////////////////////////////////////////
 149       if (L == 0) tree_root = R;
 150       else if (R == 0) tree_root = L;
 151       else {
 152          splay(N,(TrNode<K,V>*&)L,key,true);
 153          L->clear_rthread(); L->R = R;
 154          tree_root = L;
 155       }
 156       count--;
 157       return true;
 158    }
 159
 160 //////////////////////////////////////////////////////////////////////////
 161 //  Splay a tree.
 162 //
 163 //  As usually, the bookkeeping due to threading makes things a bit more
 164 //  complicated.  But it is still a lot simpler than height balanced trees.
 165 //////////////////////////////////////////////////////////////////////////
 166 template <class K, class V>
 167    int SplayTree<K,V>::splay(int d, TrNode<K,V> *& T, const K& key, Bool inf)
 168    {  if (T == 0) { P = T; return N; }
 169       int r = inf ? 1 : compare(key,T->key);
 170       if (r == 0) { found = true; last_compare = r; P = T; return N; }
 171       if (r > 0) {
 172          if (T->is_right_threaded()) { last_compare = r; P = T; return N; }
 173          switch (splay(R,(TrNode<K,V>*&)T->R,key,inf)) {
 174             case N: if (d == N) { T = (TrNode<K,V>*)lrot(T); return N; }
 175                     else return R;
 176             case R: T = (TrNode<K,V>*)lrot(T);
 177                     T = (TrNode<K,V>*)lrot(T); return N;
 178             case L: T->R = (TrNode<K,V> *)rrot(T->R);
 179                     T = (TrNode<K,V> *)lrot(T); return N;
 180          }
 181       } else {
 182          if (T->is_left_threaded()) { last_compare = r; P = T; return N; }
 183          switch (splay(L,(TrNode<K,V>*&)T->L,key,inf)) {
 184             case N: if (d == N) { T = (TrNode<K,V>*)rrot(T); return N; }
 185                     else return L;
 186             case L: T = (TrNode<K,V>*)rrot(T);
 187                     T = (TrNode<K,V>*)rrot(T); return N;
 188             case R: T->L = (TrNode<K,V>*)lrot(T->L);
 189                     T = (TrNode<K,V>*)rrot(T); return N;
 190          }
 191       }
 192       return d;
 193    }
 194
 195 #endif