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