lily/page-turn-page-breaking.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2015 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 "page-turn-page-breaking.hh"
  21
  22 #include "international.hh"
  23 #include "item.hh"
  24 #include "output-def.hh"
  25 #include "page-spacing.hh"
  26 #include "paper-book.hh"
  27 #include "paper-score.hh"
  28 #include "paper-system.hh"
  29 #include "system.hh"
  30 #include "warn.hh"
  31
  32 using std::string;
  33 using std::vector;
  34
  35 template<typename T>
  36 static bool
  37 is_break (T *g)
  38 {
  39   bool turnable = scm_is_symbol (g->get_property ("page-turn-permission"));
  40
  41   if (turnable
  42       && (!scm_is_symbol (g->get_property ("page-break-permission"))
  43           || !scm_is_symbol (g->get_property ("line-break-permission"))))
  44     {
  45       programming_error ("found a page-turnable place which was not breakable");
  46       turnable = false;
  47     }
  48
  49   return turnable;
  50 }
  51
  52 Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb)
  53   : Page_breaking (pb, is_break<Grob>, is_break<Prob>)
  54 {
  55 }
  56
  57 Page_turn_page_breaking::~Page_turn_page_breaking ()
  58 {
  59 }
  60
  61 Page_turn_page_breaking::Break_node
  62 Page_turn_page_breaking::put_systems_on_pages (vsize start,
  63                                                vsize end,
  64                                                vsize configuration,
  65                                                vsize page_number)
  66 {
  67   vsize min_p_count = min_page_count (configuration, page_number);
  68   bool auto_first = to_boolean (book_->paper_->c_variable ("auto-first-page-number"));
  69
  70   /* If [START, END] does not contain an intermediate
  71      breakpoint, we may need to consider solutions that result in a bad turn.
  72      In this case, we won't abort if the min_page_count is too big */
  73   if (start < end - 1 && min_p_count + (auto_first ? 0 : (page_number % 2)) > 2)
  74     return Break_node ();
  75
  76   /* if PAGE-NUMBER is odd, we are starting on a right hand page. That is, we
  77      have the options
  78      PAGE-NUMBER odd:
  79        - even number of pages + a blank page
  80        - odd number of pages
  81      PAGE-NUMBER even:
  82        - odd number of pages + a blank page
  83        - even number of pages
  84
  85      No matter which case PAGE-NUMBER falls into, we take the second choice if
  86      min_p_count has that evenness. (For example, if PAGE-NUMBER is even and
  87      min_p_count is even, we don't even consider the blank page option). */
  88
  89   Page_spacing_result result;
  90   if (start == 0 && auto_first)
  91     {
  92       if (min_p_count % 2)
  93         result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, 0);
  94       else
  95         result = space_systems_on_n_pages (configuration, min_p_count, page_number);
  96     }
  97   else if (page_number % 2 == min_p_count % 2)
  98     result = space_systems_on_n_pages (configuration, min_p_count, page_number);
  99   else
 100     result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, blank_page_penalty ());
 101
 102   Break_node ret;
 103   ret.prev_ = start - 1;
 104   ret.break_pos_ = end;
 105   ret.page_count_ = result.force_.size ();
 106   ret.first_page_number_ = page_number;
 107   if (auto_first && start == 0)
 108     ret.first_page_number_ += 1 - (ret.page_count_ % 2);
 109
 110   ret.div_ = current_configuration (configuration);
 111   ret.system_count_ = result.systems_per_page_;
 112
 113   ret.too_many_lines_ = all_lines_stretched (configuration);
 114   ret.demerits_ = result.demerits_;
 115   if (start > 0)
 116     ret.demerits_ += state_[start - 1].demerits_;
 117
 118   return ret;
 119 }
 120
 121 /* The number of pages taken up by a Break_node, including
 122    the blank page if there is one */
 123 vsize
 124 Page_turn_page_breaking::total_page_count (Break_node const &b)
 125 {
 126   vsize end = b.first_page_number_ + b.page_count_;
 127   return end - 1 + (end % 2) - b.first_page_number_;
 128 }
 129
 130 extern bool debug_page_breaking_scoring;
 131
 132 void
 133 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
 134 {
 135   vsize end = ending_breakpoint + 1;
 136   Break_node best;
 137   Break_node cur;
 138   Break_node this_start_best;
 139   vsize prev_best_system_count = 0;
 140
 141   for (vsize start = end; start--;)
 142     {
 143       if (start < end - 1
 144           && scm_is_eq (breakpoint_property (start + 1, "page-turn-permission"),
 145                         ly_symbol2scm ("force")))
 146         break;
 147
 148       if (start > 0 && best.demerits_ < state_[start - 1].demerits_)
 149         continue;
 150
 151       int p_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
 152       if (start > 0)
 153         {
 154           /* except possibly for the first page, enforce the fact that first_page_number_
 155              should always be even (left hand page).
 156              TODO: are there different conventions in right-to-left languages?
 157           */
 158           p_num = state_[start - 1].first_page_number_ + state_[start - 1].page_count_;
 159           p_num += p_num % 2;
 160         }
 161
 162       Line_division min_division;
 163       Line_division max_division;
 164
 165       vsize min_sys_count = min_system_count (start, end);
 166       vsize max_sys_count = max_system_count (start, end);
 167       this_start_best.demerits_ = infinity_f;
 168
 169       bool ok_page = true;
 170
 171       if (debug_page_breaking_scoring)
 172         message (_f ("page-turn-page-breaking: breaking from %d to %d", (int) start, (int) end));
 173
 174       /* heuristic: we've just added a breakpoint, we'll need at least as
 175          many systems as before */
 176       min_sys_count = max (min_sys_count, prev_best_system_count);
 177       for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++)
 178         {
 179           set_current_breakpoints (start, end, sys_count, min_division, max_division);
 180           bool found = false;
 181
 182           for (vsize i = 0; i < current_configuration_count (); i++)
 183             {
 184               cur = put_systems_on_pages (start, end, i, p_num);
 185
 186               if (isinf (cur.demerits_)
 187                   || (cur.page_count_ + (p_num % 2) > 2
 188                       && (!isinf (this_start_best.demerits_))
 189                       && total_page_count (cur) > total_page_count (this_start_best)))
 190                 {
 191                   ok_page = false;
 192                   break;
 193                 }
 194
 195               if (cur.demerits_ < this_start_best.demerits_)
 196                 {
 197                   if (debug_page_breaking_scoring)
 198                     print_break_node (cur);
 199
 200                   found = true;
 201                   this_start_best = cur;
 202                   prev_best_system_count = sys_count;
 203
 204                   /* heuristic: if we increase the number of systems, we can bound the
 205                      division from below by our current best division */
 206                   min_division = current_configuration (i);
 207                 }
 208             }
 209           if (!found && this_start_best.too_many_lines_)
 210             break;
 211         }
 212       if (isinf (this_start_best.demerits_))
 213         {
 214           assert (!isinf (best.demerits_) && start < end - 1);
 215           break;
 216         }
 217
 218       if (start == 0 && end == 1
 219           && this_start_best.first_page_number_ == 1
 220           && this_start_best.page_count_ > 1)
 221         warning (_ ("cannot fit the first page turn onto a single page."
 222                     "  Consider setting first-page-number to an even number."));
 223
 224       if (this_start_best.demerits_ < best.demerits_)
 225         best = this_start_best;
 226     }
 227   state_.push_back (best);
 228 }
 229
 230 SCM
 231 Page_turn_page_breaking::solve ()
 232 {
 233   state_.clear ();
 234   message (_f ("Calculating page and line breaks (%d possible page breaks)...",
 235                (int) last_break_position ()));
 236   for (vsize i = 0; i < last_break_position (); i++)
 237     {
 238       calc_subproblem (i);
 239       progress_indication (string ("[") + ::to_string (i + 1) + "]");
 240     }
 241   progress_indication ("\n");
 242
 243   vector<Break_node> breaking;
 244   int i = state_.size () - 1;
 245   while (i >= 0)
 246     {
 247       breaking.push_back (state_[i]);
 248       i = state_[i].prev_;
 249     }
 250   reverse (breaking);
 251
 252   message (_ ("Drawing systems..."));
 253   SCM systems = make_lines (&breaking);
 254   return make_pages (breaking, systems);
 255 }
 256
 257 /* do the line breaking in all the scores and return a big list of systems */
 258 SCM
 259 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
 260 {
 261   vector<Break_node> &soln = *psoln;
 262   for (vsize n = 0; n < soln.size (); n++)
 263     {
 264       vsize start = n > 0 ? soln[n - 1].break_pos_ : 0;
 265       vsize end = soln[n].break_pos_;
 266
 267       break_into_pieces (start, end, soln[n].div_);
 268     }
 269
 270   return systems ();
 271 }
 272
 273 SCM
 274 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
 275 {
 276   if (scm_is_null (systems))
 277     return SCM_EOL;
 278
 279   vector<vsize> lines_per_page;
 280   for (vsize i = 0; i < soln.size (); i++)
 281     {
 282       for (vsize j = 0; j < soln[i].page_count_; j++)
 283         lines_per_page.push_back (soln[i].system_count_[j]);
 284
 285       if (i + 1 < soln.size () && (soln[i].first_page_number_ + soln[i].page_count_) % 2)
 286         /* add a blank page */
 287         lines_per_page.push_back (0);
 288     }
 289
 290   /* this should only actually modify first-page-number if
 291      auto-first-page-number was true. */
 292   book_->paper_->set_variable (ly_symbol2scm ("first-page-number"),
 293                                scm_from_int (soln[0].first_page_number_));
 294   return Page_breaking::make_pages (lines_per_page, systems);
 295 }
 296
 297 void
 298 Page_turn_page_breaking::print_break_node (Break_node const &node)
 299 {
 300   int system_count = 0;
 301   for (vsize i = 0; i < node.system_count_.size (); i++)
 302     system_count += node.system_count_[i];
 303
 304   message (_f ("break starting at page %d", (int) node.first_page_number_));
 305   message (_f ("\tdemerits: %f", node.demerits_));
 306   message (_f ("\tsystem count: %d", system_count));
 307   message (_f ("\tpage count: %d", (int) node.page_count_));
 308   message (_f ("\tprevious break: %d", (int) node.prev_));
 309 }