X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fpqueue.hh;h=39e0cbe743a43508f4d0f60c8c9ff79701b35869;hb=47db9a3883d726ca53e2133a3b2298f78dd6a32e;hp=a50caefaaf65b7a1e370ddd4a4042216987c04bb;hpb=75eebcb49e52d296b1da3e1074e0825d2c780db4;p=lilypond.git

diff --git a/flower/include/pqueue.hh b/flower/include/pqueue.hh
index a50caefaaf..39e0cbe743 100644
--- a/flower/include/pqueue.hh
+++ b/flower/include/pqueue.hh
@@ -1,14 +1,25 @@
 /*
-  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--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
 
-  (c) 1997--2006 Han-Wen Nienhuys <hanwen@xs4all.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 "array.hh"
+#include "std-vector.hh"
 
 template<class K, class T>
 struct PQueue_ent
@@ -34,12 +45,12 @@ int compare (PQueue_ent<K, T> const &e1, PQueue_ent<K, T> const &e2)
 template<class T>
 class PQueue
 {
-  Array<T> heap_array_;
-  T &elt (int i)
+  vector<T> heap_array_;
+  T &elt (vsize i)
   {
     return heap_array_[i - 1];
   }
-  T const &elt (int i) const
+  T const &elt (vsize i) const
   {
     return heap_array_[i - 1];
   }
@@ -48,32 +59,44 @@ public:
       priority might fuck up the invariants
 
       @param 1 <= i < size () */
-  T &operator [] (int i) { return heap_array_[i]; }
-  T operator [] (int i) const { return heap_array_[i]; }
+  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++)
+    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_array_.size (); }
+  T front () const
+  {
+    return elt (1);
+  }
+  vsize size () const
+  {
+    return heap_array_.size ();
+  }
   void insert (T v)
   {
-    heap_array_.push (v);
-    int i = heap_array_.size ();
-    int j = i / 2;
+    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;
+        if (compare (elt (j), v) > 0)
+          {
+            elt (i) = elt (j);
+            i = j;
+            j = i / 2;
+          }
+        else
+          break;
       }
     elt (i) = v;
     OK ();
@@ -87,23 +110,23 @@ public:
   void delmin ()
   {
     assert (size ());
-    T last = heap_array_.top ();
+    T last = heap_array_.back ();
 
-    int mini = 2;
-    int lasti = 1;
+    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;
+        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 ();
+    heap_array_.pop_back ();
     OK ();
   }
   T get ()