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@xs4all.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           break;
  77       }
  78     elt (i) = v;
  79     OK ();
  80   }
  81   T max () const
  82   {
  83     //int first_leaf_i = size ();
  84     T max_t;
  85     return max_t;
  86   }
  87   void delmin ()
  88   {
  89     assert (size ());
  90     T last = heap_array_.top ();
  91
  92     int mini = 2;
  93     int lasti = 1;
  94
  95     while (mini < size ())
  96       {
  97         if (compare (elt (mini + 1), elt (mini)) < 0)
  98           mini++;
  99         if (compare (last, elt (mini)) < 0)
 100           break;
 101         elt (lasti) = elt (mini);
 102         lasti = mini;
 103         mini *= 2;
 104       }
 105     elt (lasti) = last;
 106     heap_array_.pop ();
 107     OK ();
 108   }
 109   T get ()
 110   {
 111     T t = front ();
 112     delmin ();
 113     return t;
 114   }
 115 };
 116
 117 #endif // PQUEUE_HH