]> git.donarmstrong.com Git - lilypond.git/blobdiff - lily/spacing-spanner.cc
Merge branch 'master' into lilypond/translation
[lilypond.git] / lily / spacing-spanner.cc
index 64eecf07586d1a419a2853739e4432c3a3200ab0..0395506bbcb79dbecc9e1423e08bcee9d821bdc0 100644 (file)
 /*
 /*
-  spacing-spanner.cc -- implement Spacing_spanner
+  This file is part of LilyPond, the GNU music typesetter.
 
 
-  source file of the GNU LilyPond music typesetter
+  Copyright (C) 1999--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
 
 
-  (c) 1999--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  LilyPond is free software: you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation, either version 3 of the License, or
+  (at your option) any later version.
+
+  LilyPond is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
 */
 
 */
 
+#include "spacing-spanner.hh"
+
 #include <math.h>
 #include <cstdio>
 
 #include <math.h>
 #include <cstdio>
 
+#include "spacing-options.hh"
+#include "international.hh"
 #include "main.hh"
 #include "main.hh"
-#include "system.hh"
-#include "warn.hh"
-#include "output-def.hh"
-#include "paper-score.hh"
-#include "paper-column.hh"
 #include "moment.hh"
 #include "note-spacing.hh"
 #include "moment.hh"
 #include "note-spacing.hh"
-#include "misc.hh"
-#include "warn.hh"
-#include "staff-spacing.hh"
-#include "spring.hh"
+#include "output-def.hh"
 #include "paper-column.hh"
 #include "paper-column.hh"
+#include "paper-score.hh"
+#include "pointer-group-interface.hh"
+#include "separation-item.hh"
+#include "skyline-pair.hh"
 #include "spaceable-grob.hh"
 #include "spaceable-grob.hh"
-#include "break-align-interface.hh"
 #include "spacing-interface.hh"
 #include "spacing-interface.hh"
