lily/optimal-page-breaking.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2012 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 Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb)
  30   : Page_breaking (pb, 0, 0)
  31 {
  32 }
  33
  34 Optimal_page_breaking::~Optimal_page_breaking ()
  35 {
  36 }
  37
  38 extern bool debug_page_breaking_scoring;
  39
  40 SCM
  41 Optimal_page_breaking::solve ()
  42 {
  43   vsize end = last_break_position ();
  44   vsize max_sys_count = max_system_count (0, end);
  45   vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
  46
  47   set_to_ideal_line_configuration (0, end);
  48
  49   Page_spacing_result best;
  50   SCM forced_page_count = book_->paper_->c_variable ("page-count");
  51   vsize page_count = robust_scm2int (forced_page_count, 1);
  52   Line_division ideal_line_division = current_configuration (0);
  53   Line_division best_division = ideal_line_division;
  54   vsize min_sys_count = 1;
  55
  56   // Note that system_count () only counts non-title systems.
  57   vsize ideal_sys_count = system_count ();
  58
  59   if (!scm_is_integer (forced_page_count))
  60     {
  61       /* find out the ideal number of pages */
  62       message (_ ("Finding the ideal number of pages..."));
  63
  64       best = space_systems_on_best_pages (0, first_page_num);
  65
  66       page_count = best.systems_per_page_.size ();
  67       if (page_count == 0)
  68         {
  69           min_sys_count = 0;
  70         }
  71       else
  72         {
  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     }
  81   else
  82     {
  83       /* If systems-per-page and page-count are both specified, we know exactly
  84          how many systems should be present. */
  85       if (systems_per_page () > 0)
  86         {
  87           ideal_sys_count = systems_per_page () * page_count;
  88
  89           if (ideal_sys_count > max_system_count (0, end)
  90               || ideal_sys_count < min_system_count (0, end))
  91             {
  92               warning (_ ("could not satisfy systems-per-page and page-count at the same time, ignoring systems-per-page"));
  93               ideal_sys_count = system_count ();
  94               min_sys_count = page_count;
  95             }
  96           else
  97             {
  98               set_current_breakpoints (0, end, ideal_sys_count);
  99               min_sys_count = max_sys_count = ideal_sys_count;
 100               ideal_line_division = best_division = current_configuration (0);
 101             }
 102         }
 103       else
 104         min_sys_count = page_count;
 105
 106       /* TODO: the following line will spit out programming errors if the
 107          ideal line spacing doesn't fit on PAGE_COUNT pages */
 108       best = space_systems_on_n_pages (0, page_count, first_page_num);
 109     }
 110
 111   if (page_count == 1)
 112     message (_ ("Fitting music on 1 page..."));
 113   else if (scm_is_integer (forced_page_count) || page_count == 0)
 114     message (_f ("Fitting music on %d pages...", (int)page_count));
 115   else
 116     message (_f ("Fitting music on %d or %d pages...", (int)page_count - 1, (int)page_count));
 117
 118   /* try a smaller number of systems than the ideal number for line breaking */
 119   Line_division bound = ideal_line_division;
 120   for (vsize sys_count = ideal_sys_count + 1; --sys_count >= min_sys_count;)
 121     {
 122       Page_spacing_result best_for_this_sys_count;
 123       set_current_breakpoints (0, end, sys_count, Line_division (), bound);
 124
 125       if (debug_page_breaking_scoring)
 126         message (_f ("trying %d systems", (int)sys_count));
 127
 128       for (vsize i = 0; i < current_configuration_count (); i++)
 129         {
 130           Page_spacing_result cur;
 131
 132           if (scm_is_integer (forced_page_count))
 133             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 134           else
 135             cur = space_systems_on_best_pages (i, first_page_num);
 136
 137           if (cur.demerits_ < best_for_this_sys_count.demerits_)
 138             {
 139               best_for_this_sys_count = cur;
 140               bound = current_configuration (i);
 141             }
 142         }
 143
 144       if (debug_page_breaking_scoring)
 145         message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
 146
 147       if (best_for_this_sys_count.demerits_ < best.demerits_)
 148         {
 149           best = best_for_this_sys_count;
 150           best_division = bound;
 151         }
 152
 153       /* Check to see if we already have too few systems. There are two ways
 154          we check this: if we are trying one less than the ideal number of pages
 155          and the pages are stretched on average then we have too
 156          few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
 157          have too few systems. In either case, though, we need to continue reducing
 158          the number of systems if max-systems-per-page requires it. */
 159       if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
 160         {
 161           if (best_for_this_sys_count.page_count () < page_count
 162               && best_for_this_sys_count.average_force () > 0)
 163             break;
 164
 165           if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
 166             break;
 167         }
 168     }
 169
 170   /* try a larger number of systems than the ideal line breaking number. This
 171      is more or less C&P. */
 172   bound = ideal_line_division;
 173   for (vsize sys_count = ideal_sys_count + 1; sys_count <= max_sys_count; sys_count++)
 174     {
 175       Real best_demerits_for_this_sys_count = infinity_f;
 176       set_current_breakpoints (0, end, sys_count, bound);
 177
 178       if (debug_page_breaking_scoring)
 179         message (_f ("trying %d systems", (int)sys_count));
 180
 181       for (vsize i = 0; i < current_configuration_count (); i++)
 182         {
 183           vsize min_p_count = min_page_count (i, first_page_num);
 184           Page_spacing_result cur;
 185
 186           if (min_p_count > page_count)
 187             continue;
 188           else if (scm_is_integer (forced_page_count))
 189             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 190           else
 191             cur = space_systems_on_best_pages (i, first_page_num);
 192
 193           if (cur.demerits_ < best.demerits_)
 194             {
 195               best = cur;
 196               best_division = current_configuration (i);
 197             }
 198
 199           if (cur.demerits_ < best_demerits_for_this_sys_count)
 200             {
 201               best_demerits_for_this_sys_count = cur.demerits_;
 202               bound = current_configuration (i);
 203             }
 204         }
 205
 206       if (debug_page_breaking_scoring)
 207         message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
 208
 209       if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
 210           && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
 211         break;
 212     }
 213
 214   message (_ ("Drawing systems..."));
 215   break_into_pieces (0, end, best_division);
 216   SCM lines = systems ();
 217   return make_pages (best.systems_per_page_, lines);
 218 }
 219