include/AD/trees/pagoda.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 pagodas_h
  26 #define pagodas_h
  27
  28 ///////////////////////////////////////////////////////////////////////////
  29 // Class |Pagodas|.
  30 // The algorithm implemented here is in Gonnet's\cite{Algorithms}.
  31 ///////////////////////////////////////////////////////////////////////////
  32
  33 #include <AD/trees/trees.h>
  34
  35 template <class K, class V>
  36    class Pagoda : public BinaryTree<K,V> {
  37       Pagoda(const Pagoda& p);
  38
  39       TrNode<K,V> * merge_tree(TrNode<K,V> *, TrNode<K,V> *);
  40
  41    public:
  42
  43       ///////////////////////////////////////////////////////////////////
  44       //  Constructors and destructor
  45       ///////////////////////////////////////////////////////////////////
  46       Pagoda() {}
  47      ~Pagoda() {}
  48
  49       ///////////////////////////////////////////////////////////////////
  50       //  New mutators
  51       ///////////////////////////////////////////////////////////////////
  52       void clear() { clear2(); }
  53       BinaryNode * insert(const K&, const V&);
  54       BinaryNode * min() const { return tree_root; }
  55       Bool delete_min();
  56       Bool remove(const K&) { error("Pagoda::remove"); }
  57    };
  58
  59 ////////////////////////////////////////////////////////////////////////
  60 // Implementation of the template methods
  61 /////////////////////////////////////////////////////////////////////////
  62
  63 /////////////////////////////////////////////////////////////////////////
  64 //  The most basic operation of pagodas is merging two trees
  65 /////////////////////////////////////////////////////////////////////////
  66 template <class K, class V>
  67    TrNode<K,V> * Pagoda<K,V>::merge_tree(TrNode<K,V> * a, TrNode<K,V> * b)
  68    {  if (a == 0) return b;
  69       if (b == 0) return a;
  70       TrNode<K,V> * bot_a, * bot_b, * r, * temp;
  71       bot_a = (TrNode<K,V>*)a->R; a->R = 0;
  72       bot_b = (TrNode<K,V>*)b->L; b->L = 0;
  73       r = 0;
  74       while (bot_a != 0 && bot_b != 0) {
  75          if (compare(bot_a->key, bot_b->key) > 0) {
  76             temp = (TrNode<K,V>*)bot_a->R;
  77             if (r == 0) bot_a->R = bot_a;
  78             else { bot_a->R = r->R; r->R = bot_a; }
  79             r = bot_a; bot_a = temp;
  80          } else {
  81             temp = (TrNode<K,V>*)bot_b->L;
  82             if (r == 0) bot_b->L = bot_b;
  83             else { bot_b->L = r->L; r->L = bot_b; }
  84             r = bot_b; bot_b = temp;
  85          }
  86       }
  87       if (bot_b == 0) { a->R = r->R; r->R = bot_a; return a; }
  88       else            { b->L = r->L; r->L = bot_b; return b; }
  89    }
  90
  91 /////////////////////////////////////////////////////////////////////////
  92 // Pagoda insertion
  93 /////////////////////////////////////////////////////////////////////////
  94 template <class K, class V>
  95    BinaryNode * Pagoda<K,V>::insert(const K& key, const V& value)
  96    {  TrNode<K,V> * P = new TrNode<K,V>(key,value);
  97       P->L = P; P->R = P;
  98       count++;
  99       tree_root = merge_tree((TrNode<K,V>*)tree_root,P);
 100       return P;
 101    }
 102
 103 /////////////////////////////////////////////////////////////////////////
 104 // Pagoda deletion
 105 /////////////////////////////////////////////////////////////////////////
 106 template <class K, class V>
 107    Bool Pagoda<K,V>::delete_min()
 108    {  if (tree_root) {
 109          TrNode<K,V> * P = (TrNode<K,V>*)tree_root;
 110          BinaryNode * l, * r;
 111          if (P->L == P) l = 0;
 112          else { for (l = P->L; l->L != P; l = l->L); l->L = P->L; }
 113          if (P->R == P) r = 0;
 114          else { for (r = P->R; r->R != P; r = r->R); r->R = P->R; }
 115          tree_root = merge_tree((TrNode<K,V>*)l,(TrNode<K,V>*)r);
 116          count--;
 117          delete P;
 118          return true;
 119       } else
 120          return false;
 121    }
 122
 123 #endif