X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fstd-vector.hh;h=76a11bb9252237189463c667290df2cd01ecc183;hb=5b4b0d6e9a197e8f9eb085b7c2ad78b8be3e5cfc;hp=8c31e664aa23f26835db10f6d69b1e6b5d8db40c;hpb=1e2c23a85f2dbb849f5c71696c1bd320816270cb;p=lilypond.git diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh index 8c31e664aa..76a11bb925 100644 --- a/flower/include/std-vector.hh +++ b/flower/include/std-vector.hh @@ -3,19 +3,30 @@ 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 @@ -24,7 +35,7 @@ int default_compare (T const &a, T const &b) { if (a < b) return -1; - else if (a > b) + else if (b < a) return 1; else return 0; @@ -42,7 +53,6 @@ int default_compare (T *const &a, T *const &b) } #include "compare.hh" -#include "config.hh" #ifndef VSIZE #define VSIZE @@ -66,21 +76,25 @@ namespace std { public: typedef typename __vector::iterator iterator; typedef typename __vector::const_iterator const_iterator; - + vector () : __vector () { } - + + vector (vector const& v) : __vector (v) + { + } + vector (const_iterator b, const_iterator e) : __vector (b, e) { } - + T* data () { return &(*this)[0]; } - + T const* data () const { @@ -128,148 +142,68 @@ 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; - - /* 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 -void -binary_search_bounds (vector const &table, - T const *key, int (*compare) (T *const &, T *const &), - vsize *lo, - vsize *hi) +template +vsize +lower_bound (vector const &v, + T const &key, + Compare less, + vsize b=0, vsize e=VPOS) { - vsize cmp; - int result; - - /* binary search */ - do - { - cmp = (*lo + *hi) / 2; - - result = (*compare) ((T *) key, table[cmp]); + if (e == VPOS) + e = v.size (); + typename vector::const_iterator i = lower_bound (v.begin () + b, + v.begin () + e, + key, + less); - if (result < 0) - *hi = cmp; - else - *lo = cmp; - } - while (*hi - *lo > 1); + return i - v.begin (); } -#if 0 -/* FIXME: what if COMPARE is named: int operator == (T const&, T const&), - wouldn't that work for most uses of BINARY_SEARCH? -*/ -template +template vsize -binary_search (vector const &v, - T const &key, int (*compare) (T const &, T const &), - vsize b=0, vsize e=VPOS) +upper_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 = find (v.begin () + b, - v.begin () + e, - key); - if (i != v.end ()) - return i - v.begin (); - return VPOS; + + typename vector::const_iterator i = upper_bound (v.begin () + b, + v.begin () + e, + key, + less); + + return i - v.begin (); } -#else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func. -template + +template vsize -binary_search (vector const &table, +binary_search (vector const &v, T const &key, - int (*compare) (T const &, T const &), - vsize lo=0, - vsize hi=VPOS) + Compare less=less (), + vsize b=0, vsize e=VPOS) { - if (hi == VPOS) - hi = table.size (); + vsize lb = lower_bound (v, key, less, b, e); - if (lo >= hi) + if (lb == v.size () || less (key, v[lb])) return VPOS; - - binary_search_bounds (table, key, compare, &lo, &hi); - - if (! (*compare) (key, table[lo])) - return lo; - - /* not found */ - return VPOS; + return lb; } - -#endif - - -#if 0 -/* FIXME: the COMPARE functionality is broken? */ -template +template void -vector_sort (vector &v, int (*compare) (T const &, T const &), - vsize lower=VPOS, vsize upper=VPOS) +vector_sort (vector &v, + Compare less, + vsize b=0, vsize e=VPOS) { - typename vector::iterator b = v.begin (); - typename vector::iterator e = v.begin (); - if (lower == VPOS) - { - lower = 0; - upper = v.size (); - } - sort (b + lower, e + upper, compare); -} -#else + 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); + sort (v.begin () + b, v.begin () + e, less); } -#endif - + template void reverse (vector &v) @@ -293,7 +227,7 @@ find (vector const &v, T const &key) return find (v.begin (), v.end (), key); } -#if HAVE_BOOST_LAMBDA +#if HAVE_BOOST_LAMBDA_LAMBDA_HPP #include using namespace boost::lambda; template @@ -324,4 +258,9 @@ junk_pointers (vector &v) } #endif /* HAVE_BOOST_LAMBDA */ +vector string_split (string str, char c); +string string_join (vector const &strs, string infix); + +#define iterof(i,s) typeof((s).begin()) i((s).begin()) + #endif /* STD_VECTOR_HH */