X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fpage-spacing.cc;h=c236c94e88936193defac0c3f5ffa6631901503f;hb=76f060825126f528cdadd56fb88b47fdb3d9560d;hp=60e5174c3b5f0c10e6c1aa0a843f1575e205b996;hpb=feb23985504e99693ff87201cd26bf78282506ed;p=lilypond.git

diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc
index 60e5174c3b..c236c94e88 100644
--- a/lily/page-spacing.cc
+++ b/lily/page-spacing.cc
@@ -4,7 +4,7 @@
 
   source file of the GNU LilyPond music typesetter
 
-  (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
+  (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
 */
 
 #include "page-spacing.hh"
@@ -13,31 +13,38 @@
 #include "page-breaking.hh"
 #include "warn.hh"
 
-/* In order to prevent possible division by zero, we require every line
-   to have a spring of non-zero length. */
-Real
-line_space (const Line_details &line)
-{
-  return max (0.1, line.space_);
-}
-
 void
 Page_spacing::calc_force ()
 {
-  if (rod_height_ + last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_)
+  /* If the first system contains a title, we add back in the page-top-space. */
+  bool starts_with_title = first_line_.compressed_nontitle_lines_count_ < first_line_.compressed_lines_count_;
+  Real height = starts_with_title ? page_height_ + page_top_space_ : page_height_;
+
+  if (rod_height_ + last_line_.bottom_padding_ >= height)
     force_ = infinity_f;
   else
-    force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_;
+    force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_)
+      / max (0.1, inverse_spring_k_);
+}
+
+void
+Page_spacing::resize (Real new_height)
+{
+  page_height_ = new_height;
+  calc_force ();
 }
 
 void
 Page_spacing::append_system (const Line_details &line)
 {
+  if (!rod_height_)
+    first_line_ = line;
+
   rod_height_ += last_line_.padding_;
 
   rod_height_ += line.extent_.length ();
-  spring_len_ += line_space (line);
-  inverse_spring_k_ += max (0.1, line.inverse_hooke_);
+  spring_len_ += line.space_;
+  inverse_spring_k_ += line.inverse_hooke_;
 
   last_line_ = line;
 
@@ -53,8 +60,10 @@ Page_spacing::prepend_system (const Line_details &line)
     last_line_ = line;
 
   rod_height_ += line.extent_.length ();
-  spring_len_ += line_space (line);
-  inverse_spring_k_ += max (0.1, line.inverse_hooke_);
+  spring_len_ += line.space_;
+  inverse_spring_k_ += line.inverse_hooke_;
+
+  first_line_ = line;
 
   calc_force ();
 }
@@ -77,18 +86,17 @@ Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_nu
   ragged_last_ = breaker->is_last () && breaker->ragged_last ();
 }
 
-Spacing_result
+Page_spacing_result
 Page_spacer::solve (vsize page_count)
 {
   if (page_count > max_page_count_)
     resize (page_count);
 
-  Spacing_result ret;
-  ret.force_.resize (page_count);
-  ret.systems_per_page_.resize (page_count);
+  Page_spacing_result ret;
 
   vsize system = lines_.size () - 1;
-  vsize tack_onto_the_end = 0;
+  vsize extra_systems = 0;
+  vsize extra_pages = 0;
 
   if (isinf (state_.at (system, page_count-1).demerits_))
     {
@@ -104,13 +112,28 @@ Page_spacer::solve (vsize page_count)
 
       if (i)
 	{
-	  tack_onto_the_end = system - i;
+	  extra_systems = system - i;
 	  system = i;
 	}
       else
-	return Spacing_result (); /* couldn't salvage it -- probably going to crash */
+	{
+	  /* try chopping off pages from the end */
+	  vsize j;
+	  for (j = page_count; j && isinf (state_.at (system, j-1).demerits_); j--)
+	    ;
+
+	  if (j)
+	    {
+	      extra_pages = page_count - j;
+	      page_count = j;
+	    }
+	  else
+	    return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */
+	}
     }
 
+  ret.force_.resize (page_count);
+  ret.systems_per_page_.resize (page_count);
   ret.penalty_ = state_.at (system, page_count-1).penalty_
     + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_;
 
@@ -125,9 +148,23 @@ Page_spacer::solve (vsize page_count)
       if (p == 0)
 	ret.systems_per_page_[p] = system + 1;
       else
-	ret.systems_per_page_[p] = system - ps.prev_ + tack_onto_the_end;
+	ret.systems_per_page_[p] = system - ps.prev_;
       system = ps.prev_;
     }
