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