-#include "pointer-group-interface.hh"
-#include "grob-array.hh"
-
-/*
-  TODO: this file/class is too complex. Should figure out how to chop
-  this up even more.
-*/
-
-class Spacing_spanner
-{
-public:
-  static void standard_breakable_column_spacing (Grob *me, Item *l, Item *r,
-                                                Real *fixed, Real *space, Moment);
-
-  static Real default_bar_spacing (Grob *, Grob *, Grob *, Moment);
-  static Real note_spacing (Grob *, Grob *, Grob *, Moment, bool *);
-  static Real get_duration_space (Grob *, Moment dur, Rational shortest, bool *);
-  static Rational find_shortest (Grob *, Link_array<Grob> const &);
-  static void breakable_column_spacing (Grob *, Item *l, Item *r, Moment);
-  static void find_loose_columns () {}
-  static void prune_loose_columns (Grob *, Link_array<Grob> *cols, Rational);
-  static void find_loose_columns (Link_array<Grob> cols);
-  static void set_explicit_neighbor_columns (Link_array<Grob> const &cols);
-  static void set_implicit_neighbor_columns (Link_array<Grob> const &cols);
-  static void do_measure (Rational, Grob *me, Link_array<Grob> *cols);
-  static void musical_column_spacing (Grob *, Item *, Item *, Real, Rational);
-  DECLARE_SCHEME_CALLBACK (set_springs, (SCM));
-  static bool has_interface (Grob *);
-};
-
-/*
-  Return whether COL is fixed to its neighbors by some kind of spacing
-  constraint.
-
-
-  If in doubt, then we're not loose; the spacing engine should space
-  for it, risking suboptimal spacing.
+#include "staff-spacing.hh"
+#include "system.hh"
+#include "warn.hh"
 
 
-  (Otherwise, we might risk core dumps, and other weird stuff.)
-*/
-static bool
-loose_column (Grob *l, Grob *c, Grob *r)
+vector<Grob*>
+Spacing_spanner::get_columns (Grob *me_grob)
 {
 {
-  extract_grob_set (c, "right-neighbors", rns);
-  extract_grob_set (c, "left-neighbors", lns);
+  Spanner *me = dynamic_cast<Spanner*> (me_grob);
+  vector<Grob*> all (get_root_system (me)->used_columns ());
+  vsize start = binary_search (all, (Grob*)me->get_bound (LEFT),
+                              &Paper_column::less_than);
+  vsize end = binary_search (all, (Grob*) me->get_bound (RIGHT),
+                            &Paper_column::less_than);  
   
   
-  /*
-    If this column doesn't have a proper neighbor, we should really
-    make it loose, but spacing it correctly is more than we can
-    currently can handle.
-
-    (this happens in the following situation:
-
-    |
-    |    clef G
-    *
-
-    |               |      ||
-    |               |      ||
-    O               O       ||
-
-
-    the column containing the clef is really loose, and should be
-    attached right to the first column, but that is a lot of work for
-    such a borderline case.)
-
-  */
-  if (lns.is_empty () || rns.is_empty ())
-    return false;
-
-  Item *l_neighbor = dynamic_cast<Item *> (lns[0]);
-  Item *r_neighbor = dynamic_cast<Item *> (rns[0]);
-
-  if (!l_neighbor || !r_neighbor)
-    return false;
-
-  l_neighbor = l_neighbor->get_column ();
-  r_neighbor = dynamic_cast<Item *> (Note_spacing::right_column (r_neighbor));
-
-  if (l == l_neighbor && r == r_neighbor)
-    return false;
-
-  if (!l_neighbor || !r_neighbor)
-    return false;
-
-  /*
-    Only declare loose if the bounds make a little sense.  This means
-    some cases (two isolated, consecutive clef changes) won't be
-    nicely folded, but hey, then don't do that.
-  */
-  if (! ((Paper_column::is_musical (l_neighbor) || Item::is_breakable (l_neighbor))
-        && (Paper_column::is_musical (r_neighbor) || Item::is_breakable (r_neighbor))))
-    {
-      return false;
-    }
-
-  /*
-    A rather hairy check, but we really only want to move around
-    clefs. (anything else?)
-
-    in any case, we don't want to move bar lines.
-  */
-  extract_grob_set (c, "elements", elts);
-  for (int i = elts.size (); i--; )
-    {
-      Grob *g = elts[i];
-      if (g && Break_align_interface::has_interface (g))
-       {
-         extract_grob_set (g, "elements", gelts);
-         for (int j = gelts.size (); j--; )
-           {
-             Grob *h = gelts[j];
-
-             /*
-               ugh. -- fix staff-bar name?
-             */
-             if (h && h->get_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
-               return false;
-           }
-       }
-    }
-
-  return true;
-}
-
-/*
-  Remove columns that are not tightly fitting from COLS. In the
-  removed columns, set 'between-cols to the columns where it is in
-  between.
-*/
-void
-Spacing_spanner::prune_loose_columns (Grob *me, Link_array<Grob> *cols, Rational shortest)
-{
-  Link_array<Grob> newcols;
-  Real increment = robust_scm2double (me->get_property ("spacing-increment"), 1.2);
-  for (int i = 0; i < cols->size (); i++)
-    {
-      if (Item::is_breakable (cols->elem (i)) || Paper_column::is_musical (cols->elem (i)))
-       {
-         newcols.push (cols->elem (i));
-         continue;
-       }
-
-      Grob *c = cols->elem (i);
-      if (loose_column (cols->elem (i - 1), c, cols->elem (i + 1)))
-       {
-         extract_grob_set (c, "right-neighbors", rns_arr);
-         extract_grob_set (c, "left-neighbors", lns_arr);
-         
-         SCM lns = lns_arr.size () ? lns_arr.top()->self_scm () : SCM_BOOL_F;
-         SCM rns = rns_arr.size () ? rns_arr.top()->self_scm () : SCM_BOOL_F;
-         
-         /*
-           Either object can be non existent, if the score ends
-           prematurely.
-         */
-
-         extract_grob_set (unsmob_grob (rns), "right-items", right_items);
-         c->set_object ("between-cols", scm_cons (lns,
-                                                  right_items[0]->self_scm ()));
-
-         /*
-           Set distance constraints for loose columns
-         */
-         Drul_array<Grob *> next_door;
-         next_door[LEFT] = cols->elem (i - 1);
-         next_door[RIGHT] = cols->elem (i + 1);
-         Direction d = LEFT;
-         Drul_array<Real> dists (0, 0);
-
-         do
-           {
-             dists[d] = 0.0;
-             Item *lc = dynamic_cast<Item *> ((d == LEFT) ? next_door[LEFT] : c);
-             Item *rc = dynamic_cast<Item *> (d == LEFT ? c : next_door[RIGHT]);
-
-
-             extract_grob_set (lc, "spacing-wishes", wishes);
-             for (int k = wishes.size(); k--;)
-               {
-                 Grob *sp = wishes[k];
-                 if (Note_spacing::left_column (sp) != lc
-                     || Note_spacing::right_column (sp) != rc)
-                   continue;
-
-                 Real space, fixed;
-                 fixed = 0.0;
-                 bool dummy;
-
-                 if (d == LEFT)
-                   {
-                     /*
-                       The note spacing should be taken from the musical
-                       columns.
-
-                     */
-                     Real base = note_spacing (me, lc, rc, shortest, &dummy);
-                     Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
-
-                     space -= increment;
-
-                     dists[d] = max (dists[d], space);
-                   }
-                 else
-                   {
-                     Real space, fixed_space;
-                     Staff_spacing::get_spacing_params (sp,
-                                                        &space, &fixed_space);
-
-                     dists[d] = max (dists[d], fixed_space);
-                   }
-               }
-           }
-         while (flip (&d) != LEFT);
-
-         Rod r;
-         r.distance_ = dists[LEFT] + dists[RIGHT];
-         r.item_drul_[LEFT] = dynamic_cast<Item *> (cols->elem (i - 1));
-         r.item_drul_[RIGHT] = dynamic_cast<Item *> (cols->elem (i + 1));
-
-         r.add_to_cols ();
-       }
-      else
-       {
-         newcols.push (c);
-       }
-    }
-
-  *cols = newcols;
-}
-
-/*
-  Set neighboring columns determined by the spacing-wishes grob property.
-*/
-void
-Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> const &cols)
-{
-  for (int i = 0; i < cols.size (); i++)
-    {
-      SCM right_neighbors = Grob_array::make_array ();
-      Grob_array *rn_arr = unsmob_grob_array (right_neighbors);
-      int min_rank = 100000;   // inf.
-
-      extract_grob_set (cols[i], "spacing-wishes", wishes);
-      for (int k = wishes.size(); k--;)
-       {
-         Item *wish = dynamic_cast<Item *> ( wishes[k]);
-
-         Item *lc = wish->get_column ();
-         Grob *right = Note_spacing::right_column (wish);
-
-         if (!right)
-           continue;
-
-         Item *rc = dynamic_cast<Item *> (right);
-
-         int right_rank = Paper_column::get_rank (rc);
-         int left_rank = Paper_column::get_rank (lc);
-
-         /*
-           update the left column.
-         */
-         if (right_rank <= min_rank)
-           {
-             if (right_rank < min_rank)
-               rn_arr->clear ();
-
-             min_rank = right_rank;
-             rn_arr->add (wish);
-           }
-
-         /*
-           update the right column of the wish.
-         */
-         int maxrank = 0;
-
-         extract_grob_set (rc, "left-neighbors", lns_arr);
-         if (lns_arr.size ())
-           {
-             Item *it = dynamic_cast<Item *> (lns_arr.top());
-             maxrank = Paper_column::get_rank (it->get_column ());
-           }
-
-         if (left_rank >= maxrank)
-           {
-             
-             if (left_rank > maxrank)
-               {
-                 Grob_array *ga = unsmob_grob_array (rc->get_object ("left-neighbors"));
-                 if (ga)
-                   ga->clear ();
-               }
-
-             Pointer_group_interface::add_grob (rc, ly_symbol2scm ("left-neighbors"), wish);
-           }
-       }
-
-      if (rn_arr->size ())
-       {
-         cols[i]->set_object ("right-neighbors", right_neighbors);
-       }
-    }
-}
-
-/*
-  Set neighboring columns that have no left/right-neighbor set
-  yet. Only do breakable non-musical columns, and musical columns.
-*/
-void
-Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> const &cols)
-{
-  for (int i = 0; i < cols.size (); i++)
-    {
-      Item *it = dynamic_cast<Item *> (cols[i]);
-      if (!Item::is_breakable (it) && !Paper_column::is_musical (it))
-       continue;
-
-      // it->breakable || it->musical
-
-      /*
-       sloppy with typing left/right-neighbors should take list, but paper-column found instead.
-      */
-      extract_grob_set (cols[i], "left-neighbors", lns);
-      if (lns.is_empty () && i )
-       {
-         SCM ga_scm = Grob_array::make_array();
-         Grob_array *ga = unsmob_grob_array (ga_scm);
-         ga->add (cols[i-1]);
-         cols[i]->set_object ("left-neighbors", ga_scm);
-       }
-      extract_grob_set (cols[i], "right-neighbors", rns);
-      if (rns.is_empty () && i < cols.size () - 1)
-       {
-         SCM ga_scm = Grob_array::make_array();
-         Grob_array *ga = unsmob_grob_array (ga_scm);
-         ga->add (cols[i+1]);
-         cols[i]->set_object ("right-neighbors", ga_scm);
-       }
-    }
+  all = vector<Grob*> (all.begin () + start,
+                      all.begin () + end + 1);
+  return all;
 }
 
 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
 SCM
 Spacing_spanner::set_springs (SCM smob)
 {
 }
 
 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
 SCM
 Spacing_spanner::set_springs (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
+  Spanner *me = unsmob_spanner (smob);
 
   /*
 
   /*
-    can't use get_system() ? --hwn.
+    can't use get_system () ? --hwn.
   */
   */
-  Link_array<Grob> all (me->pscore_->root_system ()->columns ());
-
-  set_explicit_neighbor_columns (all);
-
-  SCM preset_shortest = me->get_property ("common-shortest-duration");
-  Rational global_shortest;
-  if (unsmob_moment (preset_shortest))
-    {
-      global_shortest = unsmob_moment (preset_shortest)->main_part_;
-    }
-  else
-    {
-      global_shortest = find_shortest (me, all);
-      if (be_verbose_global)
-       message (_f ("Global shortest duration is %s", global_shortest.to_string ()) + "\n");
-    }
-  prune_loose_columns (me, &all, global_shortest);
-  set_implicit_neighbor_columns (all);
+  Spacing_options options;
+  options.init_from_grob (me);
+  vector<Grob*> cols = Spacing_spanner::get_columns (me);
+  set_explicit_neighbor_columns (cols);
 
 
-  int j = 0;
-  for (int i = 1; i < all.size (); i++)
-    {
-      Grob *sc = all[i];
-      if (Item::is_breakable (sc))
-       {
-         Link_array<Grob> measure (all.slice (j, i + 1));
-         do_measure (global_shortest, me, &measure);
-         j = i;
-       }
-    }
+  prune_loose_columns (me, &cols, &options);
+  set_implicit_neighbor_columns (cols);
+  generate_springs (me, cols, &options);
 
   return SCM_UNSPECIFIED;
 }
 
   return SCM_UNSPECIFIED;
 }
