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     void
  55     concat (vector<T> const &v)
  56     {
  57       __vector<T>::insert (this->end (), v.begin (), v.end ());
  58     }
  59
  60     /* Flower-Array compatibility.  */
  61     T const &
  62     boundary (int dir, vsize i) const
  63     {
  64       assert (dir);
  65       if (dir == 1)
  66         return this->top (i);
  67       else
  68         return this->at (i);
  69     }
  70
  71     T &
  72     boundary (int dir, vsize i)
  73     {
  74       assert (dir);
  75       if (dir == 1)
  76         return this->top (i);
  77       else
  78         return this->at (i);
  79     }
  80
  81     T const &
  82     elem (vsize i) const
  83     {
  84       return this->at (i);
  85     }
  86
  87     T &
  88     elem (vsize i)
  89     {
  90       return this->at (i);
  91     }
  92
  93 #if 1 // FIXME, silly, but keep for s/r
  94     T const &
  95     elem_ref (vsize i) const
  96     {
  97       return elem (i);
  98     }
  99
 100     T &
 101     elem_ref (vsize i)
 102     {
 103       return elem (i);
 104     }
 105 #endif
 106
 107 #if 0
 108     T *
 109     remove_array ()
 110     {
 111       // FIXME, no algorithm for this?
 112       T *p = new T[this->size ()];
 113       for (vsize i = 0; i < this->size (); i++)
 114         p[i] = (*this)[i];
 115       this->clear ();
 116       return p;
 117     }
 118 #else
 119     T *
 120     remove_array ()
 121     {
 122       T *p = &(*this)[0];
 123       // forget array?
 124       //this->resize (0);
 125       return p;
 126     }
 127 #endif
 128
 129     void
 130     reverse ()
 131     {
 132       // CHECKME: for a simple vector, like vector<int>, this should
 133       // expand to memrev.
 134       ::std::reverse (this->begin (), this->end ());
 135     }
 136
 137     void swap (vsize i, vsize j)
 138     {
 139       T t ((*this)[i]);
 140       (*this)[i] = (*this)[j];
 141       (*this)[j] = t;
 142     }
 143
 144     T const &
 145     top (vsize i) const
 146     {
 147       return (*this)[this->size () - i - 1];
 148     }
 149
 150     T&
 151     top (vsize i)
 152     {
 153       return (*this)[this->size () - i - 1];
 154     }
 155   };
 156
 157 #if 0
 158   template<typename T>
 159   vsize
 160   //  binary_search (std::vector<T> const &v,
 161   binary_search (vector<T> const &v,
 162                  T const &key, int (*compare) (T const &, T const &),
 163                  vsize b=0, vsize e=VPOS)
 164   {
 165     //(void) compare;
 166     typename vector<T>::const_iterator i = find (v.iter (b), v.iter (e), key);
 167     if (i != v.end ())
 168       return i - v.begin ();
 169     return VPOS;
 170   }
 171 #else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
 172   template<class T>
 173   void
 174   binary_search_bounds (vector<T> const &table,
 175                         T const &key, int (*compare) (T const &, T const &),
 176                         vsize *lo,
 177                         vsize *hi)
 178   {
 179     int cmp;
 180     int result;
 181
 182     /* binary search */
 183     do
 184       {
 185         cmp = (*lo + *hi) / 2;
 186
 187         result = (*compare) (key, table[cmp]);
 188
 189         if (result < 0)
 190           *hi = cmp;
 191         else
 192           *lo = cmp;
 193       }
 194     while (*hi - *lo > 1);
 195   }
 196
 197   template<class T>
 198   vsize
 199   binary_search (vector<T> const &table,
 200                  T const &key, int (*compare) (T const &, T const &),
 201                  vsize lo=0,
 202                  vsize hi=VPOS)
 203   {
 204     if (hi == VPOS)
 205       hi = table.size ();
 206
 207     binary_search_bounds (table, key, compare, &lo, &hi);
 208
 209     if (! (*compare) (key, table[lo]))
 210       return lo;
 211
 212     /* not found */
 213     return VPOS;
 214   }
 215 #endif
 216
 217
 218 #if 0
 219   /* FIXME: the simple test works, but lily barfs.  */
 220   template<typename T>
 221   void
 222   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 223                vsize lower=VPOS, vsize upper=VPOS)
 224   {
 225     typename vector<T>::iterator b = v.begin ();
 226     typename vector<T>::iterator e = v.begin ();
 227     if (lower == VPOS)
 228       {
 229         lower = 0;
 230         upper = v.size ();
 231       }
 232     ::std::sort (b + lower, e + upper, compare);
 233   }
 234 #else
 235   // ugh, c&p
 236 template<typename T> void
 237 vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 238              vsize lower=VPOS, vsize upper=VPOS)
 239 {
 240   if (lower == VPOS)
 241     {
 242       lower = 0;
 243       upper = v.size () - 1;
 244     }
 245   if (upper == VPOS || lower >= upper)
 246     return;
 247   v.swap (lower, (lower + upper) / 2);
 248   vsize last = lower;
 249   for (vsize i = lower +1; i <= upper; i++)
 250     if (compare (v[i], v[lower]) < 0)
 251       v.swap (++last, i);
 252   v.swap (lower, last);
 253   vector_sort (v, compare, lower, last - 1);
 254   vector_sort (v, compare, last + 1, upper);
 255 }
 256
 257 #endif
 258
 259 }
 260
 261
 262
 263 #else /* ! STD_VECTOR */
 264
 265 namespace std {
 266
 267 #ifndef Array
 268 #define vector Array
 269 #endif
 270
 271   using namespace std;
 272
 273 #ifndef VSIZE
 274 #define VSIZE
 275   typedef int vsize;
 276 #define VPOS -1
 277 #endif
 278
 279 }
 280
 281
 282 #endif /* STD_VECTOR */
 283
 284 template<typename T>
 285 int default_compare (T const &a, T const &b)
 286 {
 287    if (a < b)
 288      return -1;
 289    else if (a > b)
 290      return 1;
 291    else
 292      return 0;
 293 }
 294
 295
 296 #include "array.hh"
 297
 298 #endif /* STD_VECTOR_HH */