Ensure that even non-adjacent columns get a rod if they might collide.

6 files changed, 110 insertions, 50 deletions

diff --git a/input/regression/beam-feather-knee-stem-length.ly b/input/regression/beam-feather-knee-stem-length.ly
index 838f01b7f5..09649c7d01 100644
--- a/input/regression/beam-feather-knee-stem-length.ly
+++ b/input/regression/beam-feather-knee-stem-length.ly
@@ -1,4 +1,4 @@
-\version "2.11.29"
+\version "2.11.28"
 \header {
 
   texidoc="In feathered beams, stems in knees reach up to the feathered part correctly.
diff --git a/input/regression/spacing-non-adjacent-columns1.ly b/input/regression/spacing-non-adjacent-columns1.ly
new file mode 100644
index 0000000000..e7adfc015a
--- /dev/null
+++ b/input/regression/spacing-non-adjacent-columns1.ly
@@ -0,0 +1,21 @@
+\version "2.11.28"
+\paper {ragged-right = ##t}
+\header {
+  texidoc = "The spacing engine avoids collisions between non-adjacent columns."
+}
+
+
+foo = \relative c'' {
+  g'32[ c,]
+}
+
+bar = \relative c {
+  c16 <feses ases ceses eses ases ceses eses geses beses deses>4
+}
+
+\new PianoStaff {
+  <<
+    \new Voice \foo
+    \new Voice \bar
+  >>
+}
\ No newline at end of file
diff --git a/input/regression/spacing-non-adjacent-columns2.ly b/input/regression/spacing-non-adjacent-columns2.ly
new file mode 100644
index 0000000000..9635cff1ce
--- /dev/null
+++ b/input/regression/spacing-non-adjacent-columns2.ly
@@ -0,0 +1,21 @@
+\version "2.11.28"
+\paper {ragged-right = ##t}
+\header {
+  texidoc = "The spacing engine avoids collisions between non-adjacent columns."
+}
+
+
+foo = \relative c'' {
+  g'32[ c,]
+}
+
+bar = \relative c {
+  s16 <feses ases ceses eses ases ceses eses geses beses deses>4
+}
+
+\new PianoStaff {
+  <<
+    \new Voice \foo
+    \new Voice \bar
+  >>
+}
diff --git a/lily/include/separation-item.hh b/lily/include/separation-item.hh
index c8d3b93e0f..d1280c7a9e 100644
--- a/lily/include/separation-item.hh
+++ b/lily/include/separation-item.hh
@@ -23,7 +23,7 @@ struct Separation_item
   static vector<Box> boxes (Grob *me, Grob *left);
   static Skyline conditional_skyline (Grob *, Grob *);
   static Grob *extremal_break_aligned_grob (Grob *, Direction, Interval *);
-  static bool set_distance (Drul_array<Item *>, Real);
+  static Real set_distance (Item *left, Item *right, Real padding);
   static bool is_empty (Grob *me);
   static void add_item (Grob *, Item *);
   static void add_conditional_item (Grob *, Grob *);
diff --git a/lily/separation-item.cc b/lily/separation-item.cc
index 6d721b6399..a8d63c2e1a 100644
--- a/lily/separation-item.cc
+++ b/lily/separation-item.cc
@@ -30,13 +30,12 @@ Separation_item::add_conditional_item (Grob *me, Grob *e)
   Pointer_group_interface::add_grob (me, ly_symbol2scm ("conditional-elements"), e);
 }
 
-bool
-Separation_item::set_distance (Drul_array<Item *> items,
-			       Real padding)
+Real
+Separation_item::set_distance (Item *l, Item *r, Real padding)
 {
-  Drul_array<Skyline_pair*> lines (Skyline_pair::unsmob (items[LEFT]->get_property ("horizontal-skylines")),
-				   Skyline_pair::unsmob (items[RIGHT]->get_property ("horizontal-skylines")));
-  Skyline right = conditional_skyline (items[RIGHT], items[LEFT]);
+  Drul_array<Skyline_pair*> lines (Skyline_pair::unsmob (l->get_property ("horizontal-skylines")),
+				   Skyline_pair::unsmob (r->get_property ("horizontal-skylines")));
+  Skyline right = conditional_skyline (r, l);
   right.merge ((*lines[RIGHT])[LEFT]);
   
   Real dist = padding + (*lines[LEFT])[RIGHT].distance (right);
@@ -44,13 +43,13 @@ Separation_item::set_distance (Drul_array<Item *> items,
     {
       Rod rod;
 
-      rod.item_drul_ = items;
+      rod.item_drul_ = Drul_array<Item*> (l, r);
 
       rod.distance_ = dist;
       rod.add_to_cols ();
     }
 
-  return dist > 0;
+  return max (dist, 0.0);
 }
 
 bool
diff --git a/lily/spacing-spanner.cc b/lily/spacing-spanner.cc
index 9078c54bd3..19739adf6a 100644
--- a/lily/spacing-spanner.cc
+++ b/lily/spacing-spanner.cc
@@ -209,71 +209,90 @@ Spacing_spanner::generate_pair_spacing (Grob *me,
 }
 
 static void
-set_column_rods (vector<Grob*> const &cols, vsize idx, Real padding)
+set_column_rods (vector<Grob*> const &cols, Real padding)
 {
+  /* distances[i] will be the minimum distance between column i and column i+1 */
+  vector<Real> distances;
 
-  /*
-    This is an inner loop: look for the first normal (unbroken) Left
-    grob.  This looks like an inner loop (ie. quadratic total), but in
-    most cases, the interesting L will just be the first entry of
-    NEXT, making it linear in most of the cases.
-  */
-  Item *r = dynamic_cast<Item*> (cols[idx]);
+  for (vsize i = 1; i < cols.size (); i++)
+    {
+      Item *r = dynamic_cast<Item*> (cols[i]);
+      Item *rb = r->find_prebroken_piece (LEFT);
 
-  if (Separation_item::is_empty (r))
-    return;
+      if (Separation_item::is_empty (r) && (!rb || Separation_item::is_empty (rb)))
+	continue;
 
-  bool constraint = false;
-  bool grace = false;
+      Skyline_pair *skys = Skyline_pair::unsmob (r->get_property ("horizontal-skylines"));
+      Real right_stickout = skys ? (*skys)[LEFT].max_height () : 0.0;
 
-  idx--;
-  do
-    {
-      Item *l = dynamic_cast<Item*> (cols[idx]);
-      Item *lb = l->find_prebroken_piece (RIGHT);
+      Drul_array<Item*> r_cols (r, rb);
+      Drul_array<Real> cur_dist (0.0, 0.0);
 
-      if (Separation_item::is_empty (l) && (!lb || Separation_item::is_empty (lb)))
-	continue;
+      /* This is an inner loop and hence it is potentially quadratic. However, we only continue
+	 as long as there is a rod to insert. Therefore, this loop will usually only execute
+	 a constant number of times per iteration of the outer loop. */
+      for (vsize j = i; j--;)
+	{
+	  Item *l = dynamic_cast<Item*> (cols[j]);
+	  Item *lb = l->find_prebroken_piece (RIGHT);
+	  Skyline_pair *skys = Skyline_pair::unsmob (l->get_property ("horizontal-skylines"));
+	  Real left_stickout = skys ? (*skys)[RIGHT].max_height () : 0.0;
+	  bool done = true;
+
+	  Direction d = LEFT;
+	  do
+	    {
+	      if (j < i-1)
+		cur_dist[d] += distances[j];
 
-      if (lb)
-	Separation_item::set_distance (Drul_array<Item*> (lb, r), padding);
-      constraint = Separation_item::set_distance (Drul_array<Item *> (l, r), padding);
+	      Item *r_col = r_cols[d];
+	      bool touches = right_stickout - left_stickout + cur_dist[d] < 0.0;
+	      Real dist = 0.0;
 
+	      /* we set a distance for the line-starter column even if it's non-broken counterpart
+		 doesn't touch the right column. */
+	      if (lb)
+		Separation_item::set_distance (lb, r_col, padding);
 
-      /*
-	This check is because grace notes are set very tight, and
-	the accidentals of main note may stick out so far to cover
-	a barline preceding the grace note.
-      */
-      grace = spanned_time_interval (l, r).length ().main_part_ == Rational (0);
+	      if (touches || j == i-1)
+		dist = Separation_item::set_distance (l, r_col, padding);
 
-      /*
-	this grob doesn't cause a constraint. We look further until we
-	find one that does.
-      */
+	      if (j == i-1 && d == LEFT)
+		distances.push_back (dist);
+
+	      if (j == i-1)
+		cur_dist[d] = distances[j];
+
+	      done = done && !touches;
+	    }
+	  while (flip (&d) != LEFT && rb);
+
+	  /* we need the empty check for gregorian notation, where there are a lot of
+	     extraneous paper-columns that we need to skip over */
+	  if (done && !Separation_item::is_empty (l))
+	    break;
+	}
     }
-  while (idx-- && (!constraint || grace));
 }
 
+
 void
 Spacing_spanner::generate_springs (Grob *me,
 				   vector<Grob*> const &cols,
 				   Spacing_options const *options)
 {
-  Paper_column *prev = 0;
-  for (vsize i = 0; i < cols.size (); i++)
+  Paper_column *prev = dynamic_cast<Paper_column*> (cols[0]);
+  for (vsize i = 1; i < cols.size (); i++)
     {
       Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
       Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i+1]) : 0;
       
-      if (i > 0)
-	{
-	  generate_pair_spacing (me, prev, col, next, options);
-	  set_column_rods (cols, i, 0.1); // FIXME
-	}
+      generate_pair_spacing (me, prev, col, next, options);
 
       prev = col;
     }
+
+  set_column_rods (cols, 0.1); // FIXME: padding
 }
 
 /*