diff options
author | Joe Neeman <joeneeman@gmail.com> | 2009-03-12 15:06:37 -0700 |
---|---|---|
committer | Joe Neeman <joeneeman@gmail.com> | 2009-03-12 15:07:34 -0700 |
commit | df221999366536dd66fbad10d1a3a32657976d99 (patch) | |
tree | c0126276a52b92b626718c201c7887015e7115e1 | |
parent | 626609cc7a4ae66412702d2c22eef2eb3088917e (diff) |
Tie up some loose ends with min-systems-per-page.
Adds regression tests for min-systems-per-page.
-rw-r--r-- | input/regression/page-breaking-min-systems-per-page1.ly | 18 | ||||
-rw-r--r-- | input/regression/page-breaking-min-systems-per-page2.ly | 14 | ||||
-rw-r--r-- | lily/include/page-breaking.hh | 1 | ||||
-rw-r--r-- | lily/include/page-spacing-result.hh | 11 | ||||
-rw-r--r-- | lily/include/page-spacing.hh | 4 | ||||
-rw-r--r-- | lily/optimal-page-breaking.cc | 37 | ||||
-rw-r--r-- | lily/page-breaking.cc | 67 | ||||
-rw-r--r-- | lily/page-spacing-result.cc | 1 | ||||
-rw-r--r-- | lily/page-spacing.cc | 18 |
9 files changed, 134 insertions, 37 deletions
diff --git a/input/regression/page-breaking-min-systems-per-page1.ly b/input/regression/page-breaking-min-systems-per-page1.ly new file mode 100644 index 0000000000..b8e9ce6a1a --- /dev/null +++ b/input/regression/page-breaking-min-systems-per-page1.ly @@ -0,0 +1,18 @@ +\version "2.13.1" + +#(set-default-paper-size "a6") + +\header { + texidoc = "The min-systems-per-page variable forces each page to have +a minimum number of systems. Titles do not count as systems here. + +This exposes a bug with the current implementation; min-systems-per-page +is not honored if to do so we would need uneven line breaking." + title = "Example" +} + +\paper { + min-systems-per-page = 5 +} + +{ \repeat unfold 11 { c'1 } \pageBreak \repeat unfold 6 { c'1 } }
\ No newline at end of file diff --git a/input/regression/page-breaking-min-systems-per-page2.ly b/input/regression/page-breaking-min-systems-per-page2.ly new file mode 100644 index 0000000000..56fb1a61fb --- /dev/null +++ b/input/regression/page-breaking-min-systems-per-page2.ly @@ -0,0 +1,14 @@ +\version "2.13.1" + +#(set-default-paper-size "a6") + +\header { + texidoc = "The min-systems-per-page variable takes precedence over +the desire not to overfill a page." +} + +\paper { + min-systems-per-page = 20 +} + +\repeat unfold 21 { c'1 }
\ No newline at end of file diff --git a/lily/include/page-breaking.hh b/lily/include/page-breaking.hh index 9fa108edd2..c6c1bc02c8 100644 --- a/lily/include/page-breaking.hh +++ b/lily/include/page-breaking.hh @@ -108,6 +108,7 @@ public: Real page_top_space () const; vsize system_count () const; Real line_count_penalty (int line_count) const; + int line_count_status (int line_count) const; bool too_many_lines (int line_count) const; bool too_few_lines (int line_count) const; diff --git a/lily/include/page-spacing-result.hh b/lily/include/page-spacing-result.hh index 870fbda7e1..83da406df0 100644 --- a/lily/include/page-spacing-result.hh +++ b/lily/include/page-spacing-result.hh @@ -13,11 +13,22 @@ #include "std-vector.hh" #include "lily-proto.hh" +// This enum is a bitfield: since we use one System_count_status +// to represent the system count of several pages simultaneously, +// it could be that one page has too many systems while another +// has too few. +typedef enum { + SYSTEM_COUNT_OK = 0, + SYSTEM_COUNT_TOO_MANY = 1, + SYSTEM_COUNT_TOO_FEW = 2 +} System_count_status; + struct Page_spacing_result { vector<vsize> systems_per_page_; vector<Real> force_; Real penalty_; Real demerits_; + int system_count_status_; Real average_force () const; vsize page_count () const; diff --git a/lily/include/page-spacing.hh b/lily/include/page-spacing.hh index 3730262c75..958a1b21ff 100644 --- a/lily/include/page-spacing.hh +++ b/lily/include/page-spacing.hh @@ -26,7 +26,7 @@ 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 + (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. */ @@ -53,12 +53,14 @@ private: force_ = infinity_f; penalty_ = infinity_f; prev_ = VPOS; + system_count_status_ = SYSTEM_COUNT_OK; } Real demerits_; Real force_; Real penalty_; vsize prev_; + int system_count_status_; }; Page_breaking const *breaker_; diff --git a/lily/optimal-page-breaking.cc b/lily/optimal-page-breaking.cc index 47a2edafbe..13b2669aaf 100644 --- a/lily/optimal-page-breaking.cc +++ b/lily/optimal-page-breaking.cc @@ -23,6 +23,11 @@ is_break (Grob *) return false; } +// FIXME: divide the page breaking into subproblems wherever there is a page break. +// This will allow us to tweak line-breaking independently on both sides of a +// page break (currently, we only get to request a number of systems for an entire score +// at a time), which is necessary for min-systems-per-page and \pageBreak to interact +// correctly. Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb) : Page_breaking (pb, is_break) { @@ -102,27 +107,34 @@ Optimal_page_breaking::solve () else cur = space_systems_on_n_or_one_more_pages (i, page_count-1, first_page_num); - if (cur.demerits_ < best_for_this_sys_count.demerits_ || isinf (best_for_this_sys_count.demerits_)) + if (cur.demerits_ < best_for_this_sys_count.demerits_) { best_for_this_sys_count = cur; bound = current_configuration (i); } } - if (best_for_this_sys_count.demerits_ < best.demerits_ || isinf (best.demerits_)) + if (best_for_this_sys_count.demerits_ < best.demerits_) { best = best_for_this_sys_count; best_division = bound; } - /* if the pages are stretched on average, stop trying to reduce sys_count */ - if (best_for_this_sys_count.page_count () < page_count - && best_for_this_sys_count.average_force () > 0) - break; - + /* Check to see if we already have too few systems. There are two ways + we check this: if we are trying one less than the ideal number of pages + and the pages are stretched on average then we have too + few systems. If the spacing is worse than BAD_SPACING_PENALTY, then we + have too few systems. In either case, though, we need to continue reducing + the number of systems if max-systems-per-page requires it. */ + if (!(best.system_count_status_ & SYSTEM_COUNT_TOO_MANY)) + { + if (best_for_this_sys_count.page_count () < page_count + && best_for_this_sys_count.average_force () > 0) + break; - if (isinf (best_for_this_sys_count.demerits_)) - break; + if (best_for_this_sys_count.demerits_ >= BAD_SPACING_PENALTY) + break; + } } /* try a larger number of systems than the ideal line breaking number. This @@ -144,19 +156,20 @@ Optimal_page_breaking::solve () else cur = space_systems_on_n_pages (i, page_count, first_page_num); - if (cur.demerits_ < best.demerits_ || isinf (best.demerits_)) + if (cur.demerits_ < best.demerits_) { best = cur; best_division = current_configuration (i); } - if (cur.demerits_ < best_demerits_for_this_sys_count || isinf (best_demerits_for_this_sys_count)) + if (cur.demerits_ < best_demerits_for_this_sys_count) { best_demerits_for_this_sys_count = cur.demerits_; bound = current_configuration (i); } } - if (isinf (best_demerits_for_this_sys_count)) + if (best_demerits_for_this_sys_count >= BAD_SPACING_PENALTY + && !(best.system_count_status_ & SYSTEM_COUNT_TOO_FEW)) break; } diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc index 3bc8597c2a..1c0d21cdc7 100644 --- a/lily/page-breaking.cc +++ b/lily/page-breaking.cc @@ -101,9 +101,20 @@ Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break) ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom")); ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom")); page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0); - systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0); - max_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0); - min_systems_per_page_ = robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0); + systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0)); + max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0)); + min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0)); + + if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_)) + { + warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set")); + min_systems_per_page_ = max_systems_per_page_ = 0; + } + if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_) + { + warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values")); + min_systems_per_page_ = max_systems_per_page_ = 0; + } create_system_list (); find_chunks_and_breaks (is_break); @@ -178,6 +189,17 @@ Page_breaking::line_count_penalty (int line_count) const return 0; } +int +Page_breaking::line_count_status (int line_count) const +{ + if (too_many_lines (line_count)) + return SYSTEM_COUNT_TOO_MANY; + if (too_few_lines (line_count)) + return SYSTEM_COUNT_TOO_FEW; + + return SYSTEM_COUNT_OK; +} + /* translate indices into breaks_ into start-end parameters for the line breaker */ void Page_breaking::line_breaker_args (vsize sys, @@ -691,11 +713,10 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num) + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0); Real next_spring_height = cur_spring_height + cached_line_details_[i].space_; Real next_height = next_rod_height + (ragged () ? next_spring_height : 0); + int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_; - line_count += cached_line_details_[i].compressed_nontitle_lines_count_; - - if ((next_height > cur_page_height && cur_rod_height > 0) - || too_many_lines (line_count) + if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0)) + || too_many_lines (next_line_count) || (i > 0 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force"))) { @@ -709,6 +730,7 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num) { cur_rod_height = next_rod_height; cur_spring_height = next_spring_height; + line_count = next_line_count; } } @@ -727,7 +749,8 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num) cur_page_height = page_height (first_page_num + ret - 1, true); Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0); - if (cur_height > cur_page_height + if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_) + && cur_height > cur_page_height /* don't increase the page count if the last page had only one system */ && cur_rod_height > cached_line_details_.back ().extent_.length ()) ret++; @@ -918,6 +941,7 @@ Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration, Page_spacing_result Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num) { + // TODO: add support for min/max-systems-per-page. Page_spacing_result res; vsize page = 0; vsize page_first_line = 0; @@ -987,7 +1011,7 @@ Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result Real line_force = 0; Real line_penalty = 0; - Real page_force = 0; + Real page_demerits = res.penalty_; Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10); for (vsize i = 0; i < uncompressed_line_details_.size (); i++) @@ -999,10 +1023,8 @@ Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result for (vsize i = 0; i < res.force_.size (); i++) { Real f = res.force_[i]; - if (isinf (f) && res.systems_per_page_[i] == 1) - page_force += BAD_SPACING_PENALTY; - else - page_force += f * f; + + page_demerits += min(f*f, BAD_SPACING_PENALTY); } /* for a while we tried averaging page and line forces across pages instead @@ -1010,7 +1032,7 @@ Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result with a very bad page force (for example because of a forced page break), the page breaker will put in a _lot_ of pages so that the bad force becomes averaged out over many pages. */ - res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting; + res.demerits_ = line_force + line_penalty + page_demerits * page_weighting; return res; } @@ -1038,6 +1060,7 @@ Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real ret.systems_per_page_.push_back (lines.size ()); ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_); ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_; + ret.system_count_status_ |= line_count_status (line_count); /* don't do finalize_spacing_result () because we are only an internal function */ return ret; @@ -1074,6 +1097,12 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n // on min-systems-per-page and max-systems-per-page. vector<Real> page1_penalty; vector<Real> page2_penalty; + + // page1_status and page2_status keep track of whether the min-systems-per-page + // and max-systems-per-page constraints are satisfied. + vector<int> page1_status; + vector<int> page2_status; + Page_spacing page1 (page1_height, page_top_space_); Page_spacing page2 (page2_height, page_top_space_); int page1_line_count = 0; @@ -1083,6 +1112,8 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n 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); + page1_status.resize (cached_line_details_.size () - 1, 0); + page2_status.resize (cached_line_details_.size () - 1, 0); /* find the page 1 and page 2 forces for each page-breaking position */ for (vsize i = 0; i < page1_force.size (); i++) @@ -1094,6 +1125,7 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_; page1_penalty[i] = line_count_penalty (page1_line_count); + page1_status[i] = line_count_status (page1_line_count); if (ragged2) page2_force[page2_force.size () - 1 - i] = @@ -1101,6 +1133,7 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n else page2_force[page2_force.size () - 1 - i] = page2.force_; page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count); + page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count); } /* find the position that minimises the sum of the page forces */ @@ -1109,14 +1142,11 @@ 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 + Real dem = f + 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_; @@ -1132,6 +1162,7 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n ret.systems_per_page_.push_back (cached_line_details_.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.system_count_status_ = page1_status[best_sys_count-1] | page2_status[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_ diff --git a/lily/page-spacing-result.cc b/lily/page-spacing-result.cc index f3d5b21e22..19ae1d9b76 100644 --- a/lily/page-spacing-result.cc +++ b/lily/page-spacing-result.cc @@ -14,6 +14,7 @@ Page_spacing_result::Page_spacing_result () { penalty_ = 0; demerits_ = infinity_f; + system_count_status_ = SYSTEM_COUNT_OK; } vsize diff --git a/lily/page-spacing.cc b/lily/page-spacing.cc index 3eb4ecfe53..c60f0d88b1 100644 --- a/lily/page-spacing.cc +++ b/lily/page-spacing.cc @@ -198,15 +198,19 @@ Page_spacer::calc_subproblem (vsize page, vsize line) 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; - line_count += lines_[page_start].compressed_nontitle_lines_count_; 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))) + + // 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 (line == lines_.size () - 1 && ragged && last && space.force_ > 0) @@ -221,7 +225,7 @@ Page_spacer::calc_subproblem (vsize page, vsize line) 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; demerits += penalty; @@ -230,6 +234,8 @@ Page_spacer::calc_subproblem (vsize page, vsize 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; } } |