+
+  if (extra_systems)
+    {
+      ret.systems_per_page_.back () += extra_systems;
+      ret.demerits_ += BAD_SPACING_PENALTY;
+    }
+  if (extra_pages)
+    {
+      ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY);
+      ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0);
+      ret.demerits_ += BAD_SPACING_PENALTY;
+    }
+
+
   ret.demerits_ += ret.penalty_;
   return ret;
 }
@@ -149,43 +186,66 @@ Page_spacer::resize (vsize page_count)
   max_page_count_ = page_count;
 }
 
+// Carries out one step in the dynamic programming algorithm for putting systems
+// on a fixed number of pages. One call to this routine calculates the best
+// configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that
+// we have previously called calc_subproblem(page-1, k) for every k < LINE.
+//
+// This algorithm is similar to the constrained-breaking algorithm.
 bool
 Page_spacer::calc_subproblem (vsize page, vsize line)
 {
   bool last = line == lines_.size () - 1;
-  Page_spacing space (breaker_->page_height (page + first_page_num_, last));
+  Page_spacing space (breaker_->page_height (page + first_page_num_, last),
+		      breaker_->page_top_space ());
   Page_spacing_node &cur = state_.at (line, page);
   bool ragged = ragged_ || (ragged_last_ && last);
+  int line_count = 0;
 
   for (vsize page_start = line+1; page_start > page && page_start--;)
     {
       Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
 
       space.prepend_system (lines_[page_start]);
-      if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged)))
+
+      // This 'if' statement is a little hard to parse. It won't consider this configuration
+      // if it is overfull unless the current configuration is the first one with this start
+      // point. We also make an exception (and consider this configuration) if the previous
+      // configuration we tried had fewer lines than min-systems-per-page.
+      if (!breaker_->too_few_lines (line_count)
+	  && page_start < line
+	  && (isinf (space.force_) || (space.force_ < 0 && ragged)))
 	break;
 
+      line_count += lines_[page_start].compressed_nontitle_lines_count_;
       if (page > 0 || page_start == 0)
 	{
-	  if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0)
+	  // If the last page is ragged, set its force to zero. This way, we will leave
+	  // the last page half-empty rather than trying to balance things out
+	  // (which only makes sense in non-ragged situations).
+	  if (line == lines_.size () - 1 && ragged && last && space.force_ > 0)
 	    space.force_ = 0;
 
-	  /* we may have to deal with single lines that are taller than a page */
+	  Real demerits = space.force_ * space.force_;
+	  /* If a single line is taller than a page, we need to consider it as
+	     a possible solution (but we give it a very bad score). */
 	  if (isinf (space.force_) && page_start == line)
-	    space.force_ = -200000;
+	    demerits = BAD_SPACING_PENALTY;
+	  demerits += (prev ? prev->demerits_ : 0);
 
-	  Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0);
-	  Real penalty = 0;
+	  Real penalty = breaker_->line_count_penalty (line_count);
 	  if (page_start > 0)
-	    penalty = lines_[page_start-1].page_penalty_
+	    penalty += lines_[page_start-1].page_penalty_
 	      + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0;
 
-	  dem += penalty;
-	  if (dem < cur.demerits_ || page_start == line)
+	  demerits += penalty;
+	  if (demerits < cur.demerits_ || page_start == line)
 	    {
-	      cur.demerits_ = dem;
+	      cur.demerits_ = demerits;
 	      cur.force_ = space.force_;
 	      cur.penalty_ = penalty + (prev ? prev->penalty_ : 0);
+	      cur.system_count_status_ = breaker_->line_count_status (line_count)
+		| (prev ? prev->system_count_status_ : 0);
 	      cur.prev_ = page_start - 1;
 	    }
 	}