From ba420bc05855eeca5fb937939261baffd614c2ef Mon Sep 17 00:00:00 2001 From: Joe Neeman Date: Tue, 8 Aug 2006 10:01:22 +0000 Subject: [PATCH] * scm/page.scm (make-page): make it friendlier to call (esp. from C++) * scm/layout-page-layout.scm (make-page-from-systems): new function (optimal-page-breaks): use the new page-breaking calling convention * scm/define-context-properties.scm (all-user-translation-properties): add revokePageTurns * lily/paper-column-engraver.cc (stop_translation_timestep): add revokePageTurns functionality. If there is a special barline within the breakable region, break there instead of at the end of the region. * lily/paper-book.cc (pages): use the new page-breaking calling convention --- ChangeLog | 16 + .../optimal-page-breaking-hstretch.ly | 22 + .../page-turn-page-breaking-badturns.ly | 21 + input/regression/page-turn-page-breaking.ly | 29 ++ lily/include/optimal-page-breaking.hh | 30 ++ lily/include/page-breaking.hh | 82 ++++ lily/include/page-spacing.hh | 37 ++ lily/include/page-turn-page-breaking.hh | 76 +++ lily/include/paper-column-engraver.hh | 6 +- lily/optimal-page-breaking.cc | 172 +++++++ lily/page-breaking-scheme.cc | 30 ++ lily/page-breaking.cc | 314 ++++++++++++ lily/page-spacing.cc | 445 ++++++++++++++++++ lily/page-turn-engraver.cc | 125 +++++ lily/page-turn-page-breaking.cc | 274 +++++++++++ lily/paper-book.cc | 2 +- lily/paper-column-engraver.cc | 100 +++- ly/declarations-init.ly | 1 + ly/paper-defaults.ly | 6 + scm/define-context-properties.scm | 1 + scm/layout-page-layout.scm | 22 +- scm/page.scm | 26 +- 22 files changed, 1809 insertions(+), 28 deletions(-) create mode 100644 input/regression/optimal-page-breaking-hstretch.ly create mode 100644 input/regression/page-turn-page-breaking-badturns.ly create mode 100644 input/regression/page-turn-page-breaking.ly create mode 100644 lily/include/optimal-page-breaking.hh create mode 100644 lily/include/page-breaking.hh create mode 100644 lily/include/page-spacing.hh create mode 100644 lily/include/page-turn-page-breaking.hh create mode 100644 lily/optimal-page-breaking.cc create mode 100644 lily/page-breaking-scheme.cc create mode 100644 lily/page-breaking.cc create mode 100644 lily/page-spacing.cc create mode 100644 lily/page-turn-engraver.cc create mode 100644 lily/page-turn-page-breaking.cc diff --git a/ChangeLog b/ChangeLog index 4e060b0131..2cdff9a358 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +2006-08-08 Joe Neeman + + * scm/page.scm (make-page): make it friendlier to call (esp. from C++) + + * scm/layout-page-layout.scm (make-page-from-systems): new function + (optimal-page-breaks): use the new page-breaking calling convention + + * scm/define-context-properties.scm (all-user-translation-properties): + add revokePageTurns + + * lily/paper-column-engraver.cc (stop_translation_timestep): add + revokePageTurns functionality. If there is a special barline within + the breakable region, break there instead of at the end of the region. + + * lily/paper-book.cc (pages): use the new page-breaking calling convention + 2006-08-07 Erik Sandberg * lily/lexer.ll, lily/source-file.cc: Add \sourcefileline command diff --git a/input/regression/optimal-page-breaking-hstretch.ly b/input/regression/optimal-page-breaking-hstretch.ly new file mode 100644 index 0000000000..64eef4e6d1 --- /dev/null +++ b/input/regression/optimal-page-breaking-hstretch.ly @@ -0,0 +1,22 @@ +\version "2.9.13" + +\header{ + texidoc="The optimal page breaker will stretch the +systems horizontally so that the vertical spacing will be +more acceptable. The page-spacing-weight parameter +controls the relative importance of vertical/horizontal +spacing. +" +} + +\paper { + #(define page-breaking ly:optimal-breaking) + page-spacing-weight = #10 + ragged-last-bottom = ##f +} + +\relative c' { + \repeat unfold 5 {a b c d} +} + + diff --git a/input/regression/page-turn-page-breaking-badturns.ly b/input/regression/page-turn-page-breaking-badturns.ly new file mode 100644 index 0000000000..cae98946a7 --- /dev/null +++ b/input/regression/page-turn-page-breaking-badturns.ly @@ -0,0 +1,21 @@ +\version "2.9.13" + +\header{ + texidoc="If there are no good places to have a page turn, +the optimal-breaker will just have to recover gracefully. This +should appear on 3 pages. +" +} + +\paper { + #(define page-breaking ly:page-turn-breaking) + paper-height = #70 +} + +\relative c' { + a b c d a b c d \break + c d e f c d e f \break + d e f g d e f g +} + + diff --git a/input/regression/page-turn-page-breaking.ly b/input/regression/page-turn-page-breaking.ly new file mode 100644 index 0000000000..88aea25c01 --- /dev/null +++ b/input/regression/page-turn-page-breaking.ly @@ -0,0 +1,29 @@ +\version "2.9.13" + +\header{ + texidoc="The page-turn breaker will put a page turn after +a rest unless there is a 'special' barline within the rest, +in which case the turn will go after the special barline. +" +} + +\paper { + #(define page-breaking ly:page-turn-breaking) + paper-height = #70 +} + +\layout { + \context { + \Staff + \consists "Page_turn_engraver" + } +} + +\relative c' { + a b c d a b c d \break + c d e f c d e f R1*4 + \repeat unfold 15 {d4 e f g} \break + c d e f c d e f R1*2 \bar "||" R1*2 + \repeat unfold 15 {d4 e f g} +} + diff --git a/lily/include/optimal-page-breaking.hh b/lily/include/optimal-page-breaking.hh new file mode 100644 index 0000000000..8e312233ad --- /dev/null +++ b/lily/include/optimal-page-breaking.hh @@ -0,0 +1,30 @@ +/* + optimal-page-breaking.hh -- declare a page-breaker that + will break pages in such a way that both horizontal and + vertical spacing will be acceptable + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#ifndef OPTIMAL_PAGE_BREAKING_HH +#define OPTIMAL_PAGE_BREAKING_HH + +#include "page-breaking.hh" +#include "page-spacing.hh" + +class Optimal_page_breaking: public Page_breaking +{ +public: + virtual SCM solve (); + + Optimal_page_breaking (Paper_book *pb); + virtual ~Optimal_page_breaking (); + +private: + SCM make_lines (vector line_count); + Spacing_result try_page_spacing (vector line_count); +}; + +#endif /* OPTIMAL_PAGE_BREAKING_HH */ diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh new file mode 100644 index 0000000000..4930c99d9e --- /dev/null +++ b/lily/include/page-breaking.hh @@ -0,0 +1,82 @@ +/* + page-breaking.hh -- declare a superclass and utility + functions for several different page-breaking algorithms + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#ifndef PAGE_BREAKING_HH +#define PAGE_BREAKING_HH + +#include "constrained-breaking.hh" +#include "lily-guile.hh" + +/* Either a paper-score, markup or header. + */ +struct System_spec +{ + System_spec (Paper_score*, int); + System_spec (Prob*); + System_spec (); + + Paper_score *pscore_; + Prob *prob_; + + vsize score_break_count_; /* for scores, this is the number of start-points our line- + breaker has */ +}; + +struct Break_position +{ + vsize sys_; /* the index in our all_ list */ + vsize score_break_; /* if sys_ is a score, then we start at the score_brk_'th + possible page-break in the score */ + + Break_position (vsize s=VPOS, vsize brk=VPOS) + { + sys_ = s; + score_break_ = brk; + } +}; + +class Page_breaking +{ +public: + virtual SCM solve () = 0; + + Page_breaking (Paper_book *pb, bool allow_intra_score_breaks); + virtual ~Page_breaking (); + +protected: + std::vector breaks_; + std::vector all_; + std::vector line_breaking_; + + Paper_book *book_; + + Real page_height (int page_number, bool last); + vsize next_system (vsize starting_break_index) const; + + void create_system_list (bool allow_intra_score_breaks); + std::vector find_page_break_indices (Paper_score *pscore); + + SCM make_pages (vector lines_per_page, SCM lines); + + void calc_system_count_bounds (vsize start, vsize end, + vector *min, + vector *max); + + void divide_systems (vsize system_count, vector const &min, + vector const &max, + vector > *result, + vector *cur); + + void line_breaker_args (vsize i, vsize *break_st, vsize *break_end); + vsize get_min_systems (vsize sys, vsize break_start, vsize break_end); + vsize get_max_systems (vsize sys, vsize break_start, vsize break_end); + vector get_line_breaks (vsize sys, vsize sys_count, vsize st, vsize end); + vector get_line_details (vsize start_break, vsize end_break, vector const &div); +}; +#endif /* PAGE_BREAKING_HH */ diff --git a/lily/include/page-spacing.hh b/lily/include/page-spacing.hh new file mode 100644 index 0000000000..e7e3b4888a --- /dev/null +++ b/lily/include/page-spacing.hh @@ -0,0 +1,37 @@ +/* + page-spacing.hh -- routines for spacing systems + vertically across pages + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#ifndef PAGE_SPACING_HH +#define PAGE_SPACING_HH + +#include "constrained-breaking.hh" + +struct Spacing_result { + vector systems_per_page_; + vector force_; + Real penalty_; + Real demerits_; + + Spacing_result () + { + penalty_ = 0; + demerits_ = 0; + } +}; + +Spacing_result +space_systems_on_min_pages (vector const&, + Real page_height, + Real odd_pages_penalty); +Spacing_result +space_systems_on_best_pages (vector const&, + Real page_height, + Real odd_pages_penalty); + +#endif /* PAGE_SPACING_HH */ diff --git a/lily/include/page-turn-page-breaking.hh b/lily/include/page-turn-page-breaking.hh new file mode 100644 index 0000000000..e386cc85da --- /dev/null +++ b/lily/include/page-turn-page-breaking.hh @@ -0,0 +1,76 @@ +/* + page-turn-page-breaking.hh -- break lines and pages optimally + for a whole Paper_book such that page turns can only occur + at specific places. + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#ifndef PAGE_TURN_PAGE_BREAKING_HH +#define PAGE_TURN_PAGE_BREAKING_HH + +#include "constrained-breaking.hh" +#include "page-breaking.hh" +#include "lily-guile.hh" + +/* + A dynamic programming solution to breaking pages + */ +class Page_turn_page_breaking: public Page_breaking +{ +public: + virtual SCM solve (); + + Page_turn_page_breaking (Paper_book *pb); + virtual ~Page_turn_page_breaking (); + +protected: + struct Break_node + { + vsize prev_; + int first_page_number_; + vsize page_count_; + + Real force_; + Real penalty_; + + Real line_force_; + Real line_penalty_; + + /* true if every score here is too widely spaced */ + bool too_many_lines_; + + Real demerits_; + vsize break_pos_; /* index into breaks_ */ + + vector div_; /* our division of systems between scores on this page */ + vector system_count_; /* systems per page */ + + Break_node () + { + prev_ = break_pos_ = VPOS; + penalty_ = force_ = 0; + line_penalty_ = line_force_ = 0; + demerits_ = infinity_f; + first_page_number_ = 0; + too_many_lines_ = false; + } + }; + + std::vector state_; + + Break_node put_systems_on_pages (vsize start, + vsize end, + vector const &lines, + vector const &system_div, + int page_number); + + SCM make_lines (vector *breaks); + SCM make_pages (vector const &breaks, SCM systems); + + Real calc_demerits (Break_node const &me); + void calc_subproblem (vsize i); +}; +#endif /* PAGE_TURN_PAGE_BREAKING_HH */ diff --git a/lily/include/paper-column-engraver.hh b/lily/include/paper-column-engraver.hh index d3b9430e35..e5db58c7a3 100644 --- a/lily/include/paper-column-engraver.hh +++ b/lily/include/paper-column-engraver.hh @@ -19,6 +19,9 @@ class Paper_column_engraver : public Engraver void set_columns (Paper_column *, Paper_column *); TRANSLATOR_DECLARATIONS (Paper_column_engraver); + Paper_column *find_turnable_column (Moment after_this); + void revoke_page_turns (Moment after_this, Real new_penalty); + protected: void stop_translation_timestep (); void start_translation_timestep (); @@ -41,8 +44,9 @@ protected: bool first_; Moment last_moment_; - Moment last_breakable_moment_; + Paper_column *last_special_barline_column_; Paper_column *last_breakable_column_; + vector page_turnable_columns_; public: }; diff --git a/lily/optimal-page-breaking.cc b/lily/optimal-page-breaking.cc new file mode 100644 index 0000000000..800c524591 --- /dev/null +++ b/lily/optimal-page-breaking.cc @@ -0,0 +1,172 @@ +/* + optimal-page-breaking.hh -- implement a page-breaker that + will break pages in such a way that both horizontal and + vertical spacing will be acceptable + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#include "optimal-page-breaking.hh" +#include "output-def.hh" +#include "page-spacing.hh" +#include "paper-book.hh" +#include "paper-score.hh" +#include "prob.hh" +#include "system.hh" + +Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb) + : Page_breaking (pb, false) +{ +} + +Optimal_page_breaking::~Optimal_page_breaking () +{ +} + +Spacing_result +Optimal_page_breaking::try_page_spacing (vector line_count) +{ + vector lines = get_line_details (0, breaks_.size () - 1, line_count); + Real page_h = page_height (1, false); // FIXME + SCM force_sym = ly_symbol2scm ("blank-last-page-force"); + Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0); + Spacing_result ret = space_systems_on_best_pages (lines, page_h, blank_force); + + bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom")); + bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom")); + + /* add in the line penalties */ + Real line_force = 0; + Real line_penalty = 0; + Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1); + + for (vsize i = 0; i < lines.size (); i++) + { + line_force += fabs (lines[i].force_); + line_penalty += lines[i].break_penalty_; + } + + if (ragged_all) + for (vsize i = 0; i < ret.force_.size () - 1; i++) + ret.force_[i] = min (0.0, ret.force_[i]); + if (ragged_all || ragged_last) + ret.force_.back () = min (0.0, ret.force_.back ()); + + ret.demerits_ = ret.force_[0] * ret.force_[0] * page_weighting; + for (vsize i = 1; i < ret.force_.size (); i++) + { + Real uniformity = fabs (ret.force_[i] - ret.force_[i-1]); + ret.demerits_ += (ret.force_[i] * ret.force_[i] + + uniformity * uniformity) * page_weighting; + } + ret.demerits_ += line_force + line_penalty; + return ret; +} + +/* The algorithm is as follows: + 1) break everything into its preferred number of lines + 2) decrease the number of lines until we've decreased + the number of pages + 3) increase the number of lines until we've increased + the number of pages + Take the best score we've found +*/ +SCM +Optimal_page_breaking::solve () +{ + vector ideal_line_count; + vector max_line_count; + vector min_line_count; + vector last_best_line_count; + vector best_line_count; + vsize last_line_total = 0; + + calc_system_count_bounds (0, breaks_.size () - 1, &min_line_count, &max_line_count); + ideal_line_count.resize (all_.size (), 1); + for (vsize i = 0; i < all_.size (); i++) + { + if (all_[i].pscore_) + ideal_line_count[i] = line_breaking_[i].get_best_solution (0, VPOS).size (); + last_line_total += ideal_line_count[i]; + } + + Spacing_result best_result = try_page_spacing (ideal_line_count); + vsize original_page_count = best_result.systems_per_page_.size (); + best_line_count = ideal_line_count; + last_best_line_count = ideal_line_count; + + Direction d = original_page_count > 1 ? DOWN : UP; + vector > div; + Spacing_result this_best_result; + do { + do { + vector blank; + + vector this_best_line_count; + this_best_result.demerits_ = infinity_f; + + last_line_total += d; + div.clear (); + divide_systems (last_line_total, + d == DOWN ? min_line_count : last_best_line_count, + d == DOWN ? last_best_line_count : max_line_count, + &div, &blank); + + for (vsize i = 0; i < div.size (); i++) + { + Spacing_result cur = try_page_spacing (div[i]); + if (cur.demerits_ < this_best_result.demerits_) + { + this_best_result = cur; + this_best_line_count = div[i]; + } + } + last_best_line_count = this_best_line_count; + + if (this_best_result.demerits_ < best_result.demerits_) + { + best_line_count = this_best_line_count; + best_result = this_best_result; + } + } while (div.size () && this_best_result.systems_per_page_.size () == original_page_count); + + /* we're finished decreasing system count, let's try raising it */ + last_best_line_count = ideal_line_count; + last_line_total = 0; + for (vsize i = 0; i < ideal_line_count.size (); i++) + last_line_total += ideal_line_count[i]; + + } while (flip (&d) != DOWN); + + SCM lines = make_lines (best_line_count); + SCM pages = make_pages (best_result.systems_per_page_, lines); + return pages; +} + +SCM +Optimal_page_breaking::make_lines (vector line_count) +{ + assert (line_count.size () == all_.size ()); + + SCM ret = SCM_EOL; + for (vsize i = 0; i < all_.size (); i++) + { + if (all_[i].pscore_) + { + vector line_brk = line_breaking_[i].get_solution (0, VPOS, line_count[i]); + System *sys = all_[i].pscore_->root_system (); + + sys->break_into_pieces (line_brk); + ret = scm_append (scm_list_2 (ret, scm_vector_to_list (sys->get_paper_systems ()))); + } + else + { + SCM l = scm_cons (all_[i].prob_->self_scm (), SCM_EOL); + ret = scm_append (scm_list_2 (ret, l)); + all_[i].prob_->unprotect (); + } + } + return ret; +} diff --git a/lily/page-breaking-scheme.cc b/lily/page-breaking-scheme.cc new file mode 100644 index 0000000000..2c28da917e --- /dev/null +++ b/lily/page-breaking-scheme.cc @@ -0,0 +1,30 @@ +/* + page-breaking-scheme.cc -- implement bindings to the various + page-breakers + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#include "paper-book.hh" +#include "page-turn-page-breaking.hh" +#include "optimal-page-breaking.hh" + +LY_DEFINE (ly_page_turn_breaking, "ly:page-turn-breaking", + 1, 0, 0, (SCM pb), + "Optimally break (pages and lines) the Paper_book PB such that page turns " + "only happen in specified places, returning its pages.") +{ + Page_turn_page_breaking b (unsmob_paper_book (pb)); + return b.solve (); +} + +LY_DEFINE (ly_optimal_breaking, "ly:optimal-breaking", + 1, 0, 0, (SCM pb), + "Optimally break (pages and lines) the Paper_book PB to minimise badness in " + "bother vertical and horizontal spacing.") +{ + Optimal_page_breaking b (unsmob_paper_book (pb)); + return b.solve (); +} diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc new file mode 100644 index 0000000000..e944aa601f --- /dev/null +++ b/lily/page-breaking.cc @@ -0,0 +1,314 @@ +/* + page-breaking.cc -- implement a superclass and utility + functions for use by various page-breaking algorithms + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#include "page-breaking.hh" + +#include "international.hh" +#include "item.hh" +#include "output-def.hh" +#include "page-spacing.hh" +#include "paper-book.hh" +#include "paper-score.hh" +#include "paper-system.hh" +#include "system.hh" +#include "warn.hh" + +System_spec::System_spec (Paper_score *ps, int break_count) +{ + pscore_ = ps; + prob_ = 0; + score_break_count_ = break_count; +} + +System_spec::System_spec (Prob *pb) +{ + pscore_ = 0; + prob_ = pb; + score_break_count_ = 0; +} + +System_spec::System_spec () +{ + pscore_ = 0; + prob_ = 0; + score_break_count_ = 0; +} + +/* for Page_breaking, the start index (when we are dealing with the stuff + between a pair of breakpoints) refers to the break_ index of the end of + the previous page. So the system index of the start of the current page + could either be the same as the end of the previous page or one more than + it. */ + +/* Turn a break index into the sys index that starts the next page */ +vsize Page_breaking::next_system (vsize start) const +{ + vsize sys = breaks_[start].sys_; + + if (sys == VPOS) /* beginning of the piece */ + return 0; + if (all_[sys].pscore_ && all_[sys].score_break_count_ > breaks_[start].score_break_) + return sys; /* the score overflows the previous page */ + return sys + 1; /* this page starts with a new sys */ +} + +Page_breaking::Page_breaking (Paper_book *pb, bool allow_intra_score_breaks) +{ + book_ = pb; + create_system_list (allow_intra_score_breaks); +} + +Page_breaking::~Page_breaking () +{ +} + +/* translate indices into breaks_ into start-end parameters for the line breaker */ +void +Page_breaking::line_breaker_args (vsize i, vsize *start, vsize *end) +{ + assert (all_[i].pscore_); + assert (next_system (*start) <= i && i <= breaks_[*end].sys_); + + vsize start_col = 0; + vsize end_col = VPOS; + + if (breaks_[*start].sys_ == i) + start_col = breaks_[*start].score_break_; + if (breaks_[*end].sys_ == i) + end_col = breaks_[*end].score_break_; + + assert (end_col && (end_col == VPOS || end_col <= all_[breaks_[*end].sys_].score_break_count_)); + *start = start_col; + *end = end_col; +} + +vector +Page_breaking::get_line_breaks (vsize i, vsize sys_count, vsize start, vsize end) +{ + assert (all_[i].pscore_); + line_breaker_args (i, &start, &end); + return line_breaking_[i].get_solution (start, end, sys_count); +} + +vector +Page_breaking::get_line_details (vsize start_break, vsize end_break, vector const &div) +{ + vector ret; + + for (vsize i = next_system (start_break); i <= breaks_[end_break].sys_; i++) + { + if (all_[i].pscore_) + { + vsize div_index = i - next_system (start_break); + vsize start = start_break; + vsize end = end_break; + + line_breaker_args (i, &start, &end); + vector l = line_breaking_[i].get_details (start, end, div[div_index]); + ret.insert (ret.end (), l.begin (), l.end ()); + } + else + ret.push_back (Line_details (all_[i].prob_)); + } + return ret; +} + +vsize +Page_breaking::get_min_systems (vsize i, vsize start, vsize end) +{ + line_breaker_args (i, &start, &end); + return line_breaking_[i].get_min_systems (start, end); +} + +vsize +Page_breaking::get_max_systems (vsize i, vsize start, vsize end) +{ + line_breaker_args (i, &start, &end); + return line_breaking_[i].get_max_systems (start, end); +} + +Real +Page_breaking::page_height (int page_num, bool last) +{ + SCM mod = scm_c_resolve_module ("scm page"); + SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height"); + SCM make_page = scm_c_module_lookup (mod, "make-page"); + + calc_height = scm_variable_ref (calc_height); + make_page = scm_variable_ref (make_page); + + SCM page = scm_apply_0 (make_page, scm_list_n ( + book_->self_scm (), + ly_symbol2scm ("page-number"), scm_from_int (page_num), + ly_symbol2scm ("is-last"), scm_from_bool (last), + SCM_UNDEFINED)); + SCM height = scm_apply_1 (calc_height, page, SCM_EOL); + return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space")); +} + +SCM +Page_breaking::make_pages (vector lines_per_page, SCM systems) +{ + SCM module = scm_c_resolve_module ("scm layout-page-layout"); + SCM make_page = scm_c_module_lookup (module, "make-page-from-systems"); + make_page = scm_variable_ref (make_page); + SCM book = book_->self_scm (); + bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom")); + bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom")); + SCM ret = SCM_EOL; + + for (vsize i = 0; i < lines_per_page.size (); i++) + { + SCM page_num = scm_from_int (i + 1); + SCM last = scm_from_bool (i == lines_per_page.size () - 1); + SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last)); + SCM line_count = scm_from_int (lines_per_page[i]); + SCM lines = scm_list_head (systems, line_count); + SCM page = scm_apply_0 (make_page, + scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED)); + + ret = scm_cons (page, ret); + systems = scm_list_tail (systems, line_count); + } + return scm_reverse (ret); +} + +/* if allow_intra_score_breaks is false, that doesn't necessarily mean that there will + be no page turns in the middle of a score, only that we don't give special + consideration to any internal part of a score. + + Corollary: if allow_intra_score_breaks is false, any \pageTurn or \noPageTurn commands + in the middle of a score will be ignored. +*/ +void +Page_breaking::create_system_list (bool allow_intra_score_breaks) +{ + breaks_.push_back (Break_position ()); + + SCM specs = book_->get_system_specs (); + for (SCM s = specs; s != SCM_EOL; s = scm_cdr (s)) + { + if (Paper_score *ps = dynamic_cast (unsmob_music_output (scm_car (s)))) + { + /* add a breakpoint at the end of the last score, if necessary */ + if (all_.size () && all_.back ().pscore_) + breaks_.push_back (Break_position (all_.size () - 1, + all_.back ().score_break_count_)); + + vector score_brk; + if (allow_intra_score_breaks) + score_brk = find_page_break_indices (ps); + + all_.push_back (System_spec (ps, score_brk.size () + 1)); + + for (vsize i = 0; i < score_brk.size(); i++) + breaks_.push_back (Break_position (all_.size () - 1, i + 1)); + + /* include a line breaker at the start of the score */ + score_brk.insert (score_brk.begin (), 0); + line_breaking_.push_back (Constrained_breaking (score_brk)); + line_breaking_.back ().set_pscore (ps); + } + else + { + Prob *pb = unsmob_prob (scm_car (s)); + assert (pb); + + pb->protect (); + // ignore penalties (from break-before) in favour of using \pageBreak at the + // end of the score + if (all_.size () && all_.back ().pscore_) + breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_)); + all_.push_back (System_spec (pb)); + line_breaking_.push_back (Constrained_breaking ()); + } + } + + /* add the ending breakpoint */ + if (all_.back ().pscore_) + breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_)); + else + breaks_.push_back (Break_position (all_.size () - 1)); +} + +vector +Page_breaking::find_page_break_indices (Paper_score *pscore) +{ + vector all = pscore->root_system ()->columns (); + vector ret; + + /* we don't include breaks at the beginning and end */ + for (vsize i = 0; i < all.size () - 1; i++) + if (scm_is_symbol (all[i]->get_property ("page-turn-permission"))) + ret.push_back(i); + + return ret; +} + +void +Page_breaking::calc_system_count_bounds (vsize start, vsize end, + vector *min, + vector *max) +{ + for (vsize i = next_system (start); i <= breaks_[end].sys_; i++) + { + if (all_[i].pscore_) + { + min->push_back (get_min_systems (i, start, end)); + max->push_back (get_max_systems (i, start, end)); + } + else + { + min->push_back (1); + max->push_back (1); + } + } +} + +/* calculate all possible ways of dividing system_count between the System_specs */ +void +Page_breaking::divide_systems (vsize system_count, + vector const &min_sys, + vector const &max_sys, + vector > *result, + vector *cur_division) +{ + vsize my_index = cur_division->size (); + vsize others_min = 0; + vsize others_max = 0; + + for (vsize i = my_index + 1; i < min_sys.size (); i++) + { + others_min += min_sys[i]; + others_max += max_sys[i]; + } + others_max = min (others_max, system_count); + vsize real_min = max (min_sys[my_index], system_count - others_max); + vsize real_max = min (max_sys[my_index], system_count - others_min); + + if (real_min > real_max || real_min <= 0) + { + /* this should never happen within a recursive call. If it happens + at all, it means that we were called with an unsolvable problem + and we should return an empty result */ + assert (my_index == 0); + return; + } + + for (vsize i = real_min; i <= real_max; i++) + { + cur_division->push_back (i); + if (my_index == min_sys.size () - 1) + result->push_back (*cur_division); + else + divide_systems (system_count - i, min_sys, max_sys, result, cur_division); + cur_division->pop_back (); + } +} + diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc new file mode 100644 index 0000000000..32025a7078 --- /dev/null +++ b/lily/page-spacing.cc @@ -0,0 +1,445 @@ +/* + page-spacing.cc - implement routines for spacing + systems vertically on pages + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#include "page-spacing.hh" +#include "matrix.hh" + +/* + A much simplified rods-and-springs problem. + */ +struct Page_spacing +{ + Real force_; + Real page_height_; + Real rod_height_; + Real spring_len_; + Real inverse_spring_k_; + + Line_details last_line_; + + Page_spacing (Real page_height) + { + page_height_ = page_height; + clear (); + } + + void calc_force (); + + void append_system (const Line_details &line); + void prepend_system (const Line_details &line); + void clear (); +}; + +void +Page_spacing::calc_force () +{ + if (rod_height_ + last_line_.bottom_padding_ >= page_height_ || !inverse_spring_k_) + force_ = infinity_f; + else + force_ = (page_height_ - rod_height_ - last_line_.bottom_padding_ - spring_len_) / inverse_spring_k_; +} + +void +Page_spacing::append_system (const Line_details &line) +{ + rod_height_ += last_line_.padding_; + + rod_height_ += line.extent_.length (); + spring_len_ += line.space_; + inverse_spring_k_ += line.inverse_hooke_; + + last_line_ = line; + + calc_force (); +} + +void +Page_spacing::prepend_system (const Line_details &line) +{ + if (rod_height_) + rod_height_ += line.padding_; + else + last_line_ = line; + + rod_height_ += line.extent_.length (); + spring_len_ += line.space_; + inverse_spring_k_ += line.inverse_hooke_; + + calc_force (); +} + +void +Page_spacing::clear () +{ + force_ = rod_height_ = spring_len_ = 0; + inverse_spring_k_ = 0; +} + +/* for each forbidden page break, merge the systems around it into one system. */ +static vector +compress_lines (const vector &orig) +{ + vector ret; + + for (vsize i = 0; i < orig.size (); i++) + { + if (i < orig.size () - 1 && orig[i].page_permission_ == SCM_EOL) + { + Line_details compressed = orig[i+1]; + compressed.extent_[DOWN] = orig[i].extent_[DOWN]; + compressed.extent_[UP] = orig[i].extent_[UP] + orig[i+1].extent_.length () + orig[i].padding_; + compressed.space_ += orig[i].space_; + compressed.inverse_hooke_ += orig[i].inverse_hooke_; + + /* we don't need the force_ field for the vertical spacing, + so we use force_ = -1 to signal that the line was compressed + (and force_ = +1 otherwise). + This makes uncompression much easier. */ + compressed.force_ = -1; + ret.push_back (compressed); + i++; + } + else + { + ret.push_back (orig[i]); + ret.back ().force_ = 1; + } + } + return ret; +} + +/* translate the number of systems-per-page into something meaningful for + the uncompressed lines. +*/ +static vector +uncompress_solution (vector const &systems_per_page, + vector const &compressed) +{ + vector ret; + vsize start_sys = 0; + + for (vsize i = 0; i < systems_per_page.size (); i++) + { + int compressed_count = 0; + for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++) + if (compressed[j].force_ < 0) + compressed_count++; + + ret.push_back (systems_per_page[i] + compressed_count); + start_sys += systems_per_page[i]; + } + return ret; +} + +/* the cases for page_count = 1 or 2 can be done in O(n) time. Since they + are by far the most common cases, we have special functions for them */ +static Spacing_result +space_systems_on_1_page (vector const &lines, Real page_height) +{ + Page_spacing space (page_height); + Spacing_result ret; + + for (vsize i = 0; i < lines.size (); i++) + space.append_system (lines[i]); + + ret.systems_per_page_.push_back (lines.size ()); + ret.force_.push_back (space.force_); + ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_; + ret.demerits_ = ret.force_.back () * ret.force_.back () + ret.penalty_; + + return ret; +} + +static Spacing_result +space_systems_on_2_pages (vector const &lines, Real page_height) +{ + /* if there is a forced break, this reduces to 2 1-page problems */ + for (vsize i = 0; i < lines.size () - 1; i++) + if (lines[i].page_permission_ == ly_symbol2scm ("force")) + { + vector lines1 (lines.begin (), lines.begin () + i + 1); + vector lines2 (lines.begin () + i + 1, lines.end ()); + Spacing_result p1 = space_systems_on_1_page (lines1, page_height); + Spacing_result p2 = space_systems_on_1_page (lines2, page_height); + + p1.systems_per_page_.push_back (p2.systems_per_page_[0]); + p1.force_.push_back (p2.force_[0]); + p1.penalty_ += p2.penalty_ - lines[i].turn_penalty_; + p1.demerits_ += p2.demerits_ - lines[i].turn_penalty_; + return p1; + } + + vector page1_force; + vector page2_force; + Page_spacing page1 (page_height); + Page_spacing page2 (page_height); + + page1_force.resize (lines.size () - 1, infinity_f); + page2_force.resize (lines.size () - 1, infinity_f); + + for (vsize i = 0; i < page1_force.size (); i++) + { + page1.append_system (lines[i]); + page2.prepend_system (lines[lines.size () - 1 - i]); + page1_force[i] = page1.force_; + page2_force[page2_force.size () - 1 - i] = page2.force_; + } + + vsize best_sys_count = 1; + Real best_demerits = infinity_f; + for (vsize i = 0; i < page1_force.size (); i++) + { + Real dem = page1_force[i] * page1_force[i] + + page2_force[i] * page2_force[i] + + lines[i+1].page_penalty_ + + lines.back ().page_penalty_ + lines.back ().turn_penalty_; + if (dem < best_demerits) + { + best_demerits = dem; + best_sys_count = i+1; + } + } + + Spacing_result ret; + ret.systems_per_page_.push_back (best_sys_count); + ret.systems_per_page_.push_back (lines.size () - best_sys_count); + ret.force_.push_back (page1_force[best_sys_count-1]); + ret.force_.push_back (page2_force[best_sys_count-1]); + ret.penalty_ = lines[best_sys_count-1].page_penalty_ + + lines.back ().page_penalty_ + + lines.back ().turn_penalty_; + ret.demerits_ = best_demerits; + + return ret; +} + +/* for page_count > 2, we use a dynamic algorithm similar to + constrained-breaking -- we have a class that stores the intermediate + calculations so they can be reused for querying different page counts. +*/ + +class Page_spacer +{ +public: + Page_spacer (vector const &lines, Real page_height); + Spacing_result solve (vsize page_count); + +private: + struct Page_spacing_node + { + Page_spacing_node () + { + demerits_ = infinity_f; + force_ = infinity_f; + penalty_ = infinity_f; + prev_ = VPOS; + } + + Real demerits_; + Real force_; + Real penalty_; + vsize prev_; + }; + + Real page_height_; + vector lines_; + Matrix state_; + vsize max_page_count_; + + void resize (vsize page_count); + bool calc_subproblem (vsize page, vsize lines); +}; + +Page_spacer::Page_spacer (vector const &lines, Real page_height) + : lines_ (lines) +{ + page_height_ = page_height; + max_page_count_ = 0; +} + +Spacing_result +Page_spacer::solve (vsize page_count) +{ + if (page_count > max_page_count_) + resize (page_count); + + Spacing_result ret; + ret.force_.resize (page_count); + ret.systems_per_page_.resize (page_count); + + vsize system = lines_.size () - 1; + + ret.penalty_ = state_.at (system, page_count-1).penalty_ + + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_; + + for (vsize p = page_count; p--;) + { + assert (system != VPOS); + + Page_spacing_node const &ps = state_.at (system, p); + ret.force_[p] = ps.force_; + ret.demerits_ += ps.force_ * ps.force_; + if (p == 0) + ret.systems_per_page_[p] = system + 1; + else + ret.systems_per_page_[p] = system - ps.prev_; + system = ps.prev_; + } + ret.demerits_ += ret.penalty_; + return ret; +} + +void +Page_spacer::resize (vsize page_count) +{ + assert (page_count > 0); + + if (max_page_count_ >= page_count) + return; + + state_.resize (lines_.size (), page_count, Page_spacing_node ()); + for (vsize page = max_page_count_; page < page_count; page++) + for (vsize line = page; line < lines_.size (); line++) + if (!calc_subproblem (page, line)) + break; + + max_page_count_ = page_count; +} + +bool +Page_spacer::calc_subproblem (vsize page, vsize line) +{ + Page_spacing space (page_height_); + Page_spacing_node &cur = state_.at (line, page); + + for (vsize page_start = line+1; page_start > page && page_start--;) + { + Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0; + + space.prepend_system (lines_[page_start]); + if (isinf (space.force_)) + break; + + if (page == 0 && page_start > 0) + continue; + + Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0); + Real penalty = 0; + if (page_start > 0) + penalty = lines_[page_start-1].page_penalty_ + + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0; + + dem += penalty; + if (dem < cur.demerits_) + { + cur.demerits_ = dem; + cur.force_ = space.force_; + cur.penalty_ = penalty + (prev ? prev->penalty_ : 0); + cur.prev_ = page_start - 1; + } + } + return !isinf (cur.demerits_); +} + +static vsize +min_page_count (vector const &lines, Real page_height) +{ + vsize ret = 1; + Real cur_rod_height = 0; + + for (vsize i = 0; i < lines.size (); i++) + { + Real next_height = cur_rod_height + lines[i].extent_.length () + + ((i > 0 && cur_rod_height > 0) ? lines[i-1].padding_: 0); + + if ((next_height > page_height && cur_rod_height > 0) + || (i > 0 && lines[i-1].page_permission_ == ly_symbol2scm ("force"))) + { + ret++; + cur_rod_height = lines[i].extent_.length (); + } + else + cur_rod_height = next_height; + } + return ret; +} + +Spacing_result +space_systems_on_min_pages (vector const &lines, + Real page_height, + Real odd_pages_penalty) +{ + vector compressed_lines = compress_lines (lines); + vsize min_p_count = min_page_count (compressed_lines, page_height); + Spacing_result ret; + + if (min_p_count == 1) + { + Spacing_result candidate1 = space_systems_on_1_page (compressed_lines, page_height); + candidate1.force_.back () += odd_pages_penalty; + candidate1.demerits_ += odd_pages_penalty; + if (compressed_lines.size () == 1) + ret = candidate1; + else + { + Spacing_result candidate2 = space_systems_on_2_pages (compressed_lines, page_height); + ret = (candidate1.demerits_ < candidate2.demerits_) ? + candidate1 : candidate2; + } + } + else if (min_p_count == 2) + ret = space_systems_on_2_pages (compressed_lines, page_height); + else + { + Page_spacer ps (compressed_lines, page_height); + Spacing_result candidate1 = ps.solve (min_p_count); + if (min_p_count % 2 == 0) + ret = candidate1; + else + { + candidate1.force_.back () += odd_pages_penalty; + candidate1.demerits_ += odd_pages_penalty; + + if (min_p_count == compressed_lines.size ()) + ret = candidate1; + else + { + Spacing_result candidate2 = ps.solve (min_p_count + 1); + ret = (candidate1.demerits_ < candidate2.demerits_) ? + candidate1 : candidate2; + } + } + } + ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines); + return ret; +} + +Spacing_result +space_systems_on_best_pages (vector const &lines, + Real page_height, + Real odd_pages_penalty) +{ + vector compressed_lines = compress_lines (lines); + vsize min_p_count = min_page_count (compressed_lines, page_height); + + Page_spacer ps (compressed_lines, page_height); + Spacing_result best = ps.solve (min_p_count); + best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0; + + for (vsize i = min_p_count+1; i <= compressed_lines.size (); i++) + { + Spacing_result cur = ps.solve (i); + cur.demerits_ += (i % 2) ? odd_pages_penalty : 0; + if (cur.demerits_ < best.demerits_) + best = cur; + } + + best.systems_per_page_ = uncompress_solution (best.systems_per_page_, compressed_lines); + return best; +} diff --git a/lily/page-turn-engraver.cc b/lily/page-turn-engraver.cc new file mode 100644 index 0000000000..1a2bf5f5b4 --- /dev/null +++ b/lily/page-turn-engraver.cc @@ -0,0 +1,125 @@ +/* + page-turn-engraver.cc -- implement Page_turn_engraver + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#include "engraver.hh" + +#include "context.hh" +#include "duration.hh" +#include "grob.hh" +#include "international.hh" +#include "moment.hh" +#include "warn.hh" + +class Page_turn_engraver : public Engraver +{ + Moment rest_begin_; + Moment repeat_begin_; + Moment note_end_; + Rational repeat_begin_rest_length_; + + Real penalty (Rational rest_len); + +protected: + DECLARE_ACKNOWLEDGER (note_head); + +public: + TRANSLATOR_DECLARATIONS (Page_turn_engraver); + void stop_translation_timestep (); +}; + +Page_turn_engraver::Page_turn_engraver () +{ + repeat_begin_ = Moment (-1); + repeat_begin_rest_length_ = 0; + rest_begin_ = 0; + note_end_ = 0; +} + +Real +Page_turn_engraver::penalty (Rational rest_len) +{ + Rational min_turn = robust_scm2moment (get_property ("minPageTurnLength"), Moment (1)).main_part_; + + return (rest_len < min_turn) ? infinity_f : 0; +} + +void +Page_turn_engraver::acknowledge_note_head (Grob_info gi) +{ + SCM dur_log_scm = gi.grob ()->get_property ("duration-log"); + if (!scm_is_number (dur_log_scm)) + return; + + int dur_log = scm_to_int (dur_log_scm); + int dot_count = robust_scm2int (gi.grob ()->get_property ("dot-count"), 0); + + if (rest_begin_ < now_mom ()) + { + Real pen = penalty ((now_mom () - rest_begin_).main_part_); + if (!isinf (pen)) + { + SCM val = scm_cons (rest_begin_.smobbed_copy (), scm_from_double (pen)); + context ()->get_score_context ()->set_property ("allowPageTurn", val); + } + } + + if (rest_begin_ <= repeat_begin_) + repeat_begin_rest_length_ = (now_mom () - repeat_begin_).main_part_; + note_end_ = now_mom () + Moment (Duration (dur_log, dot_count).get_length ()); +} + +void +Page_turn_engraver::stop_translation_timestep () +{ + /* C&P from Repeat_acknowledge_engraver */ + SCM cs = get_property ("repeatCommands"); + bool start = false; + bool end = false; + + for (; scm_is_pair (cs); cs = scm_cdr (cs)) + { + SCM command = scm_car (cs); + if (command == ly_symbol2scm ("start-repeat")) + start = true; + else if (command == ly_symbol2scm ("end-repeat")) + end = true; + } + + if (end && repeat_begin_.main_part_ >= Moment (0)) + { + Real pen = penalty ((now_mom () - rest_begin_).main_part_ + repeat_begin_rest_length_); + Moment *m = unsmob_moment (get_property ("minimumRepeatLengthForPageTurn")); + if (m && *m > (now_mom () - repeat_begin_)) + pen = infinity_f; + if (pen > 0) + { + SCM val = scm_cons (repeat_begin_.smobbed_copy (), scm_from_double (pen)); + context ()->get_score_context ()->set_property ("revokePageTurns", val); + } + repeat_begin_ = Moment (-1); + } + if (start) + { + repeat_begin_ = now_mom (); + repeat_begin_rest_length_ = 0; + } + rest_begin_ = note_end_; +} + +#include "translator.icc" + +ADD_ACKNOWLEDGER (Page_turn_engraver, note_head); +ADD_TRANSLATOR (Page_turn_engraver, + /* doc */ "Decide where page turns are allowed to go", + /* create */ "", + /* accept */ "", + /* read */ "", + /* write */ + "allowPageTurn " + "revokePageTurns " + ); diff --git a/lily/page-turn-page-breaking.cc b/lily/page-turn-page-breaking.cc new file mode 100644 index 0000000000..338fe4a54d --- /dev/null +++ b/lily/page-turn-page-breaking.cc @@ -0,0 +1,274 @@ +/* + page-turn-page-breaking.cc -- implement Page_turn_page_breaking + + source file of the GNU LilyPond music typesetter + + (c) 2006 Joe Neeman +*/ + +#include "page-turn-page-breaking.hh" + +#include "international.hh" +#include "item.hh" +#include "output-def.hh" +#include "page-spacing.hh" +#include "paper-book.hh" +#include "paper-score.hh" +#include "paper-system.hh" +#include "system.hh" +#include "warn.hh" + +Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb) + : Page_breaking (pb, true) +{ +} + +Page_turn_page_breaking::~Page_turn_page_breaking () +{ +} + +Real +Page_turn_page_breaking::calc_demerits (const Break_node &me) +{ + 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) +{ + 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); + + 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.penalty_ = result.penalty_; + ret.div_ = div; + 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; + } + return ret; +} + +void +Page_turn_page_breaking::calc_subproblem (vsize ending_breakpoint) +{ + vsize end = ending_breakpoint + 1; + Break_node best; + Break_node cur; + Break_node this_start_best; + vsize prev_best_system_count = 0; + + for (vsize start = end; start--;) + { + if (start > 0 && best.demerits_ < state_[start-1].demerits_) + continue; + + int p_num = 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); + } + + 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]; + } + } + + for (vsize i = 0; i < min_systems.size (); i++) + { + min_system_count += min_systems[i]; + max_system_count += max_systems[i]; + } + + bool ok_page = true; + + /* 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++) + { + vector > div; + vector blank; + bool found = false; + divide_systems (sys_count, min_systems, max_systems, &div, &blank); + + for (vsize d = 0; d < div.size (); d++) + { + vector line = get_line_details (start, end, div[d]); + + cur = put_systems_on_pages (start, end, line, div[d], 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))) + { + ok_page = false; + break; + } + cur.demerits_ = calc_demerits (cur); + + if (cur.demerits_ < this_start_best.demerits_) + { + found = true; + this_start_best = cur; + prev_best_system_count = sys_count; + } + } + if (!found && this_start_best.too_many_lines_) + break; + } + if (isinf (this_start_best.demerits_)) + { + assert (!isinf (best.demerits_) && start < end - 1); + break; + } + if (this_start_best.demerits_ < best.demerits_) + best = this_start_best; + } + state_.push_back (best); +} + +SCM +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++) + { + calc_subproblem (i); + progress_indication (string ("[") + to_string (i + 1) + "]"); + } + progress_indication ("\n"); + + vector breaking; + int i = state_.size () - 1; + while (i >= 0) + { + breaking.push_back (state_[i]); + i = state_[i].prev_; + } + reverse (breaking); + + message (_ ("Drawing systems...")); + SCM systems = make_lines (&breaking); + return make_pages (breaking, systems); +} + +/* do the line breaking in all the scores and return a big list of systems */ +SCM +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 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); + } + } + return ret; +} + +SCM +Page_turn_page_breaking::make_pages (vector const &soln, SCM systems) +{ + 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]); + + if (i > 0 && i < soln.size () - 1 && soln[i].page_count_ % 2) + /* add a blank page */ + lines_per_page.push_back (0); + } + return Page_breaking::make_pages (lines_per_page, systems); +} diff --git a/lily/paper-book.cc b/lily/paper-book.cc index 8ef498aaec..b91129b5d2 100644 --- a/lily/paper-book.cc +++ b/lily/paper-book.cc @@ -381,7 +381,7 @@ Paper_book::pages () pages_ = SCM_EOL; SCM proc = paper_->c_variable ("page-breaking"); - pages_ = scm_apply_0 (proc, scm_list_2 (systems (), self_scm ())); + pages_ = scm_apply_0 (proc, scm_list_1(self_scm ())); return pages_; } diff --git a/lily/paper-column-engraver.cc b/lily/paper-column-engraver.cc index d3602d732a..32bb0b2fdd 100644 --- a/lily/paper-column-engraver.cc +++ b/lily/paper-column-engraver.cc @@ -7,6 +7,8 @@ */ #include "paper-column-engraver.hh" +#include "system.hh" +#include "international.hh" #include "axis-group-interface.hh" #include "context.hh" #include "item.hh" @@ -26,9 +28,9 @@ Paper_column_engraver::Paper_column_engraver () musical_column_ = 0; breaks_ = 0; system_ = 0; - first_ = true; + last_special_barline_column_ = 0; last_breakable_column_ = 0; - last_breakable_moment_ = Moment (-1); + first_ = true; } void @@ -84,6 +86,7 @@ Paper_column_engraver::acknowledge_staff_spacing (Grob_info gi) ly_symbol2scm ("spacing-wishes"), gi.grob ()); } + void Paper_column_engraver::acknowledge_note_spacing (Grob_info gi) { @@ -167,6 +170,56 @@ Paper_column_engraver::process_music () } } +/* return either + - the last column with a special (ie. not "|" or "") barline + - the last column + after the given moment +*/ +Paper_column* +Paper_column_engraver::find_turnable_column (Moment after_this) +{ + if (last_special_barline_column_) + { + Moment m = *unsmob_moment (last_special_barline_column_->get_property ("when")); + if (m >= after_this) + return last_special_barline_column_; + } + if (last_breakable_column_) + { + Moment m = *unsmob_moment (last_breakable_column_->get_property ("when")); + if (m >= after_this) + return last_breakable_column_; + } + return 0; +} + +void +Paper_column_engraver::revoke_page_turns (Moment after_this, Real new_penalty) +{ + if (!page_turnable_columns_.size ()) + return; + + for (vsize i = page_turnable_columns_.size () - 1; i--;) + { + Paper_column *col = page_turnable_columns_[i]; + Moment mom = *unsmob_moment (col->get_property ("when")); + if (mom >= after_this) + { + if (isinf (new_penalty)) + { + col->del_property ( ly_symbol2scm ("page-turn-permission")); + page_turnable_columns_.erase (page_turnable_columns_.begin () + i); + } + else + { + Real prev_pen = robust_scm2double (col->get_property ("page-turn-penalty"), 0); + if (new_penalty > prev_pen) + col->set_property ("page-turn-penalty", scm_from_double (new_penalty)); + } + } + } +} + void Paper_column_engraver::stop_translation_timestep () { @@ -192,25 +245,50 @@ Paper_column_engraver::stop_translation_timestep () { breaks_++; last_breakable_column_ = command_column_; - last_breakable_moment_ = now_mom (); + + SCM which_bar = get_property ("whichBar"); + if (scm_is_string (which_bar)) + { + string bar = ly_scm2string (which_bar); + if (bar != "" && bar != "|") + last_special_barline_column_ = command_column_; + } + if (! (breaks_%8)) progress_indication ("[" + to_string (breaks_) + "]"); } SCM page_br = get_property ("allowPageTurn"); - if (scm_is_pair (page_br) && last_breakable_moment_ >= Rational (0)) + if (scm_is_pair (page_br) && last_breakable_column_) { SCM pen = scm_cdr (page_br); Moment *m = unsmob_moment (scm_car (page_br)); - if (m && scm_is_number (pen) && *m <= last_breakable_moment_) + if (m) { - last_breakable_column_->set_property ("page-turn-permission", ly_symbol2scm ("allow")); - last_breakable_column_->set_property ("page-turn-penalty", pen); + Paper_column *turn = find_turnable_column (*m); + if (turn) + { + turn->set_property ("page-turn-permission", ly_symbol2scm ("allow")); + turn->set_property ("page-turn-penalty", pen); + page_turnable_columns_.push_back (turn); + } } } + /* The page-turn-engraver is allowed to change its mind and revoke previously-allowed + page turns (for example if there is a volta repeat where a turn is inconvenient) */ + SCM revokes = get_property ("revokePageTurns"); + if (scm_is_pair (revokes)) + { + Moment *start = unsmob_moment (scm_car (revokes)); + Real pen = robust_scm2double (scm_cdr (revokes), infinity_f); + if (start) + revoke_page_turns (*start, pen); + } + context ()->get_score_context ()->unset_property (ly_symbol2scm ("forbidBreak")); context ()->get_score_context ()->unset_property (ly_symbol2scm ("allowPageTurn")); + context ()->get_score_context ()->unset_property (ly_symbol2scm ("revokePageTurns")); first_ = false; break_events_.clear (); @@ -247,9 +325,13 @@ ADD_TRANSLATOR (Paper_column_engraver, /* accept */ "break-event", /* read */ "forbidBreak " - "allowPageTurn", + "allowPageTurn " + "revokePageTurns " + , /* write */ "forbidBreak " "allowPageTurn " + "revokePageTurns " "currentCommandColumn " - "currentMusicalColumn"); + "currentMusicalColumn " + ); diff --git a/ly/declarations-init.ly b/ly/declarations-init.ly index 027849b88c..659629a021 100644 --- a/ly/declarations-init.ly +++ b/ly/declarations-init.ly @@ -46,6 +46,7 @@ pageTurn = #(make-event-chord (list (make-music 'PageBreakEvent 'break-permission 'force) (make-music 'PageTurnEvent 'break-permission 'force))) noPageTurn = #(make-event-chord (list (make-music 'PageTurnEvent 'break-permission '()))) +allowPageTurn = #(make-event-chord (list (make-music 'PageTurnEvent 'break-permission 'allow))) stopStaff = #(make-event-chord (list (make-span-event 'StaffSpanEvent STOP))) startStaff = #(make-event-chord (list (make-span-event 'StaffSpanEvent START))) diff --git a/ly/paper-defaults.ly b/ly/paper-defaults.ly index 2620cfc1c1..9fae0cabd5 100644 --- a/ly/paper-defaults.ly +++ b/ly/paper-defaults.ly @@ -76,6 +76,12 @@ %% ragged-last-bottom= ##t + %% + %% settings for the page breaker + %% + blank-last-page-force = 0 + blank-page-force = 10 + #(define font-defaults '((font-encoding . fetaMusic))) diff --git a/scm/define-context-properties.scm b/scm/define-context-properties.scm index 837238ab58..af87ed9220 100644 --- a/scm/define-context-properties.scm +++ b/scm/define-context-properties.scm @@ -339,6 +339,7 @@ whether they are processed in this context.") (restNumberThreshold ,number? "If a multimeasure rest has more measures than this, a number is printed. ") + (revokePageTurns ,pair? "Signals to the paper-column-engraver to revoke (or increase the penalties for) all the page turns within a time interval. Used to disable page turns that occur within an unturnable volta repeat.") (shapeNoteStyles ,vector? "Vector of symbols, listing style for each note head relative to the tonic (qv.) of the scale.") (shortInstrumentName ,markup? "See @code{instrument}") diff --git a/scm/layout-page-layout.scm b/scm/layout-page-layout.scm index 8756062384..215b5003d0 100644 --- a/scm/layout-page-layout.scm +++ b/scm/layout-page-layout.scm @@ -13,7 +13,7 @@ #:use-module (scm page) #:use-module (scm layout-page-dump) #:use-module (lily) - #:export (post-process-pages optimal-page-breaks)) + #:export (post-process-pages optimal-page-breaks make-page-from-systems)) (define (post-process-pages layout pages) (if (ly:output-def-lookup layout 'write-page-layout #f) @@ -160,6 +160,20 @@ is what have collected so far, and has ascending page numbers." (+ y topskip)) (cdr space-result))))) +(define (make-page-from-systems paper-book lines page-number ragged? last?) + (let* + ((page (make-page + paper-book + 'lines lines + 'page-number page-number + 'is-last last?)) + (height (page-printable-height page)) + (posns (if (> (length lines) 0) + (cdr (space-systems height lines ragged? (ly:paper-book-paper paper-book))) + '()))) + (page-set-property! page 'configuration posns) + page)) + (define (walk-paths done-lines best-paths current-lines last? current-best paper-book page-alist) "Return the best optimal-page-break-node that contains @@ -170,8 +184,7 @@ corresponding to DONE-LINES. CURRENT-BEST is the best result sofar, or #f." (let* ((paper (ly:paper-book-paper paper-book)) (this-page (make-page - page-alist - 'paper-book paper-book + paper-book 'is-last last? 'page-number (if (null? best-paths) (ly:output-def-lookup paper 'first-page-number) @@ -258,9 +271,10 @@ DONE." paper-book page-alist)))) -(define-public (optimal-page-breaks lines paper-book) +(define-public (optimal-page-breaks paper-book) "Return pages as a list starting with 1st page. Each page is a 'page Prob." (let* ((paper (ly:paper-book-paper paper-book)) + (lines (ly:paper-book-systems paper-book)) (page-alist (layout->page-init paper)) (force-equalization-factor (ly:output-def-lookup paper 'verticalequalizationfactor 0.3))) diff --git a/scm/page.scm b/scm/page.scm index 258589ae53..802c92ca17 100644 --- a/scm/page.scm +++ b/scm/page.scm @@ -37,10 +37,11 @@ (define page-module (current-module)) -(define (make-page init . args) +(define (make-page paper-book . args) (let* ((p (apply ly:make-prob (append - (list 'page init) + (list 'page (layout->page-init (ly:paper-book-paper paper-book)) + 'paper-book paper-book) args)))) (page-set-property! p 'head-stencil (page-header p)) @@ -114,8 +115,8 @@ (define (annotate-space-left page) (let* - ((p-book (page-property page 'paper-book)) - (layout (ly:paper-book-paper p-book)) + ((paper-book (page-property page 'paper-book)) + (layout (ly:paper-book-paper paper-book)) (arrow (annotate-y-interval layout "space left" (cons (- 0.0 @@ -193,10 +194,9 @@ (define (page-header-or-footer page dir) (let* - ((p-book (page-property page 'paper-book)) - (layout (ly:paper-book-paper p-book)) - (scopes (ly:paper-book-scopes p-book)) - (lines (page-lines page)) + ((paper-book (page-property page 'paper-book)) + (layout (ly:paper-book-paper paper-book)) + (scopes (ly:paper-book-scopes paper-book)) (number (page-page-number page)) (last? (page-property page 'is-last)) ) @@ -250,10 +250,10 @@ create offsets. (page-translate-systems page) (let* - ((p-book (page-property page 'paper-book)) + ((paper-book (page-property page 'paper-book)) (prop (lambda (sym) (page-property page sym))) - (layout (ly:paper-book-paper p-book)) - (scopes (ly:paper-book-scopes p-book)) + (layout (ly:paper-book-paper paper-book)) + (scopes (ly:paper-book-scopes paper-book)) (lines (page-lines page)) (number (page-page-number page)) @@ -386,8 +386,8 @@ create offsets. (define (calc-printable-height page) "Printable area for music and titles; matches default-page-make-stencil." (let* - ((p-book (page-property page 'paper-book)) - (layout (ly:paper-book-paper p-book)) + ((paper-book (page-property page 'paper-book)) + (layout (ly:paper-book-paper paper-book)) (h (- (ly:output-def-lookup layout 'paper-height) (ly:output-def-lookup layout 'top-margin) (ly:output-def-lookup layout 'bottom-margin))) -- 2.39.5