Index: lily/simple-spacer.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/simple-spacer.cc,v
retrieving revision 1.96
diff -u -r1.96 simple-spacer.cc
--- lily/simple-spacer.cc	11 Feb 2006 11:35:17 -0000	1.96
+++ lily/simple-spacer.cc	20 Apr 2006 02:10:38 -0000
@@ -59,14 +59,29 @@
 
 Simple_spacer::Simple_spacer ()
 {
-  /*
-    Give an extra penalty for compression. Needed to avoid compressing
-    tightly spaced lines.
-  */
-  active_count_ = 0;
   force_ = 0.;
-  indent_ = 0.0;
-  default_space_ = 20 PT;
+  fits_ = true;
+}
+
+Real
+Simple_spacer::force ()
+{
+  return force_;
+}
+
+bool
+Simple_spacer::fits ()
+{
+  return fits_;
+}
+
+Real
+Simple_spacer::rod_force (int l, int r, Real dist)
+{
+  Real c = range_stiffness (l, r);
+  Real d = range_ideal_len (l, r);
+  Real block_stretch = dist - d;
+  return c * block_stretch;
 }
 
 void
@@ -78,30 +93,11 @@
       return;
     }
 
-  Real c = range_stiffness (l, r);
-  if (isinf (c))
-    {
-      /*
-	If a spring is fixed, we have to do something here:
-	we let the rod override the spring.
-      */
-      Real total_dist = 0.;
-      for (int i = l; i < r; i++)
-	total_dist += springs_[i].ideal_;
-
-      if (total_dist < dist)
-	for (int i = l; i < r; i++)
-	  springs_[i].ideal_ *= dist / total_dist;
+  Real block_force = rod_force (l, r, dist);
 
+  if (isinf (block_force))
       return;
-    }
-
-  Real d = range_ideal_len (l, r);
-  Real block_stretch = dist - d;
-
-  Real block_force = c * block_stretch;
   force_ = max (force_, block_force);
-
   for (int i = l; i < r; i++)
     springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
 }
@@ -120,122 +116,121 @@
 {
   Real den = 0.0;
   for (int i = l; i < r; i++)
-    {
-      if (springs_[i].is_active_)
-	den += 1 * springs_[i].inverse_hooke_;
-    }
+    den += springs_[i].inverse_hooke_;
 
   return 1 / den;
 }
 
 Real
-Simple_spacer::active_blocking_force () const
+Simple_spacer::configuration_length () const
 {
-  Real bf = -infinity_f;
+  Real l = 0.;
   for (vsize i = 0; i < springs_.size (); i++)
-    if (springs_[i].is_active_)
-      bf = max (bf, springs_[i].block_force_);
-  return bf;
-}
-
-Real
-Simple_spacer::active_springs_stiffness () const
-{
-  Real stiff = range_stiffness (0, springs_.size ());
-  if (isinf (stiff))
-    {
-      /*
-	all springs are inactive. Take the stiffness of the
-	latest spring to block.
-      */
-
-      Real max_block_force = -infinity_f;
-      int max_i = -1;
-      for (vsize i = 0; i < springs_.size (); i++)
-	{
-	  if (springs_[i].block_force_ > max_block_force)
-	    {
-	      max_i = i;
-	      max_block_force = springs_[i].block_force_;
-	    }
-	}
+    l += springs_[i].length (force_);
 
-      stiff = 1/springs_[max_i].inverse_hooke_;
-    }
-  return stiff;
+  return l;
 }
 
 void
-Simple_spacer::set_active_states ()
+Simple_spacer::solve (Real line_len, bool ragged)
 {
-  /* float comparison is safe, since force is only copied.  */
-  for (vsize i = 0; i < springs_.size (); i++)
-    if (springs_[i].is_active_
-	&& springs_[i].block_force_ >= force_)
-      {
-	springs_[i].is_active_ = false;
-	active_count_--;
-      }
+  Real conf = configuration_length ();
+
+  ragged_ = ragged;
+  line_len_ = line_len;
+  if (ragged)
+    {
+      force_ = 0;
+      fits_ = configuration_length () <= line_len_;
+      /* we need to calculate a force here to prevent a bunch of short lines */
+      if (fits_)
+	force_ = expand_line ();
+    }
+  else if (conf < line_len_)
+    force_ = expand_line ();
+  else if (conf > line_len_)
+    force_ = compress_line ();
 }
 
 Real
-Simple_spacer::configuration_length () const
+Simple_spacer::expand_line ()
 {
-  Real l = 0.;
-  for (vsize i = 0; i < springs_.size (); i++)
-    l += springs_[i].length (force_);
+  double inv_hooke = 0;
+  double cur_len = configuration_length ();
 
-  return l;
-}
+  fits_ = true;
+  for (vsize i=0; i < springs_.size (); i++)
+    inv_hooke += springs_[i].inverse_hooke_;
 
-bool
-Simple_spacer::is_active () const
-{
-  return active_count_;
+  assert (cur_len <= line_len_);
+  return (line_len_ - cur_len) / inv_hooke + force_;
 }
 
-void
-Simple_spacer::my_solve_linelen ()
+Real
+Simple_spacer::compress_line ()
 {
-  while (is_active ())
+  double inv_hooke = 0;
+  double cur_len = configuration_length ();
+  double cur_force = force_;
+
+  fits_ = true;
+  for (vsize i=0; i < springs_.size (); i++)
+    inv_hooke += springs_[i].inverse_hooke_;
+
+  assert (line_len_ <= cur_len);
+
+  vector<Spring_description> sorted_springs = springs_;
+  sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring_description> ());
+  for (vsize i = 0; i < sorted_springs.size (); i++)
     {
-      force_ = active_blocking_force ();
-      Real conf = configuration_length ();
+      Spring_description sp = sorted_springs[i];
 
-      if (conf < line_len_)
-	{
-	  force_ += (line_len_ - conf) * active_springs_stiffness ();
-	  break;
-	}
-      else
-	set_active_states ();
+      assert (sp.block_force_ <= cur_force);
+      if (isinf (sp.block_force_))
+	break;
+
+      double block_dist = (cur_force - sp.block_force_) * inv_hooke;
+      if (cur_len - block_dist <= line_len_)
+	return cur_force + (line_len_ - cur_len) / inv_hooke;
+      cur_len -= block_dist;
+      inv_hooke -= sp.inverse_hooke_;
+      cur_force = sp.block_force_;
     }
