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