flower/include/pqueue.hh

   1 /*
   2   pqueue.hh -- declare PQueue_ent and PQueue
   3
   4   source file of the Flower Library
   5
   6   (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9
  10 #ifndef PQUEUE_HH
  11 #define PQUEUE_HH
  12 #include "varray.hh"
  13
  14
  15 template<class K, class T>
  16 struct PQueue_ent
  17 {
  18     T val;
  19     K key;
  20 };
  21
  22 template<class K, class T>
  23 int compare (PQueue_ent<K,T> const &e1 , PQueue_ent<K,T> const &e2) {
  24     return compare(e1.key , e2.key);
  25 }
  26
  27 /**
  28   Priority queue using a (variable size) in-situ heap.
  29
  30   Hungarian postfix pq
  31
  32  */
  33 template<class T>
  34 class PQueue {
  35     Array<T> heap_arr_;
  36     T &elt(int i) {
  37         return heap_arr_[i-1];
  38     }
  39     T const&elt(int i) const {
  40         return heap_arr_[i-1];
  41     }
  42 public:
  43     /** acces an heap element.  Careful with this, as changing the
  44       priority might fuck up the invariants
  45
  46       @param 1 <= i < size() */
  47     T& operator[](int i) { return heap_arr_[i]; }
  48     T operator[](int i) const { return heap_arr_[i]; }
  49     void OK() const
  50     {
  51 #ifndef NDEBUG
  52         for (int i =2; i <= size(); i++)
  53             assert(compare (elt(i/2), elt(i)) <= 0);
  54 #endif
  55     }
  56     T front () const { return elt(1); }
  57     int size() const { return heap_arr_.size(); }
  58     void insert(T v) {
  59         heap_arr_.push(v);
  60         int i = heap_arr_.size();
  61         int j = i / 2 ;
  62         while (j) {
  63             if (compare(elt(j), v) > 0) {
  64                 elt(i) = elt(j);
  65                 i = j;
  66                 j = i/2;
  67             } else {
  68                 break;
  69             }
  70         }
  71         elt(i) = v;
  72         OK();
  73     }
  74     T max() const {
  75         int first_leaf_i = size();
  76         T max_t;
  77         return max_t;
  78     }
  79     void delmin( ) {
  80         assert(size());
  81         T last = heap_arr_.top();
  82
  83         int mini=2;
  84         int lasti=1;
  85
  86         while ( mini < size() ) {
  87             if (compare(elt(mini + 1), elt(mini)) <0)
  88                 mini++;
  89             if (compare(last,elt(mini) ) < 0)
  90                 break;
  91             elt(lasti) = elt(mini);
  92             lasti = mini;
  93             mini *= 2;
  94         }
  95         elt(lasti) = last;
  96         heap_arr_.pop();
  97         OK();
  98     }
  99     T get() {
 100         T t = front();
 101         delmin();
 102         return t;
 103     }
 104 };
 105
 106
 107 #endif // PQUEUE_HH