2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2015 Joe Neeman <joeneeman@gmail.com>
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.
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.
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/>.
20 #include "page-turn-page-breaking.hh"
22 #include "international.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"
36 bool turnable = scm_is_symbol (g->get_property ("page-turn-permission"));
39 && (!scm_is_symbol (g->get_property ("page-break-permission"))
40 || !scm_is_symbol (g->get_property ("line-break-permission"))))
42 programming_error ("found a page-turnable place which was not breakable");
49 Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb)
50 : Page_breaking (pb, is_break<Grob>, is_break<Prob>)
54 Page_turn_page_breaking::~Page_turn_page_breaking ()
58 Page_turn_page_breaking::Break_node
59 Page_turn_page_breaking::put_systems_on_pages (vsize start,
64 vsize min_p_count = min_page_count (configuration, page_number);
65 bool auto_first = to_boolean (book_->paper_->c_variable ("auto-first-page-number"));
67 /* If [START, END] does not contain an intermediate
68 breakpoint, we may need to consider solutions that result in a bad turn.
69 In this case, we won't abort if the min_page_count is too big */
70 if (start < end - 1 && min_p_count + (auto_first ? 0 : (page_number % 2)) > 2)
73 /* if PAGE-NUMBER is odd, we are starting on a right hand page. That is, we
76 - even number of pages + a blank page
79 - odd number of pages + a blank page
80 - even number of pages
82 No matter which case PAGE-NUMBER falls into, we take the second choice if
83 min_p_count has that evenness. (For example, if PAGE-NUMBER is even and
84 min_p_count is even, we don't even consider the blank page option). */
86 Page_spacing_result result;
87 if (start == 0 && auto_first)
90 result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, 0);
92 result = space_systems_on_n_pages (configuration, min_p_count, page_number);
94 else if (page_number % 2 == min_p_count % 2)
95 result = space_systems_on_n_pages (configuration, min_p_count, page_number);
97 result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, blank_page_penalty ());
100 ret.prev_ = start - 1;
101 ret.break_pos_ = end;
102 ret.page_count_ = result.force_.size ();
103 ret.first_page_number_ = page_number;
104 if (auto_first && start == 0)
105 ret.first_page_number_ += 1 - (ret.page_count_ % 2);
107 ret.div_ = current_configuration (configuration);
108 ret.system_count_ = result.systems_per_page_;
110 ret.too_many_lines_ = all_lines_stretched (configuration);
111 ret.demerits_ = result.demerits_;
113 ret.demerits_ += state_[start - 1].demerits_;
118 /* The number of pages taken up by a Break_node, including
119 the blank page if there is one */
121 Page_turn_page_breaking::total_page_count (Break_node const &b)
123 vsize end = b.first_page_number_ + b.page_count_;
124 return end - 1 + (end % 2) - b.first_page_number_;
127 extern bool debug_page_breaking_scoring;
130 Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint)
132 vsize end = ending_breakpoint + 1;
135 Break_node this_start_best;
136 vsize prev_best_system_count = 0;
138 for (vsize start = end; start--;)
141 && scm_is_eq (breakpoint_property (start + 1, "page-turn-permission"),
142 ly_symbol2scm ("force")))
145 if (start > 0 && best.demerits_ < state_[start - 1].demerits_)
148 int p_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
151 /* except possibly for the first page, enforce the fact that first_page_number_
152 should always be even (left hand page).
153 TODO: are there different conventions in right-to-left languages?
155 p_num = state_[start - 1].first_page_number_ + state_[start - 1].page_count_;
159 Line_division min_division;
160 Line_division max_division;
162 vsize min_sys_count = min_system_count (start, end);
163 vsize max_sys_count = max_system_count (start, end);
164 this_start_best.demerits_ = infinity_f;
168 if (debug_page_breaking_scoring)
169 message (_f ("page-turn-page-breaking: breaking from %d to %d", (int) start, (int) end));
171 /* heuristic: we've just added a breakpoint, we'll need at least as
172 many systems as before */
173 min_sys_count = max (min_sys_count, prev_best_system_count);
174 for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++)
176 set_current_breakpoints (start, end, sys_count, min_division, max_division);
179 for (vsize i = 0; i < current_configuration_count (); i++)
181 cur = put_systems_on_pages (start, end, i, p_num);
183 if (isinf (cur.demerits_)
184 || (cur.page_count_ + (p_num % 2) > 2
185 && (!isinf (this_start_best.demerits_))
186 && total_page_count (cur) > total_page_count (this_start_best)))
192 if (cur.demerits_ < this_start_best.demerits_)
194 if (debug_page_breaking_scoring)
195 print_break_node (cur);
198 this_start_best = cur;
199 prev_best_system_count = sys_count;
201 /* heuristic: if we increase the number of systems, we can bound the
202 division from below by our current best division */
203 min_division = current_configuration (i);
206 if (!found && this_start_best.too_many_lines_)
209 if (isinf (this_start_best.demerits_))
211 assert (!isinf (best.demerits_) && start < end - 1);
215 if (start == 0 && end == 1
216 && this_start_best.first_page_number_ == 1
217 && this_start_best.page_count_ > 1)
218 warning (_ ("cannot fit the first page turn onto a single page."
219 " Consider setting first-page-number to an even number."));
221 if (this_start_best.demerits_ < best.demerits_)
222 best = this_start_best;
224 state_.push_back (best);
228 Page_turn_page_breaking::solve ()
231 message (_f ("Calculating page and line breaks (%d possible page breaks)...",
232 (int) last_break_position ()));
233 for (vsize i = 0; i < last_break_position (); i++)
236 progress_indication (string ("[") + ::to_string (i + 1) + "]");
238 progress_indication ("\n");
240 vector<Break_node> breaking;
241 int i = state_.size () - 1;
244 breaking.push_back (state_[i]);
249 message (_ ("Drawing systems..."));
250 SCM systems = make_lines (&breaking);
251 return make_pages (breaking, systems);
254 /* do the line breaking in all the scores and return a big list of systems */
256 Page_turn_page_breaking::make_lines (vector<Break_node> *psoln)
258 vector<Break_node> &soln = *psoln;
259 for (vsize n = 0; n < soln.size (); n++)
261 vsize start = n > 0 ? soln[n - 1].break_pos_ : 0;
262 vsize end = soln[n].break_pos_;
264 break_into_pieces (start, end, soln[n].div_);
271 Page_turn_page_breaking::make_pages (vector<Break_node> const &soln, SCM systems)
273 if (scm_is_null (systems))
276 vector<vsize> lines_per_page;
277 for (vsize i = 0; i < soln.size (); i++)
279 for (vsize j = 0; j < soln[i].page_count_; j++)
280 lines_per_page.push_back (soln[i].system_count_[j]);
282 if (i + 1 < soln.size () && (soln[i].first_page_number_ + soln[i].page_count_) % 2)
283 /* add a blank page */
284 lines_per_page.push_back (0);
287 /* this should only actually modify first-page-number if
288 auto-first-page-number was true. */
289 book_->paper_->set_variable (ly_symbol2scm ("first-page-number"),
290 scm_from_int (soln[0].first_page_number_));
291 return Page_breaking::make_pages (lines_per_page, systems);
295 Page_turn_page_breaking::print_break_node (Break_node const &node)
297 int system_count = 0;
298 for (vsize i = 0; i < node.system_count_.size (); i++)
299 system_count += node.system_count_[i];
301 message (_f ("break starting at page %d", (int) node.first_page_number_));
302 message (_f ("\tdemerits: %f", node.demerits_));
303 message (_f ("\tsystem count: %d", system_count));
304 message (_f ("\tpage count: %d", (int) node.page_count_));
305 message (_f ("\tprevious break: %d", (int) node.prev_));