flower/include/std-vector.hh

   1 /*
   2   std-vector.hh -- declare std::vector
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2006 Jan Nieuwenhuizen <janneke@gnu.org>
   7 */
   8
   9 #ifndef STD_VECTOR_HH
  10 #define STD_VECTOR_HH
  11
  12 #include <algorithm> // reverse, sort
  13
  14 #if !STD_VECTOR
  15 /* Also declare vector, in the wrong way.  */
  16 #include <algorithm>
  17 #include <iostream>
  18 #include <sstream>
  19 #endif
  20
  21
  22 #include "compare.hh"
  23
  24 #if STD_VECTOR
  25
  26 #define vector __vector
  27 #include <vector>
  28 #undef vector
  29
  30 namespace std {
  31
  32   #ifndef VSIZE
  33   #define VSIZE
  34   typedef size_t vsize;
  35   #define VPOS UINT_MAX
  36   #endif
  37
  38   /* Interface without pointer arithmetic (iterator) semantics.  */
  39   template<typename T>
  40   class vector : public __vector<T>
  41   {
  42   public:
  43     typedef typename __vector<T>::iterator iterator;
  44     typedef typename __vector<T>::const_iterator const_iterator;
  45
  46     vector<T> () : __vector<T> ()
  47     {
  48     }
  49
  50     vector<T> (const_iterator b, const_iterator e) : __vector<T> (b, e)
  51     {
  52     }
  53
  54     /* Flower-Array compatibility.  */
  55     T const &
  56     boundary (int dir, vsize i) const
  57     {
  58       assert (dir);
  59       if (dir == 1)
  60         return this->top (i);
  61       else
  62         return this->at (i);
  63     }
  64
  65     T &
  66     boundary (int dir, vsize i)
  67     {
  68       assert (dir);
  69       if (dir == 1)
  70         return this->top (i);
  71       else
  72         return this->at (i);
  73     }
  74
  75     T const &
  76     top (vsize i) const
  77     {
  78       return (*this)[this->size () - i - 1];
  79     }
  80
  81     T&
  82     top (vsize i)
  83     {
  84       return (*this)[this->size () - i - 1];
  85     }
  86   };
  87
  88 #if 0
  89   template<typename T>
  90   vsize
  91   //  binary_search (std::vector<T> const &v,
  92   binary_search (vector<T> const &v,
  93                  T const &key, int (*compare) (T const &, T const &),
  94                  vsize b=0, vsize e=VPOS)
  95   {
  96     //(void) compare;
  97     typename vector<T>::const_iterator i = find (v.iter (b), v.iter (e), key);
  98     if (i != v.end ())
  99       return i - v.begin ();
 100     return VPOS;
 101   }
 102 #else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
 103   template<class T>
 104   void
 105   binary_search_bounds (vector<T> const &table,
 106                         T const &key, int (*compare) (T const &, T const &),
 107                         vsize *lo,
 108                         vsize *hi)
 109   {
 110     int cmp;
 111     int result;
 112
 113     /* binary search */
 114     do
 115       {
 116         cmp = (*lo + *hi) / 2;
 117
 118         result = (*compare) (key, table[cmp]);
 119
 120         if (result < 0)
 121           *hi = cmp;
 122         else
 123           *lo = cmp;
 124       }
 125     while (*hi - *lo > 1);
 126   }
 127
 128   template<class T>
 129   vsize
 130   binary_search (vector<T> const &table,
 131                  T const &key, int (*compare) (T const &, T const &),
 132                  vsize lo=0,
 133                  vsize hi=VPOS)
 134   {
 135     if (hi == VPOS)
 136       hi = table.size ();
 137
 138     binary_search_bounds (table, key, compare, &lo, &hi);
 139
 140     if (! (*compare) (key, table[lo]))
 141       return lo;
 142
 143     /* not found */
 144     return VPOS;
 145   }
 146 #endif
 147
 148
 149 #if 0
 150   /* FIXME: the simple test works, but lily barfs.  */
 151   template<typename T>
 152   void
 153   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 154                vsize lower=VPOS, vsize upper=VPOS)
 155   {
 156     typename vector<T>::iterator b = v.begin ();
 157     typename vector<T>::iterator e = v.begin ();
 158     if (lower == VPOS)
 159       {
 160         lower = 0;
 161         upper = v.size ();
 162       }
 163     ::std::sort (b + lower, e + upper, compare);
 164   }
 165 #else
 166
 167   template<typename T>
 168   void
 169   swap (T *a, T *b)
 170   {
 171     T t = *a;
 172     *a = *b;
 173     *b = t;
 174   }
 175
 176   // ugh, c&p
 177 template<typename T> void
 178 vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 179              vsize lower=VPOS, vsize upper=VPOS)
 180 {
 181   if (lower == VPOS)
 182     {
 183       lower = 0;
 184       upper = v.size () - 1;
 185     }
 186   if (upper == VPOS || lower >= upper)
 187     return;
 188   swap (v[lower], v[(lower + upper) / 2]);
 189   vsize last = lower;
 190   for (vsize i = lower +1; i <= upper; i++)
 191     if (compare (v[i], v[lower]) < 0)
 192       swap (v[++last], v[i]);
 193   swap (v[lower], v[last]);
 194   vector_sort (v, compare, lower, last - 1);
 195   vector_sort (v, compare, last + 1, upper);
 196 }
 197
 198   template<typename T>
 199   void
 200   reverse (vector<T> &v)
 201   {
 202     // CHECKME: for a simple vector, like vector<int>, this should
 203     // expand to memrev.
 204     ::std::reverse (v.begin (), v.end ());
 205   }
 206
 207 #endif
 208
 209 }
 210
 211
 212
 213 #else /* ! STD_VECTOR */
 214
 215 namespace std {
 216
 217 #ifndef Array
 218 #define vector Array
 219 #endif
 220
 221   using namespace std;
 222
 223 #ifndef VSIZE
 224 #define VSIZE
 225   typedef int vsize;
 226 #define VPOS -1
 227 #endif
 228
 229 }
 230
 231
 232 #endif /* STD_VECTOR */
 233
 234 template<typename T>
 235 int default_compare (T const &a, T const &b)
 236 {
 237    if (a < b)
 238      return -1;
 239    else if (a > b)
 240      return 1;
 241    else
 242      return 0;
 243 }
 244
 245
 246 #include "array.hh"
 247
 248 #endif /* STD_VECTOR_HH */