X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fsimple-spacer.cc;h=a44e9f8d7546d8262d7a74af30fae5226a9f82c9;hb=ed463da03e0dd394c86ccd89fdea435b53b622b7;hp=46ccff03d85b56fb84b48cc08b47d68a1498a1f0;hpb=6ae532ffb4350961d3901a42b67d1db620f925a5;p=lilypond.git

diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc
index 46ccff03d8..a44e9f8d75 100644
--- a/lily/simple-spacer.cc
+++ b/lily/simple-spacer.cc
@@ -1,124 +1,408 @@
+/*   
+  simple-spacer.cc -- implement Simple_spacer
+  
+  source file of the GNU LilyPond music typesetter
+  
+  (c) 1999--2003 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+
+  TODO:
+  - add support for different stretch/shrink constants?
+  
+*/
+#include <stdio.h>
+#include <math.h>
+#include <libc-extension.hh>	// isinf
+
 #include "simple-spacer.hh"
-#include "idealspacing.hh"
-// #include ""
+#include "paper-column.hh"
+#include "spring.hh"
+#include "rod.hh"
+#include "warn.hh"
+#include "column-x-positions.hh"
+#include "spaceable-grob.hh"
+#include "dimensions.hh"
+
+
+/*
+   A simple spacing constraint solver. The approach:
+
+   Stretch the line uniformly until none of the constraints (rods)
+   block.  It then is very wide.
+
+      Compress until the next constraint blocks,
+
+      Mark the springs over the constrained part to be non-active.
+      
+   Repeat with the smaller set of non-active constraints, until all
+   constraints blocked, or until the line is as short as desired.
+
+   This is much simpler, and much much faster than full scale
+   Constrained QP. On the other hand, a situation like this will not
+   be typeset as dense as possible, because
+
+   c4                   c4           c4                  c4
+   veryveryverylongsyllable2         veryveryverylongsyllable2
+   " "4                 veryveryverylongsyllable2        syllable4
+
+
+   can be further compressed to
+
+
+   c4    c4                        c4   c4
+   veryveryverylongsyllable2       veryveryverylongsyllable2
+   " "4  veryveryverylongsyllable2      syllable4
 
 
+   Perhaps this is not a bad thing, because the 1st looks better anyway.  */
+
+
+Simple_spacer::Simple_spacer ()
+{
+  /*
+    Give an extra penalty for compression. Needed to avoid compressing
+    tightly spaced lines.
+  */
+  compression_penalty_b_ = false;
+  active_count_ = 0;
+  force_ = 0.;
+  indent_ =0.0;
+  default_space_ = 20 PT;
+}
+
 void
-Spring_info::set(Idealspacing *i)
+Simple_spacer::add_rod (int l, int r, Real dist)
 {
-  space_f_ = i->space_f_;
-  hooke_f_ = i->hooke_f_;
+  if (isinf (dist) || isnan (dist))
+    {
+      programming_error ("Weird minimum distance. Ignoring");
+      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;
+
+      return;
+    }
+  
+  Real d = range_ideal_len (l,r);
+  Real block_stretch = dist - d;
+  
+  Real block_force = c * block_stretch;
+  force_ = force_ >? block_force;
+
+  for (int i=l; i < r; i++)
+    springs_[i].block_force_ = block_force >?
+      springs_[i].block_force_ ;
 }
 
-Spring_info::Spring_info()
+Real
+Simple_spacer::range_ideal_len (int l, int r)   const
 {
-  space_f_ = 0.0;
-  hooke_f_ = 1.0;
-  blocking_stretch_f_ = infinity_f;
-  blocking_rod_l_ = 0;
+  Real d =0.;
+  for (int i=l; i < r; i++)
+    d += springs_[i].ideal_;
+  return d;
 }
 
-  
+Real
+Simple_spacer::range_stiffness (int l, int r) const
+{
+  Real den =0.0;
+  for (int i=l; i < r; i++)
+    {
+      if (springs_[i].active_b_)
+	den += 1 / springs_[i].hooke_;
+    }
+
+  return 1 / den;
+}
+
+Real
+Simple_spacer::active_blocking_force () const
+{
+  Real bf = - infinity_f; 
+  for (int i=0; i < springs_.size (); i++)
+    if (springs_[i].active_b_)
+      {
+	bf = bf >? springs_[i].block_force_;
+      }
+  return bf;
+}
+
+Real
+Simple_spacer::active_springs_stiffness () const
+{
+  return range_stiffness (0, springs_.size ());
+}
 
 void
