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   /* If ragged_last is true, the last page will have
  70      zero force no matter what. In this case, we exclude it from the average or
  71      we will become biased towards scores with less pages (because the force
  72      of zero will affect the average more when there are fewer pages) */
  73   if (!ragged_last || ret.force_.size () > 1)
  74     ret.demerits_ /= ret.force_.size () - (ragged_last ? 1 : 0);
  75   line_force /= lines.size ();
  76   ret.demerits_ += line_force + line_penalty;
  77   return ret;
  78 }
  79
  80 SCM
  81 Optimal_page_breaking::solve ()
  82 {
  83   vsize end = breaks_.size () - 1;
  84   vsize min_sys_count = min_system_count (0, end);
  85   vsize max_sys_count = max_system_count (0, end);
  86   vsize max_page_count = INT_MAX;
  87   vsize cur_page_count = 0;
  88   Spacing_result best;
  89   Line_division best_division;
  90   Line_division lower_bound;
  91
  92   for (vsize sys_count = min_sys_count;
  93        cur_page_count <= max_page_count && sys_count <= max_sys_count;
  94        sys_count++)
  95     {
  96       Real this_best_demerits = infinity_f;
  97       vector<Line_division> div = line_divisions (0, end, sys_count, lower_bound);
  98       for (vsize d = 0; d < div.size (); d++)
  99         {
 100           Spacing_result cur = try_page_spacing (div[d]);
 101           cur_page_count = cur.systems_per_page_.size ();
 102           if (cur.demerits_ < best.demerits_ || isinf (best.demerits_))
 103             {
 104               best = cur;
 105               best_division = div[d];
 106             }
 107
 108           if (cur.demerits_ < this_best_demerits || isinf (best.demerits_))
 109             {
 110               this_best_demerits = cur.demerits_;
 111               lower_bound = div[d];
 112             }
 113
 114           vector<Line_details> det = line_details (0, end, div[d]);
 115           bool all_lines_stretched = true;
 116           for (vsize i = 0; i < det.size (); i++)
 117             if (det[i].force_ < 0)
 118               all_lines_stretched = false;
 119
 120           if (all_lines_stretched)
 121             max_page_count = min (max_page_count, cur_page_count + 1);
 122         }
 123     }
 124
 125   break_into_pieces (0, end, best_division);
 126   SCM lines = systems ();
 127   return make_pages (best.systems_per_page_, lines);
 128 }
 129