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