Re: dumb stacking page breaker

[Nicolas Sceaux]

Nicolas Sceaux <address@hidden> writes:

> When building scores >>20 pages (some of my scores have more than 150),
> the time and amount of memory used by the ly:optimal-page-breaking
> function is crippling (it also used to be the case with the original
> optimal page breaking function).
>
> [...]
>
>  1) compute the line breaks in the most straightforward way, that is
>     without considering page breaks or the number of systems per page.
>     Just lines as regular as possible wrt horizontal spacing and
>     considering the manual line break permissions.
>
>  2) compute the page breaks by stacking on each page as many lines as
>     possible, and account for manual page break permissions.

Joe,

Here is a patch where a stacking-page-breaking function is
implemented. May you review it, and tell me if there is something wrong
or some bad coding, before I go on with documentation and regression
tests? The first tests I have made so far are satisfying. (Also
suggestions for a better name are welcome:)

nicolas

diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh
index 082384d..98ed808 100644
--- a/lily/include/page-breaking.hh
+++ b/lily/include/page-breaking.hh
@@ -116,6 +116,11 @@ protected:
   void break_into_pieces (vsize start, vsize end, Line_division const &div);
   SCM systems ();
 
+  vector<Line_details> get_uncompressed_lines (Page_breaking::Line_division 
const &div);
+  static vector<Line_details> compress_lines (const vector<Line_details> 
&orig);
+  static vector<vsize> uncompress_solution (vector<vsize> const 
&systems_per_page,
+                                            vector<Line_details> const 
&compressed);
+  
   void set_current_breakpoints (vsize start,
                                vsize end,
                                vsize system_count,
diff --git a/lily/include/stacking-page-breaking.hh 
b/lily/include/stacking-page-breaking.hh
new file mode 100644
index 0000000..61b2b36
--- /dev/null
+++ b/lily/include/stacking-page-breaking.hh
@@ -0,0 +1,30 @@
+/*
+  stacking-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 <address@hidden>
+*/
+
+#ifndef STACKING_PAGE_BREAKING_HH
+#define STACKING_PAGE_BREAKING_HH
+
+#include "page-breaking.hh"
+#include "page-spacing.hh"
+
+class Stacking_page_breaking: public Page_breaking
+{
+public:
+  virtual SCM solve ();
+
+  Stacking_page_breaking (Paper_book *pb);
+  virtual ~Stacking_page_breaking ();
+
+protected:
+  vector<vsize> compute_page_breaks (vector<Line_details> const &lines,
+                                     int first_page_num);
+};
+
+#endif /* STACKING_PAGE_BREAKING_HH */
diff --git a/lily/page-breaking-scheme.cc b/lily/page-breaking-scheme.cc
index 2241b50..0a86744 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 "stacking-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:opti
   Optimal_page_breaking b (unsmob_paper_book (pb));
   return b.solve ();
 }
+
+LY_DEFINE (ly_stacking_breaking, "ly:stacking-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.")
+{
+  Stacking_page_breaking b (unsmob_paper_book (pb));
+  return b.solve ();
+}
diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc
index 9ad8336..9b6f3a2 100644
--- a/lily/page-breaking.cc
+++ b/lily/page-breaking.cc
@@ -21,8 +21,8 @@
 
 /* for each forbidden page break, merge the systems around it into one
    system. */
