From 626609cc7a4ae66412702d2c22eef2eb3088917e Mon Sep 17 00:00:00 2001 From: Joe Neeman Date: Mon, 29 Dec 2008 18:42:53 +1100 Subject: [PATCH] Add basic support for min-systems-per-page. --- lily/include/page-spacing.hh | 9 +++++++- lily/page-breaking.cc | 40 +++++++++++++++++++++++++++--------- lily/page-spacing.cc | 24 +++++++++++----------- 3 files changed, 50 insertions(+), 23 deletions(-) diff --git a/lily/include/page-spacing.hh b/lily/include/page-spacing.hh index bd64c31122..3730262c75 100644 --- a/lily/include/page-spacing.hh +++ b/lily/include/page-spacing.hh @@ -23,8 +23,15 @@ but small enough that nothing will overflow to infinity (so that we can still distinguish bad spacings by the number of BAD_SPACING_PENALTYs that they incur. + + BAD_SPACING_PENALTY is for occasions where the spacing is bad. + TERRIBLE_SPACING_PENALTY is for when we are disregarding a user override + (for example, we are failing to satisfy min-systems-per-page. These user + overrides are more important than getting good spacing, so they get a + larger penalty. */ -const Real BAD_SPACING_PENALTY = 200000; +const Real BAD_SPACING_PENALTY = 1e6; +const Real TERRIBLE_SPACING_PENALTY = 1e8; /* for page_count > 2, we use a dynamic algorithm similar to diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc index c265f38d72..3bc8597c2a 100644 --- a/lily/page-breaking.cc +++ b/lily/page-breaking.cc @@ -170,8 +170,12 @@ Page_breaking::too_few_lines (int line_count) const Real Page_breaking::line_count_penalty (int line_count) const { - // TODO: also check min_systems_per_page (once we support it in Page_spacer) - return too_many_lines (line_count) ? BAD_SPACING_PENALTY : 0; + if (too_many_lines (line_count)) + return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY; + if (too_few_lines (line_count)) + return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY; + + return 0; } /* translate indices into breaks_ into start-end parameters for the line breaker */ @@ -996,9 +1000,9 @@ Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result { Real f = res.force_[i]; if (isinf (f) && res.systems_per_page_[i] == 1) - f = BAD_SPACING_PENALTY; - - page_force += f * f; + page_force += BAD_SPACING_PENALTY; + else + page_force += f * f; } /* for a while we tried averaging page and line forces across pages instead @@ -1023,13 +1027,17 @@ Page_breaking::space_systems_on_1_page (vector const &lines, Real { Page_spacing space (page_height, page_top_space_); Page_spacing_result ret; + int line_count = 0; for (vsize i = 0; i < lines.size (); i++) - space.append_system (lines[i]); + { + space.append_system (lines[i]); + line_count += lines[i].compressed_nontitle_lines_count_; + } 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.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_; /* don't do finalize_spacing_result () because we are only an internal function */ return ret; @@ -1061,6 +1069,11 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n vector page1_force; vector page2_force; + + // page1_penalty and page2_penalty store the penalties based + // on min-systems-per-page and max-systems-per-page. + vector page1_penalty; + vector page2_penalty; Page_spacing page1 (page1_height, page_top_space_); Page_spacing page2 (page2_height, page_top_space_); int page1_line_count = 0; @@ -1068,6 +1081,8 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n page1_force.resize (cached_line_details_.size () - 1, infinity_f); page2_force.resize (cached_line_details_.size () - 1, infinity_f); + page1_penalty.resize (cached_line_details_.size () - 1, infinity_f); + page2_penalty.resize (cached_line_details_.size () - 1, infinity_f); /* find the page 1 and page 2 forces for each page-breaking position */ for (vsize i = 0; i < page1_force.size (); i++) @@ -1077,13 +1092,15 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_; page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_; - page1_force[i] = + (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_; + page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_; + page1_penalty[i] = line_count_penalty (page1_line_count); if (ragged2) 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_; + page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count); } /* find the position that minimises the sum of the page forces */ @@ -1092,13 +1109,15 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n for (vsize i = 0; i < page1_force.size (); i++) { Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i]; + // FIXME: Why do we look at unevenness here? We don't use it in + // finalize_spacing_result, so this gives us a different measure of demerits. Real uneven = 2 * (page1_force[i] - page2_force[i]); // NOTE: we treat max-systems-per-page and min-systems-per-page as soft // constraints. That is, we penalize harshly when they don't happen // but we don't completely reject. Real dem = uneven * uneven + f - + line_count_penalty (i+1) + line_count_penalty (page2_force.size () - i) + + page1_penalty[i] + page2_penalty[i] + cached_line_details_[i+1].page_penalty_ + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_; if (dem < best_demerits) @@ -1115,7 +1134,8 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n ret.force_.push_back (page2_force[best_sys_count-1]); ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_ + cached_line_details_.back ().page_penalty_ - + cached_line_details_.back ().turn_penalty_; + + cached_line_details_.back ().turn_penalty_ + + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1]; /* don't do finalize_spacing_result () because we are only an internal function */ return ret; diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc index 3bfee3e739..3eb4ecfe53 100644 --- a/lily/page-spacing.cc +++ b/lily/page-spacing.cc @@ -200,10 +200,10 @@ Page_spacer::calc_subproblem (vsize page, vsize line) Page_spacing_node const *prev = page > 0 ? &state_.at (page_start-1, page-1) : 0; line_count += lines_[page_start].compressed_nontitle_lines_count_; - if (breaker_->too_many_lines (line_count)) - break; - space.prepend_system (lines_[page_start]); + // FIXME: The following line doesn't respect min-systems-per-page. More + // generally, what should we do when respecting min-systems-per-page + // would cause a page to be overfull? if (page_start < line && (isinf (space.force_) || (space.force_ < 0 && ragged))) break; @@ -212,22 +212,22 @@ Page_spacer::calc_subproblem (vsize page, vsize line) 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, in - which case we can't make the force infinite, but we should make - it very large. */ + 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_ = -BAD_SPACING_PENALTY; + 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_ + (page % 2 == 0) ? lines_[page_start-1].turn_penalty_ : 0; - dem += penalty; - if (dem < cur.demerits_ || page_start == line) + 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.prev_ = page_start - 1; -- 2.39.5