X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fpage-spacing.cc;h=4120afb514116df57c7ecd5450f2a11ee4680120;hb=a7d058d67feb06da25298c3df77e0740f8069d62;hp=71e51fa685633383f409ffb963c917135cb1284d;hpb=0e5d83a9ceb4a143f83d22406d7eb816314ff9f7;p=lilypond.git diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc index 71e51fa685..4120afb514 100644 --- a/lily/page-spacing.cc +++ b/lily/page-spacing.cc @@ -1,10 +1,20 @@ /* - 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--2010 Joe Neeman - (c) 2006--2009 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" @@ -16,8 +26,9 @@ void Page_spacing::calc_force () { - /* If the first system is a title, we add back in the page-top-space. */ - Real height = first_line_.title_ ? page_height_ + page_top_space_ : page_height_; + 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; @@ -36,12 +47,17 @@ Page_spacing::resize (Real new_height) void Page_spacing::append_system (const Line_details &line) { - if (!rod_height_) - first_line_ = line; - - rod_height_ += last_line_.padding_; - - rod_height_ += line.extent_.length (); + if (rod_height_) + { + rod_height_ += line.tallness_; + } + else + { + rod_height_ += line.full_height (); + first_line_ = line; + } + if (!line.tight_spacing_) + rod_height_ += line.title_ ? last_line_.title_padding_ : last_line_.padding_; spring_len_ += line.space_; inverse_spring_k_ += line.inverse_hooke_; @@ -53,12 +69,14 @@ Page_spacing::append_system (const Line_details &line) void Page_spacing::prepend_system (const Line_details &line) { - if (rod_height_) - rod_height_ += line.padding_; + if (rod_height_ && !first_line_.tight_spacing_) + rod_height_ += first_line_.title_ ? line.title_padding_ : line.padding_; else last_line_ = line; - rod_height_ += line.extent_.length (); + rod_height_ -= first_line_.full_height (); + rod_height_ += first_line_.tallness_; + rod_height_ += line.full_height(); spring_len_ += line.space_; inverse_spring_k_ += line.inverse_hooke_; @@ -154,17 +172,14 @@ Page_spacer::solve (vsize page_count) if (extra_systems) { ret.systems_per_page_.back () += extra_systems; - ret.demerits_ += 200000; + ret.force_.back () = BAD_SPACING_PENALTY; } if (extra_pages) { - ret.force_.insert (ret.force_.end (), extra_pages, 200000); + ret.force_.insert (ret.force_.end (), extra_pages, BAD_SPACING_PENALTY); ret.systems_per_page_.insert (ret.systems_per_page_.end (), extra_pages, 0); - ret.demerits_ += 200000; } - - ret.demerits_ += ret.penalty_; return ret; } @@ -185,44 +200,78 @@ Page_spacer::resize (vsize page_count) 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. bool Page_spacer::calc_subproblem (vsize page, vsize line) { bool last = line == lines_.size () - 1; Page_spacing space (breaker_->page_height (page + first_page_num_, last), - breaker_->page_top_space ()); + breaker_); Page_spacing_node &cur = state_.at (line, page); bool ragged = ragged_ || (ragged_last_ && last); + int line_count = 0; 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 (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged))) + + // 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 + && (isinf (space.force_) || (space.force_ < 0 && ragged))) break; + line_count += lines_[page_start].compressed_nontitle_lines_count_; if (page > 0 || page_start == 0) { + // 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; - /* we may have to deal with single lines that are taller than a page */ + Real demerits = space.force_ * space.force_; + /* If a single line is taller than a page, we need to consider it as + a possible solution (but we give it a very bad score). */ if (isinf (space.force_) && page_start == line) - space.force_ = -200000; + demerits = BAD_SPACING_PENALTY; + demerits += (prev ? prev->demerits_ : 0); - Real dem = fabs (space.force_) + (prev ? prev->demerits_ : 0); - Real penalty = 0; + Real penalty = breaker_->line_count_penalty (line_count); if (page_start > 0) - penalty = lines_[page_start-1].page_penalty_ + 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) + /* 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_ = dem; + 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; } }