@@ -418,19 +84,25 @@ Spacing_spanner::set_springs (SCM smob)
   note has a different duration, but hey, don't write that kind of
   stuff, then.
 */
   note has a different duration, but hey, don't write that kind of
   stuff, then.
 */
-Rational
-Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
+
+MAKE_SCHEME_CALLBACK (Spacing_spanner, calc_common_shortest_duration, 1);
+SCM 
+Spacing_spanner::calc_common_shortest_duration (SCM grob)
 {
 {
+  Spanner *me = unsmob_spanner (grob);
+
+  vector<Grob*> cols (get_columns (me));
+  
   /*
     ascending in duration
   */
   /*
     ascending in duration
   */
-  Array<Rational> durations;
-  Array<int> counts;
+  vector<Rational> durations;
+  vector<int> counts;
 
   Rational shortest_in_measure;
   shortest_in_measure.set_infinite (1);
 
 
   Rational shortest_in_measure;
   shortest_in_measure.set_infinite (1);
 
-  for (int i = 0; i < cols.size (); i++)
+  for (vsize i = 0; i < cols.size (); i++)
     {
       if (Paper_column::is_musical (cols[i]))
        {
     {
       if (Paper_column::is_musical (cols[i]))
        {
@@ -448,15 +120,15 @@ Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
          shortest_in_measure = min (shortest_in_measure, this_shortest.main_part_);
        }
       else if (!shortest_in_measure.is_infinity ()
          shortest_in_measure = min (shortest_in_measure, this_shortest.main_part_);
        }
       else if (!shortest_in_measure.is_infinity ()
-              && Item::is_breakable (cols[i]))
+              && Paper_column::is_breakable (cols[i]))
        {
        {
-         int j = 0;
+         vsize j = 0;
          for (; j < durations.size (); j++)
            {
              if (durations[j] > shortest_in_measure)
                {
          for (; j < durations.size (); j++)
            {
              if (durations[j] > shortest_in_measure)
                {
-                 counts.insert (1, j);
-                 durations.insert (shortest_in_measure, j);
+                 counts.insert (counts.begin () + j, 1);
+                 durations.insert (durations.begin () + j, shortest_in_measure);
                  break;
                }
              else if (durations[j] == shortest_in_measure)
                  break;
                }
              else if (durations[j] == shortest_in_measure)
@@ -468,25 +140,23 @@ Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
 
          if (durations.size () == j)
            {
 
          if (durations.size () == j)
            {
-             durations.push (shortest_in_measure);
-             counts.push (1);
+             durations.push_back (shortest_in_measure);
+             counts.push_back (1);
            }
 
          shortest_in_measure.set_infinite (1);
        }
     }
 
            }
 
          shortest_in_measure.set_infinite (1);
        }
     }
 
-  int max_idx = -1;
+  vsize max_idx = VPOS;
   int max_count = 0;
   int max_count = 0;
-  for (int i = durations.size (); i--;)
+  for (vsize i = durations.size (); i--;)
     {
       if (counts[i] >= max_count)
        {
          max_idx = i;
          max_count = counts[i];
        }
     {
       if (counts[i] >= max_count)
        {
          max_idx = i;
          max_count = counts[i];
        }
-
-      //      printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
     }
 
   SCM bsd = me->get_property ("base-shortest-duration");
     }
 
   SCM bsd = me->get_property ("base-shortest-duration");
@@ -494,238 +164,337 @@ Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
   if (Moment *m = unsmob_moment (bsd))
     d = m->main_part_;
 
   if (Moment *m = unsmob_moment (bsd))
     d = m->main_part_;
 
-  if (max_idx >= 0)
+  if (max_idx != VPOS)
     d = min (d, durations[max_idx]);
 
     d = min (d, durations[max_idx]);
 
-  return d;
+  return Moment (d).smobbed_copy ();
 }
 
 }
 
-/*
-  Generate spacing for a single measure. We used to have code that did
-  per-measure spacing. Now we have piecewise spacing. We should fix
-  this to support "spacing-regions": some regions have different notes
-  (different time sigs) than others, and should be spaced differently.
-*/
 void
 void
-Spacing_spanner::do_measure (Rational global_shortest, Grob *me,
-                            Link_array<Grob> *cols)
+Spacing_spanner::generate_pair_spacing (Grob *me,
+                                       Paper_column *left_col, Paper_column *right_col,
+                                       Paper_column *after_right_col,
+                                       Spacing_options const *options)
+{
+  if (Paper_column::is_musical (left_col))
+    {
+      if (!Paper_column::is_musical (right_col)
+         && (options->float_nonmusical_columns_ || to_boolean (right_col->get_property ("maybe-loose")))
+         && after_right_col
+         && Paper_column::is_musical (after_right_col))
+       {
+         /*
+           TODO: should generate rods to prevent collisions.
+         */
+         musical_column_spacing (me, left_col, after_right_col, options);
+         right_col->set_object ("between-cols", scm_cons (left_col->self_scm (),
+                                                          after_right_col->self_scm ()));
+       }
+      else
+       musical_column_spacing (me, left_col, right_col, options);
+
+      if (Item *rb = right_col->find_prebroken_piece (LEFT))
+       musical_column_spacing (me, left_col, rb, options);
+    }
+  else
+    {
+      /*
+       The case that the right part is broken as well is rather
+       rare, but it is possible, eg. with a single empty measure,
+       or if one staff finishes a tad earlier than the rest.
+      */
+      Item *lb = left_col->find_prebroken_piece (RIGHT);
+      Item *rb = right_col->find_prebroken_piece (LEFT);
+
+      if (left_col && right_col)
+       breakable_column_spacing (me, left_col, right_col, options);
+
+      if (lb && right_col)
+       breakable_column_spacing (me, lb, right_col, options);
+
+      if (left_col && rb)
+       breakable_column_spacing (me, left_col, rb, options);
+
+      if (lb && rb)
+       breakable_column_spacing (me, lb, rb, options);
+    }
+}
+
+static void
+set_column_rods (vector<Grob*> const &cols, Real padding)
 {
 {
-  Real headwid = robust_scm2double (me->get_property ("spacing-increment"), 1);
-  for (int i = 0; i < cols->size () - 1; i++)
+  /* distances[i] will be the minimum distance between column i and column i+1 */
+  vector<Real> distances;
+
+  for (vsize i = 1; i < cols.size (); i++)
     {
     {
-      Item *l = dynamic_cast<Item *> (cols->elem (i));
-      Item *r = dynamic_cast<Item *> (cols->elem (i + 1));
+      assert (distances.size () == i-1);
 
 
-      Paper_column *lc = dynamic_cast<Paper_column *> (l);
-      Paper_column *rc = dynamic_cast<Paper_column *> (r);
+      Item *r = dynamic_cast<Item*> (cols[i]);
+      Item *rb = r->find_prebroken_piece (LEFT);
 
 
-      if (Paper_column::is_musical (l))
+      if (Separation_item::is_empty (r) && (!rb || Separation_item::is_empty (rb)))
        {
        {
-         musical_column_spacing (me, lc, rc, headwid, global_shortest);
-         if (Item *rb = r->find_prebroken_piece (LEFT))
-           musical_column_spacing (me, lc, rb, headwid, global_shortest);
+         distances.push_back (0);
+         continue;
        }
        }
-      else
+
+      Skyline_pair *skys = Skyline_pair::unsmob (r->get_property ("horizontal-skylines"));
+      Real right_stickout = skys ? (*skys)[LEFT].max_height () : 0.0;
+
+      /* min rather than max because right-stickout will be negative if the right-hand column
+        sticks out a lot to the left */
+      right_stickout = min (right_stickout,
+                           Separation_item::conditional_skyline (r, cols[i-1]).max_height ());
+
+      Drul_array<Item*> r_cols (r, rb);
+      Drul_array<Real> cur_dist (0.0, 0.0);
+
+      /* 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--;)
        {
        {
-         /*
-           The case that the right part is broken as well is rather
-           rare, but it is possible, eg. with a single empty measure,
-           or if one staff finishes a tad earlier than the rest.
-         */
+         Item *l = dynamic_cast<Item*> (cols[j]);
          Item *lb = l->find_prebroken_piece (RIGHT);
          Item *lb = l->find_prebroken_piece (RIGHT);
-         Item *rb = r->find_prebroken_piece (LEFT);
+         Skyline_pair *skys = Skyline_pair::unsmob (l->get_property ("horizontal-skylines"));
+         Real left_stickout = skys ? (*skys)[RIGHT].max_height () : 0.0;
+         bool done = true;
 
 
-         if (i == 0 && Paper_column::get_rank (l) == 0)
-           l = 0;
+         Direction d = LEFT;
+         do
+           {
+             if (j < i-1)
+               cur_dist[d] += distances[j];
 
 
-         if (l && r)
-           breakable_column_spacing (me, l, r, global_shortest);
-         
-         if (lb && r)
-           breakable_column_spacing (me, lb, r, global_shortest);
+             Item *r_col = r_cols[d];
+             bool touches = right_stickout - left_stickout + cur_dist[d] < 0.0;
+             Real dist = 0.0;
 
 
-         if (l && rb)
-           breakable_column_spacing (me, l, rb, global_shortest);
+             /* we set a distance for the line-starter column even if its non-broken counterpart
+                doesn't touch the right column. */
+             if (lb)
+               Separation_item::set_distance (lb, r_col, padding);
 
 
-         if (lb && rb)
-           breakable_column_spacing (me, lb, rb, global_shortest);
+             if (touches || j == i-1)
+               dist = Separation_item::set_distance (l, r_col, padding);
+
+             if (j == i-1 && d == LEFT)
+               distances.push_back (dist);
+
+             if (j == i-1)
+               cur_dist[d] = distances[j];
+
+             cur_dist[d] = max (cur_dist[d], dist);
+             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;
        }
     }
 }
 
        }
     }
 }
 
+
+void
+Spacing_spanner::generate_springs (Grob *me,
+                                  vector<Grob*> const &cols,
+                                  Spacing_options const *options)
+{
+  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;
+      
+      generate_pair_spacing (me, prev, col, next, options);
+
+      prev = col;
+    }
+
+  Real padding = robust_scm2double (prev->get_property ("padding"), 0.1);
+  set_column_rods (cols, padding);
+}
+
 /*
 /*
-  Generate the space between two musical columns LC and RC, given
-  spacing parameters INCR and SHORTEST.
+  Generate the space between two musical columns LEFT_COL and RIGHT_COL.
 */
 void
 */
 void
