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