From 298ee5a34af5f84b903e8d5b11854148e117af81 Mon Sep 17 00:00:00 2001 From: Nicolas Sceaux Date: Mon, 16 Jul 2007 15:04:33 +0200 Subject: [PATCH] New page breaking function: ly:minimal-breaking, which first computes line breaks without considering page breaking, then fills pages with as many lines as possible. --- Documentation/topdocs/NEWS.tely | 4 ++ Documentation/user/spacing.itely | 29 +++++++-- .../page-minimal-page-breaking-last-page.ly | 23 +++++++ .../regression/page-minimal-page-breaking.ly | 35 +++++++++++ lily/include/minimal-page-breaking.hh | 26 ++++++++ lily/include/page-breaking.hh | 2 + lily/include/page-spacing.hh | 2 +- lily/minimal-page-breaking.cc | 47 +++++++++++++++ lily/page-breaking-scheme.cc | 11 ++++ lily/page-breaking.cc | 60 +++++++++++++++++++ lily/page-spacing.cc | 7 +++ 11 files changed, 239 insertions(+), 7 deletions(-) create mode 100644 input/regression/page-minimal-page-breaking-last-page.ly create mode 100644 input/regression/page-minimal-page-breaking.ly create mode 100644 lily/include/minimal-page-breaking.hh create mode 100644 lily/minimal-page-breaking.cc diff --git a/Documentation/topdocs/NEWS.tely b/Documentation/topdocs/NEWS.tely index be96ec757d..e882827a9d 100644 --- a/Documentation/topdocs/NEWS.tely +++ b/Documentation/topdocs/NEWS.tely @@ -65,6 +65,10 @@ which scares away people. @end ignore +@item +A new page breaking function, @code{ly:minimal-breaking}, is dedicated +to books with many pages or a lot of texts. + @item A table of contents is included using @code{\markuplines \table-of-contents}. Elements are added to it using the @code{\tocItem} command. diff --git a/Documentation/user/spacing.itely b/Documentation/user/spacing.itely index 371c42214c..ca9bb618c5 100644 --- a/Documentation/user/spacing.itely +++ b/Documentation/user/spacing.itely @@ -557,6 +557,7 @@ The pairs * Page breaking:: * Optimal page breaking:: * Optimal page turning:: +* Minimal page breaking:: * Explicit breaks:: * Using an extra voice for breaks:: @end menu @@ -655,11 +656,11 @@ a line break. The @code{\pageBreak} and @code{\noPageBreak} commands may also be inserted at top-level, between scores and top-level markups. -Page breaks are computed by the @code{page-breaking} function. -LilyPond provides two algorithms for computing page -breaks, @code{ly:optimal-breaking} and @code{ly:page-turn-breaking}. The -default is @code{ly:optimal-breaking}, but the value can be changed in -the @code{\paper} block: +Page breaks are computed by the @code{page-breaking} function. LilyPond +provides three algorithms for computing page breaks, +@code{ly:optimal-breaking}, @code{ly:page-turn-breaking} and +@code{ly:minimal-breaking}. The default is @code{ly:optimal-breaking}, +but the value can be changed in the @code{\paper} block: @example \paper@{ @@ -769,6 +770,22 @@ top-level markups. There should only be one @code{Page_turn_engraver} in a score. If there is more than one, they will interfere with each other. +@node Minimal page breaking +@subsection Minimal page breaking + +@funindex ly:minimal-breaking + +The @code{ly:minimal-breaking} function performs minimal computations to +calculate the page breaking: it fills a page with as many systems as +possible before moving to the next one. Thus, it may be prefered for +scores with many pages, where the other page breaking functions could be +too slow or memory demanding, or a lot of texts. It is enabled using: + +@example +\paper @{ + #(define page-breaking ly:minimal-breaking) +@} +@end example @node Explicit breaks @subsection Explicit breaks @@ -906,7 +923,7 @@ staves inside a system. * Vertical spacing inside a system:: * Vertical spacing between systems:: * Explicit staff and system positioning:: -* Two-pass vertical spacing:: +* Two-pass vertical spacing:: * Vertical collision avoidance:: @end menu diff --git a/input/regression/page-minimal-page-breaking-last-page.ly b/input/regression/page-minimal-page-breaking-last-page.ly new file mode 100644 index 0000000000..796db12854 --- /dev/null +++ b/input/regression/page-minimal-page-breaking-last-page.ly @@ -0,0 +1,23 @@ +\version "2.11.27" +#(set-default-paper-size "a6") + +\header { + texidoc = "Minimal page breaker: special case when the last system is moved +to an other page when there is not enough space because of the tagline." +} + +textBox = \markup \fill-line { \override #'(box-padding . 13) \box Text } + +\book { + \header { + tagline = \markup \fill-line { \override #'(box-padding . 5) \box Tagline } + } + \paper { + #(define page-breaking ly:minimal-breaking) + } + + \markup \textBox + \markup \textBox + \markup \textBox + \markup \textBox +} \ No newline at end of file diff --git a/input/regression/page-minimal-page-breaking.ly b/input/regression/page-minimal-page-breaking.ly new file mode 100644 index 0000000000..0ff288a02b --- /dev/null +++ b/input/regression/page-minimal-page-breaking.ly @@ -0,0 +1,35 @@ +\version "2.11.27" +#(set-default-paper-size "a6") + +\header { + texidoc = "The minimal page breaker stacks as many lines on pages, +only accounting for manual page break commands." +} + +\book { + \paper { #(define page-breaking ly:minimal-breaking) } + + \score { + << + \new Staff \repeat unfold 12 { c'4 } + \new Staff \repeat unfold 12 { c'4 } + \new Staff { \repeat unfold 11 { c'4 } c'_\markup \right-align "\\pageBreak" } + >> + } + \pageBreak + \score { + << + \new Staff \repeat unfold 24 { e'4 } + \new Staff \repeat unfold 24 { e'4 } + \new Staff { \repeat unfold 23 { e'4 } e'_\markup \right-align "\\noPageBreak" } + >> + } + \noPageBreak + \score { + << + \new Staff \repeat unfold 12 { g'4 } + \new Staff \repeat unfold 12 { g'4 } + \new Staff \repeat unfold 12 { g'4 } + >> + } +} \ No newline at end of file diff --git a/lily/include/minimal-page-breaking.hh b/lily/include/minimal-page-breaking.hh new file mode 100644 index 0000000000..b57ab8b607 --- /dev/null +++ b/lily/include/minimal-page-breaking.hh @@ -0,0 +1,26 @@ +/* + minimal-page-breaking.hh -- declare a page-breaker that stacks as + many systems on a page before moving to the next one. Specialized + for books with many pages, or a lot of text. + + source file of the GNU LilyPond music typesetter + + (c) 2007 Nicolas Sceaux +*/ + +#ifndef MINIMAL_PAGE_BREAKING_HH +#define MINIMAL_PAGE_BREAKING_HH + +#include "page-breaking.hh" +#include "page-spacing.hh" + +class Minimal_page_breaking: public Page_breaking +{ +public: + virtual SCM solve (); + + Minimal_page_breaking (Paper_book *pb); + virtual ~Minimal_page_breaking (); +}; + +#endif /* MINIMAL_PAGE_BREAKING_HH */ diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh index 082384d0fe..52a95812c4 100644 --- a/lily/include/page-breaking.hh +++ b/lily/include/page-breaking.hh @@ -131,6 +131,8 @@ protected: vsize first_page_num); Page_spacing_result space_systems_on_best_pages (vsize configuration_index, vsize first_page_num); + Page_spacing_result pack_systems_on_least_pages (vsize configuration_index, + vsize first_page_num); vsize min_page_count (vsize configuration_index, vsize first_page_num); bool all_lines_stretched (vsize configuration_index); Real blank_page_penalty () const; diff --git a/lily/include/page-spacing.hh b/lily/include/page-spacing.hh index ba05a4de9d..9bb37804a7 100644 --- a/lily/include/page-spacing.hh +++ b/lily/include/page-spacing.hh @@ -71,7 +71,7 @@ struct Page_spacing } void calc_force (); - + void resize (Real new_height); void append_system (const Line_details &line); void prepend_system (const Line_details &line); void clear (); diff --git a/lily/minimal-page-breaking.cc b/lily/minimal-page-breaking.cc new file mode 100644 index 0000000000..870340f83d --- /dev/null +++ b/lily/minimal-page-breaking.cc @@ -0,0 +1,47 @@ +/* + minimal-page-breaking.cc -- implement a page-breaker that stacks as + many systems on a page before moving to the next one. Specialized + for books with many pages, or a lot of text. + + source file of the GNU LilyPond music typesetter + + (c) 2007 Nicolas Sceaux +*/ + +#include "international.hh" +#include "minimal-page-breaking.hh" +#include "output-def.hh" +#include "page-spacing.hh" +#include "paper-book.hh" + +static bool +is_break (Grob *g) +{ + (void) g; /* shutup warning */ + return false; +} + +Minimal_page_breaking::Minimal_page_breaking (Paper_book *pb) + : Page_breaking (pb, is_break) +{ +} + +Minimal_page_breaking::~Minimal_page_breaking () +{ +} + +SCM +Minimal_page_breaking::solve () +{ + vsize end = last_break_position (); + + message ("Computing line breaks..."); + set_to_ideal_line_configuration (0, end); + break_into_pieces (0, end, current_configuration (0)); + + message (_ ("Computing page breaks...")); + vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1); + Page_spacing_result res = pack_systems_on_least_pages (0, first_page_num); + SCM lines = systems (); + return make_pages (res.systems_per_page_, lines); +} diff --git a/lily/page-breaking-scheme.cc b/lily/page-breaking-scheme.cc index 2241b503a7..d9f9df152a 100644 --- a/lily/page-breaking-scheme.cc +++ b/lily/page-breaking-scheme.cc @@ -10,6 +10,7 @@ #include "paper-book.hh" #include "page-turn-page-breaking.hh" #include "optimal-page-breaking.hh" +#include "minimal-page-breaking.hh" LY_DEFINE (ly_page_turn_breaking, "ly:page-turn-breaking", 1, 0, 0, (SCM pb), @@ -30,3 +31,13 @@ LY_DEFINE (ly_optimal_breaking, "ly:optimal-breaking", Optimal_page_breaking b (unsmob_paper_book (pb)); return b.solve (); } + +LY_DEFINE (ly_minimal_breaking, "ly:minimal-breaking", + 1, 0, 0, (SCM pb), + "Break (pages and lines) the @code{Paper_book} object @var{pb}" + "without looking for optimal spacing: stack as many lines on" + "a page before moving to the next one.") +{ + Minimal_page_breaking b (unsmob_paper_book (pb)); + return b.solve (); +} diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc index 9ad833610a..b6951925ad 100644 --- a/lily/page-breaking.cc +++ b/lily/page-breaking.cc @@ -526,6 +526,7 @@ Page_breaking::cache_line_details (vsize configuration_index) { if (cached_configuration_index_ != configuration_index) { + cached_configuration_index_ = configuration_index; SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding"); if (!scm_is_number (padding_scm)) padding_scm = book_->paper_->c_variable ("between-system-padding"); @@ -758,6 +759,65 @@ Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_pag return finalize_spacing_result (configuration, best); } +Page_spacing_result +Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num) +{ + Page_spacing_result res; + vsize page = 0; + vsize page_first_line = 0; + Page_spacing space (page_height (first_page_num, false)); + + cache_line_details (configuration); + for (vsize line = 0; line < cached_line_details_.size (); line++) + { + Real prev_force = space.force_; + space.append_system (cached_line_details_[line]); + if ((line > page_first_line) + && (isinf (space.force_) + || ((line > 0) + && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force"))))) + { + res.systems_per_page_.push_back (line - page_first_line); + res.force_.push_back (prev_force); + res.penalty_ += cached_line_details_[line-1].page_penalty_; + page++; + space.resize (page_height (first_page_num + page, false)); + space.clear (); + space.append_system (cached_line_details_[line]); + page_first_line = line; + } + + if (line == cached_line_details_.size () - 1) + { + /* This is the last line */ + /* When the last page height was computed, we did not know yet that it + * was the last one. If the systems put on it don't fit anymore, the last + * system is moved to a new page */ + space.resize (page_height (first_page_num + page, true)); + if ((line > page_first_line) && (isinf (space.force_))) + { + res.systems_per_page_.push_back (line - page_first_line); + res.force_.push_back (prev_force); + /* the last page containing the last line */ + space.resize (page_height (first_page_num + page + 1, true)); + space.clear (); + space.append_system (cached_line_details_[line]); + res.systems_per_page_.push_back (1); + res.force_.push_back (space.force_); + res.penalty_ += cached_line_details_[line-1].page_penalty_; + res.penalty_ += cached_line_details_[line].page_penalty_; + } + else + { + res.systems_per_page_.push_back (line + 1 - page_first_line); + res.force_.push_back (space.force_); + res.penalty_ += cached_line_details_[line].page_penalty_; + } + } + } + return finalize_spacing_result (configuration, res); +} + /* Calculate demerits and fix res.systems_per_page_ so that it refers to the original line numbers, not the ones given by compress_lines (). */ Page_spacing_result diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc index fa1c273f37..82a037bde5 100644 --- a/lily/page-spacing.cc +++ b/lily/page-spacing.cc @@ -23,6 +23,13 @@ Page_spacing::calc_force () / max (0.1, inverse_spring_k_); } +void +Page_spacing::resize (Real new_height) +{ + page_height_ = new_height; + calc_force (); +} + void Page_spacing::append_system (const Line_details &line) { -- 2.39.2