include/AD/trees/leftist.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 leftist_trees_h
  26 #define leftist_trees_h
  27
  28 ///////////////////////////////////////////////////////////////////////////
  29 // Class |LeftistTree| can be used to implement priority queues
  30 ///////////////////////////////////////////////////////////////////////////
  31
  32 #include <AD/trees/trees.h>
  33
  34 ///////////////////////////////////////////////////////////////////////////
  35 //  Forward class declarations
  36 ///////////////////////////////////////////////////////////////////////////
  37 template <class K, class V> class LeftistNode;
  38 template <class K, class V> class LeftistTree;
  39
  40 ///////////////////////////////////////////////////////////////////////////
  41 //  A leftist node also holds the node distance
  42 ///////////////////////////////////////////////////////////////////////////
  43 template <class K, class V>
  44    class LeftistNode : public TrNode<K,V> {
  45       int dist;
  46       friend class LeftistTree<K,V>;
  47    public:
  48       LeftistNode(const K& k, const V& v) : dist(1), TrNode<K,V>(k,v) {}
  49      ~LeftistNode() {}
  50    };
  51
  52 ///////////////////////////////////////////////////////////////////////////
  53 //  The tree class
  54 ///////////////////////////////////////////////////////////////////////////
  55 template <class K, class V>
  56    class LeftistTree : public BinaryTree<K,V> {
  57       LeftistTree(const LeftistTree& p);
  58
  59       LeftistNode<K,V> * leftist_union(LeftistNode<K,V> *, LeftistNode<K,V> *);
  60
  61    public:
  62
  63       ///////////////////////////////////////////////////////////////////
  64       //  Constructors and destructor
  65       ///////////////////////////////////////////////////////////////////
  66       LeftistTree() {}
  67      ~LeftistTree() {}
  68
  69       ///////////////////////////////////////////////////////////////////
  70       //  New mutators
  71       ///////////////////////////////////////////////////////////////////
  72       void clear() { clear2(); }
  73       BinaryNode * insert(const K&, const V&);
  74       BinaryNode * min() const { return tree_root; }
  75       Bool delete_min();
  76       Bool remove(const K&) { error("LeftistTree<K,V>::remove"); }
  77    };
  78
  79 ////////////////////////////////////////////////////////////////////////
  80 //  Implementation of the template methods
  81 ////////////////////////////////////////////////////////////////////////
  82
  83 ////////////////////////////////////////////////////////////////////////
  84 //  Merge two leftist trees together
  85 ////////////////////////////////////////////////////////////////////////
  86 template <class K, class V>
  87    LeftistNode<K,V> *
  88       LeftistTree<K,V>::leftist_union(LeftistNode<K,V>* A, LeftistNode<K,V>* B)
  89    {
  90       /////////////////////////////////////////////////////////////////////
  91       // Base conditions
  92       /////////////////////////////////////////////////////////////////////
  93       if (A == 0) return B;
  94       if (B == 0) return A;
  95       /////////////////////////////////////////////////////////////////////
  96       //  Make sure the root is the smaller element
  97       /////////////////////////////////////////////////////////////////////
  98       if (compare(A->key, B->key) > 0)
  99          { LeftistNode<K,V> * C = A; A = B; B = C; }
 100
 101       /////////////////////////////////////////////////////////////////////
 102       //  Now merge recursively
 103       /////////////////////////////////////////////////////////////////////
 104       A->R = leftist_union((LeftistNode<K,V>*)(A->R),B);
 105
 106       /////////////////////////////////////////////////////////////////////
 107       //  Make sure the left side is taller; we're leftists.
 108       /////////////////////////////////////////////////////////////////////
 109       if (A == 0 || A->dist < ((LeftistNode<K,V>*)(A->R))->dist)
 110          { BinaryNode * t = A->L; A->L = A->R; A->R = t; }
 111
 112       /////////////////////////////////////////////////////////////////////
 113       //  Finally, update the distance
 114       /////////////////////////////////////////////////////////////////////
 115       if (A->L == 0) A->dist = 1;
 116       else {
 117          int m = ((LeftistNode<K,V>*)A->L)->dist;
 118          int n = ((LeftistNode<K,V>*)A->R)->dist;
 119          A->dist = 1 + (m < n ? m : n);
 120       }
 121       return A;
 122    }
 123
 124 ////////////////////////////////////////////////////////////////////////
 125 //  Tree insertion
 126 ////////////////////////////////////////////////////////////////////////
 127 template <class K, class V>
 128    BinaryNode * LeftistTree<K,V>::insert(const K& key, const V& value)
 129    {  LeftistNode<K,V> * P = new LeftistNode<K,V>(key,value);
 130       tree_root = leftist_union((LeftistNode<K,V>*)tree_root,P);
 131       count++;
 132       return P;
 133    }
 134
 135 ////////////////////////////////////////////////////////////////////////
 136 //  Tree deletion
 137 ////////////////////////////////////////////////////////////////////////
 138 template <class K, class V>
 139    Bool LeftistTree<K,V>::delete_min()
 140    {  LeftistNode<K,V> * T = (LeftistNode<K,V>*)tree_root;
 141       if (T) {
 142          tree_root = leftist_union((LeftistNode<K,V>*)(T->L),
 143                                    (LeftistNode<K,V>*)(T->R));
 144          count--;
 145          delete T;
 146          return true;
 147       } else return false;
 148    }
 149
 150 #endif