flower/include/std-vector.hh

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2015 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 #ifdef DEBUG
  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 #include <vector>
  72
  73 template<typename T>
  74 T const &
  75 boundary (vector<T> const &v, int dir, vsize i)
  76 {
  77   assert (dir);
  78   return v[dir == -1 ? i : v.size () - 1 - i];
  79 }
  80
  81 template<typename T>
  82 T &
  83 boundary (vector<T> &v, int dir, vsize i)
  84 {
  85   assert (dir);
  86   return v[dir == -1 ? i : v.size () - 1 - i];
  87 }
  88
  89 template<typename T>
  90 T const &
  91 back (vector<T> const &v, vsize i)
  92 {
  93   return v[v.size () - i - 1];
  94 }
  95
  96 template<typename T>
  97 T &
  98 back (vector<T> &v, vsize i)
  99 {
 100   return v[v.size () - i - 1];
 101 }
 102
 103 template<typename T>
 104 void
 105 concat (vector<T> &v, vector<T> const &w)
 106 {
 107   v.insert (v.end (), w.begin (), w.end ());
 108 }
 109
 110 template<typename T, typename Compare>
 111 vsize
 112 lower_bound (vector<T> const &v,
 113              T const &key,
 114              Compare less,
 115              vsize b = 0, vsize e = VPOS)
 116 {
 117   if (e == VPOS)
 118     e = v.size ();
 119   typename vector<T>::const_iterator i = lower_bound (v.begin () + b,
 120                                                       v.begin () + e,
 121                                                       key,
 122                                                       less);
 123
 124   return i - v.begin ();
 125 }
 126
 127 template<typename T, typename Compare>
 128 vsize
 129 upper_bound (vector<T> const &v,
 130              T const &key,
 131              Compare less,
 132              vsize b = 0, vsize e = VPOS)
 133 {
 134   if (e == VPOS)
 135     e = v.size ();
 136
 137   typename vector<T>::const_iterator i = upper_bound (v.begin () + b,
 138                                                       v.begin () + e,
 139                                                       key,
 140                                                       less);
 141
 142   return i - v.begin ();
 143 }
 144
 145 template<typename T, typename Compare>
 146 vsize
 147 binary_search (vector<T> const &v,
 148                T const &key,
 149                Compare less,
 150                vsize b = 0, vsize e = VPOS)
 151 {
 152   vsize lb = lower_bound (v, key, less, b, e);
 153
 154   if (lb == v.size () || less (key, v[lb]))
 155     return VPOS;
 156   return lb;
 157 }
 158
 159 template<typename T, typename Compare>
 160 void
 161 vector_sort (vector<T> &v,
 162              Compare less,
 163              vsize b = 0, vsize e = VPOS)
 164 {
 165   if (e == VPOS)
 166     e = v.size ();
 167
 168   sort (v.begin () + b, v.begin () + e, less);
 169 }
 170
 171 template<typename T>
 172 void
 173 reverse (vector<T> &v)
 174 {
 175   // CHECKME: for a simple vector, like vector<int>, this should
 176   // expand to memrev.
 177   reverse (v.begin (), v.end ());
 178 }
 179
 180 template<typename T>
 181 void
 182 uniq (vector<T> &v)
 183 {
 184   v.erase (unique (v.begin (), v.end ()), v.end ());
 185 }
 186
 187 template<typename T>
 188 typename vector<T>::const_iterator
 189 find (vector<T> const &v, T const &key)
 190 {
 191   return find (v.begin (), v.end (), key);
 192 }
 193
 194 template<typename T> struct del : public unary_function<T, void>
 195 {
 196   void operator () (T x)
 197   {
 198     delete x;
 199     x = 0;
 200   }
 201 };
 202
 203 template<typename T>
 204 void
 205 junk_pointers (vector<T> &v)
 206 {
 207   // Hmm.
 208   for_each (v.begin (), v.end (), del<T> ());
 209   v.clear ();
 210 }
 211
 212 vector<string> string_split (string str, char c);
 213 string string_join (vector<string> const &strs, const string &infix);
 214
 215 #define iterof(i,s) typeof((s).begin()) i((s).begin())
 216
 217 #endif /* STD_VECTOR_HH */