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 template<typename T, typename Compare>
 195 void
 196 vector_sort (vector<T> &v,
 197              Compare less,
 198              vsize b=0, vsize e=VPOS)
 199 {
 200   if (e == VPOS)
 201     e = v.size ();
 202
 203   sort (v.begin () + b, v.begin () + e, less);
 204 }
 205
 206 template<typename T>
 207 void
 208 reverse (vector<T> &v)
 209 {
 210   // CHECKME: for a simple vector, like vector<int>, this should
 211   // expand to memrev.
 212   reverse (v.begin (), v.end ());
 213 }
 214
 215 template<typename T>
 216 void
 217 uniq (vector<T> &v)
 218 {
 219   v.erase (unique (v.begin (), v.end ()), v.end ());
 220 }
 221
 222 template<typename T>
 223 typename vector<T>::const_iterator
 224 find (vector<T> const &v, T const &key)
 225 {
 226   return find (v.begin (), v.end (), key);
 227 }
 228
 229 #if HAVE_BOOST_LAMBDA
 230 #include <boost/lambda/lambda.hpp>
 231 using namespace boost::lambda;
 232 template<typename T>
 233 void
 234 junk_pointers (vector<T> &v)
 235 {
 236   for_each (v.begin (), v.end (), (delete _1, _1 = 0));
 237   v.clear ();
 238 }
 239 #else
 240
 241 template<typename T> struct del : public unary_function<T, void>
 242 {
 243   void operator() (T x)
 244   {
 245     delete x;
 246     x = 0;
 247   }
 248 };
 249
 250 template<typename T>
 251 void
 252 junk_pointers (vector<T> &v)
 253 {
 254   // Hmm.
 255   for_each (v.begin (), v.end (), del<T> ());
 256   v.clear ();
 257 }
 258 #endif /* HAVE_BOOST_LAMBDA */
 259
 260 vector<string> string_split (string str, char c);
 261
 262 #define iterof(i,s) typeof((s).begin()) i((s).begin())
 263
 264 #endif /* STD_VECTOR_HH */