2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
22 #include "std-vector.hh"
24 template<class K, class T>
31 template<class K, class T>
32 int compare (PQueue_ent<K, T> const &e1, PQueue_ent<K, T> const &e2)
34 return compare (e1.key, e2.key);
38 Priority queue using a (variable size) in-situ heap.
42 TODO: add increase/decrease operations,
48 vector<T> heap_array_;
51 return heap_array_[i - 1];
53 T const &elt (vsize i) const
55 return heap_array_[i - 1];
58 /** acces an heap element. Careful with this, as changing the
59 priority might fuck up the invariants
61 @param 1 <= i < size () */
62 T &operator [] (vsize i)
64 return heap_array_[i];
66 T operator [] (vsize i) const
68 return heap_array_[i];
73 for (vsize i = 2; i <= size (); i++)
74 assert (compare (elt (i / 2), elt (i)) <= 0);
83 return heap_array_.size ();
87 heap_array_.push_back (v);
88 vsize i = heap_array_.size ();
92 if (compare (elt (j), v) > 0)
106 //int first_leaf_i = size ();
113 T last = heap_array_.back ();
118 while (mini < size ())
120 if (compare (elt (mini + 1), elt (mini)) < 0)
122 if (compare (last, elt (mini)) < 0)
124 elt (lasti) = elt (mini);
129 heap_array_.pop_back ();