X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fpage-turn-page-breaking.cc;h=9008def09ab408f985bd086210585c8078edc660;hb=57ffd7abe84ffb14e82902b2616ee3fbaf808fd2;hp=338fe4a54d310cc5d7d7884904ffeaa9239e83df;hpb=6224c5c3bfe0a4c7aef15a060a323c77c99bd3f0;p=lilypond.git diff --git a/lily/page-turn-page-breaking.cc b/lily/page-turn-page-breaking.cc index 338fe4a54d..9008def09a 100644 --- a/lily/page-turn-page-breaking.cc +++ b/lily/page-turn-page-breaking.cc @@ -1,9 +1,20 @@ /* - page-turn-page-breaking.cc -- implement Page_turn_page_breaking + This file is part of LilyPond, the GNU music typesetter. - source file of the GNU LilyPond music typesetter + Copyright (C) 2006--2014 Joe Neeman - (c) 2006 Joe Neeman + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see . */ #include "page-turn-page-breaking.hh" @@ -18,75 +29,103 @@ #include "system.hh" #include "warn.hh" -Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb) - : Page_breaking (pb, true) +template +static bool +is_break (T *g) { + bool turnable = scm_is_symbol (g->get_property ("page-turn-permission")); + + if (turnable + && (!scm_is_symbol (g->get_property ("page-break-permission")) + || !scm_is_symbol (g->get_property ("line-break-permission")))) + { + programming_error ("found a page-turnable place which was not breakable"); + turnable = false; + } + + return turnable; } -Page_turn_page_breaking::~Page_turn_page_breaking () +Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb) + : Page_breaking (pb, is_break, is_break) { } -Real -Page_turn_page_breaking::calc_demerits (const Break_node &me) +Page_turn_page_breaking::~Page_turn_page_breaking () { - Real prev_f = 0; - Real prev_dem = 0; - Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1); - if (me.prev_ != VPOS) - { - prev_f = state_[me.prev_].force_; - prev_dem = state_[me.prev_].demerits_; - } - - Real dem = me.force_ * me.force_ * page_weighting - + me.line_force_ * me.line_force_ - + fabs (me.force_ - prev_f); - if (isinf (me.line_force_) || isinf (me.force_)) - dem = infinity_f; - - return dem + prev_dem + me.penalty_ + me.line_penalty_; } Page_turn_page_breaking::Break_node Page_turn_page_breaking::put_systems_on_pages (vsize start, - vsize end, - vector const &lines, - vector const &div, - int page_number) + vsize end, + vsize configuration, + vsize page_number) { - bool last = end == breaks_.size () - 1; - Real page_h = page_height (1, false); // FIXME - SCM force_sym = last ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force"); - Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0); - Spacing_result result = space_systems_on_min_pages (lines, page_h, blank_force); + vsize min_p_count = min_page_count (configuration, page_number); + bool auto_first = to_boolean (book_->paper_->c_variable ("auto-first-page-number")); + + /* If [START, END] does not contain an intermediate + breakpoint, we may need to consider solutions that result in a bad turn. + In this case, we won't abort if the min_page_count is too big */ + if (start < end - 1 && min_p_count + (auto_first ? 0 : (page_number % 2)) > 2) + return Break_node (); + + /* if PAGE-NUMBER is odd, we are starting on a right hand page. That is, we + have the options + PAGE-NUMBER odd: + - even number of pages + a blank page + - odd number of pages + PAGE-NUMBER even: + - odd number of pages + a blank page + - even number of pages + + No matter which case PAGE-NUMBER falls into, we take the second choice if + min_p_count has that evenness. (For example, if PAGE-NUMBER is even and + min_p_count is even, we don't even consider the blank page option). */ + + Page_spacing_result result; + if (start == 0 && auto_first) + { + if (min_p_count % 2) + result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, 0); + else + result = space_systems_on_n_pages (configuration, min_p_count, page_number); + } + else if (page_number % 2 == min_p_count % 2) + result = space_systems_on_n_pages (configuration, min_p_count, page_number); + else + result = space_systems_on_n_or_one_more_pages (configuration, min_p_count, page_number, blank_page_penalty ()); Break_node ret; ret.prev_ = start - 1; ret.break_pos_ = end; - ret.first_page_number_ = page_number; ret.page_count_ = result.force_.size (); - ret.force_ = 0; - for (vsize i = 0; i < result.force_.size (); i++) - ret.force_ += fabs (result.force_[i]); + ret.first_page_number_ = page_number; + if (auto_first && start == 0) + ret.first_page_number_ += 1 - (ret.page_count_ % 2); - ret.penalty_ = result.penalty_; - ret.div_ = div; + ret.div_ = current_configuration (configuration); ret.system_count_ = result.systems_per_page_; - ret.too_many_lines_ = true; - ret.line_force_ = 0; - ret.line_penalty_ = 0; - for (vsize i = 0; i < lines.size (); i++) - { - ret.line_force_ += fabs (lines[i].force_); - ret.line_penalty_ += lines[i].break_penalty_; - if (lines[i].force_ < 0) - ret.too_many_lines_ = false; - } + ret.too_many_lines_ = all_lines_stretched (configuration); + ret.demerits_ = result.demerits_; + if (start > 0) + ret.demerits_ += state_[start - 1].demerits_; + return ret; } +/* The number of pages taken up by a Break_node, including + the blank page if there is one */ +vsize +Page_turn_page_breaking::total_page_count (Break_node const &b) +{ + vsize end = b.first_page_number_ + b.page_count_; + return end - 1 + (end % 2) - b.first_page_number_; +} + +extern bool debug_page_breaking_scoring; + void Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint) { @@ -98,77 +137,69 @@ Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint) for (vsize start = end; start--;) { - if (start > 0 && best.demerits_ < state_[start-1].demerits_) + if (start < end - 1 + && breakpoint_property (start + 1, "page-turn-permission") == ly_symbol2scm ("force")) + break; + + if (start > 0 && best.demerits_ < state_[start - 1].demerits_) continue; - int p_num = 1; + int p_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1); if (start > 0) { - /* if the last node has an odd number of pages and is not the first page, - add a blank page */ - int p_count = state_[start-1].page_count_; - int f_p_num = state_[start-1].first_page_number_; - p_num = f_p_num + p_count + ((f_p_num > 1) ? p_count % 2 : 0); + /* except possibly for the first page, enforce the fact that first_page_number_ + should always be even (left hand page). + TODO: are there different conventions in right-to-left languages? + */ + p_num = state_[start - 1].first_page_number_ + state_[start - 1].page_count_; + p_num += p_num % 2; } - vector min_systems; - vector max_systems; - vsize min_system_count = 0; - vsize max_system_count = 0; - this_start_best.demerits_ = infinity_f; - calc_system_count_bounds (start, end, &min_systems, &max_systems); - - /* heuristic: we've prepended some music, only the first system is allowed - to get more lines */ - if (this_start_best.page_count_ == 2 && this_start_best.div_.size ()) - { - vsize ds = max_systems.size () - this_start_best.div_.size (); - for (vsize i = ds + 1; i < max_systems.size (); i++) - { - assert (this_start_best.div_[i - ds] <= max_systems[i]); - max_systems[i] = this_start_best.div_[i - ds]; - } - } + Line_division min_division; + Line_division max_division; - for (vsize i = 0; i < min_systems.size (); i++) - { - min_system_count += min_systems[i]; - max_system_count += max_systems[i]; - } + vsize min_sys_count = min_system_count (start, end); + vsize max_sys_count = max_system_count (start, end); + this_start_best.demerits_ = infinity_f; bool ok_page = true; + if (debug_page_breaking_scoring) + message (_f ("page-turn-page-breaking: breaking from %d to %d", (int) start, (int) end)); + /* heuristic: we've just added a breakpoint, we'll need at least as many systems as before */ - min_system_count = max (min_system_count, prev_best_system_count); - for (vsize sys_count = min_system_count; sys_count <= max_system_count && ok_page; sys_count++) + min_sys_count = max (min_sys_count, prev_best_system_count); + for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++) { - vector > div; - vector blank; + set_current_breakpoints (start, end, sys_count, min_division, max_division); bool found = false; - divide_systems (sys_count, min_systems, max_systems, &div, &blank); - for (vsize d = 0; d < div.size (); d++) + for (vsize i = 0; i < current_configuration_count (); i++) { - vector line = get_line_details (start, end, div[d]); - - cur = put_systems_on_pages (start, end, line, div[d], p_num); + cur = put_systems_on_pages (start, end, i, p_num); - if (cur.page_count_ > 2 && - (start < end - 1 || (!isinf (this_start_best.demerits_) - && cur.page_count_ + cur.page_count_ % 2 - > this_start_best.page_count_ + this_start_best.page_count_ % 2))) + if (isinf (cur.demerits_) + || (cur.page_count_ + (p_num % 2) > 2 + && (!isinf (this_start_best.demerits_)) + && total_page_count (cur) > total_page_count (this_start_best))) { ok_page = false; break; } - cur.demerits_ = calc_demerits (cur); if (cur.demerits_ < this_start_best.demerits_) { + if (debug_page_breaking_scoring) + print_break_node (cur); + found = true; this_start_best = cur; prev_best_system_count = sys_count; + + /* heuristic: if we increase the number of systems, we can bound the + division from below by our current best division */ + min_division = current_configuration (i); } } if (!found && this_start_best.too_many_lines_) @@ -179,6 +210,13 @@ Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint) assert (!isinf (best.demerits_) && start < end - 1); break; } + + if (start == 0 && end == 1 + && this_start_best.first_page_number_ == 1 + && this_start_best.page_count_ > 1) + warning (_ ("cannot fit the first page turn onto a single page." + " Consider setting first-page-number to an even number.")); + if (this_start_best.demerits_ < best.demerits_) best = this_start_best; } @@ -190,11 +228,11 @@ Page_turn_page_breaking::solve () { state_.clear (); message (_f ("Calculating page and line breaks (%d possible page breaks)...", - (int)breaks_.size () - 1) + " "); - for (vsize i = 0; i < breaks_.size () - 1; i++) + (int) last_break_position ())); + for (vsize i = 0; i < last_break_position (); i++) { calc_subproblem (i); - progress_indication (string ("[") + to_string (i + 1) + "]"); + progress_indication (string ("[") + ::to_string (i + 1) + "]"); } progress_indication ("\n"); @@ -219,56 +257,49 @@ Page_turn_page_breaking::make_lines (vector *psoln) vector &soln = *psoln; for (vsize n = 0; n < soln.size (); n++) { - vsize start = n > 0 ? soln[n-1].break_pos_ : 0; + vsize start = n > 0 ? soln[n - 1].break_pos_ : 0; vsize end = soln[n].break_pos_; - /* break each score into pieces */ - for (vsize i = next_system (start); i <= breaks_[end].sys_; i++) - { - vsize d = i - next_system (start); - if (all_[i].pscore_) - { - vector line_brk; - - line_brk = get_line_breaks (i, soln[n].div_[d], start, end); - all_[i].pscore_->root_system ()->break_into_pieces (line_brk); - assert (line_brk.size () == soln[n].div_[d]); - } - } - } - SCM ret = SCM_EOL; - SCM *tail = &ret; - for (vsize i = 0; i < all_.size (); i++) - { - if (all_[i].pscore_) - for (SCM s = scm_vector_to_list (all_[i].pscore_->root_system ()->get_paper_systems ()); - scm_is_pair (s); s = scm_cdr (s)) - { - *tail = scm_cons (scm_car (s), SCM_EOL); - tail = SCM_CDRLOC (*tail); - } - else - { - *tail = scm_cons (all_[i].prob_->self_scm (), SCM_EOL); - all_[i].prob_->unprotect (); - tail = SCM_CDRLOC (*tail); - } + break_into_pieces (start, end, soln[n].div_); } - return ret; + + return systems (); } SCM Page_turn_page_breaking::make_pages (vector const &soln, SCM systems) { + if (scm_is_null (systems)) + return SCM_EOL; + vector lines_per_page; for (vsize i = 0; i < soln.size (); i++) { for (vsize j = 0; j < soln[i].page_count_; j++) - lines_per_page.push_back (soln[i].system_count_[j]); + lines_per_page.push_back (soln[i].system_count_[j]); - if (i > 0 && i < soln.size () - 1 && soln[i].page_count_ % 2) - /* add a blank page */ - lines_per_page.push_back (0); + if (i + 1 < soln.size () && (soln[i].first_page_number_ + soln[i].page_count_) % 2) + /* add a blank page */ + lines_per_page.push_back (0); } + + /* this should only actually modify first-page-number if + auto-first-page-number was true. */ + book_->paper_->set_variable (ly_symbol2scm ("first-page-number"), + scm_from_int (soln[0].first_page_number_)); return Page_breaking::make_pages (lines_per_page, systems); } + +void +Page_turn_page_breaking::print_break_node (Break_node const &node) +{ + int system_count = 0; + for (vsize i = 0; i < node.system_count_.size (); i++) + system_count += node.system_count_[i]; + + message (_f ("break starting at page %d", (int) node.first_page_number_)); + message (_f ("\tdemerits: %f", node.demerits_)); + message (_f ("\tsystem count: %d", system_count)); + message (_f ("\tpage count: %d", (int) node.page_count_)); + message (_f ("\tprevious break: %d", (int) node.prev_)); +}