lily/optimal-page-breaking.cc

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