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       best = space_systems_on_best_pages (0, first_page_num);
  63
  64       page_count = best.systems_per_page_.size ();
  65       ideal_sys_count = best.system_count ();
  66       min_sys_count = ideal_sys_count - best.systems_per_page_.back ();
  67
  68       if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1)
  69         min_sys_count -= best.systems_per_page_[page_count - 2];
  70
  71       min_sys_count = max (min_sys_count, (vsize)1);
  72     }
  73   else
  74     {
  75       /* If systems-per-page and page-count are both specified, we know exactly
  76          how many systems should be present. */
  77       if (systems_per_page () > 0)
  78         {
  79           ideal_sys_count = systems_per_page () * page_count;
  80
  81           if (ideal_sys_count > max_system_count (0, end)
  82               || ideal_sys_count < min_system_count (0, end))
  83             {
  84               warning (_ ("could not satisfy systems-per-page and page-count at the same time, ignoring systems-per-page"));
  85               ideal_sys_count = best.system_count ();
  86               min_sys_count = page_count;
  87             }
  88           else
  89             {
  90               set_current_breakpoints (0, end, ideal_sys_count);
  91               min_sys_count = max_sys_count = ideal_sys_count;
  92               ideal_line_division = best_division = current_configuration (0);
  93             }
  94         }
  95       else
  96         min_sys_count = page_count;
  97
  98       /* TODO: the following line will spit out programming errors if the
  99          ideal line spacing doesn't fit on PAGE_COUNT pages */
 100       best = space_systems_on_n_pages (0, page_count, first_page_num);
 101     }
 102
 103   if (page_count == 1)
 104     message (_ ("Fitting music on 1 page..."));
 105   else if (scm_is_integer (forced_page_count))
 106     message (_f ("Fitting music on %d pages...", (int)page_count));
 107   else
 108     message (_f ("Fitting music on %d or %d pages...", (int)page_count-1, (int)page_count));
 109
 110   /* try a smaller number of systems than the ideal number for line breaking */
 111   Line_division bound = ideal_line_division;
 112   for (vsize sys_count = ideal_sys_count + 1; --sys_count >= min_sys_count;)
 113     {
 114       Page_spacing_result best_for_this_sys_count;
 115       set_current_breakpoints (0, end, sys_count, Line_division (), bound);
 116
 117       if (debug_page_breaking_scoring)
 118         message (_f ("trying %d systems", (int)sys_count));
 119
 120       for (vsize i = 0; i < current_configuration_count (); i++)
 121         {
 122           Page_spacing_result cur;
 123
 124           if (scm_is_integer (forced_page_count))
 125             cur = space_systems_on_n_pages (i, page_count, first_page_num);
 126           else
 127             cur = space_systems_on_best_pages (i, first_page_num);
 128
 129           if (cur.demerits_ < best_for_this_sys_count.demerits_)
 130             {
 131               best_for_this_sys_count = cur;
 132               bound = current_configuration (i);
 133             }
 134         }
 135
 136       if (debug_page_breaking_scoring)
 137         message (_f ("best score for this sys-count: %f", best_for_this_sys_count.demerits_));
 138
 139       if (best_for_this_sys_count.demerits_ < best.demerits_)
 140         {
 141           best = best_for_this_sys_count;
 142           best_division = bound;
 143         }
 144
 145       /* Check to see if we already have too few systems. There are two ways
 146          we check this: if we are trying one less than the ideal number of pages
 147          and the pages are stretched on average then we have too
 148          few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we
 149          have too few systems. In either case, though, we need to continue reducing
 150          the number of systems if max-systems-per-page requires it. */
 151       if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY))
 152         {
 153           if (best_for_this_sys_count.page_count () < page_count
 154               && best_for_this_sys_count.average_force () > 0)
 155             break;
 156
 157           if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY)
 158             break;
 159         }
 160     }
 161
 162   /* try a larger number of systems than the ideal line breaking number. This
 163      is more or less C&P, but the loop bounds make it difficult to try something
 164      like do {...} while (flip(&d) != UP). */
 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