X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;ds=sidebyside;f=flower%2Finclude%2Fstd-vector.hh;h=fd7f963dbac268171a164ef1c2869d77a9b025d9;hb=e59102924fa3a23511d297b123488dd810e7067c;hp=3386ac74b8d117bc64999201dd0fe394811740a9;hpb=86fac535aef982d4f98f9f51e7476ab84b28c247;p=lilypond.git diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh index 3386ac74b8..fd7f963dba 100644 --- a/flower/include/std-vector.hh +++ b/flower/include/std-vector.hh @@ -1,5 +1,5 @@ /* - std-vector.hh -- declare std::vector + std-vector.hh -- declare vector source file of the GNU LilyPond music typesetter @@ -9,149 +9,248 @@ #ifndef STD_VECTOR_HH #define STD_VECTOR_HH -#include // reverse, sort +#include /* find, reverse, sort */ +#include /* unary_function */ +#include -#if !STD_VECTOR -/* Also declare vector, in the wrong way. */ -#include -#include -#include +using namespace std; + +#if HAVE_BOOST_LAMBDA +#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; +} + +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 +#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) + /* Interface without pointer arithmetic (iterator) semantics. */ + template > + class vector : public __vector { - assert (dir); - return v[dir == -1 ? i : v.size () - 1 - i]; - } + public: + typedef typename __vector::iterator iterator; + typedef typename __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]; - } + vector () : __vector () + { + } - template - T const & - back (vector const &v, vsize i) - { - return v[v.size () - i - 1]; - } + 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 + { + return &(*this)[0]; + } + }; + +} /* namespace std */ + +#endif /* !HAVE_STL_DATA_METHOD */ + +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) +{ + 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; + + /* 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) +{ + vsize cmp; + int result; + + /* binary search */ + do + { + cmp = (*lo + *hi) / 2; + + result = (*compare) ((T *) key, table[cmp]); + + if (result < 0) + *hi = cmp; + else + *lo = cmp; + } + while (*hi - *lo > 1); +} - template - T& - back (vector &v, vsize i) - { - return v[v.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) - { - //(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; - } +/* FIXME: what if COMPARE is named: int operator == (T const&, T const&), + wouldn't that work for most uses of BINARY_SEARCH? +*/ +template +vsize +binary_search (vector const &v, + T const &key, int (*compare) (T const &, T const &), + 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; +} #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) - { - 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) +{ + if (hi == VPOS) + hi = table.size (); - 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 (); + if (lo >= hi) + return VPOS; - binary_search_bounds (table, key, compare, &lo, &hi); + binary_search_bounds (table, key, compare, &lo, &hi); + + if (! (*compare) (key, table[lo])) + return lo; + + /* not found */ + return VPOS; +} - if (! (*compare) (key, table[lo])) - return lo; - /* not found */ - return VPOS; - } #endif #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) - { - 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); - } +/* 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 (); + } + sort (b + lower, e + upper, compare); +} #else - template - void - swap (T *a, T *b) - { - T t = *a; - *a = *b; - *b = t; - } - - // ugh, c&p +// ugh, c&p template void vector_sort (vector &v, int (*compare) (T const &, T const &), vsize lower=VPOS, vsize upper=VPOS) @@ -172,55 +271,64 @@ vector_sort (vector &v, int (*compare) (T const &, T const &), vector_sort (v, compare, lower, last - 1); vector_sort (v, compare, last + 1, upper); } - - template - void - reverse (vector &v) - { - // CHECKME: for a simple vector, like vector, this should - // expand to memrev. - ::std::reverse (v.begin (), v.end ()); - } - #endif +template +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 ()); +} - -#else /* ! STD_VECTOR */ - -namespace std { - -#ifndef Array -#define vector Array -#endif - - using namespace std; - -#ifndef VSIZE -#define VSIZE - typedef int vsize; -#define VPOS -1 -#endif - +template +typename vector::const_iterator +find (vector const &v, T const &key) +{ + return find (v.begin (), v.end (), key); } +#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 -#endif /* STD_VECTOR */ +template struct del : public unary_function +{ + void operator() (T x) + { + delete x; + x = 0; + } +}; template -int default_compare (T const &a, T const &b) +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 (); } - +#endif /* HAVE_BOOST_LAMBDA */ + +vector string_split (string str, char c); -#include "array.hh" +#define iterof(i,s) typeof((s).begin()) i((s).begin()) #endif /* STD_VECTOR_HH */