From 17a931f59656dce7d0979520ea5e6ff60bbab698 Mon Sep 17 00:00:00 2001
From: Han-Wen Nienhuys <hanwen@lilypond.org>
Date: Thu, 3 Feb 2011 23:20:59 -0200
Subject: [PATCH] Introduce Beam_scoring_problem::quant_range, for quickly
 filtering out invalid positions.

This reduces the number of scoring passes from 40k to 20k in
morgenlied.ly with #'region-size = 4.
---
 lily/beam-quanting.cc                | 57 ++++++++++++++++++++++------
 lily/include/beam-scoring-problem.hh |  6 +++
 2 files changed, 52 insertions(+), 11 deletions(-)

diff --git a/lily/beam-quanting.cc b/lily/beam-quanting.cc
index 977e5755e0..4b822cbac4 100644
--- a/lily/beam-quanting.cc
+++ b/lily/beam-quanting.cc
@@ -152,12 +152,13 @@ void Beam_scoring_problem::init_stems ()
   for (int a = 2; a--;)
     common[a] = common_refpoint_of_array (stems, beam, Axis (a));
 
-  Grob *fvs = Beam::first_normal_stem (beam);
-  Grob *lvs = Beam::last_normal_stem (beam);
-    
-  x_span = Interval (fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0,
-                     lvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0);
-
+  Drul_array<Grob *> edge_stems(Beam::first_normal_stem (beam),
+                                Beam::last_normal_stem (beam));
+  Direction d = LEFT;
+  do
+    x_span[d] = edge_stems[d] ? edge_stems[d]->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
+  while (flip (&d) != LEFT);
+  
   Drul_array<bool> dirs_found (0, 0);
   for (vsize i = 0; i < stems.size (); i++)
     {
@@ -171,7 +172,7 @@ void Beam_scoring_problem::init_stems ()
       dirs_found[si.dir_] = true;
 
       bool f = to_boolean (s->get_property ("french-beaming"))
-        && s != lvs && s != fvs;
+        && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
 
       Real y = Beam::calc_stem_y (beam, s, common, x_span[LEFT], x_span[RIGHT], CENTER, 
                                   Interval (0, 0), f);
@@ -193,8 +194,24 @@ void Beam_scoring_problem::init_stems ()
   edge_beam_counts =  Drul_array<int>
     (Stem::beam_multiplicity (stems[0]).length () + 1,
      Stem::beam_multiplicity (stems.back ()).length () + 1);
-    
+
+  // TODO - why are we dividing by staff_space?
   beam_translation = Beam::get_beam_translation (beam) / staff_space;
+
+  d = LEFT;
+  do
+    {
+      Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
+        - beam->relative_coordinate (common[Y_AXIS], Y_AXIS);
+      Interval heads = Stem::head_positions(edge_stems[d]) * 0.5 * staff_space;
+
+      Direction ed = edge_dirs[d];
+      heads.widen(0.5 * staff_space
+                  + (edge_beam_counts[d] - 1) * beam_translation + beam_thickness * .5);
+      quant_range[d][ed] = ed * infinity_f;
+      quant_range[d][-ed] = heads[ed] + stem_offset;
+    }
+  while (flip (&d) != LEFT);
 }
 
 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys)
@@ -247,9 +264,27 @@ Beam_scoring_problem::generate_quants (vector<Beam_configuration*> *scores) cons
 
   for (vsize i = 0; i < unshifted_quants.size (); i++)
     for (vsize j = 0; j < unshifted_quants.size (); j++)
-      scores->push_back (Beam_configuration::new_config (unquanted_y,
-                                                         Interval (unshifted_quants[i],
-                                                                   unshifted_quants[j])));
+      {
+        Beam_configuration *c =
+          Beam_configuration::new_config (unquanted_y,
+                                          Interval (unshifted_quants[i],
+                                                    unshifted_quants[j]));
+        
+        Direction d = LEFT;
+        do
+          {
+            if (!quant_range[d].contains (c->y[d]))
+              {
+                delete c;
+                c = NULL;
+                break;
+              }
+          }
+        while (flip (&d) != LEFT);
+        if (c)   
+          scores->push_back (c);
+      }
+    
 }
 
 
diff --git a/lily/include/beam-scoring-problem.hh b/lily/include/beam-scoring-problem.hh
index 755fb388f2..ba244589be 100644
--- a/lily/include/beam-scoring-problem.hh
+++ b/lily/include/beam-scoring-problem.hh
@@ -137,6 +137,12 @@ private:
   Real staff_radius;
   Drul_array<int> edge_beam_counts;
   Drul_array<Direction> edge_dirs;
+
+  // Half-open intervals, representing allowed positions for the beam,
+  // starting from close to the notehead to the direction of the stem
+  // end.  This is used for quickly weeding out invalid
+  // Beam_configurations.
+  Drul_array<Interval> quant_range;
   Real beam_translation;
 
   void init_stems ();
-- 
2.39.2