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