X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fstd-vector.hh;h=76a11bb9252237189463c667290df2cd01ecc183;hb=5b4b0d6e9a197e8f9eb085b7c2ad78b8be3e5cfc;hp=e8367ae8a625e7068b5b70c1fe6beac96cd06c4f;hpb=6c68e65859bae109509e1c464fdfca6de4b5ddd1;p=lilypond.git diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh index e8367ae8a6..76a11bb925 100644 --- a/flower/include/std-vector.hh +++ b/flower/include/std-vector.hh @@ -1,31 +1,44 @@ /* - std-vector.hh -- declare std::vector + std-vector.hh -- declare vector source file of the GNU LilyPond music typesetter - (c) 2006 Jan Nieuwenhuizen + (c) 2006--2008 Jan Nieuwenhuizen */ #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 + +using namespace std; -#if HAVE_BOOST_LAMBDA +#if HAVE_BOOST_LAMBDA_LAMBDA_HPP #include #endif 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 +52,215 @@ 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 __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) - { - assert (dir); - return v[dir == -1 ? i : v.size () - 1 - i]; - } - - 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) + /* Interface without pointer arithmetic (iterator) semantics. */ + template > + class vector : public __vector { - return v[v.size () - i - 1]; - } + public: + typedef typename __vector::iterator iterator; + typedef typename __vector::const_iterator const_iterator; - 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; + vector () : __vector () + { + } - int cmp; - int result; + vector (vector const& v) : __vector (v) + { + } - /* binary search */ - do - { - cmp = (*lo + *hi) / 2; + vector (const_iterator b, const_iterator e) : __vector (b, e) + { + } - result = (*compare) (key, table[cmp]); + T* + data () + { + return &(*this)[0]; + } - if (result < 0) - *hi = cmp; - else - *lo = cmp; - } - while (*hi - *lo > 1); - } + T const* + data () const + { + 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 (); +} /* namespace std */ - if (lo >= hi) - return VPOS; +#endif /* !HAVE_STL_DATA_METHOD */ - binary_search_bounds (table, key, compare, &lo, &hi); +template +T const & +boundary (vector const &v, int dir, vsize i) +{ + assert (dir); + return v[dir == -1 ? i : v.size () - 1 - i]; +} - if (! (*compare) (key, table[lo])) - return lo; +template +T & +boundary (vector &v, int dir, vsize i) +{ + assert (dir); + return v[dir == -1 ? i : v.size () - 1 - i]; +} - /* not found */ - return VPOS; - } +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]; +} -#endif +template +void +concat (vector &v, vector const& w) +{ + v.insert (v.end (), w.begin (), w.end ()); +} +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 (); +} -#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 +upper_bound (vector const &v, + T const &key, + Compare less, + vsize b=0, vsize e=VPOS) +{ + if (e == VPOS) + e = v.size (); - // 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 ()); - } + typename vector::const_iterator i = upper_bound (v.begin () + b, + v.begin () + e, + key, + less); - template - void - uniq (vector &v) - { - v.erase (unique (v.begin (), v.end ()), v.end ()); - } + return i - v.begin (); +} - template - typename vector::const_iterator - find (vector const &v, T const &key) - { - return ::std::find (v.begin (), v.end (), key); - } +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); -#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 + if (lb == v.size () || less (key, v[lb])) + return VPOS; + return lb; +} - template struct del : public unary_function - { - void operator() (T x) - { - delete x; - x = 0; - } - }; +template +void +vector_sort (vector &v, + Compare less, + vsize b=0, vsize e=VPOS) +{ + if (e == VPOS) + e = v.size (); - template - void - junk_pointers (vector &v) - { - // Hmm. - ::std::for_each (v.begin (), v.end (), del ()); - v.clear (); - } -#endif /* HAVE_BOOST_LAMBDA */ + sort (v.begin () + b, v.begin () + e, less); +} +template +void +reverse (vector &v) +{ + // CHECKME: for a simple vector, like vector, this should + // expand to memrev. + reverse (v.begin (), v.end ()); } -#else /* ! STD_VECTOR */ +template +void +uniq (vector &v) +{ + v.erase (unique (v.begin (), v.end ()), v.end ()); +} -namespace std { +template +typename vector::const_iterator +find (vector const &v, T const &key) +{ + return find (v.begin (), v.end (), key); +} -#ifndef Array -#define vector Array -#endif +#if HAVE_BOOST_LAMBDA_LAMBDA_HPP +#include +using namespace boost::lambda; +template +void +junk_pointers (vector &v) +{ + for_each (v.begin (), v.end (), (delete _1, _1 = 0)); + v.clear (); +} +#else - 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 (); } +#endif /* HAVE_BOOST_LAMBDA */ -#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 */