-static vector<Line_details>
-compress_lines (const vector<Line_details> &orig)
+vector<Line_details>
+Page_breaking::compress_lines (const vector<Line_details> &orig)
 {
   vector<Line_details> ret;
 
@@ -56,9 +56,9 @@ compress_lines (const vector<Line_detail
 /* translate the number of systems-per-page into something meaningful for
    the uncompressed lines.
 */
-static vector<vsize>
-uncompress_solution (vector<vsize> const &systems_per_page,
-                    vector<Line_details> const &compressed)
+vector<vsize>
+Page_breaking::uncompress_solution (vector<vsize> const &systems_per_page,
+                                    vector<Line_details> const &compressed)
 {
   vector<vsize> ret;
   vsize start_sys = 0;
@@ -521,39 +521,47 @@ Page_breaking::current_configuration_cou
   return current_configurations_.size ();
 }
 
+vector<Line_details>
+Page_breaking::get_uncompressed_lines (Page_breaking::Line_division const &div)
+{
+  vector<Line_details> uncompressed_line_details;
+  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");
+  Real padding = robust_scm2double (padding_scm, 0.0);
+  
+  uncompressed_line_details.clear ();
+  for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
+    {
+      vsize sys = next_system (current_chunks_[i]);
+      if (system_specs_[sys].pscore_)
+       {
+         vsize start;
+         vsize end;
+         line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], 
&start, &end);
+         vector<Line_details> details = line_breaking_[sys].line_details 
(start, end, div[i]);
+         uncompressed_line_details.insert (uncompressed_line_details.end (), 
details.begin (), details.end ());
+       }
+      else
+       {
+         assert (div[i] == 1);
+         uncompressed_line_details.push_back (Line_details 
(system_specs_[sys].prob_));
+         uncompressed_line_details.back ().padding_ =
+           robust_scm2double (system_specs_[sys].prob_->get_property 
("next-padding"),
+                              padding);
+       }
+    }
+  return uncompressed_line_details;
+}
+
 void
 Page_breaking::cache_line_details (vsize configuration_index)
 {
+  /* what is the purpose of cached_configuration_index_? it is never set,
+     save in clear_line_details_cache -- ns */
   if (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");
-      Real padding = robust_scm2double (padding_scm, 0.0);
-
-      Line_division &div = current_configurations_[configuration_index];
-      uncompressed_line_details_.clear ();
-      for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
-       {
-         vsize sys = next_system (current_chunks_[i]);
-         if (system_specs_[sys].pscore_)
-           {
-             vsize start;
-             vsize end;
-             line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], 
&start, &end);
-
-             vector<Line_details> details = line_breaking_[sys].line_details 
(start, end, div[i]);
-             uncompressed_line_details_.insert (uncompressed_line_details_.end 
(), details.begin (), details.end ());
-           }
-         else
-           {
-             assert (div[i] == 1);
-             uncompressed_line_details_.push_back (Line_details 
(system_specs_[sys].prob_));
-             uncompressed_line_details_.back ().padding_ =
-                robust_scm2double (system_specs_[sys].prob_->get_property 
("next-padding"),
-                                   padding);
-           }
-       }
+      uncompressed_line_details_ = get_uncompressed_lines 
(current_configurations_[configuration_index]);
       cached_line_details_ = compress_lines (uncompressed_line_details_);
     }
 }
diff --git a/lily/stacking-page-breaking.cc b/lily/stacking-page-breaking.cc
new file mode 100644
index 0000000..b54702b
--- /dev/null
+++ b/lily/stacking-page-breaking.cc
@@ -0,0 +1,99 @@
+/*
+  stacking-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 <address@hidden>
+*/
+
+#include "international.hh"
+#include "stacking-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;
+}
+
+Stacking_page_breaking::Stacking_page_breaking (Paper_book *pb)
+  : Page_breaking (pb, is_break)
+{
+}
+
+Stacking_page_breaking::~Stacking_page_breaking ()
+{
+}
+
+vector<vsize>
+Stacking_page_breaking::compute_page_breaks (vector<Line_details> const &lines,
+                                             int first_page_num)
+{
+  vector<vsize> systems_per_page;
+  vsize line = 0;
+  vsize page_first_line = 0;
+  for (vsize page = 0 ; line < lines.size () ; page ++)
+    {
+      Page_spacing space (page_height (page + first_page_num, false));
+      page_first_line = line;
+      bool go_to_next_page = false;
+      while ((line < lines.size ()) && !go_to_next_page)
+        {
+          space.append_system (lines [line]);
+          if ((line > page_first_line)
+              && (isinf (space.force_)
+                  || (lines [line].page_permission_ == ly_symbol2scm 
("force"))))
+            {
+              systems_per_page.push_back (line - page_first_line);
+              go_to_next_page = true;
+            }
+          else
+            {
+              if (line == lines.size () - 1)
+                systems_per_page.push_back (line + 1 - page_first_line);
+              line ++;
+            }
+        }
+    }
+  Page_spacing space (page_height (systems_per_page.size () - 1 + 
first_page_num, true));
+  for (line = page_first_line ; line < lines.size () ; line ++)
+    {
+      space.append_system (lines [line]);
+      if ((line > page_first_line) && isinf (space.force_))
+        {
+          /* put this line and the following on another page */
+          systems_per_page.back () = line - page_first_line;
+          systems_per_page.push_back (lines.size () - line);
+          break;
+        }
+    }
+  return systems_per_page;
+}
+
+SCM
+Stacking_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);
+  vector<Line_details> uncompressed_lines = get_uncompressed_lines 
(current_configuration (0));
+  vector<Line_details> compressed_lines = compress_lines (uncompressed_lines);
+  vector<vsize> systems_per_page = compute_page_breaks (compressed_lines, 
first_page_num);
+  systems_per_page = uncompress_solution (systems_per_page, compressed_lines);
+
+  SCM lines = systems ();
+  return make_pages (systems_per_page, lines);
+}
+
+
+