-Spacing_spanner::musical_column_spacing (Grob *me, Item *lc, Item *rc, Real increment, Rational global_shortest)
+Spacing_spanner::musical_column_spacing (Grob *me,
+                                        Item *left_col,
+                                        Item *right_col,
+                                        Spacing_options const *options)
 {
 {
-  bool expand_only = false;
-  Real base_note_space = note_spacing (me, lc, rc, global_shortest, &expand_only);
+  Real base_note_space = note_spacing (me, left_col, right_col, options);
+  Spring spring;
 
 
-  Real compound_note_space = 0.0;
-  Real compound_fixed_note_space = 0.0;
-  int wish_count = 0;
+  if (options->stretch_uniformly_)
+    spring = Spring (base_note_space, 0.0);
+  else
+    {
+      vector<Spring> springs;
+      extract_grob_set (left_col, "spacing-wishes", wishes);
 
 
-  extract_grob_set (lc, "right-neighbors", neighbors);
+      for (vsize i = 0; i < wishes.size (); i++)
+       {
+         Grob *wish = wishes[i];
+         if (Spacing_interface::left_column (wish) != left_col)
+           {
+             /* This shouldn't really happen, but the ancient music
+                stuff really messes up the spacing code, grrr
+             */
+             continue;
+           }
 
 
-  /*
-    We adjust the space following a note only if the next note
-    happens after the current note (this is set in the grob
-    property SPACING-SEQUENCE.
-  */
-  for (int i = 0; i < neighbors.size (); i++)
-    {
-      Grob *wish = neighbors[i];
+         extract_grob_set (wish, "right-items", right_items);
+         bool found_matching_column = false;
+         for (vsize j = 0; j < right_items.size (); j++)
+           {
+             Item *it = dynamic_cast<Item*> (right_items[j]);
+             if (it && (right_col == it->get_column ()
+                        || right_col->original () == it->get_column ()))
+               found_matching_column = true;
+           }
 
 
-      Item *wish_rcol = Note_spacing::right_column (wish);
-      if (Note_spacing::left_column (wish) != lc
-         || (wish_rcol != rc && wish_rcol != rc->original_))
-       continue;
+         /*
+           This is probably a waste of time in the case of polyphonic
+           music.  */
+         if (found_matching_column && Note_spacing::has_interface (wish))
+           {
+             Real inc = options->increment_;
+             Grob *gsp = unsmob_grob (left_col->get_object ("grace-spacing"));
+             if (gsp && Paper_column::when_mom (left_col).grace_part_)
+               {
+                 Spacing_options grace_opts;
+                 grace_opts.init_from_grob (gsp);
+                 inc = grace_opts.increment_;
+               }
+             springs.push_back (Note_spacing::get_spacing (wish, right_col, base_note_space, inc));
+           }
+       }
 
 
-      /*
-       This is probably a waste of time in the case of polyphonic
-       music.  */
-      if (Note_spacing::has_interface (wish))
+      if (springs.empty ())
        {
        {
-         Real space = 0.0;
-         Real fixed = 0.0;
-
-         Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
 
 
-         compound_note_space = compound_note_space + space;
-         compound_fixed_note_space = compound_fixed_note_space + fixed;
-         wish_count++;
+         if (!Paper_column::is_musical (right_col))
+           {
+             /*
+               There used to be code that examined left_col->extent
+               (X_AXIS), but this is resulted in unexpected wide
+               spacing, because the width of s^"text" output is also
+               taken into account here.
+              */
+             spring = Spring (max (base_note_space, options->increment_),
+                              options->increment_);
+           }
+         else
+           {
+             /*
+               Min distance should be 0.0. If there are no spacing
+               wishes, we're probably dealing with polyphonic spacing
+               of hemiolas.      
+             */
+             spring = Spring (base_note_space, 0.0);
+           }
        }
        }
+      else
+       spring = merge_springs (springs);
     }
 
     }
 
-  if (Paper_column::when_mom (rc).grace_part_
-      && !Paper_column::when_mom (lc).grace_part_)
+  if (Paper_column::when_mom (right_col).grace_part_
+      && !Paper_column::when_mom (left_col).grace_part_)
     {
       /*
        Ugh. 0.8 is arbitrary.
       */
     {
       /*
        Ugh. 0.8 is arbitrary.
       */
-      compound_note_space *= 0.8;
-    }
-
-  if (compound_note_space < 0 || wish_count == 0)
-    {
-      compound_note_space = base_note_space;
-      compound_fixed_note_space = increment;
-    }
-  else
-    {
-      compound_note_space /= wish_count;
-      compound_fixed_note_space /= wish_count;
+      spring *= 0.8;
     }
 
     }
 
-  /*
-    Whatever we do, the fixed space is smaller than the real
-    space.
-
-    TODO: this criterion is discontinuous in the derivative.
-    Maybe it should be continuous?
-  */
-  compound_fixed_note_space = min (compound_fixed_note_space, compound_note_space);
-
-  bool packed = to_boolean (me->get_layout ()->c_variable ("packed"));
-  Real inverse_strength = 1.0;
-  Real distance = 1.0;
-
   /*
     TODO: make sure that the space doesn't exceed the right margin.
   */
   /*
     TODO: make sure that the space doesn't exceed the right margin.
   */
-  if (packed)
+  if (options->packed_)
     {
       /*
        In packed mode, pack notes as tight as possible.  This makes
     {
       /*
        In packed mode, pack notes as tight as possible.  This makes
-       sense mostly in combination with raggedright mode: the notes
+       sense mostly in combination with ragged-right mode: the notes
        are then printed at minimum distance.  This is mostly useful
        for ancient notation, but may also be useful for some flavours
        are then printed at minimum distance.  This is mostly useful
        for ancient notation, but may also be useful for some flavours
-       of contemporary music.  If not in raggedright mode, lily will
-       pack as much bars of music as possible into a line, but the
+       of contemporary music.  If not in ragged-right mode, lily will
+       pack as many bars of music as possible into a line, but the
        line will then be stretched to fill the whole linewidth.
        line will then be stretched to fill the whole linewidth.
+
+       Note that we don't actually pack things as tightly as possible:
+       we don't allow the next column to begin before this one ends.
       */
       */
-      inverse_strength = 1.0;
-      distance = compound_fixed_note_space;
-    }
-  else
-    {
-      inverse_strength = (compound_note_space - compound_fixed_note_space);
-      distance = compound_note_space;
+      /* FIXME: the else clause below is the "right" thing to do,
+        but we can't do it because of all the empty columns that the
+        ligature-engravers leave lying around. In that case, the extent of
+        the column is incorrect because it includes note-heads that aren't
+        there. We get around this by only including the column extent if
+        the left-hand column is "genuine". This is a dirty hack and it
+        should be fixed in the ligature-engravers. --jneem
+      */
+      if (Paper_column::is_extraneous_column_from_ligature (left_col))
+       spring.set_distance (spring.min_distance ());
+      else
+       spring.set_distance (max (left_col->extent (left_col, X_AXIS)[RIGHT],
+                                 spring.min_distance ()));
+
+      spring.set_inverse_stretch_strength (1.0);
     }
 
     }
 
-  Spaceable_grob::add_spring (lc, rc, distance, inverse_strength);
+  Spaceable_grob::add_spring (left_col, right_col, spring);
 }
 
 /*
 }
 
 /*
-  The one-size-fits all spacing. It doesn't take into account
-  different spacing wishes from one to the next column.
-*/
-void
-Spacing_spanner::standard_breakable_column_spacing (Grob *me, Item *l, Item *r,
-                                                   Real *fixed, Real *space,
-                                                   Moment shortest)
+  Check if COL fills the whole measure.
+ */
+bool
+Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 {
 {
-  *fixed = 0.0;
-  Direction d = LEFT;
-  Drul_array<Item *> cols (l, r);
-
-  do
-    {
-      if (!Paper_column::is_musical (cols[d]))
-       {
-         /*
-           Tied accidentals over barlines cause problems, so lets see
-           what happens if we do this for non musical columns only.
-         */
-         Interval lext = cols[d]->extent (cols [d], X_AXIS);
-         if (!lext.is_empty ())
-           *fixed += -d * lext[-d];
-       }
-    }
-  while (flip (&d) != LEFT);
-
-  if (l->is_breakable (l) && r->is_breakable (r))
-    {
-      Moment *dt = unsmob_moment (l->get_property ("measure-length"));
-      Moment mlen (1);
-      if (dt)
-       mlen = *dt;
-
-      Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
-
-      *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
-    }
-  else
-    {
-      Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
+  System *sys = get_root_system (me);
+  Item *next = sys->column (col->get_column ()->get_rank () + 1);
+  if (!next)
+    return false;
 
 
-      if (dt == Moment (0, 0))
-       {
-         /*
-           In this case, Staff_spacing should handle the job,
-           using dt when it is 0 is silly.
-         */
-         *space = *fixed + 0.5;
-       }
-      else
-       {
-         bool dummy;
-         *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
-       }
-    }
+  if (Paper_column::is_musical (next)
+      || Paper_column::is_musical (left)
+      || !Paper_column::is_musical (col)
+      || !Paper_column::is_used (next))
+    return false;
+  
+  Moment dt =
+    Paper_column::when_mom (next) - Paper_column::when_mom (col);
+  
+  Moment *len = unsmob_moment (left->get_property ("measure-length"));
+  if (!len)
+    return false;
+  
+  /*
+    Don't check for exact measure length, since ending measures are
+    often shortened due to pickups.
+   */
+  if (dt.main_part_ > len->main_part_ / Rational (2)
+      && (next->is_broken ()
+         || next->break_status_dir ()))
+    return true;
+
+  return false;
 }
 
 /*
   Read hints from L and generate springs.
 */
 void
 }
 
 /*
   Read hints from L and generate springs.
 */
 void
-Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r, Moment shortest)
+Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
+                                          Spacing_options const *options)
 {
 {
-  Real compound_fixed = 0.0;
-  Real compound_space = 0.0;
-  int wish_count = 0;
+  vector<Spring> springs;
+  Spring spring;
 
   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 
 
   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 
@@ -733,207 +502,79 @@ Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r, Moment sh
     {
       extract_grob_set (l, "spacing-wishes", wishes);
 
     {
       extract_grob_set (l, "spacing-wishes", wishes);
 
-      for (int i = 0; i < wishes.size (); i++)
+      for (vsize i = 0; i < wishes.size (); i++)
        {
          Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 
          if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
            continue;
 
        {
          Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 
          if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
            continue;
 
-         Real space;
-         Real fixed_space;
-
          /*
            column for the left one settings should be ok due automatic
            pointer munging.
          /*
            column for the left one settings should be ok due automatic
            pointer munging.
-
          */
          assert (spacing_grob->get_column () == l);
 
          */
          assert (spacing_grob->get_column () == l);
 
-         Staff_spacing::get_spacing_params (spacing_grob,
-                                            &space, &fixed_space);
-
-         if (Paper_column::when_mom (r).grace_part_)
-           {
-             /*
-               Correct for grace notes.
-
-               Ugh. The 0.8 is arbitrary.
-             */
-             space *= 0.8;
-           }
-
-         compound_space += space;
-         compound_fixed += fixed_space;
-         wish_count++;
+         springs.push_back (Staff_spacing::get_spacing (spacing_grob, r));
        }
     }
 
        }
     }
 
-  if (compound_space <= 0.0 || !wish_count)
-    {
-      standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space,
-                                        shortest);
-      wish_count = 1;
-    }
-  else
-    {
-      compound_space /= wish_count;
-      compound_fixed /= wish_count;
-    }
-
-  assert (!isinf (compound_space));
-  compound_space = max (compound_space, compound_fixed);
-
-  /*
-    There used to be code that changed spacing depending on
-    raggedright setting.  Ugh.
-
-    Do it more cleanly, or rename the property.
-
-  */
-  Real inverse_strength = (compound_space - compound_fixed);
-  Real distance = compound_space;
-  Spaceable_grob::add_spring (l, r, distance, inverse_strength);
-}
-
-/**
-   Get the measure wide ant for arithmetic spacing.
-*/
-Real
-Spacing_spanner::get_duration_space (Grob *me, Moment d, Rational shortest, bool *expand_only)
-{
-  Real k = robust_scm2double (me->get_property ("shortest-duration-space"), 1);
-  Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
-
-  if (d < shortest)
-    {
-      /*
-       We don't space really short notes using the log of the
-       duration, since it would disproportionally stretches the long
-       notes in a piece. In stead, we use geometric spacing with constant 0.5
-       (i.e. linear.)
-
-       This should probably be tunable, to use other base numbers.
-
-       In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
-       3.6 mm (total).  head-width = 2.4, so we 1.2mm for 16th, 1.5
-       mm for 8th. (white space), suggesting that we use
-
-       (1.2 / 1.5)^{-log2(duration ratio)}
-
-
-      */
-      Rational ratio = d.main_part_ / shortest;
-
-      return ((k - 1) + double (ratio)) * incr;
-    }
+  if (springs.empty ())
+    spring = standard_breakable_column_spacing (me, l, r, options);
   else
   else
-    {
-      /*
-       John S. Gourlay. ``Spacing a Line of Music, '' Technical
-       Report OSU-CISRC-10/87-TR35, Department of Computer and
-       Information Science, The Ohio State University, 1987.
-      */
-      Real log = log_2 (shortest);
-      k -= log;
-      Rational compdur = d.main_part_ + d.grace_part_ / Rational (3);
-      *expand_only = false;
-
-      return (log_2 (compdur) + k) * incr;
-    }
-}
-
-Real
-Spacing_spanner::note_spacing (Grob *me, Grob *lc, Grob *rc,
-                              Moment shortest, bool *expand_only)
-{
-  Moment shortest_playing_len = 0;
-  SCM s = lc->get_property ("shortest-playing-duration");
-
-  if (unsmob_moment (s))
-    shortest_playing_len = *unsmob_moment (s);
-
-  if (! shortest_playing_len.to_bool ())
-    {
-      programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).to_string ());
-      shortest_playing_len = 1;
-    }
-
-  Moment lwhen = Paper_column::when_mom (lc);
-  Moment rwhen = Paper_column::when_mom (rc);
+    spring = merge_springs (springs);
 
 
-  Moment delta_t = rwhen - lwhen;
-  if (!Paper_column::is_musical (rc))
+  if (Paper_column::when_mom (r).grace_part_)
     {
       /*
     {
       /*
-       when toying with mmrests, it is possible to have musical
-       column on the left and non-musical on the right, spanning
-       several measures.
+       Correct for grace notes.
+       
+       Ugh. The 0.8 is arbitrary.
       */
       */
-
-      Moment *dt = unsmob_moment (rc->get_property ("measure-length"));
-      if (dt)
-       {
-         delta_t = min (delta_t, *dt);
-
-         /*
-           The following is an extra safety measure, such that
-           the length of a mmrest event doesn't cause havoc.
-         */
-         shortest_playing_len = min (shortest_playing_len, *dt);
-       }
+      spring *= 0.8;
     }
     }
