lily/optimal-page-breaking.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2010 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   vsize ideal_sys_count = system_count ();
  56
  57   if (!scm_is_integer (forced_page_count))
  58     {
  59       /* find out the ideal number of pages */
  60       message (_ ("Finding the ideal number of pages..."));
  61
  62       if (systems_per_page () > 0)
  63         best = space_systems_with_fixed_number_per_page (0, first_page_num);
  64       else
  65         best = space_systems_on_best_pages (0, first_page_num);
  66
  67       page_count = best.systems_per_page_.size ();
  68       ideal_sys_count = best.system_count ();
  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       /* TODO: the following line will spit out programming errors if the
  79          ideal line spacing doesn't fit on PAGE_COUNT pages */
  80       /* TODO: the interaction between systems_per_page and page_count needs to
  81          be considered. */
  82       best = space_systems_on_n_pages (0, page_count, first_page_num);
  83       min_sys_count = page_count;
  84     }
  85
  86   if (page_count == 1)
  87     message (_ ("Fitting music on 1 page..."));
  88   else if (scm_is_integer (forced_page_count))
  89     message (_f ("Fitting music on %d pages...", (int)page_count));
  90   else
  91     message (_f ("Fitting music on %d or %d pages...", (int)page_count-1, (int)page_count));
  92
  93   /* try a smaller number of systems than the ideal number for line breaking */
  94   Line_division bound = ideal_line_division;
  95   for (vsize sys_count = ideal_sys_count; --sys_count >= min_sys_count;)
  96     {
  97       Page_spacing_result best_for_this_sys_count;
  98       set_current_breakpoints (0, end, sys_count, Line_division (), bound);
  99
 100       if (debug_page_breaking_scoring)
 101         message (_f ("trying %d systems", (int)sys_count));
 102
 103       for (vsize i = 0; i < current_configuration_count (); i++)
 104         {
 105           vsize min_p_count = min_page_count (i, first_page_num);
 106           Page_spacing_result cur;
 107
 108           if (min_p_count == page_count || scm_is_integer (forced_page_count))
 109             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 110           else
 111             cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num, 0);
 112
 113           if (cur.demerits_ < best_for_this_sys_count.demerits_)
 114             {
 115               best_for_this_sys_count = cur;
 116               bound = current_configuration (i);
 117             }
 118         }
 119
 120       if (debug_page_breaking_scoring)
 121         message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
 122
 123       if (best_for_this_sys_count.demerits_ < best.demerits_)
 124         {
 125           best = best_for_this_sys_count;
 126           best_division = bound;
 127         }
 128
 129       /* Check to see if we already have too few systems. There are two ways
 130          we check this: if we are trying one less than the ideal number of pages
 131          and the pages are stretched on average then we have too
 132          few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
 133          have too few systems. In either case, though, we need to continue reducing
 134          the number of systems if max-systems-per-page requires it. */
 135       if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
 136         {
 137           if (best_for_this_sys_count.page_count () < page_count
 138               && best_for_this_sys_count.average_force () > 0)
 139             break;
 140
 141           if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
 142             break;
 143         }
 144     }
 145
 146   /* try a larger number of systems than the ideal line breaking number. This
 147      is more or less C&P, but the loop bounds make it difficult to try something
 148      like do {...} while (flip(&d) != UP). */
 149   bound = ideal_line_division;
 150   for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++)
 151     {
 152       Real best_demerits_for_this_sys_count = infinity_f;
 153       set_current_breakpoints (0, end, sys_count, bound);
 154
 155       if (debug_page_breaking_scoring)
 156         message (_f ("trying %d systems", (int)sys_count));
 157
 158       for (vsize i = 0; i < current_configuration_count (); i++)
 159         {
 160           vsize min_p_count = min_page_count (i, first_page_num);
 161           Page_spacing_result cur;
 162
 163           if (min_p_count > page_count)
 164             continue;
 165           else
 166             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 167
 168           if (cur.demerits_ < best.demerits_)
 169             {
 170               best = cur;
 171               best_division = current_configuration (i);
 172             }
 173
 174           if (cur.demerits_ < best_demerits_for_this_sys_count)
 175             {
 176               best_demerits_for_this_sys_count = cur.demerits_;
 177               bound = current_configuration (i);
 178             }
 179         }
 180
 181       if (debug_page_breaking_scoring)
 182         message (_f ("best score for this sys-count: %f", best_demerits_for_this_sys_count));
 183
 184       if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY
 185         && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW))
 186         break;
 187     }
 188
 189   message (_ ("Drawing systems..."));
 190   break_into_pieces (0, end, best_division);
 191   SCM lines = systems ();
 192   return make_pages (best.systems_per_page_, lines);
 193 }
 194