Optimizations for optimal-page-breaking.

Introduce a new page-spacing routine that doesn't constrain the
number of pages.  This makes space_system_on_best_pages much
faster, and it could also be used in other parts of
Optimal_page_breaking::solve.

diff --git a/lily/include/page-spacing.hh b/lily/include/page-spacing.hh
index b670387ad691a1375c7002633d2832ace33dded2..f57060a647cde67ec15f6eb39e2cfceb16d210d8 100644 (file)
--- a/lily/include/page-spacing.hh
+++ b/lily/include/page-spacing.hh
@@ -53,6 +53,7 @@ class Page_spacer
 public:
   Page_spacer (vector<Line_details> const &lines, vsize first_page_num, Page_breaking const*);
   Page_spacing_result solve (vsize page_count);
+  Page_spacing_result solve ();
 
 private:
   struct Page_spacing_node
@@ -64,19 +65,27 @@ private:
       penalty_ = infinity_f;
       prev_ = VPOS;
       system_count_status_ = SYSTEM_COUNT_OK;
+      page_ = 0;
     }
 
     Real demerits_;
     Real force_;
     Real penalty_;
     vsize prev_;
+    vsize page_;
     int system_count_status_;
   };
 
   Page_breaking const *breaker_;
   vsize first_page_num_;
   vector<Line_details> lines_;
+
+  // If a page-count is requested, we use state_, which
+  // is indexed by page*system, for our dynamic programming
+  // intermediate storage.  Otherwise, we use simple_state_,
+  // which is indexed only by system.
   Matrix<Page_spacing_node> state_;
+  vector<Page_spacing_node> simple_state_;
   vsize max_page_count_;
 
   bool ragged_;

diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc
index 4c7c40763ebe942d7131d7df91af7d335a10775b..d22e999a7f1c0e11aa03cc1340f5eba7da880278 100644 (file)
--- a/lily/page-breaking.cc
+++ b/lily/page-breaking.cc
@@ -802,6 +802,7 @@ Page_breaking::cache_line_details (vsize configuration_index)
            }
        }
       cached_line_details_ = compress_lines (uncompressed_line_details_);
+      compute_line_heights ();
     }
 }
 
@@ -904,7 +905,6 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
   int line_count = 0;
 
   cache_line_details (configuration);
-  compute_line_heights ();
 
   if (cached_line_details_.size ())
     cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
@@ -1088,21 +1088,10 @@ Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize
 Page_spacing_result
 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
 {
-  vsize min_p_count = min_page_count (configuration, first_page_num);
-
   cache_line_details (configuration);
   Page_spacer ps (cached_line_details_, first_page_num, this);
-  Page_spacing_result best = ps.solve (min_p_count);
-
-  for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
-    {
-      Page_spacing_result cur = ps.solve (i);
-      if (cur.demerits_ < best.demerits_)
-       best = cur;
-    }
 
-  Page_spacing_result ret = finalize_spacing_result (configuration, best);
-  return ret;
+  return finalize_spacing_result (configuration, ps.solve ());
 }
 
 Page_spacing_result
@@ -1166,7 +1155,6 @@ Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_pag
   Page_spacing space (page_height (first_page_num, false), this);
 
   cache_line_details (configuration);
-  compute_line_heights ();
   for (vsize line = 0; line < cached_line_details_.size (); line++)
     {
       Real prev_force = space.force_;

diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc
index 33cf18a3fe8a64f52821229f96a3bd73e407ab1c..1a3c39cfbf709d88de4725c6238fe8636141eb15 100644 (file)
--- a/lily/page-spacing.cc
+++ b/lily/page-spacing.cc
@@ -100,6 +100,34 @@ Page_spacer::Page_spacer (vector<Line_details> const &lines, vsize first_page_nu
   ragged_last_ = breaker->is_last () && breaker->ragged_last ();
 }
 
+Page_spacing_result
+Page_spacer::solve ()
+{
+  if (simple_state_.empty ())
+    {
+      simple_state_.resize (lines_.size ());
+      for (vsize i = 0; i < lines_.size (); ++i)
+       calc_subproblem (VPOS, i);
+    }
+
+  Page_spacing_result ret;
+  vsize system = lines_.size () - 1;
+  while (system != VPOS)
+    {
+      Page_spacing_node const& cur = simple_state_[system];
+      vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_;
+
+      ret.force_.push_back (cur.force_);
+      ret.systems_per_page_.push_back (system_count);
+      ret.demerits_ += cur.force_ * cur.force_;
+      system = cur.prev_;
+    }
+
+  reverse (ret.force_);
+  reverse (ret.systems_per_page_);
+  return ret;
+}
+
 Page_spacing_result
 Page_spacer::solve (vsize page_count)
 {
@@ -203,19 +231,44 @@ Page_spacer::resize (vsize page_count)
 // we have previously called calc_subproblem(page-1, k) for every k < LINE.
 //
 // This algorithm is similar to the constrained-breaking algorithm.
+//
+// If page == VPOS, we act on simple_state_ instead of state_.  This is useful if
+// we don't want to constrain the number of pages that the solution has.  In this
+// case, the algorithm looks more like the page-turn-page-breaking algorithm.  But
+// the subproblems look similar for both, so we reuse this method.
 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),
+
+  // Note: if page == VPOS then we don't actually know yet which page number we're
+  // working on, so we have to recalculate the page height in the loop.  In that case,
+  // the algorithm may not be optimal: if our page has a very large header then perhaps
+  // we need to look ahead a few systems in order to find the best solution.  But
+  // we won't, because we stop once we overfill the page with the large header.
+  vsize page_num = page == VPOS ? 0 : page;
+  Page_spacing space (breaker_->page_height (page_num + first_page_num_, last),
                      breaker_);
-  Page_spacing_node &cur = state_.at (line, page);
+  Page_spacing_node &cur = page == VPOS ? simple_state_[line] : 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--;)
+  for (vsize page_start = line+1; page_start > page_num && page_start--;)
     {
-      Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0;
+      Page_spacing_node const *prev = 0;
+
+      if (page == VPOS)
+       {
+         if (page_start > 0)
+           {
+             prev = &simple_state_[page_start-1];
+             space.resize (breaker_->page_height (prev->page_ + 1, last));
+           }
+         else
+           space.resize (breaker_->page_height (first_page_num_, last));
+       }
+      else if (page > 0)
+       prev = &state_.at (page_start-1, page-1);
 
       space.prepend_system (lines_[page_start]);
 
@@ -270,6 +323,7 @@ Page_spacer::calc_subproblem (vsize page, vsize line)
              cur.system_count_status_ = breaker_->line_count_status (line_count)
                | (prev ? prev->system_count_status_ : 0);
              cur.prev_ = page_start - 1;
+             cur.page_ = prev ? prev->page_ + 1 : first_page_num_;
            }
        }