X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fsimple-spacer.cc;h=1d38d9a70fda59eab91069b691339bd6a7d6b98d;hb=38d7d319eabc906e82fb42002678c6d42a23b6f7;hp=900fd77988ec3fb97eb480989131d06324381155;hpb=9d4a5bbc9687aef811a60aabd9cb839412984e96;p=lilypond.git

diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc
index 900fd77988..1d38d9a70f 100644
--- a/lily/simple-spacer.cc
+++ b/lily/simple-spacer.cc
@@ -3,7 +3,7 @@
 
   source file of the GNU LilyPond music typesetter
 
-  (c) 1999--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
+  (c) 1999--2009 Han-Wen Nienhuys <hanwen@xs4all.nl>
 
   TODO:
   - add support for different stretch/shrink constants?
@@ -59,14 +59,34 @@
 
 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;
+  line_len_ = 0.0;
+  force_ = 0.0;
+  fits_ = true;
+  ragged_ = true;
+}
+
+Real
+Simple_spacer::force () const
+{
+  return force_;
+}
+
+bool
+Simple_spacer::fits () const
+{
+  return fits_;
+}
+
+Real
+Simple_spacer::rod_force (int l, int r, Real dist)
+{
+  Real d = range_ideal_len (l, r);
+  Real c = range_stiffness (l, r, dist > d);
+  Real block_stretch = dist - d;
+
+  if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
+    return 0;
+  return c * block_stretch;
 }
 
 void
@@ -78,32 +98,25 @@ Simple_spacer::add_rod (int l, int r, Real dist)
       return;
     }
 
-  Real c = range_stiffness (l, r);
-  if (isinf (c))
+  Real block_force = rod_force (l, r, dist);
+
+  if (isinf (block_force))
     {
-      /*
-	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)
+      Real spring_dist = range_ideal_len (l, r);
+      if (spring_dist < dist)
 	for (int i = l; i < r; i++)
-	  springs_[i].ideal_ *= dist / total_dist;
+	  {
+	    if (spring_dist)
+	      springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
+	    else
+	      springs_[i].set_distance (dist / (r - l));
+	  }
 
       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_);
+    springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
 }
 
 Real
@@ -111,341 +124,390 @@ Simple_spacer::range_ideal_len (int l, int r) const
 {
   Real d = 0.;
   for (int i = l; i < r; i++)
-    d += springs_[i].ideal_;
+    d += springs_[i].distance ();
   return d;
 }
 
 Real
-Simple_spacer::range_stiffness (int l, int r) const
+Simple_spacer::range_stiffness (int l, int r, bool stretch) const
 {
   Real den = 0.0;
   for (int i = l; i < r; i++)
-    {
-      if (springs_[i].is_active_)
-	den += 1 * springs_[i].inverse_hooke_;
-    }
+    den += stretch ? springs_[i].inverse_stretch_strength ()
+      : springs_[i].inverse_compress_strength ();
 
   return 1 / den;
 }
 
 Real
-Simple_spacer::active_blocking_force () const
+Simple_spacer::configuration_length (Real force) 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 (force_);
+
+  ragged_ = ragged;
+  line_len_ = line_len;
+  if (conf < line_len_)
+    force_ = expand_line ();
+  else if (conf > line_len_)
+    force_ = compress_line ();
+
+  if (ragged && force_ < 0)
+    fits_ = false;
 }
 
 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 (force_);
 
-  return l;
-}
+  fits_ = true;
+  for (vsize i=0; i < springs_.size (); i++)
+    inv_hooke += springs_[i].inverse_stretch_strength ();
 
-bool
-Simple_spacer::is_active () const
-{
-  return active_count_;
+  if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
+    return 0.0;         /* anyway, then it makes no difference what the force is */
+
+  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 (force_);
+  double cur_force = force_;
+  bool compressed = false;
+
+  /* just because we are in compress_line () doesn't mean that the line
+     will actually be compressed (as in, a negative force) because
+     we start out with a stretched line. Here, we check whether we
+     will be compressed or stretched (so we know which spring constant to use) */
+  if (configuration_length (0.0) > line_len_)
     {
-      force_ = active_blocking_force ();
-      Real conf = configuration_length ();
-
-      if (conf < line_len_)
-	{
-	  force_ += (line_len_ - conf) * active_springs_stiffness ();
-	  break;
-	}
-      else
-	set_active_states ();
+      cur_force = 0.0;
+      cur_len = configuration_length (0.0);
+      compressed = true;
     }
-}
 