-  Real dist = 0.0;
-
-  /*
-    In normal situations, the next column is at most
-    SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
-    with durations, invalidating this assumption. Here we kludge
-    around to get chord tremolos to behave properly.
 
 
-  */
-  shortest_playing_len = max (shortest_playing_len, delta_t);
-  if (delta_t.main_part_ && !lwhen.grace_part_)
+  if (Paper_column::is_musical (r)
+      && l->break_status_dir () == CENTER
+      && fills_measure (me, l, r))
     {
     {
-      dist = get_duration_space (me, shortest_playing_len,
-                                shortest.main_part_, expand_only);
-      dist *= double (delta_t.main_part_ / shortest_playing_len.main_part_);
+      Real full_measure_extra_space = robust_scm2double (l->get_property ("full-measure-extra-space"), 1.0);
+      spring.set_distance (spring.distance () + full_measure_extra_space);
+      spring.set_default_compress_strength ();
     }
     }
-  else if (delta_t.grace_part_)
+  
+  if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
     {
     {
-      /*
-       TODO: figure out how to space grace notes.
-      */
-      dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
-
-      Real grace_fact
-       = robust_scm2double (me->get_property ("grace-space-factor"), 1);
-
-      dist *= grace_fact;
+      spring.set_min_distance (0.0);
+      spring.set_default_strength ();
     }
 
     }
 
