New page breaking function: ly:minimal-breaking, which first computes

line breaks without considering page breaking, then fills pages with
as many lines as possible.

11 files changed, 239 insertions, 7 deletions

diff --git a/Documentation/topdocs/NEWS.tely b/Documentation/topdocs/NEWS.tely
index be96ec757d..e882827a9d 100644
--- a/Documentation/topdocs/NEWS.tely
+++ b/Documentation/topdocs/NEWS.tely
@@ -66,6 +66,10 @@ which scares away people.
 @end ignore
 
 @item
+A new page breaking function, @code{ly:minimal-breaking}, is dedicated
+to books with many pages or a lot of texts.
+
+@item
 A table of contents is included using @code{\markuplines \table-of-contents}.
 Elements are added to it using the @code{\tocItem} command.
 
diff --git a/Documentation/user/spacing.itely b/Documentation/user/spacing.itely
index 371c42214c..ca9bb618c5 100644
--- a/Documentation/user/spacing.itely
+++ b/Documentation/user/spacing.itely
@@ -557,6 +557,7 @@ The pairs
 * Page breaking::               
 * Optimal page breaking::       
 * Optimal page turning::        
+* Minimal page breaking::        
 * Explicit breaks::             
 * Using an extra voice for breaks::  
 @end menu
@@ -655,11 +656,11 @@ a line break.
 The @code{\pageBreak} and @code{\noPageBreak} commands may also be
 inserted at top-level, between scores and top-level markups.
 
