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--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #ifndef PQUEUE_HH
  11 #define PQUEUE_HH
  12 #include "array.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_array_;
  38     T &elt (int i) {
  39         return heap_array_[i-1];
  40     }
  41     T const&elt (int i) const {
  42         return heap_array_[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_array_[i]; }
  50     T operator[] (int i) const { return heap_array_[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_array_.size (); }
  60     void insert (T v) {
  61         heap_array_.push (v);
  62         int i = heap_array_.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_array_.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_array_.pop ();
  99         OK ();
 100     }
 101     T get () {
 102         T t = front ();
 103         delmin ();
 104         return t;
 105     }
 106 };
 107
 108
 109 #endif // PQUEUE_HH