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