+
+  fits_ = false;
+  return cur_force;
 }
 
 void
-Simple_spacer::my_solve_natural_len ()
+Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
 {
-  Real line_len_force = 0.0;
+  Spring_description desc;
 
-  while (is_active ())
+  desc.ideal_ = ideal;
+  desc.inverse_hooke_ = inverse_hooke;
+  if (!desc.is_sane ())
     {
-      force_ = max (active_blocking_force (), 0.0);
-      Real conf = configuration_length ();
+      programming_error ("insane spring found, setting to unit");
 
-      if (conf < line_len_)
-	{
-	  line_len_force = force_
-	    + (line_len_ - conf)
-	    * active_springs_stiffness ();
-	}
+      desc.inverse_hooke_ = 1.0;
+      desc.ideal_ = 1.0;
+    }
 
-      if (force_ < 1e-8) // ugh.,
-	break;
+  desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_;
+  // block at distance 0
 
-      set_active_states ();
-    }
+  springs_.push_back (desc);
+}
 
-  force_ = line_len_force;
+vector<Real>
+Simple_spacer::spring_positions () const
+{
+  vector<Real> ret;
+  ret.push_back (0.);
+
+  for (vsize i = 0; i < springs_.size (); i++)
+    ret.push_back (ret.back () + springs_[i].length (ragged_ ? 0.0 : force_));
+  return ret;
 }
 
 /****************************************************************/
@@ -244,7 +239,6 @@
 {
   ideal_ = 0.0;
   inverse_hooke_ = 0.0;
-  is_active_ = true;
   block_force_ = 0.0;
 }
 
@@ -259,10 +253,9 @@
 Real
 Spring_description::length (Real f) const
 {
-  if (!is_active_)
-    f = block_force_;
-  return ideal_ + f * inverse_hooke_;
+  return ideal_ + max (f, block_force_) * inverse_hooke_;
 }
+
 /****************************************************************/
 
 /*
@@ -278,174 +271,207 @@
   The ## forces the notes apart; we shouldn't allow the O's to touch
   this closely.
 */
-void
-Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
-{
-  if (ragged)
-    spacer_->my_solve_natural_len ();
-  else
-    spacer_->my_solve_linelen ();
-
-  positions->force_ = spacer_->force_;
 
-  /*
-    We used to have a penalty for compression, no matter what, but that
-    fucked up wtk1-fugue2 (taking 3 full pages.)
-  */
-  positions->config_.push_back (spacer_->indent_);
-  for (vsize i = 0; i < spacer_->springs_.size (); i++)
-    {
-      Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
-      positions->config_.push_back (positions->config_.back () + l);
-      /*
-	we have l>= 0 here, up to rounding errors
-      */
-    }
+struct Rod_desc
+{
+  vsize r_;
+  Real dist_;
 
-  /*
-    For raggedright, we must have a measure of music density: this is
-    to prevent lots of short lines (which all have force = 0).
-  */
-  if (ragged)
-    {
-      positions->satisfies_constraints_
-	= positions->config_.back () < spacer_->line_len_;
-    }
-  else
-    positions->satisfies_constraints_ = spacer_->is_active ();
+  bool operator< (const Rod_desc r)
+  {
+    return r_ < r.r_;
+  }
 
-  positions->cols_ = spaced_cols_;
-  positions->loose_cols_ = loose_cols_;
+  Rod_desc () {}
+  Rod_desc (vsize r, Real d)
+  {
+    r_ = r;
+    dist_ = d;
+  }
+};
 
-  /*
-    Check if breaking constraints are met.
-  */
-  bool break_satisfy = true;
-  int sz = positions->cols_.size ();
-  for (int i = sz; i--;)
-    {
-      SCM p = positions->cols_[i]->get_property ("penalty");
-      if (scm_is_number (p))
-	{
-	  if (scm_to_double (p) < -9999)
-	    break_satisfy = break_satisfy && (i == 0 || i == sz -1);
-	  if (scm_to_double (p) > 9999)
-	    break_satisfy = break_satisfy && ! (i == 0 || i == sz -1);
-	}
-    }
+struct Col_desc
+{
+  vector<Rod_desc> rods_;
+  vector<Rod_desc> end_rods_;   /* use these if they end at the last column of the line */
+  Real ideal_;
+  Real inverse_hooke_;
+  Real end_ideal_;
+  Real end_inverse_hooke_;
+  Interval keep_inside_line_;
+};
 
-  positions->satisfies_constraints_
-    = positions->satisfies_constraints_ && break_satisfy;
-}
+static int compare_paper_column_rank (Grob *const &a, Grob *const &b);
 
-void
-Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
+static void
+get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
 {
-  Spring_description desc;
+  Spring_smob *spring = 0;
 
-  desc.ideal_ = ideal;
-  desc.inverse_hooke_ = inverse_hooke;
-  if (!desc.is_sane ())
+  for (SCM s = this_col->get_object ("ideal-distances");
+       !spring && scm_is_pair (s);
+       s = scm_cdr (s))
     {
-      programming_error ("insane spring found, setting to unit");
+      Spring_smob *sp = unsmob_spring (scm_car (s));
 
-      desc.inverse_hooke_ = 1.0;
-      desc.ideal_ = 1.0;
+      if (sp->other_ == next_col)
+	spring = sp;
     }
 
-  if (!inverse_hooke)
-    desc.is_active_ = false;
-  else
-    {
-      /*
-	desc.is_active_ ?
-      */
-      desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_;
-      // block at distance 0
-
-      active_count_++;
-    }
-  springs_.push_back (desc);
-}
+  if (!spring)
+    programming_error (_f ("No spring between column %d and next one",
+			   Paper_column::get_rank (this_col)));
 
