flower/include/pqueue.hh

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 1997--2010 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   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.
  10
  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.
  15
  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/>.
  18 */
  19
  20 #ifndef PQUEUE_HH
  21 #define PQUEUE_HH
  22 #include "std-vector.hh"
  23
  24 template<class K, class T>
  25 struct PQueue_ent
  26 {
  27   T val;
  28   K key;
  29 };
  30
  31 template<class K, class T>
  32 int compare (PQueue_ent<K, T> const &e1, PQueue_ent<K, T> const &e2)
  33 {
  34   return compare (e1.key, e2.key);
  35 }
  36
  37 /**
  38    Priority queue using a (variable size) in-situ heap.
  39
  40    Hungarian postfix pq
  41
  42    TODO: add increase/decrease operations,
  43    add max () operation
  44 */
  45 template<class T>
  46 class PQueue
  47 {
  48   vector<T> heap_array_;
  49   T &elt (vsize i)
  50   {
  51     return heap_array_[i - 1];
  52   }
  53   T const &elt (vsize i) const
  54   {
  55     return heap_array_[i - 1];
  56   }
  57 public:
  58   /** acces an heap element.  Careful with this, as changing the
  59       priority might fuck up the invariants
  60
  61       @param 1 <= i < size () */
  62   T &operator [] (vsize i)
  63   {
  64     return heap_array_[i];
  65   }
  66   T operator [] (vsize i) const
  67   {
  68     return heap_array_[i];
  69   }
  70   void OK () const
  71   {
  72 #ifndef NDEBUG
  73     for (vsize i = 2; i <= size (); i++)
  74       assert (compare (elt (i / 2), elt (i)) <= 0);
  75 #endif
  76   }
  77   T front () const
  78   {
  79     return elt (1);
  80   }
  81   vsize size () const
  82   {
  83     return heap_array_.size ();
  84   }
  85   void insert (T v)
  86   {
  87     heap_array_.push_back (v);
  88     vsize i = heap_array_.size ();
  89     vsize j = i / 2;
  90     while (j)
  91       {
  92         if (compare (elt (j), v) > 0)
  93           {
  94             elt (i) = elt (j);
  95             i = j;
  96             j = i / 2;
  97           }
  98         else
  99           break;
 100       }
 101     elt (i) = v;
 102     OK ();
 103   }
 104   T max () const
 105   {
 106     //int first_leaf_i = size ();
 107     T max_t;
 108     return max_t;
 109   }
 110   void delmin ()
 111   {
 112     assert (size ());
 113     T last = heap_array_.back ();
 114
 115     vsize mini = 2;
 116     vsize lasti = 1;
 117
 118     while (mini < size ())
 119       {
 120         if (compare (elt (mini + 1), elt (mini)) < 0)
 121           mini++;
 122         if (compare (last, elt (mini)) < 0)
 123           break;
 124         elt (lasti) = elt (mini);
 125         lasti = mini;
 126         mini *= 2;
 127       }
 128     elt (lasti) = last;
 129     heap_array_.pop_back ();
 130     OK ();
 131   }
 132   T get ()
 133   {
 134     T t = front ();
 135     delmin ();
 136     return t;
 137   }
 138 };
 139
 140 #endif // PQUEUE_HH