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