X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fstd-vector.hh;h=ec45376efa8fda0e9b335ae4d71afd8f1a7bf91e;hb=dff732268215aa3dd27c2ca918db2f70f294cc53;hp=e8367ae8a625e7068b5b70c1fe6beac96cd06c4f;hpb=6c68e65859bae109509e1c464fdfca6de4b5ddd1;p=lilypond.git diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh index e8367ae8a6..ec45376efa 100644 --- a/flower/include/std-vector.hh +++ b/flower/include/std-vector.hh @@ -1,31 +1,51 @@ /* - 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--2010 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 +#if 0 + +/* + leads to dubious crashes - libstdc++ bug? +*/ +#ifndef NDEBUG +#define _GLIBCXX_DEBUG 1 +#endif +#endif + #include /* find, reverse, sort */ #include /* unary_function */ #include +#include -#if HAVE_BOOST_LAMBDA -#include -#endif +using namespace std; template int default_compare (T const &a, T const &b) { - if (a < b) - return -1; - else if (a > b) - return 1; - else - return 0; + if (a < b) + return -1; + else if (b < a) + return 1; + else + return 0; } template @@ -39,257 +59,202 @@ int default_compare (T *const &a, T *const &b) return 0; } -#if !STD_VECTOR -/* Also declare vector, in the wrong way. */ -#include -#include -#include -#endif - #include "compare.hh" -#if STD_VECTOR +#ifndef VSIZE +#define VSIZE +typedef size_t vsize; +#define VPOS ((vsize) -1) +#endif +#if HAVE_STL_DATA_METHOD +#include +#else /* !HAVE_STL_DATA_METHOD */ +#define vector __flower_vector #include +#undef vector namespace std { - #ifndef VSIZE - #define VSIZE - typedef size_t vsize; - #define VPOS UINT_MAX - #endif - - template - T const & - boundary (vector const &v, int dir, vsize i) + /* Interface without pointer arithmetic (iterator) semantics. */ + template > + class vector : public __flower_vector { - assert (dir); - return v[dir == -1 ? i : v.size () - 1 - i]; - } + public: + typedef typename __flower_vector::iterator iterator; + typedef typename __flower_vector::const_iterator const_iterator; - 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]; - } - - template - void - concat (vector &v, vector const& w) - { - v.insert (v.end (), w.begin (), w.end ()); - } - - template - void - binary_search_bounds (vector const &table, - T const &key, int (*compare) (T const &, T const &), - vsize *lo, - vsize *hi) - { - if (*lo >= *hi) - return; - - int cmp; - int result; + vector () : __flower_vector () + { + } - /* binary search */ - do - { - cmp = (*lo + *hi) / 2; + vector (vector const& v) : __flower_vector (v) + { + } - result = (*compare) (key, table[cmp]); + vector (const_iterator b, const_iterator e) : __flower_vector (b, e) + { + } - if (result < 0) - *hi = cmp; - else - *lo = cmp; - } - while (*hi - *lo > 1); - } + T* + data () + { + return &(*this)[0]; + } -#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) - { - //(void) compare; - if (e == VPOS) - e = v.size (); - typename vector::const_iterator i = find (v.begin () + b, - v.begin () + 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 - vsize - binary_search (vector const &table, - T const &key, - int (*compare) (T const &, T const &), - vsize lo=0, - vsize hi=VPOS) - { - if (hi == VPOS) - hi = table.size (); + T const* + data () const + { + return &(*this)[0]; + } + }; - if (lo >= hi) - return VPOS; +} /* namespace std */ - binary_search_bounds (table, key, compare, &lo, &hi); +#endif /* !HAVE_STL_DATA_METHOD */ - if (! (*compare) (key, table[lo])) - return lo; +template +T const & +boundary (vector const &v, int dir, vsize i) +{ + assert (dir); + return v[dir == -1 ? i : v.size () - 1 - i]; +} - /* not found */ - return VPOS; - } +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]; +} -#endif +template +T& +back (vector &v, vsize i) +{ + return v[v.size () - i - 1]; +} +template +void +concat (vector &v, vector const& w) +{ + v.insert (v.end (), w.begin (), w.end ()); +} -#if 0 - /* FIXME: the COMPARE functionality is broken? */ - template - void - vector_sort (vector &v, int (*compare) (T const &, T const &), - vsize lower=VPOS, vsize upper=VPOS) - { - 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); - } -#else +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 (); +} - // ugh, c&p - template void - vector_sort (vector &v, int (*compare) (T const &, T const &), - vsize lower=VPOS, vsize upper=VPOS) - { - if (lower == VPOS) - { - lower = 0; - upper = v.size () - 1; - } - if (upper == VPOS || lower >= upper) - return; - swap (v[lower], v[(lower + upper) / 2]); - vsize last = lower; - for (vsize i = lower +1; i <= upper; i++) - if (compare (v[i], v[lower]) < 0) - swap (v[++last], v[i]); - swap (v[lower], v[last]); - vector_sort (v, compare, lower, last - 1); - vector_sort (v, compare, last + 1, upper); - } -#endif - - template - void - reverse (vector &v) - { - // CHECKME: for a simple vector, like vector, this should - // expand to memrev. - ::std::reverse (v.begin (), v.end ()); - } +template +vsize +upper_bound (vector const &v, + T const &key, + Compare less, + vsize b=0, vsize e=VPOS) +{ + if (e == VPOS) + e = v.size (); - template - void - uniq (vector &v) - { - v.erase (unique (v.begin (), v.end ()), v.end ()); - } + typename vector::const_iterator i = upper_bound (v.begin () + b, + v.begin () + e, + key, + less); - template - typename vector::const_iterator - find (vector const &v, T const &key) - { - return ::std::find (v.begin (), v.end (), key); - } + return i - v.begin (); +} -#if HAVE_BOOST_LAMBDA -#include - using namespace boost::lambda; - template - void - junk_pointers (vector &v) - { - for_each (v.begin (), v.end (), (delete _1, _1 = 0)); - v.clear (); - } -#else +template +vsize +binary_search (vector const &v, + T const &key, + Compare less=less (), + vsize b=0, vsize e=VPOS) +{ + vsize lb = lower_bound (v, key, less, b, e); - template struct del : public unary_function - { - void operator() (T x) - { - delete x; - x = 0; - } - }; + if (lb == v.size () || less (key, v[lb])) + return VPOS; + return lb; +} - template - void - junk_pointers (vector &v) - { - // Hmm. - ::std::for_each (v.begin (), v.end (), del ()); - v.clear (); - } -#endif /* HAVE_BOOST_LAMBDA */ +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); } -#else /* ! STD_VECTOR */ +template +void +reverse (vector &v) +{ + // CHECKME: for a simple vector, like vector, this should + // expand to memrev. + reverse (v.begin (), v.end ()); +} -namespace std { +template +void +uniq (vector &v) +{ + v.erase (unique (v.begin (), v.end ()), v.end ()); +} -#ifndef Array -#define vector Array -#endif +template +typename vector::const_iterator +find (vector const &v, T const &key) +{ + return find (v.begin (), v.end (), key); +} - using namespace std; - -#ifndef VSIZE -#define VSIZE - typedef int vsize; -#define VPOS -1 -#endif +template struct del : public unary_function +{ + void operator() (T x) + { + delete x; + x = 0; + } +}; +template +void +junk_pointers (vector &v) +{ + // Hmm. + for_each (v.begin (), v.end (), del ()); + v.clear (); } -#include "array.hh" -#include "parray.hh" - -#endif /* !STD_VECTOR */ +vector string_split (string str, char c); +string string_join (vector const &strs, string infix); -using namespace std; +#define iterof(i,s) typeof((s).begin()) i((s).begin()) #endif /* STD_VECTOR_HH */