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