/*
- 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--2005 Han-Wen Nienhuys <hanwen@cs.uu.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
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];
}
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++)
+#ifdef DEBUG
+ 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 ();
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 ()