lily/optimal-page-breaking.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2010 Joe Neeman <joeneeman@gmail.com>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "international.hh"
  21 #include "optimal-page-breaking.hh"
  22 #include "output-def.hh"
  23 #include "page-spacing.hh"
  24 #include "paper-book.hh"
  25 #include "paper-score.hh"
  26 #include "prob.hh"
  27 #include "system.hh"
  28
  29 static bool
  30 is_break (Grob *g)
  31 {
  32   return g->get_property ("page-break-permission") == ly_symbol2scm ("force");
  33 }
  34
  35 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
  36   : Page_breaking (pb, is_break)
  37 {
  38 }
  39
  40 Optimal_page_breaking::~Optimal_page_breaking ()
  41 {
  42 }
  43
  44 extern bool debug_page_breaking_scoring;
  45
  46 // Solves the subproblem betwen the (END-1)th \pageBreak and the
  47 // ENDth \pageBreak.
  48 // Returns a vector of systems per page for the pages within this chunk.
  49 vector<vsize>
  50 Optimal_page_breaking::solve_chunk (vsize end, SCM forced_page_count)
  51 {
  52   vsize max_sys_count = max_system_count (end-1, end);
  53   vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
  54
  55   set_to_ideal_line_configuration (end-1, end);
  56
  57   Page_spacing_result best;
  58   vsize page_count = robust_scm2int (forced_page_count, 1);
  59   Line_division ideal_line_division = current_configuration (0);
  60   Line_division best_division = ideal_line_division;
  61   vsize min_sys_count = 1;
  62   vsize ideal_sys_count = system_count ();
  63
  64   if (!scm_is_integer (forced_page_count))
  65     {
  66       if (systems_per_page () > 0)
  67         best = space_systems_with_fixed_number_per_page (0, first_page_num);
  68       else
  69         best = space_systems_on_best_pages (0, first_page_num);
  70
  71       page_count = best.systems_per_page_.size ();
  72       ideal_sys_count = best.system_count ();
  73       min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
  74
  75       if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
  76         min_sys_count -= best.systems_per_page_[page_count - 2];
  77
  78       min_sys_count = max (min_sys_count, (vsize)1);
  79     }
  80   else
  81     {
  82       /* TODO: the following line will spit out programming errors if the
  83          ideal line spacing doesn't fit on PAGE_COUNT pages */
  84       /* TODO: the interaction between systems_per_page and page_count needs to
  85          be considered. */
  86       best = space_systems_on_n_pages (0, page_count, first_page_num);
  87       min_sys_count = page_count;
  88     }
  89
  90   if (page_count == 1 || scm_is_integer (forced_page_count))
  91     progress_indication (_f ("[%d: %d pages]", (int) end, (int) page_count));
  92   else
  93     progress_indication (_f ("[%d: %d or %d pages]", (int) end, (int) page_count-1, (int)page_count));
  94
  95   /* try a smaller number of systems than the ideal number for line breaking */
  96   Line_division bound = ideal_line_division;
  97   for (vsize sys_count = ideal_sys_count; --sys_count >= min_sys_count;)
  98     {
  99       Page_spacing_result best_for_this_sys_count;
 100       set_current_breakpoints (end-1, end, sys_count, Line_division (), bound);
 101
 102       if (debug_page_breaking_scoring)
 103         message (_f ("trying %d systems", (int)sys_count));
 104
 105       for (vsize i = 0; i < current_configuration_count (); i++)
 106         {
 107           vsize min_p_count = min_page_count (i, first_page_num);
 108           Page_spacing_result cur;
 109
 110           if (min_p_count == page_count || scm_is_integer (forced_page_count))
 111             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 112           else
 113             cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num, 0);
 114
 115           if (cur.demerits_ < best_for_this_sys_count.demerits_)
 116             {
 117               best_for_this_sys_count = cur;
 118               bound = current_configuration (i);
 119             }
 120         }
 121
 122       if (debug_page_breaking_scoring)
 123         message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
 124
 125       if (best_for_this_sys_count.demerits_ < best.demerits_)
 126         {
 127           best = best_for_this_sys_count;
 128           best_division = bound;
 129         }
 130
 131       /* Check to see if we already have too few systems. There are two ways
 132          we check this: if we are trying one less than the ideal number of pages
 133          and the pages are stretched on average then we have too
 134          few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
 135          have too few systems. In either case, though, we need to continue reducing
 136          the number of systems if max-systems-per-page requires it. */
 137       if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
 138         {
 139           if (best_for_this_sys_count.page_count () < page_count
 140               && best_for_this_sys_count.average_force () > 0)
 141             break;
 142
 143           if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
 144             break;
 145         }
 146     }
 147
 148   /* try a larger number of systems than the ideal line breaking number. This
 149      is more or less C&P, but the loop bounds make it difficult to try something
 150      like do {...} while (flip(&d) != UP). */
 151   bound = ideal_line_division;
 152   for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
 153     {
 154       Real best_demerits_for_this_sys_count = infinity_f;
 155       set_current_breakpoints (end-1, end, sys_count, bound);
 156
 157       if (debug_page_breaking_scoring)
 158         message (_f ("trying %d systems", (int)sys_count));
 159
 160       for (vsize i = 0; i < current_configuration_count (); i++)
 161         {
 162           vsize min_p_count = min_page_count (i, first_page_num);
 163           Page_spacing_result cur;
 164
 165           if (min_p_count > page_count)
 166             continue;
 167           else
 168             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 169
 170           if (cur.demerits_ < best.demerits_)
 171             {
 172               best = cur;
 173               best_division = current_configuration (i);
 174             }
 175
 176           if (cur.demerits_ < best_demerits_for_this_sys_count)
 177             {
 178               best_demerits_for_this_sys_count = cur.demerits_;
 179               bound = current_configuration (i);
 180             }
 181         }
 182
 183       if (debug_page_breaking_scoring)
 184         message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
 185
 186       if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
 187         && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
 188         break;
 189     }
 190   break_into_pieces (end-1, end, best_division);
 191
 192   return best.systems_per_page_;
 193 }
 194
 195 SCM
 196 Optimal_page_breaking::solve ()
 197 {
 198   vector<vsize> systems_per_page;
 199
 200   SCM forced_page_counts = book_->paper_->c_variable ("page-count");
 201   if (scm_is_integer (forced_page_counts))
 202     forced_page_counts = scm_list_1 (forced_page_counts);
 203
 204   bool is_forced_page_counts = false;
 205   if (scm_to_bool (scm_list_p (forced_page_counts)))
 206     {
 207       int len = scm_to_int (scm_length (forced_page_counts));
 208       if (len != (int)last_break_position ())
 209         {
 210           warning (_f ("page-count has length %d, but it should have length %d "
 211                        "(one more than the number of forced page breaks)",
 212                        len, (int)last_break_position ()));
 213         }
 214       else
 215         is_forced_page_counts = true;
 216     }
 217
 218
 219   message (_f ("Solving %d page-breaking chunks...", last_break_position ()));
 220   for (vsize end = 1; end <= last_break_position (); ++end)
 221     {
 222       SCM page_count = SCM_EOL;
 223       if (is_forced_page_counts)
 224         {
 225           page_count = scm_car (forced_page_counts);
 226           forced_page_counts = scm_cdr (forced_page_counts);
 227         }
 228
 229       vector<vsize> chunk_systems = solve_chunk (end, page_count);
 230       systems_per_page.insert (systems_per_page.end (), chunk_systems.begin (), chunk_systems.end ());
 231     }
 232
 233   message (_ ("Drawing systems..."));
 234   SCM lines = systems ();
 235   return make_pages (systems_per_page, lines);
 236 }
 237