X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fpage-breaking.cc;h=b6951925ad7ce7cc518b6b68f90efc225201eb78;hb=794a037c19a838dd56ceb59e2280059fb80d944a;hp=2cfb24bee7c5e203d366a777de967341622649cf;hpb=9abdb715196339a70bfbc8200e851eb42f192754;p=lilypond.git diff --git a/lily/page-breaking.cc b/lily/page-breaking.cc index 2cfb24bee7..b6951925ad 100644 --- a/lily/page-breaking.cc +++ b/lily/page-breaking.cc @@ -19,7 +19,8 @@ #include "system.hh" #include "warn.hh" -/* for each forbidden page break, merge the systems around it into one system. */ +/* for each forbidden page break, merge the systems around it into one + system. */ static vector compress_lines (const vector &orig) { @@ -84,20 +85,20 @@ uncompress_solution (vector const &systems_per_page, vsize Page_breaking::next_system (Break_position const &break_pos) const { - vsize sys = break_pos.sys_; + vsize sys = break_pos.system_spec_index_; if (sys == VPOS) /* beginning of the book */ return 0; - if (all_[sys].pscore_ && !break_pos.score_ender_) + if (system_specs_[sys].pscore_ && !break_pos.score_ender_) return sys; /* the score overflows the previous page */ - return sys + 1; /* this page starts with a new sys */ + return sys + 1; /* this page starts with a new System_spec */ } Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break) { book_ = pb; - ragged_ = to_boolean (pb->paper_->c_variable ("ragged")); - ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last")); + ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom")); + ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom")); create_system_list (); find_chunks_and_breaks (is_break); } @@ -126,22 +127,23 @@ Page_breaking::line_breaker_args (vsize sys, vsize *line_breaker_start, vsize *line_breaker_end) { - assert (all_[sys].pscore_); - assert (next_system (start) <= sys && sys <= end.sys_); + assert (system_specs_[sys].pscore_); + assert (next_system (start) <= sys && sys <= end.system_spec_index_); - if (start.sys_ == sys) + if (start.system_spec_index_ == sys) *line_breaker_start = start.score_break_; else *line_breaker_start = 0; - if (end.sys_ == sys) + if (end.system_spec_index_ == sys) *line_breaker_end = end.score_break_; else *line_breaker_end = VPOS; } void -Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div) +Page_breaking::break_into_pieces (vsize start_break, vsize end_break, + Line_division const &div) { vector chunks = chunk_list (start_break, end_break); bool ignore_div = false; @@ -154,7 +156,7 @@ Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_divis for (vsize i = 0; i + 1 < chunks.size (); i++) { vsize sys = next_system (chunks[i]); - if (all_[sys].pscore_) + if (system_specs_[sys].pscore_) { vsize start; vsize end; @@ -163,7 +165,7 @@ Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_divis vector pos = ignore_div ? line_breaking_[sys].best_solution (start, end) : line_breaking_[sys].solve (start, end, div[i]); - all_[sys].pscore_->root_system ()->break_into_pieces (pos); + system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos); } } } @@ -172,17 +174,19 @@ SCM Page_breaking::systems () { SCM ret = SCM_EOL; - for (vsize sys = 0; sys < all_.size (); sys++) + for (vsize sys = 0; sys < system_specs_.size (); sys++) { - if (all_[sys].pscore_) + if (system_specs_[sys].pscore_) { - all_[sys].pscore_->root_system ()->do_break_substitution_and_fixup_refpoints (); - SCM lines = all_[sys].pscore_->root_system ()->get_broken_system_grobs (); + system_specs_[sys].pscore_->root_system () + ->do_break_substitution_and_fixup_refpoints (); + SCM lines = system_specs_[sys].pscore_->root_system () + ->get_broken_system_grobs (); ret = scm_cons (lines, ret); } else { - Prob *pb = all_[sys].prob_; + Prob *pb = system_specs_[sys].prob_; ret = scm_cons (scm_list_1 (pb->self_scm ()), ret); pb->unprotect (); } @@ -214,11 +218,11 @@ Page_breaking::breakpoint_property (vsize breakpoint, char const *str) { Break_position const &pos = breaks_[breakpoint]; - if (pos.sys_ == VPOS) + if (pos.system_spec_index_ == VPOS) return SCM_EOL; - if (all_[pos.sys_].pscore_) + if (system_specs_[pos.system_spec_index_].pscore_) return pos.col_->get_property (str); - return all_[pos.sys_].prob_->get_property (str); + return system_specs_[pos.system_spec_index_].prob_->get_property (str); } SCM @@ -233,25 +237,45 @@ Page_breaking::make_pages (vector lines_per_page, SCM systems) page_stencil = scm_variable_ref (page_stencil); SCM book = book_->self_scm (); - bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom")); - bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom")); - int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1); + int first_page_number + = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1); SCM ret = SCM_EOL; + SCM label_page_table = SCM_EOL; for (vsize i = 0; i < lines_per_page.size (); i++) { SCM page_num = scm_from_int (i + first_page_number); SCM last = scm_from_bool (i == lines_per_page.size () - 1); - SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last)); + SCM rag = scm_from_bool (ragged () || (to_boolean (last) + && ragged_last ())); SCM line_count = scm_from_int (lines_per_page[i]); SCM lines = scm_list_head (systems, line_count); SCM page = scm_apply_0 (make_page, - scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED)); + scm_list_n (book, lines, page_num, + rag, last, SCM_UNDEFINED)); + + /* collect labels */ + for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l)) + { + SCM labels = SCM_EOL; + if (Grob * line = unsmob_grob (scm_car (l))) + { + System *system = dynamic_cast (line); + labels = system->get_property ("labels"); + } + else if (Prob *prob = unsmob_prob (scm_car (l))) + labels = prob->get_property ("labels"); + + for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls)) + label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num), + label_page_table); + } scm_apply_1 (page_stencil, page, SCM_EOL); ret = scm_cons (page, ret); systems = scm_list_tail (systems, line_count); } + book_->paper_->set_variable (ly_symbol2scm ("label-page-table"), label_page_table); ret = scm_reverse (ret); return ret; } @@ -279,7 +303,7 @@ Page_breaking::create_system_list () scm_vector_to_list (ps->get_paper_systems ()), scm_cdr (s))); else - all_.push_back (System_spec (ps)); + system_specs_.push_back (System_spec (ps)); } else { @@ -287,7 +311,7 @@ Page_breaking::create_system_list () assert (pb); pb->protect (); - all_.push_back (System_spec (pb)); + system_specs_.push_back (System_spec (pb)); } } } @@ -300,17 +324,18 @@ Page_breaking::find_chunks_and_breaks (Break_predicate is_break) chunks_.push_back (Break_position ()); breaks_.push_back (Break_position ()); - for (vsize i = 0; i < all_.size (); i++) + for (vsize i = 0; i < system_specs_.size (); i++) { - if (all_[i].pscore_) + if (system_specs_[i].pscore_) { - vector cols = all_[i].pscore_->root_system ()->used_columns (); + vector cols + = system_specs_[i].pscore_->root_system ()->used_columns (); vector line_breaker_columns; line_breaker_columns.push_back (0); for (vsize j = 1; j < cols.size (); j++) { - bool last = j == cols.size () - 1; + bool last = (j == cols.size () - 1); bool break_point = is_break (cols[j]); bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym; Break_position cur_pos = Break_position (i, @@ -318,7 +343,7 @@ Page_breaking::find_chunks_and_breaks (Break_predicate is_break) cols[j], last); - if (break_point || (i == all_.size () - 1 && last)) + if (break_point || (i == system_specs_.size () - 1 && last)) breaks_.push_back (cur_pos); if (chunk_end || last) chunks_.push_back (cur_pos); @@ -326,15 +351,18 @@ Page_breaking::find_chunks_and_breaks (Break_predicate is_break) if ((break_point || chunk_end) && !last) line_breaker_columns.push_back (j); } - line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns)); + line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns)); } else { /* TODO: we want some way of applying Break_p to a prob? */ - if (i == all_.size () - 1) + if (i == system_specs_.size () - 1) breaks_.push_back (Break_position (i)); chunks_.push_back (Break_position (i)); + + /* FIXME: shouldn't we push a Null_breaker or similar dummy + class? --hwn */ line_breaking_.push_back (Constrained_breaking (NULL)); } } @@ -346,8 +374,8 @@ Page_breaking::chunk_list (vsize start_index, vsize end_index) Break_position start = breaks_[start_index]; Break_position end = breaks_[end_index]; - vsize i; - for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++) + vsize i = 0; + for (; i < chunks_.size () && chunks_[i] <= start; i++) ; vector ret; @@ -383,7 +411,8 @@ Page_breaking::max_system_count (vsize start, vsize end) } Page_breaking::Line_division -Page_breaking::system_count_bounds (vector const &chunks, bool min) +Page_breaking::system_count_bounds (vector const &chunks, + bool min) { assert (chunks.size () >= 2); @@ -393,7 +422,7 @@ Page_breaking::system_count_bounds (vector const &chunks, bool m for (vsize i = 0; i + 1 < chunks.size (); i++) { vsize sys = next_system (chunks[i]); - if (all_[sys].pscore_) + if (system_specs_[sys].pscore_) { vsize start; vsize end; @@ -433,6 +462,57 @@ Page_breaking::set_current_breakpoints (vsize start, lower_bound, upper_bound, &work_in_progress); + + /* we only consider a constant number of configurations. Otherwise, + this becomes slow when there are many small scores. The constant + 5 is somewhat arbitrary. */ + if (current_configurations_.size () > 5) + { + vector > dems_and_indices; + + for (vsize i = 0; i < current_configurations_.size (); i++) + { + cache_line_details (i); + Real dem = 0; + for (vsize j = 0; j < cached_line_details_.size (); j++) + dem += cached_line_details_[j].force_ * cached_line_details_[j].force_ + + cached_line_details_[j].break_penalty_; + + dems_and_indices.push_back (pair (dem, i)); + } + vector_sort (dems_and_indices, less > ()); + + vector best_5_configurations; + for (vsize i = 0; i < 5; i++) + best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]); + + clear_line_details_cache (); + current_configurations_ = best_5_configurations; + } +} + +void +Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end) +{ + current_chunks_ = chunk_list (start, end); + current_start_breakpoint_ = start; + current_end_breakpoint_ = end; + clear_line_details_cache (); + + Line_division div; + for (vsize i = 0; i+1 < current_chunks_.size (); i++) + { + vsize sys = next_system (current_chunks_[i]); + if (system_specs_[sys].pscore_) + { + line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end); + div.push_back (line_breaking_[sys].best_solution (start, end).size ()); + } + else + div.push_back (1); + } + current_configurations_.clear (); + current_configurations_.push_back (div); } vsize @@ -446,6 +526,7 @@ Page_breaking::cache_line_details (vsize configuration_index) { if (cached_configuration_index_ != configuration_index) { + cached_configuration_index_ = configuration_index; SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding"); if (!scm_is_number (padding_scm)) padding_scm = book_->paper_->c_variable ("between-system-padding"); @@ -456,7 +537,7 @@ Page_breaking::cache_line_details (vsize configuration_index) for (vsize i = 0; i + 1 < current_chunks_.size (); i++) { vsize sys = next_system (current_chunks_[i]); - if (all_[sys].pscore_) + if (system_specs_[sys].pscore_) { vsize start; vsize end; @@ -468,8 +549,10 @@ Page_breaking::cache_line_details (vsize configuration_index) else { assert (div[i] == 1); - uncompressed_line_details_.push_back (Line_details (all_[sys].prob_)); - uncompressed_line_details_.back ().padding_ = padding; + uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_)); + uncompressed_line_details_.back ().padding_ = + robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"), + padding); } } cached_line_details_ = compress_lines (uncompressed_line_details_); @@ -537,7 +620,7 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num) Real ext_len = cached_line_details_[i].extent_.length (); Real next_rod_height = cur_rod_height + ext_len + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0); - Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]); + Real next_spring_height = cur_spring_height + cached_line_details_[i].space_; Real next_height = next_rod_height + (ragged () ? next_spring_height : 0); @@ -546,7 +629,7 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num) && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force"))) { cur_rod_height = ext_len; - cur_spring_height = line_space (cached_line_details_[i]); + cur_spring_height = cached_line_details_[i].space_; cur_page_height = page_height (first_page_num + ret, false); ret++; } @@ -581,19 +664,19 @@ Page_breaking::min_page_count (vsize configuration, vsize first_page_num) return ret; } -Spacing_result +Page_spacing_result Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num) { - Spacing_result ret; + Page_spacing_result ret; assert (n >= min_page_count (configuration, first_page_num)); cache_line_details (configuration); if (n > cached_line_details_.size ()) - return Spacing_result (); + return Page_spacing_result (); if (n == 1) ret = space_systems_on_1_page (cached_line_details_, - page_height (first_page_num, last ()), - ragged () || (last () && ragged_last ())); + page_height (first_page_num, is_last ()), + ragged () || (is_last () && ragged_last ())); else if (n == 2) ret = space_systems_on_2_pages (configuration, first_page_num); else @@ -608,25 +691,52 @@ Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize fir Real Page_breaking::blank_page_penalty () const { - SCM penalty_sym = last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force"); + SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force"); return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0); } -Spacing_result +Page_spacing_result Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num) { - Spacing_result n_res = space_systems_on_n_pages (configuration, n, first_page_num); - Spacing_result m_res = space_systems_on_n_pages (configuration, n+1, first_page_num); + Page_spacing_result n_res; + Page_spacing_result m_res; + + cache_line_details (configuration); + vsize min_p_count = min_page_count (configuration, first_page_num); + + if (n == 1) + { + bool rag = ragged () || (is_last () && ragged_last ()); + Real height = page_height (first_page_num, is_last ()); + + if (1 >= min_p_count) + n_res = space_systems_on_1_page (cached_line_details_, height, rag); + if (1 < cached_line_details_.size ()) + m_res = space_systems_on_2_pages (configuration, first_page_num); + } + else + { + Page_spacer ps (cached_line_details_, first_page_num, this); + + if (n >= min_p_count) + n_res = ps.solve (n); + if (n < cached_line_details_.size ()) + m_res = ps.solve (n+1); + } + + m_res = finalize_spacing_result (configuration, m_res); + n_res = finalize_spacing_result (configuration, n_res); + Real penalty = blank_page_penalty (); n_res.demerits_ += penalty; - n_res.force_.back () += penalty; - if (m_res.demerits_ < n_res.demerits_) - return m_res; - return n_res; + if (n_res.force_.size ()) + n_res.force_.back () += penalty; + + return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res; } -Spacing_result +Page_spacing_result Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num) { vsize min_p_count = min_page_count (configuration, first_page_num); @@ -634,13 +744,13 @@ Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_pag cache_line_details (configuration); Page_spacer ps (cached_line_details_, first_page_num, this); - Spacing_result best = ps.solve (min_p_count); + Page_spacing_result best = ps.solve (min_p_count); best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0; best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0; for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++) { - Spacing_result cur = ps.solve (i); + Page_spacing_result cur = ps.solve (i); cur.demerits_ += (i % 2) ? odd_pages_penalty : 0; if (cur.demerits_ < best.demerits_) best = cur; @@ -649,11 +759,73 @@ Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_pag return finalize_spacing_result (configuration, best); } +Page_spacing_result +Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num) +{ + Page_spacing_result res; + vsize page = 0; + vsize page_first_line = 0; + Page_spacing space (page_height (first_page_num, false)); + + cache_line_details (configuration); + for (vsize line = 0; line < cached_line_details_.size (); line++) + { + Real prev_force = space.force_; + space.append_system (cached_line_details_[line]); + if ((line > page_first_line) + && (isinf (space.force_) + || ((line > 0) + && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force"))))) + { + res.systems_per_page_.push_back (line - page_first_line); + res.force_.push_back (prev_force); + res.penalty_ += cached_line_details_[line-1].page_penalty_; + page++; + space.resize (page_height (first_page_num + page, false)); + space.clear (); + space.append_system (cached_line_details_[line]); + page_first_line = line; + } + + if (line == cached_line_details_.size () - 1) + { + /* This is the last line */ + /* When the last page height was computed, we did not know yet that it + * was the last one. If the systems put on it don't fit anymore, the last + * system is moved to a new page */ + space.resize (page_height (first_page_num + page, true)); + if ((line > page_first_line) && (isinf (space.force_))) + { + res.systems_per_page_.push_back (line - page_first_line); + res.force_.push_back (prev_force); + /* the last page containing the last line */ + space.resize (page_height (first_page_num + page + 1, true)); + space.clear (); + space.append_system (cached_line_details_[line]); + res.systems_per_page_.push_back (1); + res.force_.push_back (space.force_); + res.penalty_ += cached_line_details_[line-1].page_penalty_; + res.penalty_ += cached_line_details_[line].page_penalty_; + } + else + { + res.systems_per_page_.push_back (line + 1 - page_first_line); + res.force_.push_back (space.force_); + res.penalty_ += cached_line_details_[line].page_penalty_; + } + } + } + return finalize_spacing_result (configuration, res); +} + /* Calculate demerits and fix res.systems_per_page_ so that it refers to the original line numbers, not the ones given by compress_lines (). */ -Spacing_result -Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res) +Page_spacing_result +Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res) { + if (res.force_.empty ()) + return res; + cache_line_details (configuration); res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_); @@ -694,11 +866,11 @@ Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res) space_systems functions. This is because space_systems_on_1_page is (unlike the other space_systems functions) sometimes called on subsets of a full configuration. */ -Spacing_result +Page_spacing_result Page_breaking::space_systems_on_1_page (vector const &lines, Real page_height, bool ragged) { Page_spacing space (page_height); - Spacing_result ret; + Page_spacing_result ret; for (vsize i = 0; i < lines.size (); i++) space.append_system (lines[i]); @@ -711,13 +883,13 @@ Page_breaking::space_systems_on_1_page (vector const &lines, Real return ret; } -Spacing_result +Page_spacing_result Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num) { Real page1_height = page_height (first_page_num, false); - Real page2_height = page_height (first_page_num+1, last ()); + Real page2_height = page_height (first_page_num + 1, is_last ()); bool ragged1 = ragged (); - bool ragged2 = ragged () || (last () && ragged_last ()); + bool ragged2 = ragged () || (is_last () && ragged_last ()); /* if there is a forced break, this reduces to 2 1-page problems */ cache_line_details (configuration); @@ -726,8 +898,8 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n { vector lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1); vector lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ()); - Spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1); - Spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2); + Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1); + Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2); p1.systems_per_page_.push_back (p2.systems_per_page_[0]); p1.force_.push_back (p2.force_[0]); @@ -762,8 +934,9 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n Real best_demerits = infinity_f; for (vsize i = 0; i < page1_force.size (); i++) { - Real dem = page1_force[i] * page1_force[i] - + page2_force[i] * page2_force[i] + Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i]; + Real uneven = 2 * (page1_force[i] - page2_force[i]); + Real dem = uneven * uneven + f + cached_line_details_[i+1].page_penalty_ + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_; if (dem < best_demerits) @@ -773,7 +946,7 @@ Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_n } } - Spacing_result ret; + Page_spacing_result ret; ret.systems_per_page_.push_back (best_sys_count); ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count); ret.force_.push_back (page1_force[best_sys_count-1]); @@ -803,7 +976,14 @@ Page_breaking::current_configuration (vsize configuration_index) const return current_configurations_[configuration_index]; } -bool Page_breaking::last () const +bool +Page_breaking::is_last () const +{ + return current_end_breakpoint_ == last_break_position (); +} + +vsize +Page_breaking::last_break_position () const { - return current_end_breakpoint_ == breaks_.size () - 1; + return breaks_.size () - 1; }