flower/include/std-vector.hh

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