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