include/AD/trees/redblack.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 red_black_trees_h
  26 #define red_black_trees_h
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 //  Invariants:
  30 //     (1) the number of black links from each path from the root to
  31 //         a leaf is the same.
  32 //     (2) no red links may be followed by another red link.
  33 //////////////////////////////////////////////////////////////////////////////
  34
  35 #include <AD/trees/trees.h>
  36
  37 template <class K, class V>
  38    class RBTree : public BinaryTree<K,V> {
  39
  40       TrNode<K,V> * split(const K&, TrNode<K,V> *, TrNode<K,V> *,
  41                           TrNode<K,V> *, TrNode<K,V> *);
  42       TrNode<K,V> * rotate(const K&, TrNode<K,V> *);
  43
  44    public:
  45
  46       ///////////////////////////////////////////////////////////////////////
  47       //  Constructor and destructor
  48       ///////////////////////////////////////////////////////////////////////
  49       RBTree() {}
  50       RBTree(RBTree& t) { *this = t; }
  51      ~RBTree() {}
  52
  53       ///////////////////////////////////////////////////////////////////////
  54       // Assignment
  55       ///////////////////////////////////////////////////////////////////////
  56       // void operator = (RBTree&); // inherited
  57
  58       ///////////////////////////////////////////////////////////////////////
  59       // Mutators
  60       ///////////////////////////////////////////////////////////////////////
  61       Ix   insert(const K&, const V&);
  62       Bool remove(const K&);
  63
  64       ///////////////////////////////////////////////////////////////////////
  65       // Iterators
  66       ///////////////////////////////////////////////////////////////////////
  67       // inherited
  68    };
  69
  70 /////////////////////////////////////////////////////////////////////////////
  71 // Implementation of the template methods
  72 /////////////////////////////////////////////////////////////////////////////
  73
  74 /////////////////////////////////////////////////////////////////////////////
  75 // Tree insertion.
  76 /////////////////////////////////////////////////////////////////////////////
  77 template <class K, class V>
  78    Ix RBTree<K,V>::insert(const K& key, const V& value)
  79    {  TrNode<K,V> * gg, * g, * p, * x;
  80       p = g = x = (TrNode<K,V>*)tree_root;
  81       for(;;) {
  82          gg = g; g = p; p = x;
  83          int r = compare(key,x->key);
  84          if (r == 0 && ! duplicates_allowed) { x->value = value; return; }
  85          if (r < 0) if (x->is_left_threaded()) break;
  86                     else x = (TrNode<K,V>*)x->L;
  87          else       if (x->is_right_threaded()) break;
  88                     else x = (TrNode<K,V>*)x->R;
  89          if (x == 0) break;
  90          if (x->thread() == No_thread && x->L->is_red() && x->R->is_red())
  91             x = split(key,gg,g,p,x);
  92       }
  93       count++;
  94       x = new TrNode<K,V> (key,value);
  95       if (r < 0) p->L = x; else p->R = x;
  96       x = split(key,gg,g,p,x);
  97    }
  98
  99 /////////////////////////////////////////////////////////////////////////////
 100 //
 101 /////////////////////////////////////////////////////////////////////////////
 102 template <class K, class V>
 103    Bool RBTree<K,V>::remove(const K& key)
 104    {
 105    }
 106
 107 /////////////////////////////////////////////////////////////////////////////
 108 //
 109 /////////////////////////////////////////////////////////////////////////////
 110 template <class K, class V>
 111    TrNode<K,V> * RBTree<K,V>::split
 112       (const K& key, TrNode<K,V> * gg,
 113        TrNode<K,V> * g, TrNode<K,V> * p, TrNode<K,V> * x)
 114    {
 115    }
 116
 117 /////////////////////////////////////////////////////////////////////////////
 118 //
 119 /////////////////////////////////////////////////////////////////////////////
 120 template <class K, class V>
 121    TrNode<K,V> * RBTree<K,V>::rotate(const K&, TrNode<K,V> *)
 122    {  TrNode<K,V> * c, * gc;
 123    }
 124
 125 #endif