-static int
-compare_paper_column_rank (Grob *const &a,
-			   Grob *const &b)
-{
-  return Paper_column::get_rank (a) - Paper_column::get_rank (b);
+  *ideal = (spring) ? spring->distance_ : 5.0;
+  *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
 }
 
-void
-Simple_spacer_wrapper::add_columns (vector<Grob*> const &icols)
+static Col_desc
+get_col_desc (vector<Grob*> const &cols, vsize col_index, bool line_starter)
 {
-  vector<Grob*> cols (icols);
-  cols.clear ();
+  Grob *col = cols[col_index];
+  if (line_starter)
+    col = dynamic_cast<Item*> (col)->find_prebroken_piece (RIGHT);
 
-  for (vsize i = 0; i < icols.size (); i++)
-    if (scm_is_pair (icols[i]->get_object ("between-cols")))
-      loose_cols_.push_back (icols[i]);
-    else
-      cols.push_back (icols[i]);
+  Col_desc desc;
+  get_column_spring (col, cols[col_index+1], &desc.ideal_, &desc.inverse_hooke_);
+  if (Item::is_breakable (cols[col_index+1]))
+    get_column_spring (col,
+		       dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT),
+		       &desc.end_ideal_, &desc.end_inverse_hooke_);
 
-  spaced_cols_ = cols;
-  for (vsize i = 0; i < cols.size () - 1; i++)
+  for (SCM s = Spaceable_grob::get_minimum_distances (col);
+       scm_is_pair (s); s = scm_cdr (s))
     {
-      Spring_smob *spring = 0;
-
-      for (SCM s = cols[i]->get_object ("ideal-distances");
-	   !spring && scm_is_pair (s);
-	   s = scm_cdr (s))
+      Grob *other = unsmob_grob (scm_caar (s));
+      vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index);
+      if (j != VPOS)
 	{
-	  Spring_smob *sp = unsmob_spring (scm_car (s));
-
-	  if (sp->other_ == cols[i + 1])
-	    spring = sp;
+	  if (cols[j] == other)
+	    desc.rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s))));
+	  else
+	    desc.end_rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s))));
 	}
+    }
+  if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
+    desc.keep_inside_line_ = col->extent (col, X_AXIS);
+  return desc;
+}
 
-      if (!spring)
-	programming_error (_f ("No spring between column %d and next one",
-			       Paper_column::get_rank (cols[i])));
+vector<Real>
+get_line_forces (vector<Grob*> const &icols, vector<vsize> const &breaks,
+		 Real line_len, Real indent, bool ragged)
+{
+  vector<Real> force;
+  force.resize (breaks.size () * breaks.size ());
 
-      Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
-      Real inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0;
+  vector<Grob*> spaced_cols;
+  for (vsize i = 0; i < icols.size (); i++)
+    if (!scm_is_pair (icols[i]->get_object ("between-cols")))
+      spaced_cols.push_back (icols[i]);
 
-      spacer_->add_spring (ideal, inverse_hooke);
-    }
+  vector<Col_desc> cols;
+  cols.resize (spaced_cols.size () - 1);
+  for (vsize i = 1; i < spaced_cols.size () - 1; i++)
+    cols[i] = get_col_desc (spaced_cols, i, false);
 
-  for (vsize i = 0; i < cols.size () - 1; i++)
+  for (vsize b = 0; b < breaks.size () - 1; b++)
     {
-      for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
-	   scm_is_pair (s); s = scm_cdr (s))
-	{
-	  Grob *other = unsmob_grob (scm_caar (s));
-	  vsize j = binary_search (cols, other, &compare_paper_column_rank);
-	  if (j != VPOS && cols[j] == other)
-	    spacer_->add_rod (i, j, scm_to_double (scm_cdar (s)));
-	}
+      cols[breaks[b]] = get_col_desc (spaced_cols, breaks[b], true);
+      vsize st = breaks[b];
 
-      if (i
-	  && to_boolean (cols[i]->get_property ("keep-inside-line")))
+      for (vsize c = b+1; c < breaks.size (); c++)
 	{
-	  Interval e = cols[i]->extent (cols[i], X_AXIS);
-	  if (!e.is_empty ())
+	  vsize end = breaks[c];
+	  Simple_spacer spacer;
+
+	  for (vsize i = breaks[b]; i < end - 1; i++)
+	    spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
+	  spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_);
+
+
+	  for (vsize i = breaks[b]; i < end; i++)
+	    {
+	      for (vsize r = 0; r < cols[i].rods_.size (); r++)
+		if (cols[i].rods_[r].r_ < end)
+		  spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
+	      for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
+		if (cols[i].end_rods_[r].r_ == end)
+		  spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
+	      if (!cols[i].keep_inside_line_.is_empty ())
+		{
+		  spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
+		  spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
+		}
+	    }
+	  spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
+	  force[b * breaks.size () + c] = spacer.force ();
+	  if (!spacer.fits ())
 	    {
-	      spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
-	      spacer_->add_rod (0, i, e[LEFT]);
+	      force[b * breaks.size () + c] = infinity_f;
+	      break;
 	    }
 	}
     }
+  return force;
 }
 
