Index: flower/include/std-vector.hh =================================================================== RCS file: /sources/lilypond/lilypond/flower/include/std-vector.hh,v retrieving revision 1.25 diff -u -r1.25 std-vector.hh --- flower/include/std-vector.hh 5 May 2006 14:19:18 -0000 1.25 +++ flower/include/std-vector.hh 7 Sep 2006 06:10:33 -0000 @@ -132,106 +132,55 @@ 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) +template +vsize +upper_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; + if (e == VPOS) + e = v.size (); - result = (*compare) ((T *) key, table[cmp]); + typename vector::const_iterator i = upper_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) -{ - 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) + 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 Index: lily/keyword.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/keyword.cc,v retrieving revision 1.18 diff -u -r1.18 keyword.cc --- lily/keyword.cc 3 Feb 2006 01:32:16 -0000 1.18 +++ lily/keyword.cc 7 Sep 2006 06:10:35 -0000 @@ -9,6 +9,11 @@ using namespace std; /* for qsort */ +bool tab_less (Keyword_ent const &p1, Keyword_ent const &p2) +{ + return strcmp (p1.name_, p2.name_) < 0; +} + int tabcmp (Keyword_ent const &p1, Keyword_ent const &p2) { return strcmp (p1.name_, p2.name_); @@ -27,7 +32,7 @@ { Keyword_ent e; e.name_ = s; - vsize idx = binary_search (table_, e, tabcmp); + vsize idx = binary_search (table_, e, tab_less); if (idx != VPOS) return table_[idx].tokcode_; return VPOS; Index: lily/paper-column.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/paper-column.cc,v retrieving revision 1.98 diff -u -r1.98 paper-column.cc --- lily/paper-column.cc 4 Aug 2006 11:56:43 -0000 1.98 +++ lily/paper-column.cc 7 Sep 2006 06:10:35 -0000 @@ -79,6 +79,13 @@ - dynamic_cast (b)->rank_); } +bool +Paper_column::less_than (Grob *const &a, + Grob *const &b) +{ + return dynamic_cast (a)->rank_ < dynamic_cast (b)->rank_; +} + Moment Paper_column::when_mom (Grob *me) { Index: lily/simple-spacer.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/simple-spacer.cc,v retrieving revision 1.103 diff -u -r1.103 simple-spacer.cc --- lily/simple-spacer.cc 4 Sep 2006 05:31:27 -0000 1.103 +++ lily/simple-spacer.cc 7 Sep 2006 06:10:35 -0000 @@ -332,8 +332,6 @@ } }; -static int compare_paper_column_rank (Grob *const &a, Grob *const &b); - static bool is_loose (Grob *g) { @@ -400,7 +398,7 @@ scm_is_pair (s); s = scm_cdr (s)) { Grob *other = unsmob_grob (scm_caar (s)); - vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index); + vsize j = binary_search (cols, other, Paper_column::less_than, col_index); if (j != VPOS) { if (cols[j] == other) @@ -561,9 +559,3 @@ return ret; } -static int -compare_paper_column_rank (Grob *const &a, - Grob *const &b) -{ - return Paper_column::get_rank (a) - Paper_column::get_rank (b); -} Index: lily/source-file.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/source-file.cc,v retrieving revision 1.54 diff -u -r1.54 source-file.cc --- lily/source-file.cc 1 Sep 2006 11:57:55 -0000 1.54 +++ lily/source-file.cc 7 Sep 2006 06:10:35 -0000 @@ -335,10 +335,11 @@ if (newline_locations_[hi - 1] < pos_str0) return hi; - binary_search_bounds (newline_locations_, - (char const*&)pos_str0, - default_compare, - &lo, &hi); + lo = binary_search (newline_locations_, + pos_str0, + less (), + lo, hi); + if (*pos_str0 == '\n') lo--; Index: lily/spacing-spanner.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/spacing-spanner.cc,v retrieving revision 1.174 diff -u -r1.174 spacing-spanner.cc --- lily/spacing-spanner.cc 21 Jul 2006 11:44:58 -0000 1.174 +++ lily/spacing-spanner.cc 7 Sep 2006 06:10:35 -0000 @@ -31,9 +31,9 @@ { vector all (get_root_system (me)->columns ()); vsize start = binary_search (all, (Grob*)me->get_bound (LEFT), - &Paper_column::compare); + &Paper_column::less_than); vsize end = binary_search (all, (Grob*) me->get_bound (RIGHT), - &Paper_column::compare); + &Paper_column::less_than); all = vector::vector (all.begin () + start, all.begin () + end + 1); Index: lily/spanner.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/spanner.cc,v retrieving revision 1.150 diff -u -r1.150 spanner.cc --- lily/spanner.cc 11 Feb 2006 11:35:17 -0000 1.150 +++ lily/spanner.cc 7 Sep 2006 06:10:35 -0000 @@ -238,7 +238,7 @@ Grob * Spanner::find_broken_piece (System *l) const { - vsize idx = binary_search (broken_intos_, (Spanner *)l, Spanner::compare); + vsize idx = binary_search (broken_intos_, (Spanner *)l, Spanner::less_than); if (idx != VPOS) return broken_intos_ [idx]; return 0; @@ -251,6 +251,12 @@ } bool +Spanner::less_than (Spanner *const &a, Spanner *const &b) +{ + return a->get_system ()->get_rank () < b->get_system ()->get_rank (); +} + +bool Spanner::is_broken () const { return broken_intos_.size (); Index: lily/include/paper-column.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/paper-column.hh,v retrieving revision 1.40 diff -u -r1.40 paper-column.hh --- lily/include/paper-column.hh 4 Aug 2006 00:34:34 -0000 1.40 +++ lily/include/paper-column.hh 7 Sep 2006 06:10:35 -0000 @@ -33,6 +33,9 @@ static int compare (Grob * const &a, Grob * const &b); + static bool less_than (Grob *const &a, + Grob *const &b); + int get_rank () const { return rank_; } void set_rank (int); Index: lily/include/source-file.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/source-file.hh,v retrieving revision 1.25 diff -u -r1.25 source-file.hh --- lily/include/source-file.hh 24 Aug 2006 10:31:55 -0000 1.25 +++ lily/include/source-file.hh 7 Sep 2006 06:10:35 -0000 @@ -27,7 +27,7 @@ class Source_file { - vector newline_locations_; + vector newline_locations_; istream *istream_; vector characters_; SCM str_port_; Index: lily/include/spanner.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/spanner.hh,v retrieving revision 1.82 diff -u -r1.82 spanner.hh --- lily/include/spanner.hh 9 Jun 2006 02:20:22 -0000 1.82 +++ lily/include/spanner.hh 7 Sep 2006 06:10:35 -0000 @@ -56,6 +56,7 @@ Real spanner_length () const; static int compare (Spanner *const &, Spanner *const &); + static bool less_than (Spanner *const &, Spanner *const &); virtual Grob *find_broken_piece (System *) const; virtual void derived_mark () const; static bool has_interface (Grob *);