-Page breaks are computed by the @code{page-breaking} function.
-LilyPond provides two algorithms for computing page
-breaks, @code{ly:optimal-breaking} and @code{ly:page-turn-breaking}. The
-default is @code{ly:optimal-breaking}, but the value can be changed in
-the @code{\paper} block:
+Page breaks are computed by the @code{page-breaking} function.  LilyPond
+provides three algorithms for computing page breaks,
+@code{ly:optimal-breaking}, @code{ly:page-turn-breaking} and
+@code{ly:minimal-breaking}. The default is @code{ly:optimal-breaking},
+but the value can be changed in the @code{\paper} block:
 
 @example
 \paper@{
@@ -769,6 +770,22 @@ top-level markups.
 There should only be one @code{Page_turn_engraver} in a score. If there is more
 than one, they will interfere with each other.
 
+@node Minimal page breaking
+@subsection Minimal page breaking
+
+@funindex ly:minimal-breaking
+
+The @code{ly:minimal-breaking} function performs minimal computations to
+calculate the page breaking: it fills a page with as many systems as
+possible before moving to the next one.  Thus, it may be prefered for
+scores with many pages, where the other page breaking functions could be
+too slow or memory demanding, or a lot of texts.  It is enabled using:
+
+@example
+\paper @{
+  #(define page-breaking ly:minimal-breaking)
+@}
+@end example
 
 @node Explicit breaks
 @subsection Explicit breaks
@@ -906,7 +923,7 @@ staves inside a system.
 * Vertical spacing inside a system::  
 * Vertical spacing between systems::  
 * Explicit staff and system positioning::  
-* Two-pass vertical spacing::
+* Two-pass vertical spacing::   
 * Vertical collision avoidance::  
 @end menu
 
diff --git a/input/regression/page-minimal-page-breaking-last-page.ly b/input/regression/page-minimal-page-breaking-last-page.ly
new file mode 100644
index 0000000000..796db12854
--- /dev/null
+++ b/input/regression/page-minimal-page-breaking-last-page.ly
@@ -0,0 +1,23 @@
+\version "2.11.27"
+#(set-default-paper-size "a6")
+
+\header {
+  texidoc = "Minimal page breaker: special case when the last system is moved
+to an other page when there is not enough space because of the tagline."
+}
+
+textBox = \markup \fill-line { \override #'(box-padding . 13) \box Text }
+
+\book {
+  \header {
+    tagline = \markup \fill-line { \override #'(box-padding . 5) \box Tagline }
+  }
+  \paper {
+    #(define page-breaking ly:minimal-breaking) 
+  }
+
+  \markup \textBox
+  \markup \textBox
+  \markup \textBox
+  \markup \textBox
+}
\ No newline at end of file
diff --git a/input/regression/page-minimal-page-breaking.ly b/input/regression/page-minimal-page-breaking.ly
new file mode 100644
index 0000000000..0ff288a02b
--- /dev/null
+++ b/input/regression/page-minimal-page-breaking.ly
@@ -0,0 +1,35 @@
+\version "2.11.27"
+#(set-default-paper-size "a6")
+
+\header {
+  texidoc = "The minimal page breaker stacks as many lines on pages,
+only accounting for manual page break commands."
+}
+
+\book {
+  \paper { #(define page-breaking ly:minimal-breaking) }
+  
+  \score {
+    <<
+      \new Staff \repeat unfold 12 { c'4 }
+      \new Staff \repeat unfold 12 { c'4 }
+      \new Staff { \repeat unfold 11 { c'4 } c'_\markup \right-align "\\pageBreak" }
+    >>
+  }
+  \pageBreak
+  \score {
+    <<
+      \new Staff \repeat unfold 24 { e'4 }
+      \new Staff \repeat unfold 24 { e'4 }
+      \new Staff { \repeat unfold 23 { e'4 } e'_\markup \right-align "\\noPageBreak" }
+    >>
+  }
+  \noPageBreak
+  \score {
+    <<
+      \new Staff \repeat unfold 12 { g'4 }
+      \new Staff \repeat unfold 12 { g'4 }
+      \new Staff \repeat unfold 12 { g'4 }
+    >>
+  }
+}
\ No newline at end of file
diff --git a/lily/include/minimal-page-breaking.hh b/lily/include/minimal-page-breaking.hh
new file mode 100644
index 0000000000..b57ab8b607
--- /dev/null
+++ b/lily/include/minimal-page-breaking.hh
@@ -0,0 +1,26 @@
+/*
+  minimal-page-breaking.hh -- declare a page-breaker that stacks as
+  many systems on a page before moving to the next one. Specialized
+  for books with many pages, or a lot of text.
+
+  source file of the GNU LilyPond music typesetter
+
+  (c) 2007 Nicolas Sceaux <nicolas.sceaux@free.fr>
+*/
+
+#ifndef MINIMAL_PAGE_BREAKING_HH
+#define MINIMAL_PAGE_BREAKING_HH
+
+#include "page-breaking.hh"
+#include "page-spacing.hh"
+
+class Minimal_page_breaking: public Page_breaking
+{
+public:
+  virtual SCM solve ();
+
+  Minimal_page_breaking (Paper_book *pb);
+  virtual ~Minimal_page_breaking ();
+};
+
+#endif /* MINIMAL_PAGE_BREAKING_HH */
diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh
index 082384d0fe..52a95812c4 100644
--- a/lily/include/page-breaking.hh
+++ b/lily/include/page-breaking.hh
@@ -131,6 +131,8 @@ protected:
 						       vsize first_page_num);
   Page_spacing_result space_systems_on_best_pages (vsize configuration_index,
 					      vsize first_page_num);
+  Page_spacing_result pack_systems_on_least_pages (vsize configuration_index,
+						   vsize first_page_num);
   vsize min_page_count (vsize configuration_index, vsize first_page_num);
   bool all_lines_stretched (vsize configuration_index);
   Real blank_page_penalty () const;
diff --git a/lily/include/page-spacing.hh b/lily/include/page-spacing.hh
index ba05a4de9d..9bb37804a7 100644
--- a/lily/include/page-spacing.hh
+++ b/lily/include/page-spacing.hh
@@ -71,7 +71,7 @@ struct Page_spacing
   }
 
   void calc_force ();
-
+  void resize (Real new_height);
   void append_system (const Line_details &line);
   void prepend_system (const Line_details &line);
   void clear ();
diff --git a/lily/minimal-page-breaking.cc b/lily/minimal-page-breaking.cc
new file mode 100644
index 0000000000..870340f83d
--- /dev/null
+++ b/lily/minimal-page-breaking.cc
@@ -0,0 +1,47 @@
+/*
+  minimal-page-breaking.cc -- implement a page-breaker that stacks as
+  many systems on a page before moving to the next one. Specialized
+  for books with many pages, or a lot of text.
+
+  source file of the GNU LilyPond music typesetter
+
+  (c) 2007 Nicolas Sceaux <nicolas.sceaux@free.fr>
+*/
+
+#include "international.hh"
+#include "minimal-page-breaking.hh"
+#include "output-def.hh"
+#include "page-spacing.hh"
+#include "paper-book.hh"
+
+static bool
+is_break (Grob *g)
+{
+  (void) g; /* shutup warning */
+  return false;
+}
+
+Minimal_page_breaking::Minimal_page_breaking (Paper_book *pb)
+  : Page_breaking (pb, is_break)
+{
+}
+
+Minimal_page_breaking::~Minimal_page_breaking ()
+{
+}
+
+SCM
+Minimal_page_breaking::solve ()
+{
+  vsize end = last_break_position ();
+
+  message ("Computing line breaks...");
+  set_to_ideal_line_configuration (0, end);
+  break_into_pieces (0, end, current_configuration (0));
+
+  message (_ ("Computing page breaks..."));
+  vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
+  Page_spacing_result res = pack_systems_on_least_pages (0, first_page_num);
+  SCM lines = systems ();
+  return make_pages (res.systems_per_page_, lines);
+}
diff --git a/lily/page-breaking-scheme.cc b/lily/page-breaking-scheme.cc
index 2241b503a7..d9f9df152a 100644
--- a/lily/page-breaking-scheme.cc
+++ b/lily/page-breaking-scheme.cc
@@ -10,6 +10,7 @@
 #include "paper-book.hh"
 #include "page-turn-page-breaking.hh"
 #include "optimal-page-breaking.hh"
+#include "minimal-page-breaking.hh"
 
 LY_DEFINE (ly_page_turn_breaking, "ly:page-turn-breaking",
 	   1, 0, 0, (SCM pb),
@@ -30,3 +31,13 @@ LY_DEFINE (ly_optimal_breaking, "ly:optimal-breaking",
   Optimal_page_breaking b (unsmob_paper_book (pb));
   return b.solve ();
 }
+
+LY_DEFINE (ly_minimal_breaking, "ly:minimal-breaking",
+	   1, 0, 0, (SCM pb),
+	   "Break (pages and lines) the @code{Paper_book} object @var{pb}"
+	   "without looking for optimal spacing: stack as many lines on"
+	   "a page before moving to the next one.")
+{
+  Minimal_page_breaking b (unsmob_paper_book (pb));
+  return b.solve ();
+}
diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc
index 9ad833610a..b6951925ad 100644
--- a/lily/page-breaking.cc
+++ b/lily/page-breaking.cc
@@ -526,6 +526,7 @@ Page_breaking::cache_line_details (vsize configuration_index)
 {
   if (cached_configuration_index_ != configuration_index)
     {
+      cached_configuration_index_ = configuration_index;
       SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
       if (!scm_is_number (padding_scm))
 	padding_scm = book_->paper_->c_variable ("between-system-padding");
@@ -758,6 +759,65 @@ Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_pag
   return finalize_spacing_result (configuration, best);
 }
 
+Page_spacing_result
+Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
+{
+  Page_spacing_result res;
+  vsize page = 0;
+  vsize page_first_line = 0;
+  Page_spacing space (page_height (first_page_num, false));
+
+  cache_line_details (configuration);
+  for (vsize line = 0; line < cached_line_details_.size (); line++)
+    {
+      Real prev_force = space.force_;
+      space.append_system (cached_line_details_[line]);
+      if ((line > page_first_line)
+	  && (isinf (space.force_)
+	      || ((line > 0)
+                  && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
+	{
+	  res.systems_per_page_.push_back (line - page_first_line);
+	  res.force_.push_back (prev_force);
+          res.penalty_ += cached_line_details_[line-1].page_penalty_;
+	  page++;
+	  space.resize (page_height (first_page_num + page, false));
+	  space.clear ();
+          space.append_system (cached_line_details_[line]);
+	  page_first_line = line;
+	}
+
+      if (line == cached_line_details_.size () - 1)
+	{
+	  /* This is the last line */
+	  /* When the last page height was computed, we did not know yet that it
+	   * was the last one. If the systems put on it don't fit anymore, the last
+	   * system is moved to a new page */
+	  space.resize (page_height (first_page_num + page, true));
+	  if ((line > page_first_line) && (isinf (space.force_)))
+	    {
+	      res.systems_per_page_.push_back (line - page_first_line);
+	      res.force_.push_back (prev_force);
+	      /* the last page containing the last line */
+	      space.resize (page_height (first_page_num + page + 1, true));
+	      space.clear ();
+	      space.append_system (cached_line_details_[line]);
+	      res.systems_per_page_.push_back (1);
+	      res.force_.push_back (space.force_);
+              res.penalty_ += cached_line_details_[line-1].page_penalty_;
+              res.penalty_ += cached_line_details_[line].page_penalty_;
+	    }
+	  else
+	    {
+	      res.systems_per_page_.push_back (line + 1 - page_first_line);
+	      res.force_.push_back (space.force_);
+              res.penalty_ += cached_line_details_[line].page_penalty_;
+	    }
+	}
+    }
+  return finalize_spacing_result (configuration, res);
+}
+
 /* Calculate demerits and fix res.systems_per_page_ so that
    it refers to the original line numbers, not the ones given by compress_lines (). */
 Page_spacing_result
diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc
index fa1c273f37..82a037bde5 100644
--- a/lily/page-spacing.cc
+++ b/lily/page-spacing.cc
@@ -24,6 +24,13 @@ Page_spacing::calc_force ()
 }
 
 void
+Page_spacing::resize (Real new_height)
+{
+  page_height_ = new_height;
+  calc_force ();
+}
+
+void
 Page_spacing::append_system (const Line_details &line)
 {
   rod_height_ += last_line_.padding_;