-void
-Simple_spacer::my_solve_natural_len ()
-{
-  Real line_len_force = 0.0;
+  fits_ = true;
+  for (vsize i=0; i < springs_.size (); i++)
+    inv_hooke += compressed
+      ? springs_[i].inverse_compress_strength ()
+      : springs_[i].inverse_stretch_strength ();
 
-  while (is_active ())
-    {
-      force_ = max (active_blocking_force (), 0.0);
-      Real conf = configuration_length ();
+  assert (line_len_ <= cur_len);
 
-      if (conf < line_len_)
-	{
-	  line_len_force = force_
-	    + (line_len_ - conf)
-	    * active_springs_stiffness ();
-	}
+  vector<Spring> sorted_springs = springs_;
+  sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
+
+  for (vsize i = 0; i < sorted_springs.size (); i++)
+    {
+      Spring sp = sorted_springs[i];
 
-      if (force_ < 1e-8) // ugh.,
+      assert (sp.blocking_force () <= cur_force);
+      if (isinf (sp.blocking_force ()))
 	break;
 
-      set_active_states ();
+      double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
+      if (cur_len - block_dist < line_len_)
+	{
+	  cur_force += (line_len_ - cur_len) / inv_hooke;
+	  cur_len = line_len_;
+
+	  /*
+	    Paranoia check.
+	  */
+	  assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
+	  return cur_force;
+	}
+      
+      cur_len -= block_dist;
+      inv_hooke -= sp.inverse_compress_strength ();
+      cur_force = sp.blocking_force ();
     }
 
-  force_ = line_len_force;
+  fits_ = false;
+  return cur_force;
 }
 
-/****************************************************************/
-
-Spring_description::Spring_description ()
+void
+Simple_spacer::add_spring (Spring const &sp)
 {
-  ideal_ = 0.0;
-  inverse_hooke_ = 0.0;
-  is_active_ = true;
-  block_force_ = 0.0;
+  force_ = max (force_, sp.blocking_force ());
+  springs_.push_back (sp);
 }
 
-bool
-Spring_description::is_sane () const
+vector<Real>
+Simple_spacer::spring_positions () const
 {
-  return (inverse_hooke_ >= 0)
-    && ideal_ > 0
-    && !isinf (ideal_) && !isnan (ideal_);
+  vector<Real> ret;
+  ret.push_back (0.);
+
+  for (vsize i = 0; i < springs_.size (); i++)
+    ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
+  return ret;
 }
 
 Real
-Spring_description::length (Real f) const
+Simple_spacer::force_penalty (bool ragged) const
 {
-  if (!is_active_)
-    f = block_force_;
-  return ideal_ + f * inverse_hooke_;
-}
-/****************************************************************/
+  /* If we are ragged-right, we don't want to penalise according to the force,
+     but according to the amount of whitespace that is present after the end
+     of the line. */
+  if (ragged)
+    return max (0.0, line_len_ - configuration_length (0.0));
 
-/*
-  TODO: should a add penalty for widely varying spring forces (caused
-  by constraints, eg.
+  /* Use a convex compression penalty. */
+  Real f = force_;
+  return f - (f < 0 ? f*f*f*f*2 : 0);
+}
 
+/****************************************************************/
 
-  .     =====
-  .     |   |
-  .o|o|x ##x
-  .
+struct Rod_description
+{
+  vsize r_;
+  Real dist_;
+
+  bool operator< (const Rod_description r)
+  {
+    return r_ < r.r_;
+  }
+
+  Rod_description ()
+  {
+    r_ = 0;
+    dist_ = 0;
+  }
+
+  Rod_description (vsize r, Real d)
+  {
+    r_ = r;
+    dist_ = d;
+  }
+};
+
+struct Column_description
+{
+  vector<Rod_description> rods_;
+  vector<Rod_description> end_rods_;   /* use these if they end at the last column of the line */
+  Spring spring_;
+  Spring end_spring_;
+
+  SCM break_permission_;
+  Interval keep_inside_line_;
+
+  Column_description ()
+  {
+    break_permission_ = SCM_EOL;
+  }
+};
+
+static bool
+is_loose (Grob *g)
+{
+  return (scm_is_pair (g->get_object ("between-cols")));
+}
 
