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>   /* find, reverse, sort */
  13 #include <functional>  /* unary_function */
  14 #include <cassert>
  15
  16 #if HAVE_BOOST_LAMBDA
  17 #include <boost/lambda/lambda.hpp>
  18 #endif
  19
  20 template<typename T>
  21 int default_compare (T const &a, T const &b)
  22 {
  23    if (a < b)
  24      return -1;
  25    else if (a > b)
  26      return 1;
  27    else
  28      return 0;
  29 }
  30
  31 template<typename T>
  32 int default_compare (T *const &a, T *const &b)
  33 {
  34   if (a < b)
  35     return -1;
  36   else if (a > b)
  37     return 1;
  38   else
  39     return 0;
  40 }
  41
  42 #if !STD_VECTOR
  43 /* Also declare vector, in the wrong way.  */
  44 #include <iostream>
  45 #include <sstream>
  46 #endif
  47
  48 #include "compare.hh"
  49
  50 #if STD_VECTOR
  51
  52 #include "config.hh"
  53
  54 #if HAVE_STL_DATA_METHOD
  55 #include <vector>
  56 #else /* !HAVE_STL_DATA_METHOD */
  57 #define vector __vector
  58 #include <vector>
  59 #undef vector
  60 namespace std {
  61   /* Interface without pointer arithmetic (iterator) semantics.  */
  62   template<typename T>
  63   class vector : public __vector<T>
  64   {
  65   public:
  66     typedef typename __vector<T>::iterator iterator;
  67     typedef typename __vector<T>::const_iterator const_iterator;
  68
  69     vector<T> () : __vector<T> ()
  70     {
  71     }
  72
  73     vector<T> (const_iterator b, const_iterator e) : __vector<T> (b, e)
  74     {
  75     }
  76
  77     T*
  78     data ()
  79     {
  80       return &(*this)[0];
  81     }
  82
  83     T const*
  84     data () const
  85     {
  86       return &(*this)[0];
  87     }
  88   };
  89
  90   /* FIXME: it appears that choosing this function is broken when stl
  91      has no data () member too...  */
  92   template<typename T>
  93   void
  94   binary_search_bounds (vector<T*> const &table,
  95                         T const *key, int (*compare) (T *const &, T *const &),
  96                         unsigned *lo,
  97                         unsigned *hi)
  98   {
  99     int cmp;
 100     int result;
 101
 102     /* binary search */
 103     do
 104       {
 105         cmp = (*lo + *hi) / 2;
 106
 107         result = (*compare) ((T *) key, table[cmp]);
 108
 109         if (result < 0)
 110           *hi = cmp;
 111         else
 112           *lo = cmp;
 113       }
 114     while (*hi - *lo > 1);
 115   }
 116 }
 117
 118 #endif /* !HAVE_STL_DATA_METHOD */
 119
 120 namespace std {
 121
 122   #ifndef VSIZE
 123   #define VSIZE
 124   typedef size_t vsize;
 125   #define VPOS UINT_MAX
 126   #endif
 127
 128   template<typename T>
 129   T const &
 130   boundary (vector<T> const &v, int dir, vsize i)
 131   {
 132     assert (dir);
 133     return v[dir == -1 ? i : v.size () - 1 - i];
 134   }
 135
 136   template<typename T>
 137   T &
 138   boundary (vector<T> &v, int dir, vsize i)
 139   {
 140     assert (dir);
 141     return v[dir == -1 ? i : v.size () - 1 - i];
 142   }
 143
 144   template<typename T>
 145   T const &
 146   back (vector<T> const &v, vsize i)
 147   {
 148     return v[v.size () - i - 1];
 149   }
 150
 151   template<typename T>
 152   T&
 153   back (vector<T> &v, vsize i)
 154   {
 155     return v[v.size () - i - 1];
 156   }
 157
 158   template<typename T>
 159   void
 160   concat (vector<T> &v, vector<T> const& w)
 161   {
 162     v.insert (v.end (), w.begin (), w.end ());
 163   }
 164
 165   template<class T>
 166   void
 167   binary_search_bounds (vector<T> const &table,
 168                         T const &key, int (*compare) (T const &, T const &),
 169                         vsize *lo,
 170                         vsize *hi)
 171   {
 172     if (*lo >= *hi)
 173       return;
 174
 175     int cmp;
 176     int result;
 177
 178     /* binary search */
 179     do
 180       {
 181         cmp = (*lo + *hi) / 2;
 182
 183         result = (*compare) (key, table[cmp]);
 184
 185         if (result < 0)
 186           *hi = cmp;
 187         else
 188           *lo = cmp;
 189       }
 190     while (*hi - *lo > 1);
 191   }
 192
 193 #if 0
 194   /* FIXME: what if COMPARE is named: int operator == (T const&, T const&),
 195      wouldn't that work for most uses of BINARY_SEARCH?
 196   */
 197   template<typename T>
 198   vsize
 199   binary_search (vector<T> const &v,
 200                  T const &key, int (*compare) (T const &, T const &),
 201                  vsize b=0, vsize e=VPOS)
 202   {
 203     if (e == VPOS)
 204       e = v.size ();
 205     typename vector<T>::const_iterator i = find (v.begin () + b,
 206                                                  v.begin () + e,
 207                                                  key);
 208     if (i != v.end ())
 209       return i - v.begin ();
 210     return VPOS;
 211   }
 212 #else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
 213   template<class T>
 214   vsize
 215   binary_search (vector<T> const &table,
 216                  T const &key,
 217                  int (*compare) (T const &, T const &),
 218                  vsize lo=0,
 219                  vsize hi=VPOS)
 220   {
 221     if (hi == VPOS)
 222       hi = table.size ();
 223
 224     if (lo >= hi)
 225       return VPOS;
 226
 227     binary_search_bounds (table, key, compare, &lo, &hi);
 228
 229     if (! (*compare) (key, table[lo]))
 230       return lo;
 231
 232     /* not found */
 233     return VPOS;
 234   }
 235
 236
 237 #endif
 238
 239
 240 #if 0
 241   /* FIXME: the COMPARE functionality is broken?  */
 242   template<typename T>
 243   void
 244   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 245                vsize lower=VPOS, vsize upper=VPOS)
 246   {
 247     typename vector<T>::iterator b = v.begin ();
 248     typename vector<T>::iterator e = v.begin ();
 249     if (lower == VPOS)
 250       {
 251         lower = 0;
 252         upper = v.size ();
 253       }
 254     ::std::sort (b + lower, e + upper, compare);
 255   }
 256 #else
 257
 258   // ugh, c&p
 259   template<typename T> void
 260   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 261                vsize lower=VPOS, vsize upper=VPOS)
 262   {
 263     if (lower == VPOS)
 264       {
 265         lower = 0;
 266         upper = v.size () - 1;
 267     }
 268     if (upper == VPOS || lower >= upper)
 269       return;
 270     swap (v[lower], v[(lower + upper) / 2]);
 271     vsize last = lower;
 272     for (vsize i = lower +1; i <= upper; i++)
 273       if (compare (v[i], v[lower]) < 0)
 274         swap (v[++last], v[i]);
 275     swap (v[lower], v[last]);
 276     vector_sort (v, compare, lower, last - 1);
 277     vector_sort (v, compare, last + 1, upper);
 278   }
 279 #endif
 280
 281   template<typename T>
 282   void
 283   reverse (vector<T> &v)
 284   {
 285     // CHECKME: for a simple vector, like vector<int>, this should
 286     // expand to memrev.
 287     ::std::reverse (v.begin (), v.end ());
 288   }
 289
 290   template<typename T>
 291   void
 292   uniq (vector<T> &v)
 293   {
 294     v.erase (unique (v.begin (), v.end ()), v.end ());
 295   }
 296
 297   template<typename T>
 298   typename vector<T>::const_iterator
 299   find (vector<T> const &v, T const &key)
 300   {
 301     return ::std::find (v.begin (), v.end (), key);
 302   }
 303
 304 #if HAVE_BOOST_LAMBDA
 305 #include <boost/lambda/lambda.hpp>
 306   using namespace boost::lambda;
 307   template<typename T>
 308   void
 309   junk_pointers (vector<T> &v)
 310   {
 311     for_each (v.begin (), v.end (), (delete _1, _1 = 0));
 312     v.clear ();
 313   }
 314 #else
 315
 316   template<typename T> struct del : public unary_function<T, void>
 317   {
 318     void operator() (T x)
 319     {
 320       delete x;
 321       x = 0;
 322     }
 323   };
 324
 325   template<typename T>
 326   void
 327   junk_pointers (vector<T> &v)
 328   {
 329     // Hmm.
 330     ::std::for_each (v.begin (), v.end (), del<T> ());
 331     v.clear ();
 332   }
 333 #endif /* HAVE_BOOST_LAMBDA */
 334
 335 }
 336
 337 #else /* ! STD_VECTOR */
 338
 339 namespace std {
 340
 341 #ifndef Array
 342 #define vector Array
 343 #endif
 344
 345   using namespace std;
 346
 347 #ifndef VSIZE
 348 #define VSIZE
 349   typedef int vsize;
 350 #define VPOS -1
 351 #endif
 352
 353 }
 354
 355 #include "array.hh"
 356 #include "parray.hh"
 357
 358 #endif /* !STD_VECTOR */
 359
 360 using namespace std;
 361
 362 #endif /* STD_VECTOR_HH */