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