-  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)
+static Grob*
+maybe_find_prebroken_piece (Grob *g, Direction d)
 {
-  if (ragged)
-    spacer_->my_solve_natural_len ();
-  else
-    spacer_->my_solve_linelen ();
+  Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
+  if (ret)
+    return ret;
+  return g;
+}
 
-  positions->force_ = spacer_->force_;
+static Grob*
+next_spaceable_column (vector<Grob*> const &list, vsize starting)
+{
+  for (vsize i = starting+1; i < list.size (); i++)
+    if (!is_loose (list[i]))
+      return list[i];
+  return 0;
+}
 
-  /*
-    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
-      */
-    }
+static Column_description
+get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
+{
+  Grob *col = cols[col_index];
+  if (line_starter)
+    col = maybe_find_prebroken_piece (col, RIGHT);
 
-  /*
-    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 ();
+  Column_description description;
+  Grob *next_col = next_spaceable_column (cols, col_index);
+  if (next_col)
+    description.spring_ = Spaceable_grob::get_spring (col, next_col);
 
-  positions->cols_ = spaced_cols_;
-  positions->loose_cols_ = loose_cols_;
+  Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
+  if (end_col)
+    description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
 
-  /*
-    Check if breaking constraints are met.
-  */
-  bool break_satisfy = true;
-  int sz = positions->cols_.size ();
-  for (int i = sz; i--;)
+  for (SCM s = Spaceable_grob::get_minimum_distances (col);
+       scm_is_pair (s); s = scm_cdr (s))
     {
-      SCM p = positions->cols_[i]->get_property ("penalty");
-      if (scm_is_number (p))
+      Grob *other = unsmob_grob (scm_caar (s));
+      vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
+      if (j != VPOS)
 	{
-	  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);
+	  if (cols[j] == other)
+	    description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
+	  else /* it must end at the LEFT prebroken_piece */
+	    description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
 	}
     }
+  
+  if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
+    description.keep_inside_line_ = col->extent (col, X_AXIS);
 
-  positions->satisfies_constraints_
-    = positions->satisfies_constraints_ && break_satisfy;
+  description.break_permission_ = col->get_property ("line-break-permission");
+  return description;
 }
 
-void
-Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
+vector<Real>
+get_line_forces (vector<Grob*> const &columns,
+		 Real line_len, Real indent, bool ragged)
 {
-  Spring_description desc;
-
-  desc.ideal_ = ideal;
-  desc.inverse_hooke_ = inverse_hooke;
-  if (!desc.is_sane ())
+  vector<vsize> breaks;
+  vector<Real> force;
+  vector<Grob*> non_loose;
+  vector<Column_description> cols;
+  SCM force_break = ly_symbol2scm ("force");
+
+  for (vsize i = 0; i < columns.size (); i++)
+    if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
+      non_loose.push_back (columns[i]);
+
+  breaks.clear ();
+  breaks.push_back (0);
+  cols.push_back (Column_description ());
+  for (vsize i = 1; i + 1 < non_loose.size (); i++)
     {
-      programming_error ("insane spring found, setting to unit");
+      if (Paper_column::is_breakable (non_loose[i]))
+	breaks.push_back (cols.size ());
 
-      desc.inverse_hooke_ = 1.0;
-      desc.ideal_ = 1.0;
+      cols.push_back (get_column_description (non_loose, i, false));
     }
+  breaks.push_back (cols.size ());
+  force.resize (breaks.size () * breaks.size (), infinity_f);
 
-  if (!inverse_hooke)
-    desc.is_active_ = false;
-  else
+  for (vsize b = 0; b + 1 < breaks.size (); b++)
     {
-      /*
-	desc.is_active_ ?
-      */
-      desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_;
-      // block at distance 0
+      cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
+      vsize st = breaks[b];
 
-      active_count_++;
-    }
-  springs_.push_back (desc);
-}
+      for (vsize c = b+1; c < breaks.size (); c++)
+	{
+	  vsize end = breaks[c];
+	  Simple_spacer spacer;
 
-static int
-compare_paper_column_rank (Grob *const &a,
-			   Grob *const &b)
-{
-  return Paper_column::get_rank (a) - Paper_column::get_rank (b);
+	  for (vsize i = breaks[b]; i < end - 1; i++)
+	    spacer.add_spring (cols[i].spring_);
+	  spacer.add_spring (cols[end-1].end_spring_);
+
+
+	  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_penalty (ragged);
+
+	  if (!spacer.fits ())
+	    {
+	      if (c == b + 1)
+		force[b * breaks.size () + c] = -200000;
+	      else
+		force[b * breaks.size () + c] = infinity_f;
+	      break;
+	    }
+	  if (end < cols.size () && cols[end].break_permission_ == force_break)
+	    break;
+	}
+    }
+  return force;
 }
 