-  return dist;
+  Spaceable_grob::add_spring (l, r, spring);
 }
 
 }
 
-ADD_INTERFACE (Spacing_spanner, "spacing-spanner-interface",
-              "The space taken by a note is dependent on its duration. Doubling a\n"
-              "duration adds spacing-increment to the space. The most common shortest\n"
-              "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
-              "spaced proportonial to their duration.\n"
+ADD_INTERFACE (Spacing_spanner,
+              "The space taken by a note is dependent on its duration."
+              "  Doubling a duration adds @code{spacing-increment} to the"
+              " space.  The most common shortest note gets"
+              " @code{shortest-duration-space}.  Notes that are even shorter"
+              " are spaced proportonial to their duration.\n"
               "\n"
               "\n"
-              "Typically, the increment is the width of a black note head.  In a\n"
-              "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
-              "gets 2 note heads width (i.e. the space following a note is 1 note\n"
-              "head width) A 16th note is followed by 0.5 note head width. The\n"
-              "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
-              
-              "grace-space-factor spacing-increment base-shortest-duration "
-              "shortest-duration-space common-shortest-duration"
-
+              "Typically, the increment is the width of a black note head."
+              "  In a piece with lots of 8th notes, and some 16th notes, the"
+              " eighth note gets a 2@tie{}note heads width (i.e., the space"
+              " following a note is a 1@tie{}note head width).  A 16th note"
+              " is followed by 0.5 note head width.  The quarter note is"
+              " followed by 3@tie{}NHW, the half by 4@tie{}NHW, etc.",
+
+              /* properties */
+              "average-spacing-wishes "
+              "base-shortest-duration "
+              "common-shortest-duration "
+              "packed-spacing "
+              "shortest-duration-space "
+              "spacing-increment "
+              "strict-grace-spacing "
+              "strict-note-spacing "
+              "uniform-stretching "
               );
 
               );
 
-ADD_INTERFACE (Spacing_interface, "spacing-interface",
-              "Something to do with line breaking and spacing. "
-              "Kill this one after determining line breaks.",
-              "");
-