release: 1.0.1

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

diff --git a/flower/include/pqueue.hh b/flower/include/pqueue.hh
index dac5be52f3d787b6dd7223e4edada61ebbc8ee68..ba48993ccb94028f4e24adb171dc2512b8a78733 100644 (file)
--- a/flower/include/pqueue.hh
+++ b/flower/include/pqueue.hh
@@ -3,13 +3,13 @@
 
   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 "varray.hh"
+#include "array.hh"
 
 
 template<class K, class T>
@@ -21,7 +21,7 @@ struct PQueue_ent
 
 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);
+    return compare (e1.key , e2.key);
 }
 
 /**
@@ -29,14 +29,16 @@ int compare (PQueue_ent<K,T> const &e1 , PQueue_ent<K,T> const &e2) {
 
   Hungarian postfix pq
   
+  TODO: add increase/decrease operations,
+  add max() operation
  */
 template<class T>
 class PQueue {
     Array<T> heap_arr_;
-    T &elt(int i) {
+    T &elt (int i) {
        return heap_arr_[i-1];
     }
-    T const&elt(int i) const {
+    T const&elt (int i) const {
        return heap_arr_[i-1];
     }
 public:
@@ -50,49 +52,49 @@ public:
     {
 #ifndef NDEBUG
        for (int i =2; i <= size(); i++)
-           assert(compare (elt(i/2), elt(i)) <= 0);
+           assert (compare (elt (i/2), elt (i)) <= 0);
 #endif
     }
-    T front () const { return elt(1); }
-    int size() const { return heap_arr_.size(); }
-    void insert(T v) {
-       heap_arr_.push(v);
+    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);        
+           if (compare (elt (j), v) > 0) {
+               elt (i) = elt (j);      
                i = j;
                j = i/2;
            } else {
                break;
            }
        }
-       elt(i) = v;
+       elt (i) = v;
        OK();
     }
     T max() const {
-       int first_leaf_i = size();
+       //int first_leaf_i = size();
        T max_t;
        return max_t;
     }
-    void delmin( ) {
-       assert(size());
+    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)
+       while (mini < size()) {
+           if (compare (elt (mini + 1), elt (mini)) <0)
                mini++;
-           if (compare(last,elt(mini) ) < 0)
+           if (compare (last,elt (mini)) < 0)
                break;
-           elt(lasti) = elt(mini);
+           elt (lasti) = elt (mini);
            lasti = mini;
            mini *= 2;
        }
-       elt(lasti) = last;
+       elt (lasti) = last;
        heap_arr_.pop();
        OK();
     }