lily/optimal-page-breaking.cc

   1 /*
   2   optimal-page-breaking.hh -- 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 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
  20   : Page_breaking (pb, false)
  21 {
  22 }
  23
  24 Optimal_page_breaking::~Optimal_page_breaking ()
  25 {
  26 }
  27
  28 Spacing_result
  29 Optimal_page_breaking::try_page_spacing (vector<vsize> line_count)
  30 {
  31   vector<Line_details> lines = get_line_details (0, breaks_.size () - 1, line_count);
  32   Real page_h = page_height (1, false); // FIXME
  33   SCM force_sym = ly_symbol2scm ("blank-last-page-force");
  34   Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0);
  35   Spacing_result ret = space_systems_on_best_pages (lines, page_h, blank_force);
  36
  37   bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
  38   bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
  39
  40   /* add in the line penalties */
  41   Real line_force = 0;
  42   Real line_penalty = 0;
  43   Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1);
  44
  45   for (vsize i = 0; i < lines.size (); i++)
  46     {
  47       line_force += fabs (lines[i].force_);
  48       line_penalty += lines[i].break_penalty_;
  49     }
  50
  51   if (ragged_all)
  52     for (vsize i = 0; i < ret.force_.size () - 1; i++)
  53       ret.force_[i] = min (0.0, ret.force_[i]);
  54   if (ragged_all || ragged_last)
  55     ret.force_.back () = min (0.0, ret.force_.back ());
  56
  57   ret.demerits_ = ret.force_[0] * ret.force_[0] * page_weighting;
  58   for (vsize i = 1; i < ret.force_.size (); i++)
  59     {
  60       Real uniformity = fabs (ret.force_[i] - ret.force_[i-1]);
  61       ret.demerits_ += (ret.force_[i] * ret.force_[i]
  62                        + uniformity * uniformity) * page_weighting;
  63     }
  64   ret.demerits_ += line_force + line_penalty;
  65   return ret;
  66 }
  67
  68 /* The algorithm is as follows:
  69    1) break everything into its preferred number of lines
  70    2) decrease the number of lines until we've decreased
  71       the number of pages
  72    3) increase the number of lines until we've increased
  73       the number of pages
  74    Take the best score we've found
  75 */
  76 SCM
  77 Optimal_page_breaking::solve ()
  78 {
  79   vector<vsize> ideal_line_count;
  80   vector<vsize> max_line_count;
  81   vector<vsize> min_line_count;
  82   vector<vsize> last_best_line_count;
  83   vector<vsize> best_line_count;
  84   vsize last_line_total = 0;
  85
  86   calc_system_count_bounds (0, breaks_.size () - 1, &min_line_count, &max_line_count);
  87   ideal_line_count.resize (all_.size (), 1);
  88   for (vsize i = 0; i < all_.size (); i++)
  89     {
  90       if (all_[i].pscore_)
  91         ideal_line_count[i] = line_breaking_[i].get_best_solution (0, VPOS).size ();
  92       last_line_total += ideal_line_count[i];
  93     }
  94
  95   Spacing_result best_result = try_page_spacing (ideal_line_count);
  96   vsize original_page_count = best_result.systems_per_page_.size ();
  97   best_line_count = ideal_line_count;
  98   last_best_line_count = ideal_line_count;
  99
 100   Direction d = original_page_count > 1 ? DOWN : UP;
 101   vector<vector<vsize> > div;
 102   Spacing_result this_best_result;
 103   do {
 104     do {
 105       vector<vsize> blank;
 106
 107       vector<vsize> this_best_line_count;
 108       this_best_result.demerits_ = infinity_f;
 109
 110       last_line_total += d;
 111       div.clear ();
 112       divide_systems (last_line_total,
 113                       d == DOWN ? min_line_count       : last_best_line_count,
 114                       d == DOWN ? last_best_line_count : max_line_count,
 115                       &div, &blank);
 116
 117       for (vsize i = 0; i < div.size (); i++)
 118         {
 119           Spacing_result cur = try_page_spacing (div[i]);
 120           if (cur.demerits_ < this_best_result.demerits_)
 121             {
 122               this_best_result = cur;
 123               this_best_line_count = div[i];
 124             }
 125         }
 126       last_best_line_count = this_best_line_count;
 127
 128       if (this_best_result.demerits_ < best_result.demerits_)
 129         {
 130           best_line_count = this_best_line_count;
 131           best_result = this_best_result;
 132         }
 133     } while (div.size () && this_best_result.systems_per_page_.size () == original_page_count);
 134
 135     /* we're finished decreasing system count, let's try raising it */
 136     last_best_line_count = ideal_line_count;
 137     last_line_total = 0;
 138     for (vsize i = 0; i < ideal_line_count.size (); i++)
 139       last_line_total += ideal_line_count[i];
 140
 141   } while (flip (&d) != DOWN);
 142
 143   SCM lines = make_lines (best_line_count);
 144   SCM pages = make_pages (best_result.systems_per_page_, lines);
 145   return pages;
 146 }
 147
 148 SCM
 149 Optimal_page_breaking::make_lines (vector<vsize> line_count)
 150 {
 151   assert (line_count.size () == all_.size ());
 152
 153   SCM ret = SCM_EOL;
 154   for (vsize i = 0; i < all_.size (); i++)
 155     {
 156       if (all_[i].pscore_)
 157         {
 158           vector<Column_x_positions> line_brk = line_breaking_[i].get_solution (0, VPOS, line_count[i]);
 159           System *sys = all_[i].pscore_->root_system ();
 160
 161           sys->break_into_pieces (line_brk);
 162           ret = scm_append (scm_list_2 (ret, scm_vector_to_list (sys->get_paper_systems ())));
 163         }
 164       else
 165         {
 166           SCM l = scm_cons (all_[i].prob_->self_scm (), SCM_EOL);
 167           ret = scm_append (scm_list_2 (ret, l));
 168           all_[i].prob_->unprotect ();
 169         }
 170     }
 171   return ret;
 172 }