Index: ChangeLog =================================================================== RCS file: /sources/lilypond/lilypond/ChangeLog,v retrieving revision 1.5241 diff -u -r1.5241 ChangeLog --- ChangeLog 14 Aug 2006 08:30:20 -0000 1.5241 +++ ChangeLog 16 Aug 2006 21:35:04 -0000 @@ -1,3 +1,23 @@ +2006-08-17 Joe Neeman + + * lily/paper-column-engraver.cc (finalize): make the end of a score + breakable by default. This is to balance out a change in behaviour + of the page-turn-breaker which no longer makes the end of a score + breakable. + + * lily/paper-book.cc (pages): set the systems_ once the pages are + broken + + * lily/page-turn-page-breaking.cc (calc_subproblem): use the new + Page_breaking interface. + + * lily/page-breaking.cc (class Page_breaking): make the interface + more consistent and provide abstractions for dealing with + Line_divisions. + + * lily/optimal-page-breaking.cc (solve): use a more straightforward + algorithm. Use the new interface to Page_breaking. + 2006-08-14 Mats Bengtsson * scripts/lilypond-book.py (output): Remove obsolete(!?) Index: lily/optimal-page-breaking.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/optimal-page-breaking.cc,v retrieving revision 1.1 diff -u -r1.1 optimal-page-breaking.cc --- lily/optimal-page-breaking.cc 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/optimal-page-breaking.cc 16 Aug 2006 21:35:04 -0000 @@ -1,5 +1,5 @@ /* - 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 @@ -16,8 +16,15 @@ #include "prob.hh" #include "system.hh" +static bool +break_p (Grob *g) +{ + (void) g; /* shutup warning */ + return false; +} + Optimal_page_breaking::Optimal_page_breaking (Paper_book *pb) - : Page_breaking (pb, false) + : Page_breaking (pb, break_p) { } @@ -26,9 +33,9 @@ } 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); @@ -65,108 +72,60 @@ 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_) { - 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; + if (cur.demerits_ < this_best_demerits) + { + this_best_demerits = cur.demerits_; + lower_bound = div[d]; + } + + 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; + + if (all_lines_stretched) + max_page_count = cur_page_count + 1; } - } 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]; + break_into_pieces (0, end, best_division); + vector lines = systems (); + SCM lines_scm = SCM_EOL; - } while (flip (&d) != DOWN); + for (vsize i = 0; i < lines.size (); i++) + lines_scm = scm_cons (lines[i], lines_scm); + lines_scm = scm_reverse (lines_scm); - SCM lines = make_lines (best_line_count); - SCM pages = make_pages (best_result.systems_per_page_, lines); + SCM pages = make_pages (best.systems_per_page_, lines_scm); return pages; } -SCM -Optimal_page_breaking::make_lines (vector line_count) -{ - assert (line_count.size () == all_.size ()); - - 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 (); - } - } - return ret; -} Index: lily/page-breaking-scheme.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/page-breaking-scheme.cc,v retrieving revision 1.1 diff -u -r1.1 page-breaking-scheme.cc --- lily/page-breaking-scheme.cc 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/page-breaking-scheme.cc 16 Aug 2006 21:35:04 -0000 @@ -28,3 +28,4 @@ Optimal_page_breaking b (unsmob_paper_book (pb)); return b.solve (); } + Index: lily/page-breaking.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/page-breaking.cc,v retrieving revision 1.1 diff -u -r1.1 page-breaking.cc --- lily/page-breaking.cc 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/page-breaking.cc 16 Aug 2006 21:35:05 -0000 @@ -1,6 +1,6 @@ /* page-breaking.cc -- implement a superclass and utility - functions for use by various page-breaking algorithms + functions shared by various page-breaking algorithms source file of the GNU LilyPond music typesetter @@ -19,27 +19,6 @@ #include "system.hh" #include "warn.hh" -System_spec::System_spec (Paper_score *ps, int break_count) -{ - pscore_ = ps; - prob_ = 0; - score_break_count_ = break_count; -} - -System_spec::System_spec (Prob *pb) -{ - pscore_ = 0; - prob_ = pb; - score_break_count_ = 0; -} - -System_spec::System_spec () -{ - pscore_ = 0; - prob_ = 0; - score_break_count_ = 0; -} - /* for Page_breaking, the start index (when we are dealing with the stuff between a pair of breakpoints) refers to the break_ index of the end of the previous page. So the system index of the start of the current page @@ -47,21 +26,22 @@ it. */ /* Turn a break index into the sys index that starts the next page */ -vsize Page_breaking::next_system (vsize start) const +vsize Page_breaking::next_system (Break_position const &break_pos) const { - vsize sys = breaks_[start].sys_; + vsize sys = break_pos.sys_; - if (sys == VPOS) /* beginning of the piece */ + if (sys == VPOS) /* beginning of the book */ return 0; - if (all_[sys].pscore_ && all_[sys].score_break_count_ > breaks_[start].score_break_) + if (all_[sys].pscore_ && !break_pos.score_ender_) return sys; /* the score overflows the previous page */ return sys + 1; /* this page starts with a new sys */ } -Page_breaking::Page_breaking (Paper_book *pb, bool allow_intra_score_breaks) +Page_breaking::Page_breaking (Paper_book *pb, Break_p break_p) { book_ = pb; - create_system_list (allow_intra_score_breaks); + create_system_list (); + find_chunks_and_breaks (break_p); } Page_breaking::~Page_breaking () @@ -70,67 +50,96 @@ /* translate indices into breaks_ into start-end parameters for the line breaker */ void -Page_breaking::line_breaker_args (vsize i, vsize *start, vsize *end) +Page_breaking::line_breaker_args (vsize sys, + Break_position const &start, + Break_position const &end, + vsize *line_breaker_start, + vsize *line_breaker_end) { - assert (all_[i].pscore_); - assert (next_system (*start) <= i && i <= breaks_[*end].sys_); + assert (all_[sys].pscore_); + assert (next_system (start) <= sys && sys <= end.sys_); - vsize start_col = 0; - vsize end_col = VPOS; - - if (breaks_[*start].sys_ == i) - start_col = breaks_[*start].score_break_; - if (breaks_[*end].sys_ == i) - end_col = breaks_[*end].score_break_; + if (start.sys_ == sys) + *line_breaker_start = start.score_break_; + else + *line_breaker_start = 0; - assert (end_col && (end_col == VPOS || end_col <= all_[breaks_[*end].sys_].score_break_count_)); - *start = start_col; - *end = end_col; + if (end.sys_ == sys) + *line_breaker_end = end.score_break_; + else + *line_breaker_end = VPOS; } -vector -Page_breaking::get_line_breaks (vsize i, vsize sys_count, vsize start, vsize end) +void +Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div) { - assert (all_[i].pscore_); - line_breaker_args (i, &start, &end); - return line_breaking_[i].get_solution (start, end, sys_count); + vector chunks = chunk_list (start_break, end_break); + assert (chunks.size () == div.size () + 1); + + for (vsize i = 0; i < chunks.size () - 1; i++) + { + vsize sys = next_system (chunks[i]); + if (all_[sys].pscore_) + { + vsize start; + vsize end; + line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end); + + vector pos = line_breaking_[sys].get_solution (start, end, div[i]); + all_[sys].pscore_->root_system ()->break_into_pieces (pos); + } + } } -vector -Page_breaking::get_line_details (vsize start_break, vsize end_break, vector const &div) +vector +Page_breaking::systems () { - vector ret; - - for (vsize i = next_system (start_break); i <= breaks_[end_break].sys_; i++) + vector ret; + for (vsize sys = 0; sys < all_.size (); sys++) { - if (all_[i].pscore_) + if (all_[sys].pscore_) { - vsize div_index = i - next_system (start_break); - vsize start = start_break; - vsize end = end_break; - - line_breaker_args (i, &start, &end); - vector l = line_breaking_[i].get_details (start, end, div[div_index]); - ret.insert (ret.end (), l.begin (), l.end ()); + SCM lines = all_[sys].pscore_->root_system ()->get_paper_systems (); + vsize line_count = scm_c_vector_length (lines); + + for (vsize i = 0; i < line_count; i++) + ret.push_back (scm_c_vector_ref (lines, i)); } else - ret.push_back (Line_details (all_[i].prob_)); + { + ret.push_back (all_[sys].prob_->self_scm ()); + all_[sys].prob_->unprotect (); + } } return ret; } -vsize -Page_breaking::get_min_systems (vsize i, vsize start, vsize end) +vector +Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div) { - line_breaker_args (i, &start, &end); - return line_breaking_[i].get_min_systems (start, end); -} + vector chunks = chunk_list (start_break, end_break); + vector ret; + assert (chunks.size () == div.size () + 1); -vsize -Page_breaking::get_max_systems (vsize i, vsize start, vsize end) -{ - line_breaker_args (i, &start, &end); - return line_breaking_[i].get_max_systems (start, end); + for (vsize i = 0; i < chunks.size () - 1; i++) + { + vsize sys = next_system (chunks[i]); + if (all_[sys].pscore_) + { + vsize start; + vsize end; + line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end); + + vector details = line_breaking_[sys].get_details (start, end, div[i]); + ret.insert (ret.end (), details.begin (), details.end ()); + } + else + { + assert (div[i] == 1); + ret.push_back (Line_details (all_[sys].prob_)); + } + } + return ret; } Real @@ -179,105 +188,181 @@ return scm_reverse (ret); } -/* if allow_intra_score_breaks is false, that doesn't necessarily mean that there will - be no page turns in the middle of a score, only that we don't give special - consideration to any internal part of a score. +/* The page-turn-page-breaker needs to have a line-breaker between any two + columns with non-NULL page-turn-permission. + + The optimal-breaker needs to have a line-breaker between any two columns + with page-break-permission = 'force. - Corollary: if allow_intra_score_breaks is false, any \pageTurn or \noPageTurn commands - in the middle of a score will be ignored. + By using a grob predicate, we can accommodate both of these uses. */ void -Page_breaking::create_system_list (bool allow_intra_score_breaks) +Page_breaking::create_system_list () { - breaks_.push_back (Break_position ()); - SCM specs = book_->get_system_specs (); for (SCM s = specs; s != SCM_EOL; s = scm_cdr (s)) { if (Paper_score *ps = dynamic_cast (unsmob_music_output (scm_car (s)))) - { - /* add a breakpoint at the end of the last score, if necessary */ - if (all_.size () && all_.back ().pscore_) - breaks_.push_back (Break_position (all_.size () - 1, - all_.back ().score_break_count_)); - - vector score_brk; - if (allow_intra_score_breaks) - score_brk = find_page_break_indices (ps); - - all_.push_back (System_spec (ps, score_brk.size () + 1)); - - for (vsize i = 0; i < score_brk.size(); i++) - breaks_.push_back (Break_position (all_.size () - 1, i + 1)); - - /* include a line breaker at the start of the score */ - score_brk.insert (score_brk.begin (), 0); - line_breaking_.push_back (Constrained_breaking (score_brk)); - line_breaking_.back ().set_pscore (ps); - } + all_.push_back (System_spec (ps)); else { Prob *pb = unsmob_prob (scm_car (s)); assert (pb); pb->protect (); - // ignore penalties (from break-before) in favour of using \pageBreak at the - // end of the score - if (all_.size () && all_.back ().pscore_) - breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_)); all_.push_back (System_spec (pb)); - line_breaking_.push_back (Constrained_breaking ()); } } +} - /* add the ending breakpoint */ - if (all_.back ().pscore_) - breaks_.push_back (Break_position (all_.size () - 1, all_.back ().score_break_count_)); - else - breaks_.push_back (Break_position (all_.size () - 1)); +void Page_breaking::find_chunks_and_breaks (Break_p break_p) +{ + SCM force_sym = ly_symbol2scm ("force"); + + chunks_.push_back (Break_position ()); + breaks_.push_back (Break_position ()); + + for (vsize i = 0; i < all_.size (); i++) + { + if (all_[i].pscore_) + { + vector cols = all_[i].pscore_->root_system ()->columns (); + vector line_breaker_columns; + line_breaker_columns.push_back (0); + + for (vsize j = 0; j < cols.size (); j++) + { + bool last = j == cols.size () - 1; + bool break_point = break_p (cols[j]); + bool chunk_end = cols[i]->get_property ("page-break-permission") == force_sym; + Break_position cur_pos = Break_position (i, + line_breaker_columns.size (), + last); + + if (break_point || (i == all_.size () - 1 && last)) + breaks_.push_back (cur_pos); + if (chunk_end || last) + chunks_.push_back (cur_pos); + + if ((break_point || chunk_end) && !last) + line_breaker_columns.push_back (j); + } + line_breaking_.push_back (Constrained_breaking (line_breaker_columns)); + line_breaking_.back ().set_pscore (all_[i].pscore_); + } + else + { + /* TODO: we want some way of applying Break_p to a prob? */ + if (i == all_.size () - 1) + breaks_.push_back (Break_position (i)); + + chunks_.push_back (Break_position (i)); + line_breaking_.push_back (Constrained_breaking ()); + } + } } -vector -Page_breaking::find_page_break_indices (Paper_score *pscore) +vector +Page_breaking::chunk_list (vsize start_index, vsize end_index) { - vector all = pscore->root_system ()->columns (); - vector ret; + Break_position start = breaks_[start_index]; + Break_position end = breaks_[end_index]; - /* we don't include breaks at the beginning and end */ - for (vsize i = 0; i < all.size () - 1; i++) - if (scm_is_symbol (all[i]->get_property ("page-turn-permission"))) - ret.push_back(i); + vsize i; + for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++) + ; + + vector ret; + ret.push_back (start); + for (; i < chunks_.size () && chunks_[i] < end; i++) + ret.push_back (chunks_[i]); + ret.push_back (end); + return ret; +} +vsize +Page_breaking::min_system_count (vsize start, vsize end) +{ + vector chunks = chunk_list (start, end); + Line_division div = system_count_bounds (chunks, true); + vsize ret = 0; + + for (vsize i = 0; i < div.size (); i++) + ret += div[i]; return ret; } -void -Page_breaking::calc_system_count_bounds (vsize start, vsize end, - vector *min, - vector *max) +vsize +Page_breaking::max_system_count (vsize start, vsize end) +{ + vector chunks = chunk_list (start, end); + Line_division div = system_count_bounds (chunks, false); + vsize ret = 0; + + for (vsize i = 0; i < div.size (); i++) + ret += div[i]; + return ret; +} + +Page_breaking::Line_division +Page_breaking::system_count_bounds (vector const &chunks, bool min) { - for (vsize i = next_system (start); i <= breaks_[end].sys_; i++) + assert (chunks.size () >= 2); + + Line_division ret; + ret.resize (chunks.size () - 1, 1); + + for (vsize i = 0; i < chunks.size () - 1; i++) { - if (all_[i].pscore_) - { - min->push_back (get_min_systems (i, start, end)); - max->push_back (get_max_systems (i, start, end)); - } - else - { - min->push_back (1); - max->push_back (1); - } + vsize sys = next_system (chunks[i]); + if (all_[sys].pscore_) + { + vsize start; + vsize end; + line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end); + ret[i] = min + ? line_breaking_[sys].get_min_systems (start, end) + : line_breaking_[sys].get_max_systems (start, end); + } } + + return ret; +} + +vector +Page_breaking::line_divisions (vsize start, + vsize end, + vsize system_count, + Line_division lower_bound, + Line_division upper_bound) +{ + vector chunks = chunk_list (start, end); + + if (!lower_bound.size ()) + lower_bound = system_count_bounds (chunks, true); + if (!upper_bound.size ()) + upper_bound = system_count_bounds (chunks, false); + + assert (lower_bound.size () == chunks.size () - 1); + assert (upper_bound.size () == chunks.size () - 1); + + vector ret; + Line_division work_in_progress; + + line_divisions_rec (system_count, + lower_bound, + upper_bound, + &ret, + &work_in_progress); + return ret; } -/* calculate all possible ways of dividing system_count between the System_specs */ void -Page_breaking::divide_systems (vsize system_count, - vector const &min_sys, - vector const &max_sys, - vector > *result, - vector *cur_division) +Page_breaking::line_divisions_rec (vsize system_count, + Line_division const &min_sys, + Line_division const &max_sys, + vector *result, + Line_division *cur_division) { vsize my_index = cur_division->size (); vsize others_min = 0; @@ -307,8 +392,7 @@ if (my_index == min_sys.size () - 1) result->push_back (*cur_division); else - divide_systems (system_count - i, min_sys, max_sys, result, cur_division); + line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division); cur_division->pop_back (); } } - Index: lily/page-spacing.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/page-spacing.cc,v retrieving revision 1.1 diff -u -r1.1 page-spacing.cc --- lily/page-spacing.cc 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/page-spacing.cc 16 Aug 2006 21:35:05 -0000 @@ -219,43 +219,6 @@ return ret; } -/* for page_count > 2, we use a dynamic algorithm similar to - constrained-breaking -- we have a class that stores the intermediate - calculations so they can be reused for querying different page counts. -*/ - -class Page_spacer -{ -public: - Page_spacer (vector const &lines, Real page_height); - Spacing_result solve (vsize page_count); - -private: - struct Page_spacing_node - { - Page_spacing_node () - { - demerits_ = infinity_f; - force_ = infinity_f; - penalty_ = infinity_f; - prev_ = VPOS; - } - - Real demerits_; - Real force_; - Real penalty_; - vsize prev_; - }; - - Real page_height_; - vector lines_; - Matrix state_; - vsize max_page_count_; - - void resize (vsize page_count); - bool calc_subproblem (vsize page, vsize lines); -}; - Page_spacer::Page_spacer (vector const &lines, Real page_height) : lines_ (lines) { @@ -275,6 +238,9 @@ vsize system = lines_.size () - 1; + if (isinf (state_.at (system, page_count-1).demerits_)) + return Spacing_result (); /* bad number of pages */ + ret.penalty_ = state_.at (system, page_count-1).penalty_ + lines_.back ().page_penalty_ + lines_.back ().turn_penalty_; @@ -430,6 +396,7 @@ Page_spacer ps (compressed_lines, page_height); 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 <= compressed_lines.size (); i++) Index: lily/page-turn-page-breaking.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/page-turn-page-breaking.cc,v retrieving revision 1.1 diff -u -r1.1 page-turn-page-breaking.cc --- lily/page-turn-page-breaking.cc 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/page-turn-page-breaking.cc 16 Aug 2006 21:35:05 -0000 @@ -18,8 +18,14 @@ #include "system.hh" #include "warn.hh" +static bool +break_p (Grob *g) +{ + return scm_is_symbol (g->get_property ("page-turn-permission")); +} + Page_turn_page_breaking::Page_turn_page_breaking (Paper_book *pb) - : Page_breaking (pb, true) + : Page_breaking (pb, break_p) { } @@ -52,7 +58,7 @@ Page_turn_page_breaking::put_systems_on_pages (vsize start, vsize end, vector const &lines, - vector const &div, + Line_division const &div, int page_number) { bool last = end == breaks_.size () - 1; @@ -111,46 +117,26 @@ p_num = f_p_num + p_count + ((f_p_num > 1) ? p_count % 2 : 0); } - vector min_systems; - vector max_systems; - vsize min_system_count = 0; - vsize max_system_count = 0; - this_start_best.demerits_ = infinity_f; - calc_system_count_bounds (start, end, &min_systems, &max_systems); + Line_division min_division; + Line_division max_division; - /* heuristic: we've prepended some music, only the first system is allowed - to get more lines */ - if (this_start_best.page_count_ == 2 && this_start_best.div_.size ()) - { - vsize ds = max_systems.size () - this_start_best.div_.size (); - for (vsize i = ds + 1; i < max_systems.size (); i++) - { - assert (this_start_best.div_[i - ds] <= max_systems[i]); - max_systems[i] = this_start_best.div_[i - ds]; - } - } - - for (vsize i = 0; i < min_systems.size (); i++) - { - min_system_count += min_systems[i]; - max_system_count += max_systems[i]; - } + vsize min_sys_count = min_system_count (start, end); + vsize max_sys_count = max_system_count (start, end); + this_start_best.demerits_ = infinity_f; bool ok_page = true; /* heuristic: we've just added a breakpoint, we'll need at least as many systems as before */ - min_system_count = max (min_system_count, prev_best_system_count); - for (vsize sys_count = min_system_count; sys_count <= max_system_count && ok_page; sys_count++) + min_sys_count = max (min_sys_count, prev_best_system_count); + for (vsize sys_count = min_sys_count; sys_count <= max_sys_count && ok_page; sys_count++) { - vector > div; - vector blank; + vector div = line_divisions (start, end, sys_count, min_division, max_division); bool found = false; - divide_systems (sys_count, min_systems, max_systems, &div, &blank); for (vsize d = 0; d < div.size (); d++) { - vector line = get_line_details (start, end, div[d]); + vector line = line_details (start, end, div[d]); cur = put_systems_on_pages (start, end, line, div[d], p_num); @@ -169,6 +155,10 @@ found = true; this_start_best = cur; prev_best_system_count = sys_count; + + /* heuristic: if we increase the number of systems, we can bound the + division from below by our current best division */ + min_division = div[d]; } } if (!found && this_start_best.too_many_lines_) @@ -222,39 +212,15 @@ vsize start = n > 0 ? soln[n-1].break_pos_ : 0; vsize end = soln[n].break_pos_; - /* break each score into pieces */ - for (vsize i = next_system (start); i <= breaks_[end].sys_; i++) - { - vsize d = i - next_system (start); - if (all_[i].pscore_) - { - vector line_brk; - - line_brk = get_line_breaks (i, soln[n].div_[d], start, end); - all_[i].pscore_->root_system ()->break_into_pieces (line_brk); - assert (line_brk.size () == soln[n].div_[d]); - } - } + break_into_pieces (start, end, soln[n].div_); } + + vector lines = systems (); SCM ret = SCM_EOL; - SCM *tail = &ret; - for (vsize i = 0; i < all_.size (); i++) - { - if (all_[i].pscore_) - for (SCM s = scm_vector_to_list (all_[i].pscore_->root_system ()->get_paper_systems ()); - scm_is_pair (s); s = scm_cdr (s)) - { - *tail = scm_cons (scm_car (s), SCM_EOL); - tail = SCM_CDRLOC (*tail); - } - else - { - *tail = scm_cons (all_[i].prob_->self_scm (), SCM_EOL); - all_[i].prob_->unprotect (); - tail = SCM_CDRLOC (*tail); - } - } - return ret; + for (vsize i = 0; i < lines.size (); i++) + ret = scm_cons (lines[i], ret); + + return scm_reverse (ret); } SCM Index: lily/paper-book.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/paper-book.cc,v retrieving revision 1.133 diff -u -r1.133 paper-book.cc --- lily/paper-book.cc 8 Aug 2006 10:01:22 -0000 1.133 +++ lily/paper-book.cc 16 Aug 2006 21:35:05 -0000 @@ -382,6 +382,20 @@ pages_ = SCM_EOL; SCM proc = paper_->c_variable ("page-breaking"); pages_ = scm_apply_0 (proc, scm_list_1(self_scm ())); + + /* set systems_ from the pages */ + if (systems_ == SCM_BOOL_F) + { + systems_ = SCM_EOL; + for (SCM p = pages_; p != SCM_EOL; p = scm_cdr (p)) + { + Prob *page = unsmob_prob (scm_car (p)); + SCM systems = page->get_property ("lines"); + + systems_ = scm_append (scm_list_2 (systems_, systems)); + } + } + return pages_; } Index: lily/paper-column-engraver.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/paper-column-engraver.cc,v retrieving revision 1.21 diff -u -r1.21 paper-column-engraver.cc --- lily/paper-column-engraver.cc 8 Aug 2006 10:01:22 -0000 1.21 +++ lily/paper-column-engraver.cc 16 Aug 2006 21:35:05 -0000 @@ -43,6 +43,11 @@ { command_column_->set_property ("line-break-permission", ly_symbol2scm ("allow")); system_->set_bound (RIGHT, command_column_); + + /* FIXME: for now, we just make the end of any score page-turnable. + There needs to be a better policy... + */ + command_column_->set_property ("page-turn-permission", ly_symbol2scm ("allow")); } } Index: lily/include/optimal-page-breaking.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/optimal-page-breaking.hh,v retrieving revision 1.1 diff -u -r1.1 optimal-page-breaking.hh --- lily/include/optimal-page-breaking.hh 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/include/optimal-page-breaking.hh 16 Aug 2006 21:35:06 -0000 @@ -23,8 +23,7 @@ virtual ~Optimal_page_breaking (); private: - SCM make_lines (vector line_count); - Spacing_result try_page_spacing (vector line_count); + Spacing_result try_page_spacing (Line_division const&); }; #endif /* OPTIMAL_PAGE_BREAKING_HH */ Index: lily/include/page-breaking.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/page-breaking.hh,v retrieving revision 1.1 diff -u -r1.1 page-breaking.hh --- lily/include/page-breaking.hh 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/include/page-breaking.hh 16 Aug 2006 21:35:06 -0000 @@ -17,66 +17,112 @@ */ struct System_spec { - System_spec (Paper_score*, int); - System_spec (Prob*); - System_spec (); + System_spec (Paper_score *ps) + { + pscore_ = ps; + prob_ = NULL; + } + + System_spec (Prob *pb) + { + prob_ = pb; + pscore_ = NULL; + } + + System_spec () + { + pscore_ = NULL; + prob_ = NULL; + } Paper_score *pscore_; Prob *prob_; - - vsize score_break_count_; /* for scores, this is the number of start-points our line- - breaker has */ }; struct Break_position { - vsize sys_; /* the index in our all_ list */ + vsize sys_; /* our index in the all_ list */ vsize score_break_; /* if sys_ is a score, then we start at the score_brk_'th possible page-break in the score */ + bool score_ender_; - Break_position (vsize s=VPOS, vsize brk=VPOS) + Break_position (vsize s=VPOS, vsize brk=VPOS, bool end=false) { sys_ = s; score_break_ = brk; + score_ender_ = end; + } + + bool operator< (const Break_position &other) + { + return (sys_ == VPOS && other.sys_ != VPOS) + || (sys_ < other.sys_) + || (sys_ == other.sys_ && score_break_ < other.score_break_); + } + + bool operator<= (const Break_position &other) + { + return (sys_ == VPOS) + || (sys_ < other.sys_ && other.sys_ != VPOS) + || (sys_ == other.sys_ && score_break_ <= other.score_break_); } }; class Page_breaking { public: + typedef bool (*Break_p) (Grob *); + typedef vector Line_division; virtual SCM solve () = 0; - Page_breaking (Paper_book *pb, bool allow_intra_score_breaks); + Page_breaking (Paper_book *pb, Break_p); virtual ~Page_breaking (); protected: - std::vector breaks_; - std::vector all_; - std::vector line_breaking_; - Paper_book *book_; Real page_height (int page_number, bool last); vsize next_system (vsize starting_break_index) const; - - void create_system_list (bool allow_intra_score_breaks); - std::vector find_page_break_indices (Paper_score *pscore); + vsize next_system (Break_position const &break_pos) const; SCM make_pages (vector lines_per_page, SCM lines); - void calc_system_count_bounds (vsize start, vsize end, - vector *min, - vector *max); - - void divide_systems (vsize system_count, vector const &min, - vector const &max, - vector > *result, - vector *cur); - - void line_breaker_args (vsize i, vsize *break_st, vsize *break_end); - vsize get_min_systems (vsize sys, vsize break_start, vsize break_end); - vsize get_max_systems (vsize sys, vsize break_start, vsize break_end); - vector get_line_breaks (vsize sys, vsize sys_count, vsize st, vsize end); - vector get_line_details (vsize start_break, vsize end_break, vector const &div); + vsize min_system_count (vsize start, vsize end); + vsize max_system_count (vsize start, vsize end); + vector line_details (vsize start, vsize end, Line_division const &div); + + void break_into_pieces (vsize start, vsize end, Line_division const &div); + vector systems (); + + + vector line_divisions (vsize start, + vsize end, + vsize system_count, + Line_division lower_bound = Line_division (), + Line_division upper_bound = Line_division ()); + + vector breaks_; + +private: + vector chunks_; + vector all_; + vector line_breaking_; + + vector chunk_list (vsize start, vsize end); + Line_division system_count_bounds (vector const &chunks, bool min); + void line_breaker_args (vsize i, + Break_position const &start, + Break_position const &end, + vsize *line_breaker_start, + vsize *line_breaker_end); + + void line_divisions_rec (vsize system_count, + Line_division const &min, + Line_division const &max, + vector *result, + Line_division *cur); + + void create_system_list (); + void find_chunks_and_breaks (Break_p); }; #endif /* PAGE_BREAKING_HH */ Index: lily/include/page-spacing.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/page-spacing.hh,v retrieving revision 1.1 diff -u -r1.1 page-spacing.hh --- lily/include/page-spacing.hh 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/include/page-spacing.hh 16 Aug 2006 21:35:06 -0000 @@ -21,10 +21,47 @@ Spacing_result () { penalty_ = 0; - demerits_ = 0; + demerits_ = infinity_f; } }; +/* for page_count > 2, we use a dynamic algorithm similar to + constrained-breaking -- we have a class that stores the intermediate + calculations so they can be reused for querying different page counts. +*/ + +class Page_spacer +{ +public: + Page_spacer (vector const &lines, Real page_height); + Spacing_result solve (vsize page_count); + +private: + struct Page_spacing_node + { + Page_spacing_node () + { + demerits_ = infinity_f; + force_ = infinity_f; + penalty_ = infinity_f; + prev_ = VPOS; + } + + Real demerits_; + Real force_; + Real penalty_; + vsize prev_; + }; + + Real page_height_; + vector lines_; + Matrix state_; + vsize max_page_count_; + + void resize (vsize page_count); + bool calc_subproblem (vsize page, vsize lines); +}; + Spacing_result space_systems_on_min_pages (vector const&, Real page_height, Index: lily/include/page-turn-page-breaking.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/page-turn-page-breaking.hh,v retrieving revision 1.1 diff -u -r1.1 page-turn-page-breaking.hh --- lily/include/page-turn-page-breaking.hh 8 Aug 2006 10:01:22 -0000 1.1 +++ lily/include/page-turn-page-breaking.hh 16 Aug 2006 21:35:06 -0000 @@ -45,7 +45,7 @@ Real demerits_; vsize break_pos_; /* index into breaks_ */ - vector div_; /* our division of systems between scores on this page */ + Line_division div_; vector system_count_; /* systems per page */ Break_node () @@ -59,12 +59,12 @@ } }; - std::vector state_; + vector state_; Break_node put_systems_on_pages (vsize start, vsize end, vector const &lines, - vector const &system_div, + Line_division const &div, int page_number); SCM make_lines (vector *breaks);