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