lily/optimal-page-breaking.cc

   1 /*
   2   optimal-page-breaking.cc -- implement a page-breaker that
   3   will break pages in such a way that both horizontal and
   4   vertical spacing will be acceptable
   5
   6   source file of the GNU LilyPond music typesetter
   7
   8   (c) 2006 Joe Neeman <joeneeman@gmail.com>
   9 */
  10
  11 #include "optimal-page-breaking.hh"
  12 #include "output-def.hh"
  13 #include "page-spacing.hh"
  14 #include "paper-book.hh"
  15 #include "paper-score.hh"
  16 #include "prob.hh"
  17 #include "system.hh"
  18
  19 static bool
  20 is_break (Grob *g)
  21 {
  22   (void) g; /* shutup warning */
  23   return false;
  24 }
  25
  26 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
  27   : Page_breaking (pb, is_break)
  28 {
  29 }
  30
  31 Optimal_page_breaking::~Optimal_page_breaking ()
  32 {
  33 }
  34
  35 Spacing_result
  36 Optimal_page_breaking::try_page_spacing (Line_division const &line_count)
  37 {
  38   vector<Line_details> lines = line_details (0, breaks_.size () - 1, line_count);
  39   Real page_h = page_height (1, false); // FIXME
  40   SCM force_sym = ly_symbol2scm ("blank-last-page-force");
  41   Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
  42   bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
  43   bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
  44   Spacing_result ret = space_systems_on_best_pages (lines,
  45                                                     page_h,
  46                                                     blank_force,
  47                                                     ragged_all,
  48                                                     ragged_last);
  49
  50   /* add in the line penalties */
  51   Real line_force = 0;
  52   Real line_penalty = 0;
  53   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
  54
  55   for (vsize i = 0; i < lines.size (); i++)
  56     {
  57       line_force += lines[i].force_ * lines[i].force_;
  58       line_penalty += lines[i].break_penalty_;
  59     }
  60
  61   ret.demerits_ = ret.force_[0] * ret.force_[0] * page_weighting;
  62   for (vsize i = 1; i < ret.force_.size (); i++)
  63     {
  64       Real uniformity = fabs (ret.force_[i] - ret.force_[i-1]);
  65       ret.demerits_ += (ret.force_[i] * ret.force_[i]
  66                         + uniformity * uniformity) * page_weighting;
  67     }
  68
  69   /* for a while we tried averaging page and line forces instead of summing
  70      them, but it caused the following problem. If there is a single page
  71      with a very bad page force (for example because of a forced page break),
  72      the page breaker will put in a _lot_ of pages so that the bad force
  73      becomes averaged out over many pages. */
  74   ret.demerits_ += line_force + line_penalty;
  75   return ret;
  76 }
  77
  78 SCM
  79 Optimal_page_breaking::solve ()
  80 {
  81   vsize end = breaks_.size () - 1;
  82   vsize min_sys_count = min_system_count (0, end);
  83   vsize max_sys_count = max_system_count (0, end);
  84   vsize max_page_count = INT_MAX;
  85   vsize cur_page_count = 0;
  86   Spacing_result best;
  87   Line_division best_division;
  88   Line_division lower_bound;
  89
  90   for (vsize sys_count = min_sys_count;
  91        cur_page_count <= max_page_count && sys_count <= max_sys_count;
  92        sys_count++)
  93     {
  94       Real this_best_demerits = infinity_f;
  95       vector<Line_division> div = line_divisions (0, end, sys_count, lower_bound);
  96       for (vsize d = 0; d < div.size (); d++)
  97         {
  98           Spacing_result cur = try_page_spacing (div[d]);
  99           cur_page_count = cur.systems_per_page_.size ();
 100           if (cur.demerits_ < best.demerits_ || isinf (best.demerits_))
 101             {
 102               best = cur;
 103               best_division = div[d];
 104             }
 105
 106           if (cur.demerits_ < this_best_demerits || isinf (best.demerits_))
 107             {
 108               this_best_demerits = cur.demerits_;
 109               lower_bound = div[d];
 110             }
 111
 112           vector<Line_details> det = line_details (0, end, div[d]);
 113           bool all_lines_stretched = true;
 114           for (vsize i = 0; i < det.size (); i++)
 115             if (det[i].force_ < 0)
 116               all_lines_stretched = false;
 117
 118           if (all_lines_stretched)
 119             max_page_count = min (max_page_count, cur_page_count + 1);
 120         }
 121     }
 122
 123   break_into_pieces (0, end, best_division);
 124   SCM lines = systems ();
 125   return make_pages (best.systems_per_page_, lines);
 126 }
 127