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> (vector<T, A> const &v) : __flower_vector<T, A> (v)
  93   {
  94   }
  95
  96   vector<T, A> (const_iterator b, const_iterator e) : __flower_vector<T, A> (b, e)
  97   {
  98   }
  99
 100   T *
 101   data ()
 102   {
 103     return &(*this)[0];
 104   }
 105
 106   T const *
 107   data () const
 108   {
 109     return &(*this)[0];
 110   }
 111 };
 112
 113 } /* namespace std */
 114
 115 #endif /* !HAVE_STL_DATA_METHOD */
 116
 117 template<typename T>
 118 T const &
 119 boundary (vector<T> const &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 &
 127 boundary (vector<T> &v, int dir, vsize i)
 128 {
 129   assert (dir);
 130   return v[dir == -1 ? i : v.size () - 1 - i];
 131 }
 132
 133 template<typename T>
 134 T const &
 135 back (vector<T> const &v, vsize i)
 136 {
 137   return v[v.size () - i - 1];
 138 }
 139
 140 template<typename T>
 141 T &
 142 back (vector<T> &v, vsize i)
 143 {
 144   return v[v.size () - i - 1];
 145 }
 146
 147 template<typename T>
 148 void
 149 concat (vector<T> &v, vector<T> const &w)
 150 {
 151   v.insert (v.end (), w.begin (), w.end ());
 152 }
 153
 154 template<typename T, typename Compare>
 155 vsize
 156 lower_bound (vector<T> const &v,
 157              T const &key,
 158              Compare less,
 159              vsize b = 0, vsize e = VPOS)
 160 {
 161   if (e == VPOS)
 162     e = v.size ();
 163   typename vector<T>::const_iterator i = lower_bound (v.begin () + b,
 164                                                       v.begin () + e,
 165                                                       key,
 166                                                       less);
 167
 168   return i - v.begin ();
 169 }
 170
 171 template<typename T, typename Compare>
 172 vsize
 173 upper_bound (vector<T> const &v,
 174              T const &key,
 175              Compare less,
 176              vsize b = 0, vsize e = VPOS)
 177 {
 178   if (e == VPOS)
 179     e = v.size ();
 180
 181   typename vector<T>::const_iterator i = upper_bound (v.begin () + b,
 182                                                       v.begin () + e,
 183                                                       key,
 184                                                       less);
 185
 186   return i - v.begin ();
 187 }
 188
 189 template<typename T, typename Compare>
 190 vsize
 191 binary_search (vector<T> const &v,
 192                T const &key,
 193                Compare less = less<T> (),
 194                vsize b = 0, vsize e = VPOS)
 195 {
 196   vsize lb = lower_bound (v, key, less, b, e);
 197
 198   if (lb == v.size () || less (key, v[lb]))
 199     return VPOS;
 200   return lb;
 201 }
 202
 203 template<typename T, typename Compare>
 204 void
 205 vector_sort (vector<T> &v,
 206              Compare less,
 207              vsize b = 0, vsize e = VPOS)
 208 {
 209   if (e == VPOS)
 210     e = v.size ();
 211
 212   sort (v.begin () + b, v.begin () + e, less);
 213 }
 214
 215 template<typename T>
 216 void
 217 reverse (vector<T> &v)
 218 {
 219   // CHECKME: for a simple vector, like vector<int>, this should
 220   // expand to memrev.
 221   reverse (v.begin (), v.end ());
 222 }
 223
 224 template<typename T>
 225 void
 226 uniq (vector<T> &v)
 227 {
 228   v.erase (unique (v.begin (), v.end ()), v.end ());
 229 }
 230
 231 template<typename T>
 232 typename vector<T>::const_iterator
 233 find (vector<T> const &v, T const &key)
 234 {
 235   return find (v.begin (), v.end (), key);
 236 }
 237
 238 template<typename T> struct del : public unary_function<T, void>
 239 {
 240   void operator () (T x)
 241   {
 242     delete x;
 243     x = 0;
 244   }
 245 };
 246
 247 template<typename T>
 248 void
 249 junk_pointers (vector<T> &v)
 250 {
 251   // Hmm.
 252   for_each (v.begin (), v.end (), del<T> ());
 253   v.clear ();
 254 }
 255
 256 vector<string> string_split (string str, char c);
 257 string string_join (vector<string> const &strs, string infix);
 258
 259 #define iterof(i,s) typeof((s).begin()) i((s).begin())
 260
 261 #endif /* STD_VECTOR_HH */