lily/optimal-page-breaking.cc

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