release: 1.0.1

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

diff --git a/flower/include/pqueue.hh b/flower/include/pqueue.hh
index c8dfe1bea6754f8786e8460e9b91231c02733b01..ba48993ccb94028f4e24adb171dc2512b8a78733 100644 (file)
--- a/flower/include/pqueue.hh
+++ b/flower/include/pqueue.hh
@@ -1,72 +1,109 @@
 /*
-  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--1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
 */
 
 
 #ifndef PQUEUE_HH
 #define PQUEUE_HH
+#include "array.hh"
 
-#include "varray.hh"
+
+template<class K, class T>
+struct PQueue_ent
+{
+    T val;
+    K key;
+};
+
+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
+  
+  TODO: add increase/decrease operations,
+  add max() operation
  */
+template<class T>
+class PQueue {
+    Array<T> heap_arr_;
+    T &elt (int i) {
+       return heap_arr_[i-1];
+    }
+    T const&elt (int i) const {
+       return heap_arr_[i-1];
+    }
+public:
+    /** acces an heap element.  Careful with this, as changing the
+      priority might fuck up the invariants
 
-template<class V, class I>
-struct PQueue
-{
-    Array<V> value_arr_;
-    Array<I> indices_arr_;
-    void OK() const 
+      @param 1 <= i < size() */
+    T& operator[](int i) { return heap_arr_[i]; }
+    T operator[](int i) const { return heap_arr_[i]; }
+    void OK() const
     {
-       
-       assert(value_arr_.size() == indices_arr_.size());
+#ifndef NDEBUG
+       for (int i =2; i <= size(); i++)
+           assert (compare (elt (i/2), elt (i)) <= 0);
+#endif
     }
-    
-    void enter(V v, I idx) {
-       int j=0;
-       for (; j < value_arr_.size(); j++)
-           if (indices_arr_[j] > idx) 
+    T front() const { return elt (1); }
+    int size() const { return heap_arr_.size (); }
+    void insert (T v) {
+       heap_arr_.push (v);
+       int i = heap_arr_.size();
+       int j = i / 2 ;
+       while (j) {
+           if (compare (elt (j), v) > 0) {
+               elt (i) = elt (j);      
+               i = j;
+               j = i/2;
+           } else {
                break;
-
-       insert(j,v,idx);
-       
+           }
+       }
+       elt (i) = v;
+       OK();
     }
-    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);
+    T max() const {
+       //int first_leaf_i = size();
+       T max_t;
+       return max_t;
     }
-    int size() const
-    {
+    void delmin() {
+       assert (size());
+       T last = heap_arr_.top();
+       
+       int mini=2;
+       int lasti=1;
+
+       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_arr_.pop();
        OK();
-       return value_arr_.size();
     }
-    
-
-    void insert(int j, V v, I idx)
-    {
-       value_arr_.insert(v, j);
-       indices_arr_.insert(idx, j);
+    T get() { 
+       T t = front();
+       delmin();
+       return t;
     }
-    
+};
 
 
-    V get() {
-       V retval = front_val();
-       del(0);
-       return retval;
-    }
-    
-};
 #endif // PQUEUE_HH