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 #if 0
 129   template<typename T>
 130   vsize
 131   //  binary_search (std::vector<T> const &v,
 132   binary_search (vector<T> const &v,
 133                  T const &key, int (*compare) (T const &, T const &),
 134                  vsize b=0, vsize e=VPOS)
 135   {
 136     //(void) compare;
 137     if (e == VPOS)
 138       e = v.size ();
 139     typename vector<T>::const_iterator i = find (v.begin () + b,
 140                                                  v.begin () + e, key);
 141     if (i != v.end ())
 142       return i - v.begin ();
 143     return VPOS;
 144   }
 145 #else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
 146   template<class T>
 147   vsize
 148   binary_search (vector<T> const &table,
 149                  T const &key,
 150                  int (*compare) (T const &, T const &),
 151                  vsize lo=0,
 152                  vsize hi=VPOS)
 153   {
 154     if (hi == VPOS)
 155       hi = table.size ();
 156
 157     if (lo >= hi)
 158       return VPOS;
 159
 160     binary_search_bounds (table, key, compare, &lo, &hi);
 161
 162     if (! (*compare) (key, table[lo]))
 163       return lo;
 164
 165     /* not found */
 166     return VPOS;
 167   }
 168
 169
 170 #endif
 171
 172
 173 #if 0
 174   /* FIXME: the COMPARE functionality is broken?  */
 175   template<typename T>
 176   void
 177   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 178                vsize lower=VPOS, vsize upper=VPOS)
 179   {
 180     typename vector<T>::iterator b = v.begin ();
 181     typename vector<T>::iterator e = v.begin ();
 182     if (lower == VPOS)
 183       {
 184         lower = 0;
 185         upper = v.size ();
 186       }
 187     ::std::sort (b + lower, e + upper, compare);
 188   }
 189 #else
 190
 191   // ugh, c&p
 192   template<typename T> void
 193   vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
 194                vsize lower=VPOS, vsize upper=VPOS)
 195   {
 196     if (lower == VPOS)
 197       {
 198         lower = 0;
 199         upper = v.size () - 1;
 200     }
 201     if (upper == VPOS || lower >= upper)
 202       return;
 203     swap (v[lower], v[(lower + upper) / 2]);
 204     vsize last = lower;
 205     for (vsize i = lower +1; i <= upper; i++)
 206       if (compare (v[i], v[lower]) < 0)
 207         swap (v[++last], v[i]);
 208     swap (v[lower], v[last]);
 209     vector_sort (v, compare, lower, last - 1);
 210     vector_sort (v, compare, last + 1, upper);
 211   }
 212 #endif
 213
 214   template<typename T>
 215   void
 216   reverse (vector<T> &v)
 217   {
 218     // CHECKME: for a simple vector, like vector<int>, this should
 219     // expand to memrev.
 220     ::std::reverse (v.begin (), v.end ());
 221   }
 222
 223   template<typename T>
 224   void
 225   uniq (vector<T> &v)
 226   {
 227     v.erase (unique (v.begin (), v.end ()), v.end ());
 228   }
 229
 230   template<typename T>
 231   typename vector<T>::const_iterator
 232   find (vector<T> const &v, T const &key)
 233   {
 234     return ::std::find (v.begin (), v.end (), key);
 235   }
 236
 237 #if HAVE_BOOST_LAMBDA
 238 #include <boost/lambda/lambda.hpp>
 239   using namespace boost::lambda;
 240   template<typename T>
 241   void
 242   junk_pointers (vector<T> &v)
 243   {
 244     for_each (v.begin (), v.end (), (delete _1, _1 = 0));
 245     v.clear ();
 246   }
 247 #else
 248
 249   template<typename T> struct del : public unary_function<T, void>
 250   {
 251     void operator() (T x)
 252     {
 253       delete x;
 254       x = 0;
 255     }
 256   };
 257
 258   template<typename T>
 259   void
 260   junk_pointers (vector<T> &v)
 261   {
 262     // Hmm.
 263     ::std::for_each (v.begin (), v.end (), del<T> ());
 264     v.clear ();
 265   }
 266 #endif /* HAVE_BOOST_LAMBDA */
 267
 268 }
 269
 270 #else /* ! STD_VECTOR */
 271
 272 namespace std {
 273
 274 #ifndef Array
 275 #define vector Array
 276 #endif
 277
 278   using namespace std;
 279
 280 #ifndef VSIZE
 281 #define VSIZE
 282   typedef int vsize;
 283 #define VPOS -1
 284 #endif
 285
 286 }
 287
 288 #include "array.hh"
 289 #include "parray.hh"
 290
 291 #endif /* !STD_VECTOR */
 292
 293 using namespace std;
 294
 295 #endif /* STD_VECTOR_HH */