I haven't been doing very well with attachments lately, have I?
On Thu, 2006-09-07 at 16:34 +1000, Joe Neeman wrote:
> This removes our re-implementation of binary search and uses the STL
> version. The main change is to remove strcmp-like comparison functions
> and replace them with binary "less than" predicates.
>
> I also include wrappers for lower_bound and upper_bound. I use these in
> my working copy, but that patch isn't ready yet.
>
> If this patch is OK, I want to do the same thing for vector_sort next.
>
> 2006-09-07 Joe Neeman <[EMAIL PROTECTED]>
>
> * lily/spanner.cc (find_broken_piece):
> * lily/spacing-spanner.cc (get_columns):
> * lily/source-file.cc (get_line):
> * lily/simple-spacer.cc (get_column_description):
> * lily/keyword.cc (lookup):
> use the new binary search.
>
> * flower/include/std-vector.hh: replace binary_search with
> a more STL-like version
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<class T>
-void
-binary_search_bounds (vector<T> const &table,
- T const &key, int (*compare) (T const &, T const &),
- vsize *lo,
- vsize *hi)
+template<typename T, typename Compare>
+vsize
+lower_bound (vector<T> 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<T>::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<typename T>
-void
-binary_search_bounds (vector<T*> const &table,
- T const *key, int (*compare) (T *const &, T *const &),
- vsize *lo,
- vsize *hi)
+template<typename T, typename Compare>
+vsize
+upper_bound (vector<T> 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<T>::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<typename T>
+template<typename T, typename Compare>
vsize
binary_search (vector<T> 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<T>::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<class T>
-vsize
-binary_search (vector<T> const &table,
T const &key,
- int (*compare) (T const &, T const &),
- vsize lo=0,
- vsize hi=VPOS)
+ Compare less=less<T> (),
+ 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<typename T>
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<Paper_column*> (b)->rank_);
}
+bool
+Paper_column::less_than (Grob *const &a,
+ Grob *const &b)
+{
+ return dynamic_cast<Paper_column*> (a)->rank_ < dynamic_cast<Paper_column*> (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<char const*> (),
+ 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<Grob*> 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<Grob*>::vector<Grob*> (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<char*> newline_locations_;
+ vector<char const*> newline_locations_;
istream *istream_;
vector<char> 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 *);
_______________________________________________
lilypond-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/lilypond-devel