-Simple_spacer_wrapper::Simple_spacer_wrapper ()
-{
-  spacer_ = new Simple_spacer ();
-}
+Column_x_positions
+get_line_configuration (vector<Grob*>const &columns,
+			Real line_len,
+			Real indent,
+			bool ragged)
+{
+  vector<Col_desc> cols;
+  Simple_spacer spacer;
+  vector<Grob*> spaced_cols;
+  vector<Grob*> loose_cols;
+
+  for (vsize i = 0; i < columns.size (); i++)
+    if (scm_is_pair (columns[i]->get_object ("between-cols")))
+      loose_cols.push_back (columns[i]);
+    else
+      spaced_cols.push_back (columns[i]);
 
-Simple_spacer_wrapper::~Simple_spacer_wrapper ()
-{
-  delete spacer_;
+  cols.resize (spaced_cols.size () - 1);
+
+  for (vsize i = 0; i < cols.size (); i++)
+    cols[i] = get_col_desc (spaced_cols, i, i == 0);
+  for (vsize i = 0; i < cols.size () - 1; i++)
+    spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
+  spacer.add_spring (cols.back ().end_ideal_, cols.back ().end_inverse_hooke_);
+
+  for (vsize i = 0; i < cols.size () - 1; i++)
+    for (vsize r = 0; r < cols[i].rods_.size (); r++)
+      spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
+  for (vsize r = 0; r < cols.back ().rods_.size (); r++)
+    spacer.add_rod (cols.size () - 1, cols.size (), cols.back ().rods_[r].dist_);
+
+  Column_x_positions ret;
+  spacer.solve (line_len, ragged);
+  ret.force_ = spacer.force ();
+
+  /*
+    We used to have a penalty for compression, no matter what, but that
+    fucked up wtk1-fugue2 (taking 3 full pages.)
+  */
+  ret.config_ = spacer.spring_positions ();
+  for (vsize i = 0; i < ret.config_.size (); i++)
+    ret.config_[i] += indent;
+
+  ret.satisfies_constraints_ = spacer.fits ();
+
+  ret.cols_ = spaced_cols;
+  ret.loose_cols_ = loose_cols;
+
+  ret.cols_[0] = (dynamic_cast<Item*> (ret.cols_[0]))->find_prebroken_piece (RIGHT);
+  ret.cols_.back () = (dynamic_cast<Item*> (ret.cols_.back ()))->find_prebroken_piece (LEFT);
+  return ret;
 }
 
-Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)
+static int
+compare_paper_column_rank (Grob *const &a,
+			   Grob *const &b)
 {
+  return Paper_column::get_rank (a) - Paper_column::get_rank (b);
 }
Index: lily/simple-spacer-scheme.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/simple-spacer-scheme.cc,v
retrieving revision 1.10
diff -u -r1.10 simple-spacer-scheme.cc
--- lily/simple-spacer-scheme.cc	11 Feb 2006 11:35:17 -0000	1.10
+++ lily/simple-spacer-scheme.cc	20 Apr 2006 02:10:38 -0000
@@ -53,29 +53,11 @@
       spacer.add_rod (l, r, distance);
     }
 
-  spacer.line_len_ = scm_to_double (length);
+  spacer.solve (scm_to_double (length), is_ragged);
 
-  if (is_ragged)
-    spacer.my_solve_natural_len ();
-  else
-    spacer.my_solve_linelen ();
+  vector<Real> posns = spacer.spring_positions ();
 
-  vector<Real> posns;
-  posns.push_back (0.0);
-  for (vsize i = 0; i < spacer.springs_.size (); i++)
-    {
-      Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_);
-      posns.push_back (posns.back () + l);
-    }
-
-  SCM force_return = SCM_BOOL_F;
-  if (!isinf (spacer.force_)
-      && (spacer.is_active () || is_ragged))
-    force_return = scm_from_double (spacer.force_);
-
-  if (is_ragged
-      && posns.back () > spacer.line_len_)
-    force_return = SCM_BOOL_F;
+  SCM force_return = spacer.fits () ? scm_from_double (spacer.force ()) : SCM_BOOL_F;
 
   SCM retval = SCM_EOL;
   for (vsize i = posns.size (); i--;)
Index: lily/break-algorithm.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/break-algorithm.cc,v
retrieving revision 1.55
diff -u -r1.55 break-algorithm.cc
--- lily/break-algorithm.cc	21 Feb 2006 23:26:57 -0000	1.55
+++ lily/break-algorithm.cc	20 Apr 2006 02:10:38 -0000
@@ -29,32 +29,6 @@
   return retval;
 }
 