-Simple_spring_spacer::init ()
+Simple_spacer::set_active_states ()
+{
+  /* float comparison is safe, since force is only copied.  */
+  for (int i=0 ; i <springs_.size (); i++)
+    if (springs_[i].active_b_
+	&& springs_[i].block_force_ >= force_)
+      {
+	springs_[i].active_b_ = false;
+	active_count_ --; 
+      }
+}   
+
+Real
+Simple_spacer::configuration_length () const
 {
-  for (PCursor<Rod_info*> i(rods_.top()); i.ok (); i++)
+  Real l =0.;
+  for (int i=0; i < springs_.size (); i++)
+    l += springs_[i].length (force_);
+
+  return l;
+}
+
+bool
+Simple_spacer::active_b () const
+{
+  return active_count_; 
+}
+
+void
+Simple_spacer::my_solve_linelen ()
+{
+  while (active_b ())
     {
-      Real hooke=0.0;
-      Real dist= i->distance_f_;
+      force_ = active_blocking_force ();
+      Real conf = configuration_length ();
 
-      hooke =0.0;
-      
-      for (int j = i->cols_[LEFT]; j < i->cols_[RIGHT]; j++)
+      if (conf < line_len_)
 	{
-	  hooke += 1/springs_[j].hooke_f_;
-	  dist -= springs_[j].space_f_;
+	  force_ += (line_len_  - conf) * active_springs_stiffness ();
+	  break;
 	}
+      else
+	set_active_states ();
+    }
+}
+
+
+void
+Simple_spacer::my_solve_natural_len ()
+{
+  while (active_b ())
+    {
+      force_ = active_blocking_force () >? 0.0;
+
+      if (force_ < 1e-8) // ugh.,
+	break;
       
-      hooke = 1/hooke;
+      set_active_states ();
+    }
+}
 
-      for (int j = i->cols_[LEFT]; j < i->cols_[RIGHT]; j++)
+void
+Simple_spacer::add_columns (Link_array<Grob> const &icols)
+{
+  Link_array<Grob> cols(icols);
+  
+  for (int i =  cols.size (); i--;)
+    if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
+      {
+	loose_cols_.push (cols[i]);
+	cols.del (i);
+      }
+  
+  spaced_cols_ = cols;
+  for (int i=0; i < cols.size () - 1; i++)
+    {
+      Spring_smob *spring = 0;
+
+      for (SCM s = cols[i]->get_grob_property ("ideal-distances");
+	   !spring && gh_pair_p (s);
+	   s = ly_cdr (s))
 	{
-	  Real block_stretch = hooke * dist / (springs_[j].space_f_ *
-					       springs_[j].hooke_f_ );
+	  Spring_smob *sp = unsmob_spring (ly_car (s));
+	  
+	  
+	  if (sp->other_ == cols[i+1])
+	    spring = sp;
+	}
 
-	  if (block_stretch < springs_[j].blocking_stretch_f_)
+      Spring_description desc;
+      if (spring)
+	{
+	  desc.ideal_ = spring->distance_;
+	  desc.hooke_ = spring->strength_;
+	}
+      else
+	{
+	  programming_error (_f("No spring between column %d and next one",
+				Paper_column::get_rank (cols[i])
+				));
+	  desc.hooke_ = 1.0;
+	  desc.ideal_ = default_space_;
+
+	  continue;
+	}
+
+      if (!desc.sane_b ())
+	{
+	  programming_error ("Insane spring found. Setting to unit spring.");
+
+	  desc.hooke_ = 1.0;
+	  desc.ideal_ = 1.0;
+	}
+
+      if (isinf (desc.hooke_))
+	{
+	  desc.active_b_ = false;
+	  springs_.push (desc);
+	}
+      else
+	{
+	  desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
+	  springs_.push (desc);
+      
+	  active_count_ ++;
+	}
+
+      if (spring->expand_only_b_)
+	{
+	  compression_penalty_b_ = true;
+	}
+      
+    }
+  
+  for (int i=0; i < cols.size () - 1; i++)
+    {
+      for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
+	   gh_pair_p (s); s = ly_cdr (s))
+	{
+	  Grob * other = unsmob_grob (ly_caar (s));
+	  int oi = cols.find_index (other);
+	  if (oi >= 0)
 	    {
-	      springs_[j].blocking_stretch_f_ = block_stretch;
-	      springs_[j].blocking_rod_l_ = i.ptr ();
+	      add_rod (i, oi, gh_scm2double (ly_cdar (s)));
 	    }
 	}
     }
