X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fstd-vector.hh;h=bb2103235edf518361e1be3fed8a96b6bf7c0f6b;hb=47db9a3883d726ca53e2133a3b2298f78dd6a32e;hp=7c957202621b63e7d002bce5f503bbd05ba9db3a;hpb=586d833b4fb7a336524eb0929d693095a802fa26;p=lilypond.git diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh index 7c95720262..bb2103235e 100644 --- a/flower/include/std-vector.hh +++ b/flower/include/std-vector.hh @@ -1,259 +1,266 @@ /* - std-vector.hh -- declare std::vector + This file is part of LilyPond, the GNU music typesetter. - source file of the GNU LilyPond music typesetter + Copyright (C) 2006--2015 Jan Nieuwenhuizen - (c) 2006 Jan Nieuwenhuizen + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see . */ #ifndef STD_VECTOR_HH #define STD_VECTOR_HH -#include // reverse, sort +#if 0 -#if !STD_VECTOR -/* Also declare vector, in the wrong way. */ -#include -#include -#include +/* + leads to dubious crashes - libstdc++ bug? +*/ +#ifndef NDEBUG +#define _GLIBCXX_DEBUG 1 +#endif #endif +#include "config.hh" /* needed at least for HAVE_STL_DATA_METHOD */ +#include /* find, reverse, sort */ +#include /* unary_function */ +#include +#include + +using namespace std; + +template +int default_compare (T const &a, T const &b) +{ + if (a < b) + return -1; + else if (b < a) + return 1; + else + return 0; +} + +template +int default_compare (T *const &a, T *const &b) +{ + if (a < b) + return -1; + else if (a > b) + return 1; + else + return 0; +} #include "compare.hh" -#if STD_VECTOR +#ifndef VSIZE +#define VSIZE +typedef size_t vsize; +#define VPOS ((vsize) -1) +#endif -#define vector __vector +#if HAVE_STL_DATA_METHOD +#include +#else /* !HAVE_STL_DATA_METHOD */ +#define vector __flower_vector #include #undef vector -namespace std { +namespace std +{ - #ifndef VSIZE - #define VSIZE - typedef size_t vsize; - #define VPOS UINT_MAX - #endif +/* Interface without pointer arithmetic (iterator) semantics. */ +template > +class vector : public __flower_vector +{ +public: + typedef typename __flower_vector::iterator iterator; + typedef typename __flower_vector::const_iterator const_iterator; - /* Interface without pointer arithmetic (iterator) semantics. */ - template - class vector : public __vector - { - public: - typedef typename __vector::iterator iterator; - typedef typename __vector::const_iterator const_iterator; - - vector () : __vector () - { - } - - vector (const_iterator b, const_iterator e) : __vector (b, e) - { - } - - /* Flower-Array compatibility. */ - void - concat (vector const &v) - { - __vector::insert (this->end (), v.begin (), v.end ()); - } - - T const & - boundary (int dir, vsize i) const - { - assert (dir); - if (dir == 1) - return this->top (i); - else - return this->at (i); - } - - T & - boundary (int dir, vsize i) - { - assert (dir); - if (dir == 1) - return this->top (i); - else - return this->at (i); - } - - T * - remove_array () - { - T *p = &(*this)[0]; - /* FIXME: forget array? */ - /* this->resize (0); */ - return p; - } - - void - reverse () - { - // CHECKME: for a simple vector, like vector, this should - // expand to memrev. - ::std::reverse (this->begin (), this->end ()); - } - - void swap (vsize i, vsize j) - { - T t ((*this)[i]); - (*this)[i] = (*this)[j]; - (*this)[j] = t; - } - - T const & - top (vsize i) const - { - return (*this)[this->size () - i - 1]; - } - - T& - top (vsize i) - { - return (*this)[this->size () - i - 1]; - } - }; - -#if 0 - template - vsize - // binary_search (std::vector const &v, - binary_search (vector const &v, - T const &key, int (*compare) (T const &, T const &), - vsize b=0, vsize e=VPOS) + vector () : __flower_vector () { - //(void) compare; - typename vector::const_iterator i = find (v.iter (b), v.iter (e), key); - if (i != v.end ()) - return i - v.begin (); - return VPOS; } -#else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func. - template - void - binary_search_bounds (vector const &table, - T const &key, int (*compare) (T const &, T const &), - vsize *lo, - vsize *hi) + + vector (size_t n) : __flower_vector (n) { - int cmp; - int result; - - /* binary search */ - do - { - cmp = (*lo + *hi) / 2; - - result = (*compare) (key, table[cmp]); - - if (result < 0) - *hi = cmp; - else - *lo = cmp; - } - while (*hi - *lo > 1); } - template - vsize - binary_search (vector const &table, - T const &key, int (*compare) (T const &, T const &), - vsize lo=0, - vsize hi=VPOS) + vector (vector const &v) : __flower_vector (v) { - if (hi == VPOS) - hi = table.size (); - - binary_search_bounds (table, key, compare, &lo, &hi); - - if (! (*compare) (key, table[lo])) - return lo; + } - /* not found */ - return VPOS; + vector (const_iterator b, const_iterator e) : __flower_vector (b, e) + { } -#endif + T * + data () + { + return &(*this)[0]; + } -#if 0 - /* FIXME: the simple test works, but lily barfs. */ - template - void - vector_sort (vector &v, int (*compare) (T const &, T const &), - vsize lower=VPOS, vsize upper=VPOS) + T const * + data () const { - typename vector::iterator b = v.begin (); - typename vector::iterator e = v.begin (); - if (lower == VPOS) - { - lower = 0; - upper = v.size (); - } - ::std::sort (b + lower, e + upper, compare); + return &(*this)[0]; } -#else - // ugh, c&p -template void -vector_sort (vector &v, int (*compare) (T const &, T const &), - vsize lower=VPOS, vsize upper=VPOS) +}; + +} /* namespace std */ + +#endif /* !HAVE_STL_DATA_METHOD */ + +template +T const & +boundary (vector const &v, int dir, vsize i) { - if (lower == VPOS) - { - lower = 0; - upper = v.size () - 1; - } - if (upper == VPOS || lower >= upper) - return; - v.swap (lower, (lower + upper) / 2); - vsize last = lower; - for (vsize i = lower +1; i <= upper; i++) - if (compare (v[i], v[lower]) < 0) - v.swap (++last, i); - v.swap (lower, last); - vector_sort (v, compare, lower, last - 1); - vector_sort (v, compare, last + 1, upper); + assert (dir); + return v[dir == -1 ? i : v.size () - 1 - i]; } - -#endif +template +T & +boundary (vector &v, int dir, vsize i) +{ + assert (dir); + return v[dir == -1 ? i : v.size () - 1 - i]; } +template +T const & +back (vector const &v, vsize i) +{ + return v[v.size () - i - 1]; +} +template +T & +back (vector &v, vsize i) +{ + return v[v.size () - i - 1]; +} -#else /* ! STD_VECTOR */ +template +void +concat (vector &v, vector const &w) +{ + v.insert (v.end (), w.begin (), w.end ()); +} -namespace std { +template +vsize +lower_bound (vector const &v, + T const &key, + Compare less, + vsize b = 0, vsize e = VPOS) +{ + if (e == VPOS) + e = v.size (); + typename vector::const_iterator i = lower_bound (v.begin () + b, + v.begin () + e, + key, + less); + + return i - v.begin (); +} -#ifndef Array -#define vector Array -#endif +template +vsize +upper_bound (vector const &v, + T const &key, + Compare less, + vsize b = 0, vsize e = VPOS) +{ + if (e == VPOS) + e = v.size (); - using namespace std; - -#ifndef VSIZE -#define VSIZE - typedef int vsize; -#define VPOS -1 -#endif + typename vector::const_iterator i = upper_bound (v.begin () + b, + v.begin () + e, + key, + less); + return i - v.begin (); } +template +vsize +binary_search (vector const &v, + T const &key, + Compare less, + vsize b = 0, vsize e = VPOS) +{ + vsize lb = lower_bound (v, key, less, b, e); -#endif /* STD_VECTOR */ + if (lb == v.size () || less (key, v[lb])) + return VPOS; + return lb; +} + +template +void +vector_sort (vector &v, + Compare less, + vsize b = 0, vsize e = VPOS) +{ + if (e == VPOS) + e = v.size (); + + sort (v.begin () + b, v.begin () + e, less); +} template -int default_compare (T const &a, T const &b) +void +reverse (vector &v) +{ + // CHECKME: for a simple vector, like vector, this should + // expand to memrev. + reverse (v.begin (), v.end ()); +} + +template +void +uniq (vector &v) +{ + v.erase (unique (v.begin (), v.end ()), v.end ()); +} + +template +typename vector::const_iterator +find (vector const &v, T const &key) +{ + return find (v.begin (), v.end (), key); +} + +template struct del : public unary_function +{ + void operator () (T x) + { + delete x; + x = 0; + } +}; + +template +void +junk_pointers (vector &v) { - if (a < b) - return -1; - else if (a > b) - return 1; - else - return 0; + // Hmm. + for_each (v.begin (), v.end (), del ()); + v.clear (); } - -#include "array.hh" +vector string_split (string str, char c); +string string_join (vector const &strs, const string &infix); + +#define iterof(i,s) typeof((s).begin()) i((s).begin()) #endif /* STD_VECTOR_HH */