-void
-Simple_spacer_wrapper::add_columns (Link_array__Grob_ const &icols)
+Column_x_positions
+get_line_configuration (vector<Grob*> const &columns,
+			Real line_len,
+			Real indent,
+			bool ragged)
 {
-  Link_array__Grob_ cols (icols);
-  cols.clear ();
+  vector<Column_description> cols;
+  Simple_spacer spacer;
+  Column_x_positions ret;
 
-  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]);
+  ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
+  for (vsize i = 1; i + 1 < columns.size (); i++)
+    {
+      if (is_loose (columns[i]))
+	ret.loose_cols_.push_back (columns[i]);
+      else
+	ret.cols_.push_back (columns[i]);
+    }
+  ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
 
-  spaced_cols_ = cols;
-  for (vsize i = 0; i < cols.size () - 1; i++)
+  /* since we've already put our line-ending column in the column list, we can ignore
+     the end_XXX_ fields of our column_description */
+  for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
+    {
+      cols.push_back (get_column_description (ret.cols_, i, i == 0));
+      spacer.add_spring (cols[i].spring_);
+    }
+  for (vsize i = 0; i < cols.size (); i++)
     {
-      Spring_smob *spring = 0;
+      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 (SCM s = cols[i]->get_object ("ideal-distances");
-	   !spring && scm_is_pair (s);
-	   s = scm_cdr (s))
+      if (!cols[i].keep_inside_line_.is_empty ())
 	{
-	  Spring_smob *sp = unsmob_spring (scm_car (s));
-
-	  if (sp->other_ == cols[i + 1])
-	    spring = sp;
+	  spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
+	  spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
 	}
+    }
 
-      if (!spring)
-	programming_error (_f ("No spring between column %d and next one",
-			       Paper_column::get_rank (cols[i])));
+  spacer.solve (line_len, ragged);
+  ret.force_ = spacer.force_penalty (ragged);
 
-      Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
-      Real inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0;
+  ret.config_ = spacer.spring_positions ();
+  for (vsize i = 0; i < ret.config_.size (); i++)
+    ret.config_[i] += indent;
 
-      spacer_->add_spring (ideal, inverse_hooke);
-    }
+  ret.satisfies_constraints_ = spacer.fits ();
 
-  for (vsize i = 0; i < cols.size () - 1; i++)
+  /*
+    Check if breaking constraints are met.
+  */
+  for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
     {
-      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)));
-	}
-
-      if (i
-	  && to_boolean (cols[i]->get_property ("keep-inside-line")))
-	{
-	  Interval e = cols[i]->extent (cols[i], X_AXIS);
-	  if (!e.is_empty ())
-	    {
-	      spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
-	      spacer_->add_rod (0, i, e[LEFT]);
-	    }
-	}
+      SCM p = ret.cols_[i]->get_property ("line-break-permission");
+      if (p == ly_symbol2scm ("force"))
+	ret.satisfies_constraints_ = false;
     }
-}
-
-Simple_spacer_wrapper::Simple_spacer_wrapper ()
-{
-  spacer_ = new Simple_spacer ();
-}
 
-Simple_spacer_wrapper::~Simple_spacer_wrapper ()
-{
-  delete spacer_;
+  return ret;
 }
 
-Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)
-{
-}