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