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