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