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--2008 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #ifndef PQUEUE_HH
  10 #define PQUEUE_HH
  11 #include "std-vector.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   vector<T> heap_array_;
  38   T &elt (vsize i)
  39   {
  40     return heap_array_[i - 1];
  41   }
  42   T const &elt (vsize 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 [] (vsize i)
  52   {
  53     return heap_array_[i];
  54   }
  55   T operator [] (vsize i) const
  56   {
  57     return heap_array_[i];
  58   }
  59   void OK () const
  60   {
  61 #ifndef NDEBUG
  62     for (vsize i = 2; i <= size (); i++)
  63       assert (compare (elt (i / 2), elt (i)) <= 0);
  64 #endif
  65   }
  66   T front () const
  67   {
  68     return elt (1);
  69   }
  70   vsize size () const
  71   {
  72     return heap_array_.size ();
  73   }
  74   void insert (T v)
  75   {
  76     heap_array_.push_back (v);
  77     vsize i = heap_array_.size ();
  78     vsize j = i / 2;
  79     while (j)
  80       {
  81         if (compare (elt (j), v) > 0)
  82           {
  83             elt (i) = elt (j);
  84             i = j;
  85             j = i / 2;
  86           }
  87         else
  88           break;
  89       }
  90     elt (i) = v;
  91     OK ();
  92   }
  93   T max () const
  94   {
  95     //int first_leaf_i = size ();
  96     T max_t;
  97     return max_t;
  98   }
  99   void delmin ()
 100   {
 101     assert (size ());
 102     T last = heap_array_.back ();
 103
 104     vsize mini = 2;
 105     vsize lasti = 1;
 106
 107     while (mini < size ())
 108       {
 109         if (compare (elt (mini + 1), elt (mini)) < 0)
 110           mini++;
 111         if (compare (last, elt (mini)) < 0)
 112           break;
 113         elt (lasti) = elt (mini);
 114         lasti = mini;
 115         mini *= 2;
 116       }
 117     elt (lasti) = last;
 118     heap_array_.pop_back ();
 119     OK ();
 120   }
 121   T get ()
 122   {
 123     T t = front ();
 124     delmin ();
 125     return t;
 126   }
 127 };
 128
 129 #endif // PQUEUE_HH