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   TODO: add increase/decrease operations,
  33   add max() operation
  34  */
  35 template<class T>
  36 class PQueue {
  37     Array<T> heap_arr_;
  38     T &elt(int i) {
  39         return heap_arr_[i-1];
  40     }
  41     T const&elt(int i) const {
  42         return heap_arr_[i-1];
  43     }
  44 public:
  45     /** acces an heap element.  Careful with this, as changing the
  46       priority might fuck up the invariants
  47
  48       @param 1 <= i < size() */
  49     T& operator[](int i) { return heap_arr_[i]; }
  50     T operator[](int i) const { return heap_arr_[i]; }
  51     void OK() const
  52     {
  53 #ifndef NDEBUG
  54         for (int i =2; i <= size(); i++)
  55             assert(compare (elt(i/2), elt(i)) <= 0);
  56 #endif
  57     }
  58     T front () const { return elt(1); }
  59     int size() const { return heap_arr_.size(); }
  60     void insert(T v) {
  61         heap_arr_.push(v);
  62         int i = heap_arr_.size();
  63         int j = i / 2 ;
  64         while (j) {
  65             if (compare(elt(j), v) > 0) {
  66                 elt(i) = elt(j);
  67                 i = j;
  68                 j = i/2;
  69             } else {
  70                 break;
  71             }
  72         }
  73         elt(i) = v;
  74         OK();
  75     }
  76     T max() const {
  77         int first_leaf_i = size();
  78         T max_t;
  79         return max_t;
  80     }
  81     void delmin( ) {
  82         assert(size());
  83         T last = heap_arr_.top();
  84
  85         int mini=2;
  86         int lasti=1;
  87
  88         while ( mini < size() ) {
  89             if (compare(elt(mini + 1), elt(mini)) <0)
  90                 mini++;
  91             if (compare(last,elt(mini) ) < 0)
  92                 break;
  93             elt(lasti) = elt(mini);
  94             lasti = mini;
  95             mini *= 2;
  96         }
  97         elt(lasti) = last;
  98         heap_arr_.pop();
  99         OK();
 100     }
 101     T get() {
 102         T t = front();
 103         delmin();
 104         return t;
 105     }
 106 };
 107
 108
 109 #endif // PQUEUE_HH