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