flower/include/std-vector.hh

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