+
+
 }
 
-Array<Real>
-Simple_spring_spacer::solve ()
+/*
+  
+  TODO: should a add penalty for widely varying spring forces (caused
+  by constraints, eg.
+
+
+         =====  
+         |   |
+  o|o|  x ##x
+
+
+  The ## forces the notes apart; we shouldn't allow the O's to touch
+  this closely.
+  
+ */
+void
+Simple_spacer::solve (Column_x_positions *positions, bool ragged) 
 {
-  Real start_force = 0.0;
+  /*
+    TODO: should support natural length on only the last line.
+   */
+  ragged = ragged || (line_len_ < 0) ;
+  if (ragged)
+    my_solve_natural_len ();
+  else
+    my_solve_linelen ();
 
-  for (int i=0; i< springs_.size (); i++)
+  positions->force_ = 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 (indent_);
+  for (int i=0; i <springs_.size (); i++)
     {
-      start_force = start_force >?
-	springs_[i].blocking_stretch_f_ * springs_[i].hooke_f_;
+      Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
+      positions->config_.push (positions->config_.top () + l);
+      /*
+	we have l>= 0 here, up to rounding errors 
+      */
     }
 
-  Array<Real> stretch_factors;
-  Array<bool> blocked;
-  int blocked_count=0; 
-  Real current_len =0.0;
-  for (int i=0; i < springs_.size (); i++)
+  /*
+    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 && line_len_ > 0)
     {
-      Real stretch = start_force / (springs_[i].hooke_f_ * springs_[i].space_f_);
-      stretch_factors.push (stretch);
-      current_len += (1  + stretch) * springs_[i].space_f_;
-      blocked.push(false);
+      Real len = positions->config_.top ();
+      positions->force_ = (line_len_ - len) *  active_springs_stiffness ();
     }
 
- 
-  while (blocked_count < blocked.size ())
-    {
-      Real      next_stretch = -1.0;
-      int block_index;
-      for (int i=0; i< stretch_factors.size (); i++)
-	{
-	  if (!blocked[i])
-	    {
-	      next_stretch = next_stretch >? springs_[i].blocking_stretch_f_;
 
-	      if (next_stretch < springs_[i].blocking_stretch_f_)
-		{
-		  next_stretch = springs_[i].blocking_stretch_f_;
-		  block_index = i;
-		}
-	    }
-	}
-      current_len = 0.0;
+  positions->cols_ = spaced_cols_;
+  positions->loose_cols_ = loose_cols_;
+  positions->satisfies_constraints_b_ = (line_len_ < 0) || active_b ();
 
-      Real force = next_stretch * (springs_[block_index].space_f_* springs_[block_index].hooke_f_);
-      for (int i=0; i< stretch_factors.size (); i++)
-	{
-	  if (!blocked[i])
-	    {
-	      stretch_factors[i] = force / (springs_[i].space_f_ * springs_[i].hooke_f_);
-	    }
-	  current_len += (1.0 + stretch_factors[i]) * springs_[i].space_f_;
-	}
-
-      Rod_info *blockrod = springs_[block_index].blocking_rod_l_;
-      for (int j = blockrod->cols_ [LEFT]; j < blockrod->cols_ [RIGHT]; j++)
+  /*
+    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_grob_property( "penalty");
+      if (gh_number_p (p))
 	{
-	  blocked[j] = true;
-	  blocked_count ++;
+	  if (gh_scm2double (p) < -9999)
+	    break_satisfy = break_satisfy && (i == 0 || i == sz -1);
+	  if (gh_scm2double (p) > 9999)
+	    break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 	}
+      
     }
 
+  positions->satisfies_constraints_b_ =
+    positions->satisfies_constraints_b_ && break_satisfy;
 
-  Array<Real> distances;
-  for (int i=0; i < stretch_factors.size (); i++)
-    {
-      distances.push (stretch_factors[i] * springs_[i].space_f_);
-    }
-  return distances;
+  if (ragged && force_ < 0)
+    positions->satisfies_constraints_b_ = false;
+}
+
+/****************************************************************/
+
+Spring_description::Spring_description ()
+{
+  ideal_ =0.0;
+  hooke_ =0.0;
+  active_b_ = true;
+  block_force_ = 0.0;
+}
+
+
+bool
+Spring_description::sane_b () const
+{
+  return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
 }
 
+Real
+Spring_description::length (Real f) const
+{
+  if (!active_b_)
+    f = block_force_;
+  return ideal_ + f / hooke_ ;
+}