X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fstd-vector.hh;h=bb2103235edf518361e1be3fed8a96b6bf7c0f6b;hb=47db9a3883d726ca53e2133a3b2298f78dd6a32e;hp=83e58d299ccbc180babe5a7f2aa34f2b1a5dbca7;hpb=480562a839cf42dd9c59cf78fc73da59faf42c24;p=lilypond.git diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh index 83e58d299c..bb2103235e 100644 --- a/flower/include/std-vector.hh +++ b/flower/include/std-vector.hh @@ -1,24 +1,43 @@ /* - std-vector.hh -- declare 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 +#if 0 + +/* + 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; -#if HAVE_BOOST_LAMBDA -#include -#endif - template int default_compare (T const &a, T const &b) { @@ -52,44 +71,49 @@ typedef size_t vsize; #if HAVE_STL_DATA_METHOD #include #else /* !HAVE_STL_DATA_METHOD */ -#define vector __vector +#define vector __flower_vector #include #undef vector -namespace std { +namespace std +{ - /* Interface without pointer arithmetic (iterator) semantics. */ - template > - class vector : public __vector +/* 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; + + vector () : __flower_vector () { - 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 - { - return &(*this)[0]; - } - }; + } + + vector (size_t n) : __flower_vector (n) + { + } + + vector (vector const &v) : __flower_vector (v) + { + } + + vector (const_iterator b, const_iterator e) : __flower_vector (b, e) + { + } + + T * + data () + { + return &(*this)[0]; + } + + T const * + data () const + { + return &(*this)[0]; + } +}; } /* namespace std */ @@ -119,7 +143,7 @@ back (vector const &v, vsize i) } template -T& +T & back (vector &v, vsize i) { return v[v.size () - i - 1]; @@ -127,151 +151,71 @@ back (vector &v, vsize i) template void -concat (vector &v, vector const& w) +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) +template +vsize +lower_bound (vector const &v, + T const &key, + Compare less, + vsize b = 0, vsize e = VPOS) { - if (*lo >= *hi) - return; - - int cmp; - int result; - - /* binary search */ - do - { - cmp = (*lo + *hi) / 2; - - result = (*compare) (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 (); } -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); -} - -#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, - T const &key, - int (*compare) (T const &, T const &), - vsize lo=0, - vsize hi=VPOS) +binary_search (vector const &v, + T const &key, + Compare 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 @@ -296,21 +240,9 @@ 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 - template struct del : public unary_function { - void operator() (T x) + void operator () (T x) { delete x; x = 0; @@ -325,9 +257,9 @@ junk_pointers (vector &v) for_each (v.begin (), v.end (), del ()); v.clear (); } -#endif /* HAVE_BOOST_LAMBDA */ 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())