/*
- pqueue.hh -- declare
+ This file is part of LilyPond, the GNU music typesetter.
- source file of the LilyPond music typesetter
+ Copyright (C) 1997--2015 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 "std-vector.hh"
+
+template<class K, class T>
+struct PQueue_ent
+{
+ T val;
+ K key;
+};
-#include "varray.hh"
+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);
+}
/**
- Stupid Prioq. Should use Lists and STL.
- Smallest is put at the front.
+ Priority queue using a (variable size) in-situ heap.
-Actually, this sux. Should use a template struct PQuee_ent<V,I>
- */
+ Hungarian postfix pq
-template<class V, class I>
-struct PQueue
+ TODO: add increase/decrease operations,
+ add max () operation
+*/
+template<class T>
+class PQueue
{
- Array<V> value_arr_;
- Array<I> indices_arr_;
- void OK() const
- {
-
- assert(value_arr_.size() == indices_arr_.size());
- }
-
- void enter(V v, I idx) {
- int j=0;
- for (; j < value_arr_.size(); j++)
- if (indices_arr_[j] > idx)
- break;
+ 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
+ priority might fuck up the invariants
- insert(j,v,idx);
-
- }
- int size() { return value_arr_.size(); }
- V front_val() { return value_arr_[0]; }
- I front_idx() { return indices_arr_[0]; }
- void del(int i)
- {
- value_arr_.del(i);
- indices_arr_.del(i);
- }
- int size() const
- {
- OK();
- return value_arr_.size();
- }
-
+ @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 (vsize i = 2; i <= size (); i++)
+ assert (compare (elt (i / 2), elt (i)) <= 0);
+#endif
+ }
+ 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 ();
- void insert(int j, V v, I idx)
- {
- value_arr_.insert(v, j);
- indices_arr_.insert(idx, j);
- }
-
+ vsize mini = 2;
+ vsize lasti = 1;
-
- V get() {
- V retval = front_val();
- del(0);
- return retval;
- }
-
+ 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
projects / lilypond.git / blobdiff