X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fpage-spacing.cc;h=a2915febb20197470a4e316436881f103a94e435;hb=refs%2Fheads%2Fdebian;hp=c3a56b098724094efa89f602e631489b24f6fd2a;hpb=5516a43e8bc85c3f58b3c004a9a7fde626408939;p=lilypond.git diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc index c3a56b0987..a2915febb2 100644 --- a/lily/page-spacing.cc +++ b/lily/page-spacing.cc @@ -1,85 +1,127 @@ /* - page-spacing.cc - implement routines for spacing - systems vertically on pages + This file is part of LilyPond, the GNU music typesetter. - source file of the GNU LilyPond music typesetter + Copyright (C) 2006--2012 Joe Neeman - (c) 2006--2007 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-spacing.hh" +#include "international.hh" #include "matrix.hh" +#include "page-breaking.hh" #include "warn.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 (); -}; - -/* In order to prevent possible division by zero, we require every line - to have a spring of non-zero length. */ -static Real -line_space (const Line_details &line) +void +Page_spacing::calc_force () { - return max (0.1, line.space_); + Real height = page_height_ + - breaker_->min_whitespace_at_top_of_page (first_line_) + - breaker_->min_whitespace_at_bottom_of_page (last_line_); + + if (rod_height_ + last_line_.bottom_padding_ >= height) + force_ = -infinity_f; + else + force_ = (height - rod_height_ - last_line_.bottom_padding_ - spring_len_) + / max (0.1, inverse_spring_k_); } void -Page_spacing::calc_force () +Page_spacing::resize (Real new_height) { - 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_; + page_height_ = new_height; + calc_force (); } void Page_spacing::append_system (const Line_details &line) { - rod_height_ += last_line_.padding_; + if (rod_height_) + { + rod_height_ += line.tallness_; + spring_len_ += last_line_.spring_length (line); + + } + else + { + rod_height_ += line.full_height (); + first_line_ = line; + } - rod_height_ += line.extent_.length (); - spring_len_ += line_space (line); - inverse_spring_k_ += max (0.1, line.inverse_hooke_); + rod_height_ += account_for_footnotes (line); + inverse_spring_k_ += line.inverse_hooke_; last_line_ = line; calc_force (); } +Real +Page_spacing::account_for_footnotes (Line_details const &line) +{ + Real footnote_height = 0.0; + Real in_note_height = 0.0; + bool has_in_notes = false; + for (vsize i = 0; i < line.in_note_heights_.size (); i++) + { + in_note_height += (has_in_notes + ? 0.0 + : breaker_->in_note_padding ()); + has_in_notes = true; + in_note_height += line.in_note_heights_[i]; + } + + for (vsize i = 0; i < line.footnote_heights_.size (); i++) + { + footnote_height += (has_footnotes_ + ? 0.0 + : (breaker_->footnote_separator_stencil_height () + + breaker_->footnote_padding () + + breaker_->footnote_number_raise ())); + + has_footnotes_ = true; + footnote_height += line.footnote_heights_[i]; + footnote_height += breaker_->footnote_padding (); + } + + return (in_note_height + - (has_in_notes + ? breaker_->in_note_padding () + : 0.0)) + + + (footnote_height + + (has_footnotes_ + ? - breaker_->footnote_padding () + breaker_->footnote_footer_padding () + : 0.0)); +} + void Page_spacing::prepend_system (const Line_details &line) { if (rod_height_) - rod_height_ += line.padding_; + spring_len_ += line.spring_length (first_line_); else last_line_ = line; - rod_height_ += line.extent_.length (); - spring_len_ += line_space (line); - inverse_spring_k_ += max (0.1, line.inverse_hooke_); + rod_height_ -= first_line_.full_height (); + rod_height_ += first_line_.tallness_; + rod_height_ += line.full_height (); + rod_height_ += account_for_footnotes (line); + inverse_spring_k_ += line.inverse_hooke_; + + first_line_ = line; calc_force (); } @@ -89,198 +131,105 @@ Page_spacing::clear () { force_ = rod_height_ = spring_len_ = 0; inverse_spring_k_ = 0; + has_footnotes_ = false; } -/* for each forbidden page break, merge the systems around it into one system. */ -static vector -compress_lines (const vector &orig) +Page_spacer::Page_spacer (vector const &lines, vsize first_page_num, Page_breaking const *breaker) + : lines_ (lines) { - vector ret; - - for (vsize i = 0; i < orig.size (); i++) - { - if (ret.size () && !scm_is_symbol (ret.back ().page_permission_)) - { - Line_details const &old = ret.back (); - Line_details compressed = orig[i]; - compressed.extent_[DOWN] = old.extent_[DOWN]; - compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_; - compressed.space_ += old.space_; - compressed.inverse_hooke_ += old.inverse_hooke_; - - /* we don't need the force_ field for the vertical spacing, - so we use force_ = n to signal that the line was compressed, - reducing the number of lines by n (and force_ = 0 otherwise). - This makes uncompression much easier. */ - compressed.force_ = old.force_ + 1; - ret.back () = compressed; - } - else - { - ret.push_back (orig[i]); - ret.back ().force_ = 0; - } - } - return ret; + first_page_num_ = first_page_num; + breaker_ = breaker; + max_page_count_ = 0; + ragged_ = breaker->ragged (); + ragged_last_ = breaker->is_last () && breaker->ragged_last (); } -/* 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) +Page_spacing_result +Page_spacer::solve () { - vector ret; - vsize start_sys = 0; - - for (vsize i = 0; i < systems_per_page.size (); i++) + if (simple_state_.empty ()) { - int compressed_count = 0; - for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++) - compressed_count += (int)compressed[j].force_; - - ret.push_back (systems_per_page[i] + compressed_count); - start_sys += systems_per_page[i]; + simple_state_.resize (lines_.size ()); + for (vsize i = 0; i < lines_.size (); ++i) + calc_subproblem (VPOS, 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, bool ragged) -{ - Page_spacing space (page_height); - Spacing_result ret; - for (vsize i = 0; i < lines.size (); i++) - space.append_system (lines[i]); + Page_spacing_result ret; + if (simple_state_.empty ()) + return ret; - ret.systems_per_page_.push_back (lines.size ()); - ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_); - ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_; - ret.demerits_ = ret.force_.back () * ret.force_.back () + ret.penalty_; + ret.penalty_ = simple_state_.back ().penalty_ + + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_; + ret.system_count_status_ = simple_state_.back ().system_count_status_; - return ret; -} - -static Spacing_result -space_systems_on_2_pages (vector const &lines, - Real page_height, - bool ragged, - bool ragged_last) -{ - /* if there is a forced break, this reduces to 2 1-page problems */ - for (vsize i = 0; i + 1 < lines.size (); 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, ragged); - Spacing_result p2 = space_systems_on_1_page (lines2, page_height, ragged || ragged_last); - - 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++) + vsize system = lines_.size () - 1; + while (system != VPOS) { - page1.append_system (lines[i]); - page2.prepend_system (lines[lines.size () - 1 - i]); - page1_force[i] = (ragged && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_; + Page_spacing_node const &cur = simple_state_[system]; + vsize system_count = (cur.prev_ == VPOS) ? system + 1 : system - cur.prev_; - if (ragged || ragged_last) - page2_force[page2_force.size () - 1 - i] = - (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0; - else - 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; - } + ret.force_.push_back (cur.force_); + ret.systems_per_page_.push_back (system_count); + ret.demerits_ += cur.force_ * cur.force_; + system = cur.prev_; } - 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; - + reverse (ret.force_); + reverse (ret.systems_per_page_); return ret; } -Page_spacer::Page_spacer (vector const &lines, Real page_height, bool ragged, bool ragged_last) - : lines_ (lines) -{ - page_height_ = page_height; - max_page_count_ = 0; - ragged_ = ragged; - ragged_last_ = ragged_last; -} - -Spacing_result +Page_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); + Page_spacing_result ret; vsize system = lines_.size () - 1; - vsize tack_onto_the_end = 0; + vsize extra_systems = 0; + vsize extra_pages = 0; - if (isinf (state_.at (system, page_count-1).demerits_)) + if (isinf (state_.at (system, page_count - 1).demerits_)) { programming_error ("tried to space systems on a bad number of pages"); /* Usually, this means that we tried to cram too many systems into - to few pages. To avoid crashing, we look for the largest number of - systems that we can fit properly onto the right number of pages. - All the systems that don't fit get tacked onto the last page. + to few pages. To avoid crashing, we look for the largest number of + systems that we can fit properly onto the right number of pages. + All the systems that don't fit get tacked onto the last page. */ vsize i; - for (i = system; isinf (state_.at (i, page_count-1).demerits_) && i--; ) - ; + for (i = system; isinf (state_.at (i, page_count - 1).demerits_) && i; i--) + ; if (i) - { - tack_onto_the_end = system - i; - system = i; - } + { + extra_systems = system - i; + system = i; + } else - return Spacing_result (); /* couldn't salvage it -- probably going to crash */ + { + /* try chopping off pages from the end */ + vsize j; + for (j = page_count; j && isinf (state_.at (system, j - 1).demerits_); j--) + ; + + if (j) + { + extra_pages = page_count - j; + page_count = j; + } + else + return Page_spacing_result (); /* couldn't salvage it -- probably going to crash */ + } } - ret.penalty_ = state_.at (system, page_count-1).penalty_ - + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_; + ret.force_.resize (page_count); + ret.systems_per_page_.resize (page_count); + ret.system_count_status_ = state_.at (system, page_count - 1).system_count_status_; + ret.penalty_ = state_.at (system, page_count - 1).penalty_ + + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_; ret.demerits_ = 0; for (vsize p = page_count; p--;) @@ -291,12 +240,23 @@ Page_spacer::solve (vsize page_count) ret.force_[p] = ps.force_; ret.demerits_ += ps.force_ * ps.force_; if (p == 0) - ret.systems_per_page_[p] = system + 1; + ret.systems_per_page_[p] = system + 1; else - ret.systems_per_page_[p] = system - ps.prev_ + tack_onto_the_end; + ret.systems_per_page_[p] = system - ps.prev_; system = ps.prev_; } - ret.demerits_ += ret.penalty_; + + if (extra_systems) + { + ret.systems_per_page_.back () += extra_systems; + ret.force_.back () = BAD_SPACING_PENALTY; + } + if (extra_pages) + { + ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY); + ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0); + } + return ret; } @@ -312,154 +272,125 @@ Page_spacer::resize (vsize page_count) for (vsize page = max_page_count_; page < page_count; page++) for (vsize line = page; line < lines_.size (); line++) if (!calc_subproblem (page, line)) - break; + break; max_page_count_ = page_count; } +// Carries out one step in the dynamic programming algorithm for putting systems +// on a fixed number of pages. One call to this routine calculates the best +// configuration for putting lines 0 through LINE-1 on PAGE+1 pages, provided that +// we have previously called calc_subproblem(page-1, k) for every k < LINE. +// +// This algorithm is similar to the constrained-breaking algorithm. +// +// If page == VPOS, we act on simple_state_ instead of state_. This is useful if +// we don't want to constrain the number of pages that the solution has. In this +// case, the algorithm looks more like the page-turn-page-breaking algorithm. But +// the subproblems look similar for both, so we reuse this method. bool Page_spacer::calc_subproblem (vsize page, vsize line) { - Page_spacing space (page_height_); - Page_spacing_node &cur = state_.at (line, page); - bool ragged = ragged_ || (ragged_last_ && line == lines_.size () - 1); - - for (vsize page_start = line+1; page_start > page && page_start--;) + bool last = line == lines_.size () - 1; + + // Note: if page == VPOS then we don't actually know yet which page number we're + // working on, so we have to recalculate the page height in the loop. Therefore + // our early-exit condition from the loop depends on paper_height rather than + // page_height (ie. we break only if we would overfill a page without margins + // or headers/footers). Otherwise, the algorithm would not be optimal: + // if our page has a very large header then perhaps + // we should look ahead a few systems in order to find the best solution. A + // good example of this is input/regression/page-spacing-tall-headfoot.ly + vsize page_num = page == VPOS ? 0 : page; + Real paper_height = breaker_->paper_height (); + Page_spacing space (breaker_->page_height (page_num + first_page_num_, last), + breaker_); + Page_spacing_node &cur = page == VPOS ? simple_state_[line] : state_.at (line, page); + bool ragged = ragged_ || (ragged_last_ && last); + int line_count = 0; + + for (vsize page_start = line + 1; page_start > page_num && page_start--;) { - Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0; + Page_spacing_node const *prev = 0; + + if (page == VPOS) + { + if (page_start > 0) + { + prev = &simple_state_[page_start - 1]; + space.resize (breaker_->page_height (prev->page_ + 1, last)); + } + else + space.resize (breaker_->page_height (first_page_num_, last)); + } + else if (page > 0) + prev = &state_.at (page_start - 1, page - 1); space.prepend_system (lines_[page_start]); - if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged))) - break; + bool overfull = (space.rod_height_ > paper_height + || (ragged_ + && (space.rod_height_ + space.spring_len_ > paper_height))); + // This 'if' statement is a little hard to parse. It won't consider this configuration + // if it is overfull unless the current configuration is the first one with this start + // point. We also make an exception (and consider this configuration) if the previous + // configuration we tried had fewer lines than min-systems-per-page. + if (!breaker_->too_few_lines (line_count) + && page_start < line + && overfull) + break; + + line_count += lines_[page_start].compressed_nontitle_lines_count_; if (page > 0 || page_start == 0) - { - if (line == lines_.size () - 1 && ragged_last_ && space.force_ > 0) - space.force_ = 0; - - /* we may have to deal with single lines that are taller than a page */ - if (isinf (space.force_) && page_start == line) - space.force_ = -200000; - - 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_ || page_start == line) - { - cur.demerits_ = dem; - cur.force_ = space.force_; - cur.penalty_ = penalty + (prev ? prev->penalty_ : 0); - cur.prev_ = page_start - 1; - } - } + { + // If the last page is ragged, set its force to zero. This way, we will leave + // the last page half-empty rather than trying to balance things out + // (which only makes sense in non-ragged situations). + if (line == lines_.size () - 1 && ragged && last && space.force_ > 0) + space.force_ = 0; + + Real demerits = space.force_ * space.force_; + + // Clamp the demerits at BAD_SPACING_PENALTY, even if the page + // is overfull. This ensures that TERRIBLE_SPACING_PENALTY takes + // precedence over overfull pages. + demerits = min (demerits, BAD_SPACING_PENALTY); + demerits += (prev ? prev->demerits_ : 0); + + Real penalty = breaker_->line_count_penalty (line_count); + if (page_start > 0) + penalty += lines_[page_start - 1].page_penalty_ + + (page % 2 == 0) ? lines_[page_start - 1].turn_penalty_ : 0; + + /* Deal with widow/orphan lines */ + /* Last line of paragraph is first line on the new page */ + if ((page_start > 0) + && (page_start < lines_.size ()) + && (lines_[page_start].last_markup_line_)) + penalty += breaker_->orphan_penalty (); + /* First line of paragraph is last line on the previous page */ + if ((page_start > 0) + && (page_start < lines_.size ()) + && (lines_[page_start - 1].first_markup_line_)) + penalty += breaker_->orphan_penalty (); + + demerits += penalty; + if (demerits < cur.demerits_ || page_start == line) + { + cur.demerits_ = demerits; + cur.force_ = space.force_; + cur.penalty_ = penalty + (prev ? prev->penalty_ : 0); + cur.system_count_status_ = breaker_->line_count_status (line_count) + | (prev ? prev->system_count_status_ : 0); + cur.prev_ = page_start - 1; + cur.page_ = prev ? prev->page_ + 1 : first_page_num_; + } + } if (page_start > 0 - && lines_[page_start-1].page_permission_ == ly_symbol2scm ("force")) - break; + && lines_[page_start - 1].page_permission_ == ly_symbol2scm ("force")) + break; } return !isinf (cur.demerits_); } -vsize -min_page_count (vector const &uncompressed_lines, - Real page_height, bool ragged, bool ragged_last) -{ - vsize ret = 1; - Real cur_rod_height = 0; - vector lines = compress_lines (uncompressed_lines); - - assert (lines.size ()); - for (vsize i = lines.size (); i--;) - { - bool rag = ragged || (ragged_last && ret == 1); - Real ext_len = lines[i].extent_.length (); - Real next_height = cur_rod_height + ext_len - + (rag ? line_space (lines[i]) : 0) - + ((cur_rod_height > 0) ? lines[i].padding_: 0); - - if ((next_height > page_height && cur_rod_height > 0) - || (i + 1 < lines.size () && lines[i].page_permission_ == ly_symbol2scm ("force"))) - { - ret++; - cur_rod_height = ext_len + (rag ? line_space (lines[i]) : 0); - } - else - cur_rod_height = next_height; - } - - return ret; -} - -Spacing_result -space_systems_on_n_pages (vector const &lines, - vsize n, - Real page_height, - bool ragged, - bool ragged_last) -{ - vector compressed_lines = compress_lines (lines); - Spacing_result ret; - assert (n >= min_page_count (lines, page_height, ragged, ragged_last)); - - if (n > compressed_lines.size ()) - return Spacing_result (); - if (n == 1) - ret = space_systems_on_1_page (compressed_lines, page_height, ragged || ragged_last); - else if (n == 2) - ret = space_systems_on_2_pages (compressed_lines, page_height, ragged, ragged_last); - - Page_spacer ps (compressed_lines, page_height, ragged, ragged_last); - ret = ps.solve (n); - - ret.systems_per_page_ = uncompress_solution (ret.systems_per_page_, compressed_lines); - return ret; -} - -Spacing_result -space_systems_on_n_or_one_more_pages (vector const &lines, - vsize n, - Real page_height, - Real odd_pages_penalty, - bool ragged, - bool ragged_last) -{ - Spacing_result n_res = space_systems_on_n_pages (lines, n, page_height, ragged, ragged_last); - Spacing_result m_res = space_systems_on_n_pages (lines, n+1, page_height, ragged, ragged_last); - n_res.demerits_ += odd_pages_penalty; - n_res.force_.back () += odd_pages_penalty; - - if (n_res.demerits_ < m_res.demerits_) - return n_res; - return m_res; -} - -Spacing_result -space_systems_on_best_pages (vector const &lines, - Real page_height, - Real odd_pages_penalty, - bool ragged, - bool ragged_last) -{ - vector compressed_lines = compress_lines (lines); - vsize min_p_count = min_page_count (compressed_lines, page_height, ragged, ragged_last); - - Page_spacer ps (compressed_lines, page_height, ragged, ragged_last); - Spacing_result best = ps.solve (min_p_count); - best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0; - 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; -}