From 9b5bd8f54b358e725566bae515ccc6f74f292398 Mon Sep 17 00:00:00 2001 From: Han-Wen Nienhuys Date: Tue, 1 Feb 2011 02:22:48 -0200 Subject: [PATCH] Use queue for prioritizing slur scores. This drops the number of scoring passes for input/regression/slur-scoring.ly from 11.7k to 3.0k --- lily/include/slur-configuration.hh | 42 +++++--- lily/include/slur-scoring.hh | 5 +- lily/slur-configuration.cc | 53 +++++++++-- lily/slur-scoring.cc | 148 ++++++++++++----------------- 4 files changed, 136 insertions(+), 112 deletions(-) diff --git a/lily/include/slur-configuration.hh b/lily/include/slur-configuration.hh index 992472f22a..a4d78f99c9 100644 --- a/lily/include/slur-configuration.hh +++ b/lily/include/slur-configuration.hh @@ -24,17 +24,6 @@ #include "lily-proto.hh" #include "std-vector.hh" - -enum Configuration_tag - { - SLUR_STEM = 0x01, - SLUR_HEAD = 0x02, - SLUR_FREE = 0x04, - SLUR_FREE_HEAD = 0x08, - SLUR_FREE_STEM = 0x10, - SLUR_STEM_TIP = 0x10, - }; - class Slur_configuration { Real score_; @@ -44,9 +33,20 @@ public: Drul_array attachment_; Bezier curve_; Real height_; - unsigned tags_; int index_; + enum Slur_scorers + { + INITIAL_SCORE, + SLOPE, + EDGES, + EXTRA_ENCOMPASS, + ENCOMPASS, + NUM_SCORERS, + }; + + int next_scorer_todo; + Slur_configuration (); Real score () const { return score_; } @@ -55,12 +55,28 @@ public: void generate_curve (Slur_score_state const &state, Real r0, Real h_inf, vector const &); - void calculate_score (Slur_score_state const &); + void run_next_scorer (Slur_score_state const &); + bool done () const; + static Slur_configuration *new_config (Drul_array const &offs, int idx); + protected: void score_extra_encompass (Slur_score_state const &); void score_slopes (Slur_score_state const &); void score_edges (Slur_score_state const &); void score_encompass (Slur_score_state const &); + + friend class Slur_configuration_less; +}; + +// Comparator for a queue of Beam_configuration*. +class Slur_configuration_less +{ +public: + bool operator () (Slur_configuration* const& l, Slur_configuration* const& r) + { + // Invert + return l->score_ > r->score_; + } }; #endif /* SLUR_CONFIGURATION_HH */ diff --git a/lily/include/slur-scoring.hh b/lily/include/slur-scoring.hh index 88083fa8cc..866b216942 100644 --- a/lily/include/slur-scoring.hh +++ b/lily/include/slur-scoring.hh @@ -35,7 +35,6 @@ struct Extra_collision_info Extra_collision_info (Grob *g, Real idx, Interval x, Interval y, Real p); Extra_collision_info (); - }; struct Encompass_info @@ -105,7 +104,8 @@ struct Slur_score_state Slur_score_state (); ~Slur_score_state (); - Bezier get_best_curve (); + Slur_configuration *get_forced_configuration (Interval ys) const; + Slur_configuration *get_best_curve () const; void fill (Grob *); Direction slur_direction () const; @@ -118,7 +118,6 @@ struct Slur_score_state Encompass_info get_encompass_info (Grob *col) const; vector get_extra_encompass_infos () const; Real move_away_from_staffline (Real y, Grob *on_staff) const; - int get_closest_index (SCM inspect_quants) const; Grob *breakable_bound_item (Direction) const; }; diff --git a/lily/slur-configuration.cc b/lily/slur-configuration.cc index 630fd523d8..1285a3bb5d 100644 --- a/lily/slur-configuration.cc +++ b/lily/slur-configuration.cc @@ -177,12 +177,10 @@ Slur_configuration::generate_curve (Slur_score_state const &state, Slur_configuration::Slur_configuration () { - tags_ = 0x0; score_ = 0.0; index_ = -1; }; - void Slur_configuration::add_score (Real s, string desc) { @@ -413,6 +411,7 @@ Slur_configuration::score_edges (Slur_score_state const &state) Real demerit = factor * dy; if (state.extremes_[d].stem_ && state.extremes_[d].stem_dir_ == state.dir_ + // TODO - Stem::get_beaming() should be precomputed. && !Stem::get_beaming (state.extremes_[d].stem_, -d)) demerit /= 5; @@ -467,11 +466,51 @@ Slur_configuration ::score_slopes (Slur_score_state const &state) add_score (demerit, "slope"); } + +// This is a temporary hack to see how much we can gain by using a +// priority queue on the beams to score. +static int score_count = 0; +LY_DEFINE (ly_slur_score_count, "ly:slur-score-count", 0, 0, 0, + (), + "count number of slur scores.") { + return scm_from_int (score_count); +} + void -Slur_configuration::calculate_score (Slur_score_state const &state) +Slur_configuration::run_next_scorer (Slur_score_state const &state) +{ + switch (next_scorer_todo) { + case EXTRA_ENCOMPASS: + score_extra_encompass (state); + break; + case SLOPE: + score_slopes (state); + break; + case EDGES: + score_edges (state); + break; + case ENCOMPASS: + score_encompass (state); + break; + default: + assert (false); + } + next_scorer_todo++; + score_count++; +} + +bool +Slur_configuration::done () const +{ + return next_scorer_todo >= NUM_SCORERS; +} + +Slur_configuration * +Slur_configuration::new_config (Drul_array const &offs, int idx) { - score_extra_encompass (state); - score_slopes (state); - score_edges (state); - score_encompass (state); + Slur_configuration *conf = new Slur_configuration; + conf->attachment_ = offs; + conf->index_ = idx; + conf->next_scorer_todo = INITIAL_SCORE + 1; + return conf; } diff --git a/lily/slur-scoring.cc b/lily/slur-scoring.cc index 62eeed5837..551d4b4524 100644 --- a/lily/slur-scoring.cc +++ b/lily/slur-scoring.cc @@ -21,6 +21,8 @@ #include "slur-scoring.hh" +#include + #include "accidental-interface.hh" #include "beam.hh" #include "directional-element-interface.hh" @@ -303,17 +305,31 @@ Slur::calc_control_points (SCM smob) state.generate_curves (); SCM end_ys = me->get_property ("positions"); - Bezier best; - + SCM inspect_quants = me->get_property ("inspect-quants"); + if (is_number_pair (inspect_quants)) + end_ys = inspect_quants; + + Slur_configuration *best = NULL; if (is_number_pair (end_ys)) - best = state.configurations_[state.get_closest_index (end_ys)]->curve_; + best = state.get_forced_configuration (ly_scm2interval(end_ys)); else best = state.get_best_curve (); +#if DEBUG_SLUR_SCORING + bool debug_slurs = to_boolean (me->layout () + ->lookup_variable (ly_symbol2scm ("debug-slur-scoring"))); + if (debug_slurs) + { + string total = best->card (); + total += to_string (" TOTAL=%.2f idx=%d", best->score (), best->index_); + me->set_property ("quant-score", ly_string2scm (total)); + } +#endif + SCM controls = SCM_EOL; for (int i = 4; i--;) { - Offset o = best.control_[i] + Offset o = best->curve_.control_[i] - Offset (me->relative_coordinate (state.common_[X_AXIS], X_AXIS), me->relative_coordinate (state.common_[Y_AXIS], Y_AXIS)); controls = scm_cons (ly_offset2scm (o), controls); @@ -322,72 +338,52 @@ Slur::calc_control_points (SCM smob) return controls; } -Bezier -Slur_score_state::get_best_curve () +Slur_configuration* +Slur_score_state::get_forced_configuration (Interval ys) const { - int opt_idx = -1; - Real opt = 1e6; - -#if DEBUG_SLUR_SCORING - bool debug_slurs = to_boolean (slur_->layout () - ->lookup_variable (ly_symbol2scm ("debug-slur-scoring"))); - SCM inspect_quants = slur_->get_property ("inspect-quants"); - SCM inspect_index = slur_->get_property ("inspect-index"); - if (debug_slurs - && scm_is_integer (inspect_index)) - { - opt_idx = scm_to_int (inspect_index); - configurations_[opt_idx]->calculate_score (*this); - opt = configurations_[opt_idx]->score (); - } - else if (debug_slurs - && scm_is_pair (inspect_quants)) - { - opt_idx = get_closest_index (inspect_quants); - configurations_[opt_idx]->calculate_score (*this); - opt = configurations_[opt_idx]->score (); - } - else -#endif + Slur_configuration *best = NULL; + Real mindist = 1e6; + for (vsize i = 0; i < configurations_.size (); i++) { - for (vsize i = 0; i < configurations_.size (); i++) - configurations_[i]->calculate_score (*this); - for (vsize i = 0; i < configurations_.size (); i++) + Real d = fabs (configurations_[i]->attachment_[LEFT][Y_AXIS] - ys[LEFT]) + + fabs (configurations_[i]->attachment_[RIGHT][Y_AXIS] - ys[RIGHT]); + if (d < mindist) { - if (configurations_[i]->score () < opt) - { - opt = configurations_[i]->score (); - opt_idx = i; - } + best = configurations_[i]; + mindist = d; } } -#if DEBUG_SLUR_SCORING - if (debug_slurs) - { - string total; - if (opt_idx >= 0) - { - total = configurations_[opt_idx]->card (); - total += to_string (" TOTAL=%.2f idx=%d", configurations_[opt_idx]->score (), opt_idx); - } - else - { - total = "no sol?"; - } + while (!best->done ()) + best->run_next_scorer (*this); - slur_->set_property ("quant-score", - ly_string2scm (total)); - } -#endif + if (mindist > 1e5) + programming_error ("cannot find quant"); - if (opt_idx < 0) - { - opt_idx = 0; - programming_error ("No optimal slur found. Guessing 0."); - } - - return configurations_[opt_idx]->curve_; + return best; +} + + +Slur_configuration * +Slur_score_state::get_best_curve () const +{ + std::priority_queue, + Slur_configuration_less> queue; + for (vsize i = 0; i < configurations_.size (); i++) + queue.push (configurations_[i]); + + Slur_configuration *best = NULL; + while (true) { + best = queue.top (); + if (best->done ()) + break; + + queue.pop (); + best->run_next_scorer (*this); + queue.push (best); + } + + return best; } Grob * @@ -407,28 +403,6 @@ Slur_score_state::breakable_bound_item (Direction d) const return 0; } -int -Slur_score_state::get_closest_index (SCM inspect_quants) const -{ - Drul_array ins = ly_scm2interval (inspect_quants); - - int opt_idx = -1; - Real mindist = 1e6; - for (vsize i = 0; i < configurations_.size (); i++) - { - Real d = fabs (configurations_[i]->attachment_[LEFT][Y_AXIS] - ins[LEFT]) - + fabs (configurations_[i]->attachment_[RIGHT][Y_AXIS] - ins[RIGHT]); - if (d < mindist) - { - opt_idx = i; - mindist = d; - } - } - if (mindist > 1e5) - programming_error ("cannot find quant"); - return opt_idx; -} - /* TODO: should analyse encompasses to determine sensible region, and should limit slopes available. @@ -668,7 +642,6 @@ Slur_score_state::enumerate_attachments (Drul_array end_ys) const os[RIGHT] = base_attachments_[RIGHT]; for (int j = 0; dir_ * os[RIGHT][Y_AXIS] <= dir_ * end_ys[RIGHT]; j++) { - Slur_configuration s; Direction d = LEFT; Drul_array attach_to_stem (false, false); do @@ -729,10 +702,7 @@ Slur_score_state::enumerate_attachments (Drul_array end_ys) const } while (flip (&d) != LEFT); - s.attachment_ = os; - s.index_ = scores.size (); - - scores.push_back (new Slur_configuration (s)); + scores.push_back (Slur_configuration::new_config (os, scores.size ())); os[RIGHT][Y_AXIS] += dir_ * staff_space_ / 2; } -- 2.39.2