flower/include/std-vector.hh

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2010 Jan Nieuwenhuizen <janneke@gnu.org>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #ifndef STD_VECTOR_HH
  21 #define STD_VECTOR_HH
  22
  23 #if 0
  24
  25 /*
  26   leads to dubious crashes - libstdc++  bug?
  27 */
  28 #ifndef NDEBUG
  29 #define _GLIBCXX_DEBUG 1
  30 #endif
  31 #endif
  32
  33 #include <algorithm>   /* find, reverse, sort */
  34 #include <functional>  /* unary_function */
  35 #include <cassert>
  36 #include <string>
  37
  38 using namespace std;
  39
  40 #if HAVE_BOOST_LAMBDA_LAMBDA_HPP
  41 #include <boost/lambda/lambda.hpp>
  42 #endif
  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 (b < a)
  50     return 1;
  51   else
  52     return 0;
  53 }
  54
  55 template<typename T>
  56 int default_compare (T *const &a, T *const &b)
  57 {
  58   if (a < b)
  59     return -1;
  60   else if (a > b)
  61     return 1;
  62   else
  63     return 0;
  64 }
  65
  66 #include "compare.hh"
  67
  68 #ifndef VSIZE
  69 #define VSIZE
  70 typedef size_t vsize;
  71 #define VPOS ((vsize) -1)
  72 #endif
  73
  74 #if HAVE_STL_DATA_METHOD
  75 #include <vector>
  76 #else /* !HAVE_STL_DATA_METHOD */
  77 #define vector __flower_vector
  78 #include <vector>
  79 #undef vector
  80
  81 namespace std {
  82
  83   /* Interface without pointer arithmetic (iterator) semantics.  */
  84   template<typename T, typename A=std::allocator<T> >
  85   class vector : public __flower_vector<T, A>
  86   {
  87   public:
  88     typedef typename __flower_vector<T>::iterator iterator;
  89     typedef typename __flower_vector<T>::const_iterator const_iterator;
  90
  91     vector<T, A> () : __flower_vector<T, A> ()
  92     {
  93     }
  94
  95     vector<T, A> (vector<T, A> const& v) : __flower_vector<T, A> (v)
  96     {
  97     }
  98
  99     vector<T, A> (const_iterator b, const_iterator e) : __flower_vector<T, A> (b, e)
 100     {
 101     }
 102
 103     T*
 104     data ()
 105     {
 106       return &(*this)[0];
 107     }
 108
 109     T const*
 110     data () const
 111     {
 112       return &(*this)[0];
 113     }
 114   };
 115
 116 } /* namespace std */
 117
 118 #endif /* !HAVE_STL_DATA_METHOD */
 119
 120 template<typename T>
 121 T const &
 122 boundary (vector<T> const &v, int dir, vsize i)
 123 {
 124   assert (dir);
 125   return v[dir == -1 ? i : v.size () - 1 - i];
 126 }
 127
 128 template<typename T>
 129 T &
 130 boundary (vector<T> &v, int dir, vsize i)
 131 {
 132   assert (dir);
 133   return v[dir == -1 ? i : v.size () - 1 - i];
 134 }
 135
 136 template<typename T>
 137 T const &
 138 back (vector<T> const &v, vsize i)
 139 {
 140   return v[v.size () - i - 1];
 141 }
 142
 143 template<typename T>
 144 T&
 145 back (vector<T> &v, vsize i)
 146 {
 147   return v[v.size () - i - 1];
 148 }
 149
 150 template<typename T>
 151 void
 152 concat (vector<T> &v, vector<T> const& w)
 153 {
 154   v.insert (v.end (), w.begin (), w.end ());
 155 }
 156
 157 template<typename T, typename Compare>
 158 vsize
 159 lower_bound (vector<T> const &v,
 160              T const &key,
 161              Compare less,
 162              vsize b=0, vsize e=VPOS)
 163 {
 164   if (e == VPOS)
 165     e = v.size ();
 166   typename vector<T>::const_iterator i = lower_bound (v.begin () + b,
 167                                                       v.begin () + e,
 168                                                       key,
 169                                                       less);
 170
 171   return i - v.begin ();
 172 }
 173
 174 template<typename T, typename Compare>
 175 vsize
 176 upper_bound (vector<T> const &v,
 177              T const &key,
 178              Compare less,
 179              vsize b=0, vsize e=VPOS)
 180 {
 181   if (e == VPOS)
 182     e = v.size ();
 183
 184   typename vector<T>::const_iterator i = upper_bound (v.begin () + b,
 185                                                       v.begin () + e,
 186                                                       key,
 187                                                       less);
 188
 189   return i - v.begin ();
 190 }
 191
 192 template<typename T, typename Compare>
 193 vsize
 194 binary_search (vector<T> const &v,
 195                T const &key,
 196                Compare less=less<T> (),
 197                vsize b=0, vsize e=VPOS)
 198 {
 199   vsize lb = lower_bound (v, key, less, b, e);
 200
 201   if (lb == v.size () || less (key, v[lb]))
 202     return VPOS;
 203   return lb;
 204 }
 205
 206 template<typename T, typename Compare>
 207 void
 208 vector_sort (vector<T> &v,
 209              Compare less,
 210              vsize b=0, vsize e=VPOS)
 211 {
 212   if (e == VPOS)
 213     e = v.size ();
 214
 215   sort (v.begin () + b, v.begin () + e, less);
 216 }
 217
 218 template<typename T>
 219 void
 220 reverse (vector<T> &v)
 221 {
 222   // CHECKME: for a simple vector, like vector<int>, this should
 223   // expand to memrev.
 224   reverse (v.begin (), v.end ());
 225 }
 226
 227 template<typename T>
 228 void
 229 uniq (vector<T> &v)
 230 {
 231   v.erase (unique (v.begin (), v.end ()), v.end ());
 232 }
 233
 234 template<typename T>
 235 typename vector<T>::const_iterator
 236 find (vector<T> const &v, T const &key)
 237 {
 238   return find (v.begin (), v.end (), key);
 239 }
 240
 241 #if HAVE_BOOST_LAMBDA_LAMBDA_HPP
 242 #include <boost/lambda/lambda.hpp>
 243 using namespace boost::lambda;
 244 template<typename T>
 245 void
 246 junk_pointers (vector<T> &v)
 247 {
 248   for_each (v.begin (), v.end (), (delete _1, _1 = 0));
 249   v.clear ();
 250 }
 251 #else
 252
 253 template<typename T> struct del : public unary_function<T, void>
 254 {
 255   void operator() (T x)
 256   {
 257     delete x;
 258     x = 0;
 259   }
 260 };
 261
 262 template<typename T>
 263 void
 264 junk_pointers (vector<T> &v)
 265 {
 266   // Hmm.
 267   for_each (v.begin (), v.end (), del<T> ());
 268   v.clear ();
 269 }
 270 #endif /* HAVE_BOOST_LAMBDA */
 271
 272 vector<string> string_split (string str, char c);
 273 string string_join (vector<string> const &strs, string infix);
 274
 275 #define iterof(i,s) typeof((s).begin()) i((s).begin())
 276
 277 #endif /* STD_VECTOR_HH */