lily/optimal-page-breaking.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2011 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, but the loop bounds make it difficult to try something
 165      like do {...} while (flip(&d) != UP). */
 166   bound = ideal_line_division;
 167   for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
 168     {
 169       Real best_demerits_for_this_sys_count = infinity_f;
 170       set_current_breakpoints (0, end, sys_count, bound);
 171
 172       if (debug_page_breaking_scoring)
 173         message (_f ("trying %d systems", (int)sys_count));
 174
 175       for (vsize i = 0; i < current_configuration_count (); i++)
 176         {
 177           vsize min_p_count = min_page_count (i, first_page_num);
 178           Page_spacing_result cur;
 179
 180           if (min_p_count > page_count)
 181             continue;
 182           else if (scm_is_integer (forced_page_count))
 183             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 184           else
 185             cur = space_systems_on_best_pages (i, first_page_num);
 186
 187           if (cur.demerits_ < best.demerits_)
 188             {
 189               best = cur;
 190               best_division = current_configuration (i);
 191             }
 192
 193           if (cur.demerits_ < best_demerits_for_this_sys_count)
 194             {
 195               best_demerits_for_this_sys_count = cur.demerits_;
 196               bound = current_configuration (i);
 197             }
 198         }
 199
 200       if (debug_page_breaking_scoring)
 201         message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
 202
 203       if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
 204         && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
 205         break;
 206     }
 207
 208   message (_ ("Drawing systems..."));
 209   break_into_pieces (0, end, best_division);
 210   SCM lines = systems ();
 211   return make_pages (best.systems_per_page_, lines);
 212 }
 213