flower/include/std-vector.hh

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