flower/pqueue.hh

   1 /*
   2   pqueue.hh -- declare
   3
   4   source file of the LilyPond music typesetter
   5
   6   (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9
  10 #ifndef PQUEUE_HH
  11 #define PQUEUE_HH
  12
  13 #include "varray.hh"
  14
  15 /**
  16   Stupid Prioq. Should use Lists and STL.
  17   Smallest is put at the front.
  18  */
  19
  20 template<class V, class I>
  21 struct PQueue
  22 {
  23     Array<V> value_arr_;
  24     Array<I> indices_arr_;
  25
  26     void enter(V v, I idx) {
  27         int j=0;
  28         for (; j < value_arr_.size(); j++)
  29             if (indices_arr_[j] > idx)
  30                 break;
  31
  32         value_arr_.insert(v, j);
  33         indices_arr_.insert(idx, j);
  34     }
  35     int size() { return value_arr_.size(); }
  36     V front_val() { return value_arr_[0]; }
  37     I front_idx() { return indices_arr_[0]; }
  38     V get() {
  39         V retval = front_val();
  40         value_arr_.del(0);
  41         indices_arr_.del(0);
  42         return retval;
  43     }
  44
  45 };
  46 #endif // PQUEUE_HH