X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Foptimal-page-breaking.cc;h=3c26c9abe08c5d15ac932cd4f2ed7f025f6a19f2;hb=c6e7cab0e32ac98a1f188afb82e536679e0ae659;hp=800c52459163b6743b2e6bc664d489e073b85c4d;hpb=ba420bc05855eeca5fb937939261baffd614c2ef;p=lilypond.git diff --git a/lily/optimal-page-breaking.cc b/lily/optimal-page-breaking.cc index 800c524591..3c26c9abe0 100644 --- a/lily/optimal-page-breaking.cc +++ b/lily/optimal-page-breaking.cc @@ -1,13 +1,14 @@ /* - 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 "international.hh" #include "optimal-page-breaking.hh" #include "output-def.hh" #include "page-spacing.hh" @@ -16,8 +17,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) { } @@ -25,148 +33,130 @@ Optimal_page_breaking::~Optimal_page_breaking () { } -Spacing_result -Optimal_page_breaking::try_page_spacing (vector line_count) +SCM +Optimal_page_breaking::solve () { - vector lines = get_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")); - - /* 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); - - for (vsize i = 0; i < lines.size (); i++) + vsize end = last_break_position (); + vsize max_sys_count = max_system_count (0, end); + vsize first_page_num = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1); + SCM forced_page_count = book_->paper_->c_variable ("page-count"); + + set_to_ideal_line_configuration (0, end); + + Page_spacing_result best; + vsize page_count = robust_scm2int (forced_page_count, 1); + Line_division ideal_line_division = current_configuration (0); + Line_division best_division = ideal_line_division; + vsize min_sys_count = 1; + vsize ideal_sys_count = system_count (); + + if (!scm_is_integer (forced_page_count)) { - line_force += fabs (lines[i].force_); - line_penalty += lines[i].break_penalty_; + /* find out the ideal number of pages */ + message (_ ("Finding the ideal number of pages...")); + + best = space_systems_on_best_pages (0, first_page_num); + page_count = best.systems_per_page_.size (); + + ideal_sys_count = best.system_count (); + min_sys_count = ideal_sys_count - best.systems_per_page_.back (); + + if (page_count > 1 && best.systems_per_page_[page_count - 2] > 1) + min_sys_count -= best.systems_per_page_[page_count - 2]; } - - 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++) + else { - Real uniformity = fabs (ret.force_[i] - ret.force_[i-1]); - ret.demerits_ += (ret.force_[i] * ret.force_[i] - + uniformity * uniformity) * page_weighting; + /* todo: the following line will spit out programming errors if the + ideal line spacing doesn't fit on PAGE_COUNT pages */ + best = space_systems_on_n_pages (0, page_count, first_page_num); + min_sys_count = page_count; } - 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++) + if (page_count == 1) + message (_ ("Fitting music on 1 page...")); + else if (scm_is_integer (forced_page_count)) + message (_f ("Fitting music on %d pages...", (int)page_count)); + else + message (_f ("Fitting music on %d or %d pages...", (int)page_count-1, (int)page_count)); + + /* try a smaller number of systems than the ideal number for line breaking */ + Line_division bound = ideal_line_division; + for (vsize sys_count = ideal_sys_count; --sys_count >= min_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]; - } + Page_spacing_result best_for_this_sys_count; + set_current_breakpoints (0, end, sys_count, Line_division (), bound); - 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++) + for (vsize i = 0; i < current_configuration_count (); i++) { - Spacing_result cur = try_page_spacing (div[i]); - if (cur.demerits_ < this_best_result.demerits_) + vsize min_p_count = min_page_count (i, first_page_num); + Page_spacing_result cur; + + if (min_p_count == page_count || scm_is_integer (forced_page_count)) + cur = space_systems_on_n_pages (i, page_count, first_page_num); + 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_)) { - this_best_result = cur; - this_best_line_count = div[i]; + best_for_this_sys_count = cur; + bound = current_configuration (i); } } - last_best_line_count = this_best_line_count; - if (this_best_result.demerits_ < best_result.demerits_) + if (best_for_this_sys_count.demerits_ < best.demerits_ || isinf (best.demerits_)) { - best_line_count = this_best_line_count; - best_result = this_best_result; + best = best_for_this_sys_count; + best_division = bound; } - } 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); + /* 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; + - SCM lines = make_lines (best_line_count); - SCM pages = make_pages (best_result.systems_per_page_, lines); - return pages; -} - -SCM -Optimal_page_breaking::make_lines (vector line_count) -{ - assert (line_count.size () == all_.size ()); + if (isinf (best_for_this_sys_count.demerits_)) + break; + } - SCM ret = SCM_EOL; - for (vsize i = 0; i < all_.size (); i++) + /* try a larger number of systems than the ideal line breaking number. This + is more or less C&P, but the loop bounds make it difficult to try something + like do {...} while (flip(&d) != UP). */ + bound = ideal_line_division; + for (vsize sys_count = ideal_sys_count+1; sys_count <= max_sys_count; sys_count++) { - if (all_[i].pscore_) - { - vector line_brk = line_breaking_[i].get_solution (0, VPOS, line_count[i]); - System *sys = all_[i].pscore_->root_system (); + Real best_demerits_for_this_sys_count = infinity_f; + set_current_breakpoints (0, end, sys_count, bound); - sys->break_into_pieces (line_brk); - ret = scm_append (scm_list_2 (ret, scm_vector_to_list (sys->get_paper_systems ()))); - } - else + for (vsize i = 0; i < current_configuration_count (); i++) { - SCM l = scm_cons (all_[i].prob_->self_scm (), SCM_EOL); - ret = scm_append (scm_list_2 (ret, l)); - all_[i].prob_->unprotect (); + vsize min_p_count = min_page_count (i, first_page_num); + Page_spacing_result cur; + + if (min_p_count > page_count) + continue; + else + cur = space_systems_on_n_pages (i, page_count, first_page_num); + + if (cur.demerits_ < best.demerits_ || isinf (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)) + { + best_demerits_for_this_sys_count = cur.demerits_; + bound = current_configuration (i); + } } + if (isinf (best_demerits_for_this_sys_count)) + break; } - return ret; + + message (_ ("Drawing systems...")); + break_into_pieces (0, end, best_division); + SCM lines = systems (); + return make_pages (best.systems_per_page_, lines); } +