From 767e42120b317f7ab2ca3e7a079bc4c2a0f7a776 Mon Sep 17 00:00:00 2001 From: Jan Nieuwenhuizen Date: Thu, 2 Feb 2006 00:43:26 +0000 Subject: [PATCH] *** empty log message *** --- ChangeLog | 5 ++- flower/include/array.hh | 14 -------- flower/include/array.icc | 17 +++++----- flower/include/parray.hh | 1 + flower/include/std-vector.hh | 60 ++++++++++++++++++++++++++++++---- flower/test-std.cc | 8 +++-- lily/beam.cc | 2 +- lily/grob-pq-engraver.cc | 2 +- lily/keyword.cc | 2 +- lily/new-fingering-engraver.cc | 2 +- lily/program-option.cc | 2 +- lily/span-bar.cc | 2 +- lily/stem.cc | 2 +- lily/tuplet-engraver.cc | 2 +- 14 files changed, 82 insertions(+), 39 deletions(-) diff --git a/ChangeLog b/ChangeLog index c962264fa3..946f88a3bf 100644 --- a/ChangeLog +++ b/ChangeLog @@ -4,7 +4,10 @@ 2006-02-02 Jan Nieuwenhuizen - * flower/include/std-vector.hh (slice): Remove. + * flower/include/std-vector.hh (sort): Remove, replace by + ::vector_sort. Update callers. + + * flower/include/std-vector.hh (slice): Remove. Update callers. (sort): Bugfix. * flower/test-std.cc (vector_sort): New test. diff --git a/flower/include/array.hh b/flower/include/array.hh index fbd3d83620..f057dfd06d 100644 --- a/flower/include/array.hh +++ b/flower/include/array.hh @@ -319,9 +319,6 @@ public: elem_ref (i) = back (); resize (size () -1); } - // quicksort. - void sort (int (*compare) (T const &, T const &), - vsize lower=VPOS, vsize upper=VPOS); void concat (Array const &src) { vsize s = size_; @@ -331,17 +328,6 @@ public: void reverse (); }; -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 "array.icc" } diff --git a/flower/include/array.icc b/flower/include/array.icc index 4f1a9d0bf9..839d59a532 100644 --- a/flower/include/array.icc +++ b/flower/include/array.icc @@ -51,24 +51,25 @@ Array::insert (T k, vsize j) array_[j] = k; } -template INLINE void -Array::sort (int (*compare) (T const &, T const &), vsize lower, vsize upper) +template INLINE void +vector_sort (Array &v, int (*compare) (T const &, T const &), + vsize lower=-1, vsize upper=-1) { if (lower < 0) { lower = 0; - upper = size () - 1; + upper = v.size () - 1; } if (lower >= upper) return; - swap (lower, (lower + upper) / 2); + v.swap (lower, (lower + upper) / 2); vsize last = lower; for (vsize i = lower +1; i <= upper; i++) - if (compare (array_[i], array_[lower]) < 0) - swap (++last, i); + if (compare (v.array_[i], v.array_[lower]) < 0) + v.swap (++last, i); swap (lower, last); - sort (compare, lower, last - 1); - sort (compare, last + 1, upper); + vector_sort (v, compare, lower, last - 1); + vector_sort (v, compare, last + 1, upper); } template INLINE void diff --git a/flower/include/parray.hh b/flower/include/parray.hh index d89c2b95d2..645091f2a3 100644 --- a/flower/include/parray.hh +++ b/flower/include/parray.hh @@ -42,6 +42,7 @@ public: } Array::begin; + Array::end; Array::clear; Array::erase; Array::resize; diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh index dd3f97e30f..022d107b02 100644 --- a/flower/include/std-vector.hh +++ b/flower/include/std-vector.hh @@ -162,12 +162,6 @@ namespace std { ::std::reverse (this->begin (), this->end ()); } - void - sort (int (*compare) (T const &, T const &), vsize b=0, int e=VPOS) - { - ::std::sort (iter (b), iter(e), compare); - } - void swap (vsize i, vsize j) { T t ((*this)[i]); @@ -248,6 +242,48 @@ namespace std { } #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); + } +#else + // 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; + v.swap (lower, (lower + upper) / 2); + vsize last = lower; + for (vsize i = lower +1; i <= upper; i++) + if (compare (v[i], v[lower]) < 0) + v.swap (++last, i); + v.swap (lower, last); + vector_sort (v, compare, lower, last - 1); + vector_sort (v, compare, last + 1, upper); +} + +#endif + } @@ -273,6 +309,18 @@ namespace std { #endif /* STD_VECTOR */ +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 "array.hh" #endif /* STD_VECTOR_HH */ diff --git a/flower/test-std.cc b/flower/test-std.cc index eeceaddb15..729073f8c6 100644 --- a/flower/test-std.cc +++ b/flower/test-std.cc @@ -59,13 +59,17 @@ BOOST_AUTO_UNIT_TEST (vector_slice) #endif } -BOOST_AUTO_UNIT_TEST (vector_sort) +BOOST_AUTO_UNIT_TEST (vector_sorting) { vector v; v.push_back (2); v.push_back (1); v.push_back (0); +#if VECTOR_SORT v.sort (default_compare); +#else + vector_sort (v, default_compare); +#endif print (v); BOOST_CHECK_EQUAL (v[0], 0); BOOST_CHECK_EQUAL (v[1], 1); @@ -78,6 +82,6 @@ init_unit_test_suite (int, char**) test_suite *test = BOOST_TEST_SUITE("std::Flower"); test->add (BOOST_TEST_CASE (vector_erase)); test->add (BOOST_TEST_CASE (vector_slice)); - test->add (BOOST_TEST_CASE (vector_sort)); + test->add (BOOST_TEST_CASE (vector_sorting)); return test; } diff --git a/lily/beam.cc b/lily/beam.cc index 08e22e72ba..9d5d5aa212 100644 --- a/lily/beam.cc +++ b/lily/beam.cc @@ -401,7 +401,7 @@ Beam::print (SCM grob) gap_count = scm_to_int (me->get_property ("gap-count")); gapped = Lookup::beam (slope, w - 2 * gap_length, thick, blot); - full_beams.sort (default_compare); + vector_sort (full_beams, default_compare); if (stem_dir == UP) full_beams.reverse (); } diff --git a/lily/grob-pq-engraver.cc b/lily/grob-pq-engraver.cc index 1e55f60bde..a8e1081704 100644 --- a/lily/grob-pq-engraver.cc +++ b/lily/grob-pq-engraver.cc @@ -95,7 +95,7 @@ Grob_pq_engraver::stop_translation_timestep () while (scm_is_pair (busy) && *unsmob_moment (scm_caar (busy)) == now) busy = scm_cdr (busy); - started_now_.sort (Grob_pq_entry::compare); + vector_sort (started_now_, Grob_pq_entry::compare); SCM lst = SCM_EOL; SCM *tail = &lst; for (vsize i = 0; i < started_now_.size (); i++) diff --git a/lily/keyword.cc b/lily/keyword.cc index d854fbeecd..7279ba5291 100644 --- a/lily/keyword.cc +++ b/lily/keyword.cc @@ -19,7 +19,7 @@ Keyword_table::Keyword_table (Keyword_ent *tab) while (tab->name_) table_.push_back (*tab++); - table_.sort (tabcmp); + vector_sort (table_, tabcmp); } vsize diff --git a/lily/new-fingering-engraver.cc b/lily/new-fingering-engraver.cc index 02bb58267b..d049e1664a 100644 --- a/lily/new-fingering-engraver.cc +++ b/lily/new-fingering-engraver.cc @@ -220,7 +220,7 @@ New_fingering_engraver::position_scripts (SCM orientations, } } - scripts->sort (&Finger_tuple::compare); + vector_sort (*scripts, Finger_tuple::compare); bool up_p = scm_c_memq (ly_symbol2scm ("up"), orientations) != SCM_BOOL_F; bool down_p = scm_c_memq (ly_symbol2scm ("down"), orientations) != SCM_BOOL_F; diff --git a/lily/program-option.cc b/lily/program-option.cc index 9a756af0ed..7174b82cb9 100644 --- a/lily/program-option.cc +++ b/lily/program-option.cc @@ -126,7 +126,7 @@ get_help_string () } std::string help ("Options supported by ly:set-option\n\n"); - opts.sort (string_compare); + vector_sort (opts, string_compare); for (vsize i = 0; i < opts.size (); i++) help += opts[i]; diff --git a/lily/span-bar.cc b/lily/span-bar.cc index 6290277358..14debf7c98 100644 --- a/lily/span-bar.cc +++ b/lily/span-bar.cc @@ -72,7 +72,7 @@ Span_bar::print (SCM smobbed_me) if (!model_bar) model_bar = me; - extents.sort (&Interval::left_comparison); + vector_sort (extents, Interval::left_comparison); Stencil span_bar; for (vsize i = 1; i < extents.size (); i++) diff --git a/lily/stem.cc b/lily/stem.cc index 41f039f623..937b17c824 100644 --- a/lily/stem.cc +++ b/lily/stem.cc @@ -195,7 +195,7 @@ Stem::note_head_positions (Grob *me) ps.push_back (p); } - ps.sort (integer_compare); + vector_sort (ps, integer_compare); return ps; } diff --git a/lily/tuplet-engraver.cc b/lily/tuplet-engraver.cc index 5ad157de11..ef54824044 100644 --- a/lily/tuplet-engraver.cc +++ b/lily/tuplet-engraver.cc @@ -80,7 +80,7 @@ Tuplet_engraver::process_music () if (!tuplets_.size ()) return; - tuplets_.sort (&Tuplet_description::compare); + vector_sort (tuplets_, Tuplet_description::compare); for (vsize i = 0; i < tuplets_.size (); i++) { if (tuplets_[i].bracket_) -- 2.39.2