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