flower/include/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 Actually, this sux. Should use a template struct PQuee_ent<V,I>
  20  */
  21
  22 template<class V, class I>
  23 struct PQueue
  24 {
  25     Array<V> value_arr_;
  26     Array<I> indices_arr_;
  27     void OK() const
  28     {
  29
  30         assert(value_arr_.size() == indices_arr_.size());
  31     }
  32
  33     void enter(V v, I idx) {
  34         int j=0;
  35         for (; j < value_arr_.size(); j++)
  36             if (indices_arr_[j] > idx)
  37                 break;
  38
  39         insert(j,v,idx);
  40
  41     }
  42     int size() { return value_arr_.size(); }
  43     V front_val() { return value_arr_[0]; }
  44     I front_idx() { return indices_arr_[0]; }
  45     void del(int i)
  46     {
  47         value_arr_.del(i);
  48         indices_arr_.del(i);
  49     }
  50     int size() const
  51     {
  52         OK();
  53         return value_arr_.size();
  54     }
  55
  56
  57     void insert(int j, V v, I idx)
  58     {
  59         value_arr_.insert(v, j);
  60         indices_arr_.insert(idx, j);
  61     }
  62
  63
  64
  65     V get() {
  66         V retval = front_val();
  67         del(0);
  68         return retval;
  69     }
  70
  71 };
  72 #endif // PQUEUE_HH