Run `make grand-replace'.

[lilypond.git] / flower / include / pqueue.hh

diff --git a/flower/include/pqueue.hh b/flower/include/pqueue.hh
index c8dfe1bea6754f8786e8460e9b91231c02733b01..fa28ca011d574eec179824653de1368fabcdda97 100644 (file)
--- a/flower/include/pqueue.hh
+++ b/flower/include/pqueue.hh
@@ -1,72 +1,129 @@
 /*
-  pqueue.hh -- declare 
+  pqueue.hh -- declare PQueue_ent and PQueue
 
-  source file of the LilyPond music typesetter
+  source file of the Flower Library
 
-  (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
+  (c) 1997--2008 Han-Wen Nienhuys <hanwen@xs4all.nl>
 */
 
-
 #ifndef PQUEUE_HH
 #define PQUEUE_HH
+#include "std-vector.hh"
+
+template<class K, class T>
+struct PQueue_ent
+{
+  T val;
+  K key;
+};
 
-#include "varray.hh"
+template<class K, class T>
+int compare (PQueue_ent<K, T> const &e1, PQueue_ent<K, T> const &e2)
+{
+  return compare (e1.key, e2.key);
+}
 
 /**
-  Stupid Prioq. Should use Lists and STL.
-  Smallest is put at the front.
+   Priority queue using a (variable size) in-situ heap.
 
-Actually, this sux. Should use a template struct PQuee_ent<V,I>
- */
+   Hungarian postfix pq
 
-template<class V, class I>
-struct PQueue
+   TODO: add increase/decrease operations,
+   add max () operation
+*/
+template<class T>
+class PQueue
 {
-    Array<V> value_arr_;
-    Array<I> indices_arr_;
-    void OK() const 
-    {
-       
-       assert(value_arr_.size() == indices_arr_.size());
-    }
-    
-    void enter(V v, I idx) {
-       int j=0;
-       for (; j < value_arr_.size(); j++)
-           if (indices_arr_[j] > idx) 
-               break;
+  vector<T> heap_array_;
+  T &elt (vsize i)
+  {
+    return heap_array_[i - 1];
+  }
+  T const &elt (vsize i) const
+  {
+    return heap_array_[i - 1];
+  }
+public:
+  /** acces an heap element.  Careful with this, as changing the
+      priority might fuck up the invariants
 
-       insert(j,v,idx);
-       
-    }
-    int size() { return value_arr_.size(); }
-    V front_val() { return value_arr_[0]; }
-    I front_idx() { return indices_arr_[0]; }
-    void del(int i) 
-    {
-       value_arr_.del(i);
-       indices_arr_.del(i);
-    }
-    int size() const
-    {
-       OK();
-       return value_arr_.size();
-    }
-    
+      @param 1 <= i < size () */
+  T &operator [] (vsize i)
+  {
+    return heap_array_[i];
+  }
+  T operator [] (vsize i) const
+  {
+    return heap_array_[i];
+  }
+  void OK () const
+  {
+#ifndef NDEBUG
+    for (vsize i = 2; i <= size (); i++)
+      assert (compare (elt (i / 2), elt (i)) <= 0);
+#endif
+  }
+  T front () const
+  {
+    return elt (1);
+  }
+  vsize size () const
+  {
+    return heap_array_.size ();
+  }
+  void insert (T v)
+  {
+    heap_array_.push_back (v);
+    vsize i = heap_array_.size ();
+    vsize j = i / 2;
+    while (j)
+      {
+       if (compare (elt (j), v) > 0)
+         {
+           elt (i) = elt (j);
+           i = j;
+           j = i / 2;
+         }
+       else
+         break;
+      }
+    elt (i) = v;
+    OK ();
+  }
+  T max () const
+  {
+    //int first_leaf_i = size ();
+    T max_t;
+    return max_t;
+  }
+  void delmin ()
+  {
+    assert (size ());
+    T last = heap_array_.back ();
 
-    void insert(int j, V v, I idx)
-    {
-       value_arr_.insert(v, j);
-       indices_arr_.insert(idx, j);
-    }
-    
+    vsize mini = 2;
+    vsize lasti = 1;
 
-
-    V get() {
-       V retval = front_val();
-       del(0);
-       return retval;
-    }
-    
+    while (mini < size ())
+      {
+       if (compare (elt (mini + 1), elt (mini)) < 0)
+         mini++;
+       if (compare (last, elt (mini)) < 0)
+         break;
+       elt (lasti) = elt (mini);
+       lasti = mini;
+       mini *= 2;
+      }
+    elt (lasti) = last;
+    heap_array_.pop_back ();
+    OK ();
+  }
+  T get ()
+  {
+    T t = front ();
+    delmin ();
+    return t;
+  }
 };
+
 #endif // PQUEUE_HH