Run grand-replace (issue 3765)

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

diff --git a/flower/include/pqueue.hh b/flower/include/pqueue.hh
index cc352cb2da78ea7f4922dd657faed75c174e8cec..0b15f1fef93a039a246547b6d7d159293fc4bd9e 100644 (file)
--- a/flower/include/pqueue.hh
+++ b/flower/include/pqueue.hh
@@ -1,109 +1,140 @@
 /*
-  pqueue.hh -- declare PQueue_ent and PQueue
+  This file is part of LilyPond, the GNU music typesetter.
 
-  source file of the Flower Library
+  Copyright (C) 1997--2014 Han-Wen Nienhuys <hanwen@xs4all.nl>
 
-  (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
-*/
+  LilyPond is free software: you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation, either version 3 of the License, or
+  (at your option) any later version.
+
+  LilyPond is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
 
+  You should have received a copy of the GNU General Public License
+  along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
+*/
 
 #ifndef PQUEUE_HH
 #define PQUEUE_HH
-#include "varray.hh"
-
+#include "std-vector.hh"
 
 template<class K, class T>
 struct PQueue_ent
 {
-    T val;
-    K key;
+  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);
+int compare (PQueue_ent<K, T> const &e1, PQueue_ent<K, T> const &e2)
+{
+  return compare (e1.key, e2.key);
 }
 
 /**
-  Priority queue using a (variable size) in-situ heap.
+   Priority queue using a (variable size) in-situ heap.
 
-  Hungarian postfix pq
-  
-  TODO: add increase/decrease operations,
-  add max() operation
- */
+   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];
-    }
+class PQueue
+{
+  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
+  /** acces an heap element.  Careful with this, as changing the
       priority might fuck up the invariants
 
-      @param 1 <= i < size() */
-    T& operator[](int i) { return heap_arr_[i]; }
-    T operator[](int i) const { return heap_arr_[i]; }
-    void OK() const
-    {
+      @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 (int i =2; i <= size(); i++)
-           assert (compare (elt (i/2), elt (i)) <= 0);
+    for (vsize i = 2; i <= size (); i++)
+      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);
-       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;
-           }
-       }
-       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_arr_.top();
-       
-       int mini=2;
-       int lasti=1;
+  }
+  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 ();
 
-       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();
-    }
-    T get() { 
-       T t = front();
-       delmin();
-       return t;
-    }
-};
+    vsize mini = 2;
+    vsize 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_array_.pop_back ();
+    OK ();
+  }
+  T get ()
+  {
+    T t = front ();
+    delmin ();
+    return t;
+  }
+};
 
 #endif // PQUEUE_HH