-Simple_spacer_wrapper *
-Break_algorithm::generate_spacing_problem (vector<Grob*> const &curline,
-					   Interval line) const
-{
-  Simple_spacer_wrapper *spw = new Simple_spacer_wrapper;
-  Simple_spacer *sp = spw->spacer_;
-
-  /*
-    this is hardcoded, but this shouldn't happen anyway.
-    used to be get_dimension (ly_symbol2scm ("loose_column_distance"));
-  */
-  sp->default_space_ = 1.0;
-  sp->indent_ = line[LEFT];
-
-  /*
-    sort out how interfacing this should work;
-  */
-  if (line.is_empty ())
-    sp->line_len_ = -1;
-  else
-    sp->line_len_ = line.length ();
-
-  spw->add_columns (curline);
-  return spw;
-}
-
 Break_algorithm::Break_algorithm ()
 {
   pscore_ = 0;
Index: lily/gourlay-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/gourlay-breaking.cc,v
retrieving revision 1.95
diff -u -r1.95 gourlay-breaking.cc
--- lily/gourlay-breaking.cc	21 Feb 2006 23:26:58 -0000	1.95
+++ lily/gourlay-breaking.cc	20 Apr 2006 02:10:38 -0000
@@ -81,7 +81,7 @@
   vector<Grob*> all
     = pscore_->root_system ()->columns ();
 
-  vector<int> breaks = pscore_->find_break_indices ();
+  vector<vsize> breaks = pscore_->find_break_indices ();
 
   Break_node first_node;
   optimal_paths.push_back (first_node);
@@ -105,27 +105,15 @@
       for (vsize start_idx = break_idx; start_idx--;)
 	{
 	  vector<Grob*> line (all.begin () + breaks[start_idx],
-				  all.begin () + breaks[break_idx] + 1);
-
-	  line[0] = dynamic_cast<Item *> (line[0])->find_prebroken_piece (RIGHT);
-	  line.back () = dynamic_cast<Item *> (line.back ())->find_prebroken_piece (LEFT);
-
-	  Column_x_positions cp;
-	  cp.cols_ = line;
+			      all.begin () + breaks[break_idx] + 1);
 
 	  Interval line_dims
 	    = line_dimensions_int (pscore_->layout (), optimal_paths[start_idx].line_);
-	  Simple_spacer_wrapper *sp = generate_spacing_problem (line, line_dims);
 	  bool last_line = break_idx == breaks.size () - 1;
-	  bool ragged = ragged_right
-	    || (last_line && ragged_last);
-
-	  sp->solve (&cp, ragged);
-
-	  delete sp;
+	  bool ragged = ragged_right || (last_line && ragged_last);
 
-	  if (ragged && last_line)
-	    cp.force_ = 0.0;
+	  Column_x_positions cp = get_line_configuration (line, line_dims[RIGHT] - line_dims[LEFT],
+							  line_dims[LEFT], ragged);
 
 	  if (fabs (cp.force_) > worst_force)
 	    worst_force = fabs (cp.force_);
Index: lily/constrained-breaking.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/constrained-breaking.cc,v
retrieving revision 1.4
diff -u -r1.4 constrained-breaking.cc
--- lily/constrained-breaking.cc	9 Mar 2006 22:15:40 -0000	1.4
+++ lily/constrained-breaking.cc	20 Apr 2006 02:10:38 -0000
@@ -82,23 +82,19 @@
       if (0 == sys && j > 0)
         break; /* the first line cannot have its first break after the beginning */
 
-      Column_x_positions const *cur = &cols_[(j + start_col)*cols_rank_ + brk];
-      Column_x_positions const *prev = NULL;
+      Line_details const &cur = lines_[(j + start_col)*lines_rank_ + brk];
+      Real prev_f = 0;
       Real prev_dem = 0;
 
       if (sys > 0)
         {
-          prev = st[(sys-1) * rank + j].line_config_;
+          prev_f = st[(sys-1) * rank + j].details_.force_;
           prev_dem = st[(sys-1) * rank + j].demerits_;
         }
       if (isinf (prev_dem))
         break;
 
-      Real dem;
-      Real force;
-      Real pen;
-      combine_demerits (prev, cur, &force, &pen, &dem);
-      dem += prev_dem;
+      Real dem = combine_demerits (cur.force_, prev_f) + prev_dem;
       if (isinf (dem))
         continue;
 
@@ -107,10 +103,8 @@
         {
           found_something = true;
           st[k].demerits_ = dem;
-          st[k].force_ = force;
-          st[k].penalty_ = pen;
+          st[k].details_ = cur;
           st[k].prev_ = j;
-          st[k].line_config_ = cur;
         }
     }
   return found_something;
@@ -137,23 +131,12 @@
   Column_x_positions col;
 
   vector<Grob*> line (all_.begin () + breaks_[i],
-                      all_.begin() + breaks_[j] + 1);
-
-  line[0] = dynamic_cast<Item *> (line[0])->find_prebroken_piece (RIGHT);
-  line.back () = dynamic_cast<Item *> (line.back ())->find_prebroken_piece (LEFT);
-
-  col.cols_ = line;
-
-  /* we have no idea what line this will be -- only whether it is the first */
+		      all_.begin() + breaks_[j] + 1);
   Interval line_dims = line_dimensions_int (pscore_->layout (), i);
-  Simple_spacer_wrapper *sp = generate_spacing_problem (line, line_dims);
-
   bool last = j == breaks_.size () - 1;
   bool ragged = ragged_right || (last && ragged_last);
-  sp->solve (&col, ragged);
 
-  delete sp;
-  return col;
+  return get_line_configuration (line, line_dims[RIGHT] - line_dims[LEFT], line_dims[LEFT], ragged);
 }
 
 void
