X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Foptimal-page-breaking.cc;h=d18ad2837e92ffe2104f0a4ae326bea06b0cc38e;hb=7fb65fc23874860275fe337474edeb44166d45de;hp=800c52459163b6743b2e6bc664d489e073b85c4d;hpb=6224c5c3bfe0a4c7aef15a060a323c77c99bd3f0;p=lilypond.git diff --git a/lily/optimal-page-breaking.cc b/lily/optimal-page-breaking.cc index 800c524591..d18ad2837e 100644 --- a/lily/optimal-page-breaking.cc +++ b/lily/optimal-page-breaking.cc @@ -1,11 +1,11 @@ /* - optimal-page-breaking.hh -- implement a page-breaker that + optimal-page-breaking.cc -- implement a page-breaker that will break pages in such a way that both horizontal and vertical spacing will be acceptable source file of the GNU LilyPond music typesetter - (c) 2006 Joe Neeman + (c) 2006--2007 Joe Neeman */ #include "optimal-page-breaking.hh" @@ -16,8 +16,15 @@ #include "prob.hh" #include "system.hh" +static bool +is_break (Grob *g) +{ + (void) g; /* shutup warning */ + return false; +} + Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb) - : Page_breaking (pb, false) + : Page_breaking (pb, is_break) { } @@ -26,147 +33,91 @@ Optimal_page_breaking::~Optimal_page_breaking () } Spacing_result -Optimal_page_breaking::try_page_spacing (vector line_count) +Optimal_page_breaking::try_page_spacing (Line_division const &line_count) { - vector lines = get_line_details (0, breaks_.size () - 1, line_count); + vector lines = line_details (0, breaks_.size () - 1, line_count); Real page_h = page_height (1, false); // FIXME SCM force_sym = ly_symbol2scm ("blank-last-page-force"); Real blank_force = robust_scm2double (book_->paper_->lookup_variable (force_sym), 0); - Spacing_result ret = space_systems_on_best_pages (lines, page_h, blank_force); - bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom")); bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom")); + Spacing_result ret = space_systems_on_best_pages (lines, + page_h, + blank_force, + ragged_all, + ragged_last); /* add in the line penalties */ Real line_force = 0; Real line_penalty = 0; - Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 1); + Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10); for (vsize i = 0; i < lines.size (); i++) { - line_force += fabs (lines[i].force_); + line_force += lines[i].force_ * lines[i].force_; line_penalty += lines[i].break_penalty_; } - if (ragged_all) - for (vsize i = 0; i < ret.force_.size () - 1; i++) - ret.force_[i] = min (0.0, ret.force_[i]); - if (ragged_all || ragged_last) - ret.force_.back () = min (0.0, ret.force_.back ()); - ret.demerits_ = ret.force_[0] * ret.force_[0] * page_weighting; for (vsize i = 1; i < ret.force_.size (); i++) - { - Real uniformity = fabs (ret.force_[i] - ret.force_[i-1]); - ret.demerits_ += (ret.force_[i] * ret.force_[i] - + uniformity * uniformity) * page_weighting; - } + ret.demerits_ += ret.force_[i] * ret.force_[i] * page_weighting; + + /* for a while we tried averaging page and line forces instead of summing + them, but it caused the following problem. If there is a single page + 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. */ ret.demerits_ += line_force + line_penalty; return ret; } -/* The algorithm is as follows: - 1) break everything into its preferred number of lines - 2) decrease the number of lines until we've decreased - the number of pages - 3) increase the number of lines until we've increased - the number of pages - Take the best score we've found -*/ SCM Optimal_page_breaking::solve () { - vector ideal_line_count; - vector max_line_count; - vector min_line_count; - vector last_best_line_count; - vector best_line_count; - vsize last_line_total = 0; - - calc_system_count_bounds (0, breaks_.size () - 1, &min_line_count, &max_line_count); - ideal_line_count.resize (all_.size (), 1); - for (vsize i = 0; i < all_.size (); i++) + vsize end = breaks_.size () - 1; + vsize min_sys_count = min_system_count (0, end); + vsize max_sys_count = max_system_count (0, end); + vsize max_page_count = INT_MAX; + vsize cur_page_count = 0; + Spacing_result best; + Line_division best_division; + Line_division lower_bound; + + for (vsize sys_count = min_sys_count; + cur_page_count <= max_page_count && sys_count <= max_sys_count; + sys_count++) { - if (all_[i].pscore_) - ideal_line_count[i] = line_breaking_[i].get_best_solution (0, VPOS).size (); - last_line_total += ideal_line_count[i]; - } - - Spacing_result best_result = try_page_spacing (ideal_line_count); - vsize original_page_count = best_result.systems_per_page_.size (); - best_line_count = ideal_line_count; - last_best_line_count = ideal_line_count; - - Direction d = original_page_count > 1 ? DOWN : UP; - vector > div; - Spacing_result this_best_result; - do { - do { - vector blank; - - vector this_best_line_count; - this_best_result.demerits_ = infinity_f; - - last_line_total += d; - div.clear (); - divide_systems (last_line_total, - d == DOWN ? min_line_count : last_best_line_count, - d == DOWN ? last_best_line_count : max_line_count, - &div, &blank); - - for (vsize i = 0; i < div.size (); i++) + Real this_best_demerits = infinity_f; + vector div = line_divisions (0, end, sys_count, lower_bound); + for (vsize d = 0; d < div.size (); d++) { - Spacing_result cur = try_page_spacing (div[i]); - if (cur.demerits_ < this_best_result.demerits_) + Spacing_result cur = try_page_spacing (div[d]); + cur_page_count = cur.systems_per_page_.size (); + if (cur.demerits_ < best.demerits_ || isinf (best.demerits_)) { - this_best_result = cur; - this_best_line_count = div[i]; + best = cur; + best_division = div[d]; } - } - last_best_line_count = this_best_line_count; - - if (this_best_result.demerits_ < best_result.demerits_) - { - best_line_count = this_best_line_count; - best_result = this_best_result; - } - } while (div.size () && this_best_result.systems_per_page_.size () == original_page_count); - /* we're finished decreasing system count, let's try raising it */ - last_best_line_count = ideal_line_count; - last_line_total = 0; - for (vsize i = 0; i < ideal_line_count.size (); i++) - last_line_total += ideal_line_count[i]; - - } while (flip (&d) != DOWN); - - SCM lines = make_lines (best_line_count); - SCM pages = make_pages (best_result.systems_per_page_, lines); - return pages; -} + if (cur.demerits_ < this_best_demerits || isinf (best.demerits_)) + { + this_best_demerits = cur.demerits_; + lower_bound = div[d]; + } -SCM -Optimal_page_breaking::make_lines (vector line_count) -{ - assert (line_count.size () == all_.size ()); + vector det = line_details (0, end, div[d]); + bool all_lines_stretched = true; + for (vsize i = 0; i < det.size (); i++) + if (det[i].force_ < 0) + all_lines_stretched = false; - SCM ret = SCM_EOL; - for (vsize i = 0; i < all_.size (); i++) - { - if (all_[i].pscore_) - { - vector line_brk = line_breaking_[i].get_solution (0, VPOS, line_count[i]); - System *sys = all_[i].pscore_->root_system (); - - sys->break_into_pieces (line_brk); - ret = scm_append (scm_list_2 (ret, scm_vector_to_list (sys->get_paper_systems ()))); - } - else - { - SCM l = scm_cons (all_[i].prob_->self_scm (), SCM_EOL); - ret = scm_append (scm_list_2 (ret, l)); - all_[i].prob_->unprotect (); + if (all_lines_stretched) + max_page_count = min (max_page_count, cur_page_count + 1); } } - return ret; + + break_into_pieces (0, end, best_division); + SCM lines = systems (); + return make_pages (best.systems_per_page_, lines); } +