@@ -163,18 +146,44 @@
 
   if (!breaks_.size () && pscore_)
     {
+      Output_def *l = pscore_->layout ();
+      Real extent = scm_to_double (l->c_variable ("system-height"));
+      Real padding = scm_to_double (l->c_variable ("between-system-padding"));
+      Real space = scm_to_double (l->c_variable ("between-system-space"));
+      bool ragged_right = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
+      bool ragged_last = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
+
+      Interval first_line = line_dimensions_int (pscore_->layout (), 0);
+      Interval other_lines = line_dimensions_int (pscore_->layout (), 1);
       /* do all the rod/spring problems */
       breaks_ = pscore_->find_break_indices ();
-      cols_rank_ = breaks_.size ();
+      lines_rank_ = breaks_.size ();
       all_ = pscore_->root_system ()->columns ();
-      cols_.resize (breaks_.size () * breaks_.size ());
+      lines_.resize (breaks_.size () * breaks_.size ());
+      vector<Real> forces = get_line_forces (all_,
+					     breaks_,
+					     other_lines.length (),
+					     other_lines.length () - first_line.length (),
+					     ragged_right);
       for (vsize i = 0; i < breaks_.size () - 1; i++)
+	{
           for (vsize j = i + 1; j < breaks_.size (); j++)
             {
-              cols_[i*cols_rank_ + j] = space_line (i, j);
-              if (!cols_[i*cols_rank_ + j].satisfies_constraints_)
+	      bool last = j == breaks_.size () - 1;
+	      bool ragged = ragged_right || (last && ragged_last);
+              int k = i*lines_rank_ + j;
+
+              lines_[k].force_ = forces[k];
+              lines_[k].extent_ = extent;
+              lines_[k].padding_ = padding;
+              lines_[k].space_ = space;
+              lines_[k].inverse_hooke_ = 3; // FIXME: somewhat arbitrary
+	      if (ragged && lines_[k].force_ < 0)
+		lines_[k].force_ = infinity_f;
+              if (isinf (lines_[k].force_))
                 break;
             }
+	}
 
       /* work out all the starting indices */
       for (vsize i = 0; i < start_.size (); i++)
@@ -208,6 +217,7 @@
 {
   vsize rank;
   vsize end_brk;
+  vsize start_brk = starting_breakpoints_[start];
   prepare_solution (start, end, sys_count, &rank, &end_brk);
 
   vector<Constrained_break_node> const &st = state_[start];
@@ -218,7 +228,7 @@
     {
       for (vsize brk = end_brk; brk != VPOS; brk--)
         {
-          if (!isinf (st[sys*rank + brk].force_))
+          if (!isinf (st[sys*rank + brk].details_.force_))
             {
               if (brk != end_brk)
                 {
@@ -228,9 +238,10 @@
               /* build up the good solution */
               for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
                 {
+		  vsize prev_brk = st[cur_sys*rank + brk].prev_;
                   assert (brk != VPOS);
-                  ret.push_back( *st[cur_sys*rank + brk].line_config_ );
-                  brk = st[cur_sys*rank + brk].prev_;
+                  ret.push_back (space_line (prev_brk + start_brk, brk + start_brk));
+                  brk = prev_brk;
                 }
               reverse (ret);
               return ret;
@@ -243,76 +254,21 @@
   return ret;
 }
 
-Real
-Constrained_breaking::get_demerits (vsize start, vsize end, vsize sys_count)
-{
-  vsize rank;
-  vsize brk;
-  prepare_solution (start, end, sys_count, &rank, &brk);
-
-  return state_[start][(sys_count-1)*rank + brk].demerits_;
-}
-
-Real
-Constrained_breaking::get_force (vsize start, vsize end, vsize sys_count)
+std::vector<Line_details>
+Constrained_breaking::get_details (vsize start, vsize end, vsize sys_count)
 {
   vsize rank;
   vsize brk;
   prepare_solution (start, end, sys_count, &rank, &brk);
   vector<Constrained_break_node> const &st = state_[start];
-  Real f = 0;
+  vector<Line_details> ret;
 
   for (int sys = sys_count-1; sys >= 0 && brk != VPOS; sys--)
     {
-      f += fabs (st[sys*rank + brk].force_);
+      ret.push_back (st[sys*rank + brk].details_);
       brk = st[sys*rank + brk].prev_;
     }
-  if (brk == VPOS)
-    f = infinity_f;
-
-  return f;
-}
-
-Real
-Constrained_breaking::get_penalty (vsize start, vsize end, vsize sys_count)
-{
-  vsize rank;
-  vsize brk;
-  prepare_solution (start, end, sys_count, &rank, &brk);
-
-  return state_[start][(sys_count-1)*rank + brk].penalty_;
-}
-
-Real
-Constrained_breaking::get_page_penalty (vsize start, vsize end, vsize sys_count, vsize sys_num, bool turn)
-{
-  vsize rank;
-  vsize brk;
-  prepare_solution (start, end, sys_count, &rank, &brk);
-
-  vsize sys;
-  for (sys = sys_count-1; sys > sys_num; sys--)
-      brk = state_[start][sys*rank + brk].prev_;
-
-  if (brk == VPOS) /* we didn't satisfy constraints */
-    return 0;
-  vector<Grob*> const &cols = state_[start][sys*rank + brk].line_config_->cols_;
-  if (cols.empty ())
-    return 0;
-
-  Grob const *pc = cols.back ();
-  if (pc->original ())
-    {
-      SCM pen = pc->get_property ("page-penalty");
-      SCM turn_pen = pc->get_property ("page-turn-penalty");
-      Real ret = 0;
-      if (!turn && scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
-	ret = scm_to_double (pen);
-      if (turn && scm_is_number (turn_pen) && fabs (scm_to_double (turn_pen)) < 10000)
-        ret = scm_to_double (turn_pen);
-      return ret;
-    }
-  return 0;
+  return ret;
 }
 
 int
@@ -332,7 +288,7 @@
         {
           resize (sys_count + 3);
         }
-      if (!isinf (st[sys_count*rank + brk].force_))
+      if (!isinf (st[sys_count*rank + brk].details_.force_))
         return sys_count + 1;
     }
   /* no possible breaks satisfy constraints */
@@ -367,37 +323,15 @@
   start_.push_back (0);
 }
 
-Constrained_breaking::Constrained_breaking (vector<int> const &start)
+Constrained_breaking::Constrained_breaking (vector<vsize> const &start)
   : start_ (start)
 {
   valid_systems_ = systems_ = 0;
 }
 
-void
-Constrained_breaking::combine_demerits (Column_x_positions const *prev,
-                                        Column_x_positions const *col,
-                                        Real *force,
-                                        Real *penalty,
-                                        Real *demerits) const
-{
-  Real prev_f = prev ? prev->force_ : 0;
-
-  *penalty = 0;
-  if (col->cols_.empty () || !col->satisfies_constraints_)
-    *force = infinity_f;
-  else
-    {
-      *force = col->force_;
-
-      Grob *pc = col->cols_.back ();
-      if (pc->original ())
-        {
-          SCM pen = pc->get_property ("penalty");
-          if (scm_is_number (pen) && fabs (scm_to_double (pen)) < 10000)
-            *penalty += scm_to_double (pen);
-        }
-    }
-
-  *demerits = (*force) * (*force) + abs (prev_f - *force) + *penalty;
+Real
+Constrained_breaking::combine_demerits (Real force, Real prev_force)
+{
+  return force * force + fabs (prev_force - force);
 }
 
Index: lily/paper-score.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/paper-score.cc,v
retrieving revision 1.100
diff -u -r1.100 paper-score.cc
--- lily/paper-score.cc	23 Feb 2006 10:52:07 -0000	1.100
+++ lily/paper-score.cc	20 Apr 2006 02:10:38 -0000
@@ -29,7 +29,7 @@
   layout_ = layout;
   system_ = 0;
   systems_ = SCM_EOL;
-  paper_systems_ = SCM_EOL;
+  paper_systems_ = SCM_BOOL_F;
 }
 
 Paper_score::Paper_score (Paper_score const &s)
@@ -60,11 +60,11 @@
 }
 
 
-vector<int>
+vector<vsize>
 Paper_score::find_break_indices () const
 {
   vector<Grob*> all = root_system ()->columns ();
-  vector<int> retval;
+  vector<vsize> retval;
 
   for (vsize i = 0; i < all.size (); i++)
     if (Item::is_breakable (all[i]))
@@ -79,7 +79,9 @@
 {
   Break_algorithm *algorithm = 0;
   vector<Column_x_positions> sol;
-  
+
+  message (_ ("Calculating line breaks...") + " ");
+
   int system_count = robust_scm2int (layout ()->c_variable ("system-count"), 0);
   if (system_count)
     {
@@ -116,11 +118,6 @@
   pc.back ()->set_property ("breakable", SCM_BOOL_T);
 
   system_->pre_processing ();
-
-  vector<Column_x_positions> breaking = calc_breaking ();
-  system_->break_into_pieces (breaking);
-
-  paper_systems_ = system_->get_paper_systems ();
 }
 
 System *
@@ -136,8 +133,15 @@
 }
 
 SCM
-Paper_score::get_paper_systems () const
+Paper_score::get_paper_systems ()
 {
+  if (paper_systems_ == SCM_BOOL_F)
+    {
+      vector<Column_x_positions> breaking = calc_breaking ();
+      system_->break_into_pieces (breaking);
+      message (_ ("Drawing systems...") + " ");
+      paper_systems_ = system_->get_paper_systems ();
+    }
   return paper_systems_;
 }
 
Index: lily/system.cc
===================================================================
RCS file: /sources/lilypond/lilypond/lily/system.cc,v
retrieving revision 1.139
diff -u -r1.139 system.cc
--- lily/system.cc	21 Mar 2006 12:21:43 -0000	1.139
+++ lily/system.cc	20 Apr 2006 02:10:39 -0000
@@ -204,8 +204,8 @@
 {
   for (vsize i = 0; i < breaking.size (); i++)
     {
-      System *system = dynamic_cast<System *> (clone (i));
-      system->rank_ = i;
+      System *system = dynamic_cast<System *> (clone (broken_intos_.size ()));
+      system->rank_ = broken_intos_.size ();
 
       vector<Grob*> c (breaking[i].cols_);
       pscore_->typeset_system (system);
@@ -286,9 +286,6 @@
       (void) g->get_property ("before-line-breaking");
     }
 
-  message (_ ("Calculating line breaks..."));
-  progress_indication (" ");
-
   for (vsize i = 0; i < all_elements_->size (); i++)
     {
       Grob *e = all_elements_->grob (i);
Index: lily/include/simple-spacer.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/simple-spacer.hh,v
retrieving revision 1.34
diff -u -r1.34 simple-spacer.hh
--- lily/include/simple-spacer.hh	11 Feb 2006 11:35:16 -0000	1.34
+++ lily/include/simple-spacer.hh	20 Apr 2006 02:10:39 -0000
@@ -17,55 +17,65 @@
 {
   Real ideal_;
   Real inverse_hooke_;
-  bool is_active_;
   Real block_force_;
 
   Real length (Real force) const;
   Spring_description ();
 
   bool is_sane () const;
+
+  bool operator> (const Spring_description &s) const
+  {
+    return block_force_ > s.block_force_;
+  }
+
+  bool operator< (const Spring_description &s) const
+  {
+    return block_force_ < s.block_force_;
+  }
 };
 
 class Simple_spacer
 {
 public:
-  vector<Spring_description> springs_;
-  Real force_;
-  Real indent_;
-  Real line_len_;
-  Real default_space_;
-  int active_count_;
-
   Simple_spacer ();
 
-  void my_solve_linelen ();
-  void my_solve_natural_len ();
-  Real active_springs_stiffness () const;
-  Real range_stiffness (int, int) const;
+  void solve (Real line_len, bool ragged);
   void add_rod (int l, int r, Real dist);
   void add_spring (Real, Real);
   Real range_ideal_len (int l, int r) const;
-  Real active_blocking_force ()const;
-  Real configuration_length ()const;
-  void set_active_states ();
-  bool is_active () const;
+  Real range_stiffness (int l, int r) const;
+  Real configuration_length () const;
+  vector<Real> spring_positions () const;
+
+  Real force ();
+  bool fits ();
 
   DECLARE_SIMPLE_SMOBS (Simple_spacer,);
-};
 
-struct Simple_spacer_wrapper
-{
-  Simple_spacer *spacer_;
-  vector<Grob*> spaced_cols_;
-  vector<Grob*> loose_cols_;
-
-  Simple_spacer_wrapper ();
-  void add_columns (vector<Grob*> const &);
-  void solve (Column_x_positions *, bool);
-  ~Simple_spacer_wrapper ();
 private:
-  Simple_spacer_wrapper (Simple_spacer_wrapper const &);
+  Real expand_line ();
+  Real compress_line ();
+  Real rod_force (int l, int r, Real dist);
+
+  vector<Spring_description> springs_;
+  Real line_len_;
+  Real force_;
+  bool ragged_;
+  bool fits_;
 };
 
+/* returns a vector of dimensions breaks.size () * breaks.size () */
+vector<Real> get_line_forces (vector<Grob*> const &columns,
+			      vector<vsize> const &breaks,
+			      Real line_len,
+			      Real indent,
+			      bool ragged);
+
+Column_x_positions get_line_configuration (vector<Grob*> const &columns,
+					   Real line_len,
+					   Real indent,
+					   bool ragged);
+
 #endif /* SIMPLE_SPACER_HH */
 
Index: lily/include/break-algorithm.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/break-algorithm.hh,v
retrieving revision 1.32
diff -u -r1.32 break-algorithm.hh
--- lily/include/break-algorithm.hh	21 Feb 2006 23:26:58 -0000	1.32
+++ lily/include/break-algorithm.hh	20 Apr 2006 02:10:39 -0000
@@ -27,8 +27,6 @@
   void solve_line (Column_x_positions *) const;
   bool feasible (vector<Grob*> const &) const;
 
-  Simple_spacer_wrapper *generate_spacing_problem (vector<Grob*> const &,
-						   Interval) const;
 public:
   virtual ~Break_algorithm ();
   Simple_spacer *(*get_line_spacer) ();
Index: lily/include/constrained-breaking.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/constrained-breaking.hh,v
retrieving revision 1.4
diff -u -r1.4 constrained-breaking.hh
--- lily/include/constrained-breaking.hh	9 Mar 2006 22:15:40 -0000	1.4
+++ lily/include/constrained-breaking.hh	20 Apr 2006 02:10:39 -0000
@@ -12,6 +12,34 @@
 
 #include "break-algorithm.hh"
 
+enum {
+  FORBID = -1,
+  DEFAULT = 0,
+  FORCE = 1
+};
+
+struct Line_details {
+  Real force_;
+  Real extent_;   /* Y-exent of the system */
+  Real padding_;  /* compulsory space after this system (if we're not last on a page) */
+  Real space_;    /* spring length (stretches over extent_ but not over padding_) */
+  Real inverse_hooke_;
+
+  int page_break_;
+  Real turn_penalty_;
+
+  Line_details::Line_details ()
+  {
+    force_ = infinity_f;
+    extent_ = 0;
+    padding_ = 0;
+    space_ = 0;
+    inverse_hooke_ = 1;
+    page_break_ = 0;
+    turn_penalty_ = 0;
+  }
+};
+
 /*
    Helper to trace back an optimal path
 */
@@ -24,23 +52,17 @@
   /* unlike the Gourlay breaker, this is the sum of all demerits up to,
    * and including, this line */
   Real demerits_;
-  Real force_;
-  Real penalty_;
-  Column_x_positions const *line_config_;
+  struct Line_details details_;
 
   Constrained_break_node ()
   {
     prev_ = -1;
     demerits_ = infinity_f;
-    force_ = infinity_f;
-    penalty_ = 0;
-    line_config_ = 0;
   }
 
   void print () const
   {
-    printf ("prev break %d, demerits %f\n",
-	    prev_, demerits_);
+    printf ("prev break %d, demerits %f\n", prev_, demerits_);
   }
 };
 
@@ -50,46 +72,40 @@
 class Constrained_breaking : public Break_algorithm
 {
 public:
-  std::vector<Column_x_positions> solve ();
+  vector<Column_x_positions> solve ();
   Constrained_breaking ();
-  Constrained_breaking (std::vector<int> const &start_col_posns);
+  Constrained_breaking (vector<vsize> const &start_col_posns);
 
-  std::vector<Column_x_positions> get_solution(vsize start, vsize end, vsize sys_count);
-  Real get_demerits (vsize start, vsize end, vsize sys_count);
-  Real get_force (vsize start, vsize end, vsize sys_count);
-  Real get_penalty (vsize start, vsize end, vsize sys_count);
+  vector<Column_x_positions> get_solution(vsize start, vsize end, vsize sys_count);
+  vector<Line_details> get_details (vsize start, vsize end, vsize sys_count);
   int get_max_systems (vsize start, vsize end);
   int get_min_systems (vsize start, vsize end);
 
-  /* get the page penalty of system number sys with the given breaking */
-  Real get_page_penalty (vsize start, vsize end, vsize sys_count, vsize sys, bool turn);
-
   void resize (vsize systems);
 
 private:
   vsize valid_systems_;
   vsize systems_;
 
-  /* the (i,j)th entry is the column configuration for breaking between
+  /* the (i,j)th entry is the configuration for breaking between
     columns i and j */
-  std::vector<Column_x_positions> cols_;
-  vsize cols_rank_;
+  vector<Line_details> lines_;
+  vsize lines_rank_;
 
   /* the [i](j,k)th entry is the score for fitting the first k bars onto the
     first j systems, starting at the i'th allowed starting column */
-  std::vector<std::vector<Constrained_break_node> > state_;
+  vector<vector<Constrained_break_node> > state_;
 
-  vector<int> start_;         /* the columns at which we might be asked to start breaking */
-  vector<int> starting_breakpoints_; /* the corresponding index in breaks_ */
+  vector<vsize> start_;         /* the columns at which we might be asked to start breaking */
+  vector<vsize> starting_breakpoints_; /* the corresponding index in breaks_ */
 
   vector<Grob*> all_;
-  std::vector<int> breaks_;
+  vector<vsize> breaks_;
 
   Column_x_positions space_line (vsize start_col, vsize end_col);
   void prepare_solution (vsize start, vsize end, vsize sys_count, vsize *rank, vsize *brk);
 
-  void combine_demerits (Column_x_positions const *, Column_x_positions const *,
-                         Real *force, Real *pen, Real *dem) const;
+  Real combine_demerits (Real force, Real prev_force);
 
   bool calc_subproblem(vsize start, vsize systems, vsize max_break_index);
 };
Index: lily/include/paper-score.hh
===================================================================
RCS file: /sources/lilypond/lilypond/lily/include/paper-score.hh,v
retrieving revision 1.40
diff -u -r1.40 paper-score.hh
--- lily/include/paper-score.hh	21 Feb 2006 23:26:58 -0000	1.40
+++ lily/include/paper-score.hh	20 Apr 2006 02:10:39 -0000
@@ -29,8 +29,8 @@
 
   void typeset_system (System *);
   vector<Column_x_positions> calc_breaking ();
-  vector<int> find_break_indices () const;
-  SCM get_paper_systems () const;
+  vector<vsize> find_break_indices () const;
+  SCM get_paper_systems ();
 protected:
   virtual void process ();
   virtual void derived_mark () const;