Index: ChangeLog =================================================================== RCS file: /sources/lilypond/lilypond/ChangeLog,v retrieving revision 1.5199 diff -u -r1.5199 ChangeLog --- ChangeLog 23 Jul 2006 10:25:20 -0000 1.5199 +++ ChangeLog 24 Jul 2006 09:50:18 -0000 @@ -1,3 +1,31 @@ +2006-07-24 Joe Neeman + + * scm/define-grobs.scm (all-grob-descriptions): make NonMusicalPaperColumn + page-breakable by default + + * scm/layout-page-layout.scm (space-systems): fix bug where the force isn't + correctly calculated for a single-system page + + * scm/lily-library.scm (interval-sane?): check that the first number is no + bigger than the second number + + * lily/simple-spacer.cc (solve): allow compression even when ragged (but we + acknowledge that we aren't satisfying constraints) + + * lily/hara-kiri-group-spanner.cc (request_suicide): give equal treatment to + non-Items + + * lily/grob.cc (pure_height): add minimum-Y-extent + + * lily/gourlay-breaking.cc (solve): don't ignore a compression force, even if we're + ragged + + * lily/constrained-breaking.cc: convert code to use new Matrix class + (get_best_solution): new function + + * scm/page.scm (make-page-stencil): don't crash if we annotate-layout when there + is a page with no systems + 2006-07-23 Han-Wen Nienhuys * scm/define-grobs.scm (all-grob-descriptions): remove stray Index: flower/include/flower-proto.hh =================================================================== RCS file: /sources/lilypond/lilypond/flower/include/flower-proto.hh,v retrieving revision 1.21 diff -u -r1.21 flower-proto.hh --- flower/include/flower-proto.hh 16 Feb 2006 11:54:21 -0000 1.21 +++ flower/include/flower-proto.hh 24 Jul 2006 09:21:42 -0000 @@ -19,7 +19,7 @@ template struct Interval_t; template struct PQueue; - +template class Matrix; typedef Interval_t Interval; Index: lily/constrained-breaking.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/constrained-breaking.cc,v retrieving revision 1.7 diff -u -r1.7 constrained-breaking.cc --- lily/constrained-breaking.cc 9 Jun 2006 02:20:22 -0000 1.7 +++ lily/constrained-breaking.cc 24 Jul 2006 09:21:43 -0000 @@ -4,7 +4,7 @@ source file of the GNU LilyPond music typesetter - (c) 2006 Han-Wen Nienhuys + (c) 2006 Joe Neeman */ #include "constrained-breaking.hh" @@ -38,7 +38,7 @@ start_.size () different solution arrays. state_[i] is the array for the solution starting at column number start_[i]. - The indicies "start" and "end" refer to the index in the start_ array of the + The indices "start" and "end" refer to the index in the start_ array of the desired starting and ending columns. each solution array looks like @@ -74,22 +74,21 @@ bool found_something = false; vsize start_col = starting_breakpoints_[start]; - vector &st = state_[start]; - vsize rank = breaks_.size () - start_col; + Matrix &st = state_[start]; vsize max_index = brk - start_col; for (vsize j=sys; j < max_index; j++) { if (0 == sys && j > 0) break; /* the first line cannot have its first break after the beginning */ - Line_details const &cur = lines_[(j + start_col)*lines_rank_ + brk]; + Line_details const &cur = lines_.at (brk, j + start_col); Real prev_f = 0; Real prev_dem = 0; if (sys > 0) { - prev_f = st[(sys-1) * rank + j].details_.force_; - prev_dem = st[(sys-1) * rank + j].demerits_; + prev_f = st.at (j, sys-1).details_.force_; + prev_dem = st.at (j, sys-1).demerits_; } if (isinf (prev_dem)) break; @@ -98,13 +97,13 @@ if (isinf (dem)) continue; - int k = sys*rank + max_index; - if (isinf (st[k].demerits_) || dem < st[k].demerits_) + Constrained_break_node &n = st.at (max_index, sys); + if (isinf (n.demerits_) || dem < n.demerits_) { found_something = true; - st[k].demerits_ = dem; - st[k].details_ = cur; - st[k].prev_ = j; + n.demerits_ = dem; + n.details_ = cur; + n.prev_ = j; } } return found_something; @@ -114,10 +113,7 @@ Constrained_breaking::solve () { if (!systems_) - { - programming_error (_f ("no system number set in constrained-breaking")); - systems_ = breaks_.size () / 4; - } + return get_best_solution (0, VPOS); resize (systems_); return get_solution(0, VPOS, systems_); @@ -157,9 +153,8 @@ Interval other_lines = line_dimensions_int (pscore_->layout (), 1); /* do all the rod/spring problems */ breaks_ = pscore_->find_break_indices (); - lines_rank_ = breaks_.size (); all_ = pscore_->root_system ()->columns (); - lines_.resize (breaks_.size () * breaks_.size ()); + lines_.resize (breaks_.size (), breaks_.size (), Line_details ()); vector forces = get_line_forces (all_, breaks_, other_lines.length (), @@ -175,20 +170,25 @@ Interval extent = sys->pure_height (sys, start, end); bool last = j == breaks_.size () - 1; bool ragged = ragged_right || (last && ragged_last); - int k = i*lines_rank_ + j; - SCM pen = all_[breaks_[j]]->get_property ("line-break-penalty"); - if (scm_is_number (pen)) - lines_[k].break_penalty_ = scm_to_double (pen); + Line_details &line = lines_.at (j, i); + + Grob *c = all_[breaks_[j]]; + line.break_penalty_ = robust_scm2double (c->get_property ("line-break-penalty"), 0); + line.page_penalty_ = robust_scm2double (c->get_property ("page-break-penalty"), 0); + line.turn_penalty_ = robust_scm2double (c->get_property ("page-turn-penalty"), 0); + line.break_permission_ = c->get_property ("line-break-permission"); + line.page_permission_ = c->get_property ("page-break-permission"); + line.turn_permission_ = c->get_property ("page-turn-permission"); max_ext = max (max_ext, extent.length ()); - lines_[k].force_ = forces[k]; - lines_[k].extent_ = extent.length (); - lines_[k].padding_ = padding; - lines_[k].space_ = space; - lines_[k].inverse_hooke_ = 1; - if (ragged && lines_[k].force_ < 0) - lines_[k].force_ = infinity_f; - if (isinf (lines_[k].force_)) + line.force_ = forces[i*breaks_.size () + j]; + line.extent_ = extent; + line.padding_ = padding; + line.space_ = space; + line.inverse_hooke_ = 1; + if (ragged && line.force_ < 0) + line.force_ = infinity_f; + if (isinf (line.force_)) break; } } @@ -208,7 +208,7 @@ if (pscore_ && systems_ > valid_systems_) { for (vsize i = 0; i < state_.size (); i++) - state_[i].resize((breaks_.size () - starting_breakpoints_[i]) * systems_); + state_[i].resize (breaks_.size () - starting_breakpoints_[i], systems_, Constrained_break_node ()); /* fill out the matrices */ for (vsize i = 0; i < state_.size (); i++) @@ -223,12 +223,10 @@ vector Constrained_breaking::get_solution (vsize start, vsize end, vsize sys_count) { - vsize rank; - vsize end_brk; vsize start_brk = starting_breakpoints_[start]; - prepare_solution (start, end, sys_count, &rank, &end_brk); + vsize end_brk = prepare_solution (start, end, sys_count); - vector const &st = state_[start]; + Matrix const &st = state_[start]; vector ret; /* find the first solution that satisfies constraints */ @@ -236,7 +234,7 @@ { for (vsize brk = end_brk; brk != VPOS; brk--) { - if (!isinf (st[sys*rank + brk].details_.force_)) + if (!isinf (st.at (brk, sys).details_.force_)) { if (brk != end_brk) { @@ -246,7 +244,7 @@ /* build up the good solution */ for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--) { - vsize prev_brk = st[cur_sys*rank + brk].prev_; + vsize prev_brk = st.at (brk, cur_sys).prev_; assert (brk != VPOS); ret.push_back (space_line (prev_brk + start_brk, brk + start_brk)); brk = prev_brk; @@ -262,32 +260,67 @@ return ret; } +vector +Constrained_breaking::get_best_solution (vsize start, vsize end) +{ + vsize min_systems = get_min_systems (start, end); + vsize max_systems = get_max_systems (start, end); + Real best_demerits = infinity_f; + vector best_so_far; + + for (vsize i = min_systems; i <= max_systems; i++) + { + vsize brk = prepare_solution (start, end, i); + Real dem = state_[start].at (brk, i-1).demerits_; + + if (dem < best_demerits) + { + best_demerits = dem; + best_so_far = get_solution (start, end, i); + } + else + { + vector cur = get_solution (start, end, i); + bool too_many_lines = true; + + for (vsize j = 0; j < cur.size (); j++) + if (cur[j].force_ < 0) + { + too_many_lines = false; + break; + } + if (too_many_lines) + return best_so_far; + } + } + if (best_so_far.size ()) + return best_so_far; + return get_solution (start, end, max_systems); +} + std::vector Constrained_breaking::get_details (vsize start, vsize end, vsize sys_count) { - vsize rank; - vsize brk; - prepare_solution (start, end, sys_count, &rank, &brk); - vector const &st = state_[start]; + vsize brk = prepare_solution (start, end, sys_count); + Matrix const &st = state_[start]; vector ret; for (int sys = sys_count-1; sys >= 0 && brk != VPOS; sys--) { - ret.push_back (st[sys*rank + brk].details_); - brk = st[sys*rank + brk].prev_; + ret.push_back (st.at (brk, sys).details_); + brk = st.at (brk, sys).prev_; } + reverse (ret); return ret; } int Constrained_breaking::get_min_systems (vsize start, vsize end) { - vsize rank; - vsize brk; vsize sys_count; - - prepare_solution (start, end, 1, &rank, &brk); - vector const &st = state_[start]; + vsize brk = prepare_solution (start, end, 1); + vsize rank = breaks_.size () - starting_breakpoints_[start]; + Matrix const &st = state_[start]; /* sys_count < rank : rank is the # of breakpoints, we can't have more systems */ for (sys_count = 0; sys_count < rank; sys_count++) @@ -296,7 +329,7 @@ { resize (sys_count + 3); } - if (!isinf (st[sys_count*rank + brk].details_.force_)) + if (!isinf (st.at (brk, sys_count).details_.force_)) return sys_count + 1; } /* no possible breaks satisfy constraints */ @@ -310,8 +343,8 @@ return brk - starting_breakpoints_[start]; } -void -Constrained_breaking::prepare_solution (vsize start, vsize end, vsize sys_count, vsize *rank, vsize *brk) +vsize +Constrained_breaking::prepare_solution (vsize start, vsize end, vsize sys_count) { assert (start < start_.size () && (end == VPOS || end <= start_.size ())); assert (start < end); @@ -320,9 +353,10 @@ if (end == start_.size ()) end = VPOS; - *rank = breaks_.size () - starting_breakpoints_[start]; - *brk = end == VPOS ? breaks_.size () - 1 : starting_breakpoints_[end]; - *brk -= starting_breakpoints_[start]; + vsize brk; + brk = end == VPOS ? breaks_.size () - 1 : starting_breakpoints_[end]; + brk -= starting_breakpoints_[start]; + return brk; } Constrained_breaking::Constrained_breaking () Index: lily/gourlay-breaking.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/gourlay-breaking.cc,v retrieving revision 1.98 diff -u -r1.98 gourlay-breaking.cc --- lily/gourlay-breaking.cc 18 Jun 2006 12:57:37 -0000 1.98 +++ lily/gourlay-breaking.cc 24 Jul 2006 09:21:43 -0000 @@ -116,7 +116,7 @@ line_dims[LEFT], ragged); if (ragged && last_line) - cp.force_ = 0.0; + cp.force_ = min (cp.force_, 0.0); if (fabs (cp.force_) > worst_force) worst_force = fabs (cp.force_); Index: lily/grob.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/grob.cc,v retrieving revision 1.173 diff -u -r1.173 grob.cc --- lily/grob.cc 19 Jul 2006 21:33:03 -0000 1.173 +++ lily/grob.cc 24 Jul 2006 09:21:43 -0000 @@ -419,6 +419,10 @@ SCM_EOL)); Real offset = pure_relative_y_coordinate (refp, start, end); + SCM min_ext = get_property ("minimum-Y-extent"); + if (is_number_pair (min_ext)) + iv.unite (ly_scm2interval (min_ext)); + iv.translate (offset); return iv; } @@ -434,7 +438,7 @@ Interval_t Grob::spanned_rank_iv () { - return Interval_t (INT_MIN, INT_MAX); + return Interval_t (-1, 0); } /**************************************************************** Index: lily/hara-kiri-group-spanner.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/hara-kiri-group-spanner.cc,v retrieving revision 1.55 diff -u -r1.55 hara-kiri-group-spanner.cc --- lily/hara-kiri-group-spanner.cc 9 Jun 2006 02:20:22 -0000 1.55 +++ lily/hara-kiri-group-spanner.cc 24 Jul 2006 09:21:43 -0000 @@ -78,9 +78,9 @@ for (vsize i = 0; i < worth.size (); i++) { - Item *it = dynamic_cast (worth[i]); - if (it) - ranks.push_back (Paper_column::get_rank (it->get_column ())); + Interval_t iv = worth[i]->spanned_rank_iv (); + for (int j = iv[LEFT]; j <= iv[RIGHT]; j++) + ranks.push_back (j); } vector_sort (ranks, default_compare); uniq (ranks); Index: lily/simple-spacer.cc =================================================================== RCS file: /sources/lilypond/lilypond/lily/simple-spacer.cc,v retrieving revision 1.101 diff -u -r1.101 simple-spacer.cc --- lily/simple-spacer.cc 18 Jun 2006 12:57:37 -0000 1.101 +++ lily/simple-spacer.cc 24 Jul 2006 09:21:46 -0000 @@ -147,18 +147,13 @@ ragged_ = ragged; line_len_ = line_len; - if (ragged) - { - force_ = 0; - fits_ = configuration_length (force_) <= line_len_; - /* we need to calculate a force here to prevent a bunch of short lines */ - if (fits_) - force_ = expand_line (); - } - else if (conf < line_len_) + if (conf < line_len_) force_ = expand_line (); else if (conf > line_len_) force_ = compress_line (); + + if (ragged && force_ < 0) + fits_ = false; } Real @@ -248,7 +243,7 @@ ret.push_back (0.); for (vsize i = 0; i < springs_.size (); i++) - ret.push_back (ret.back () + springs_[i].length (ragged_ ? 0.0 : force_)); + ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_)); return ret; } @@ -456,7 +451,7 @@ if (!is_loose (icols[i])) cols.push_back (get_column_description (icols, i, false)); } - breaks.back () = cols.size () - 1; + breaks.back () = cols.size (); for (vsize b = 0; b < breaks.size () - 1; b++) { @@ -488,9 +483,16 @@ } } spacer.solve ((b == 0) ? line_len - indent : line_len, ragged); - force[b * breaks.size () + c] = spacer.force (); - if (cols[end].break_permission_ == force_break) + /* add a (convex) penalty for compression. We do this _only_ in get_line_forces, + not get_line_configuration. This is temporary, for backwards compatibility; + the old line/page-breaking stuff ignores page breaks when it calculates line + breaks, so compression penalties can result in scores (eg. wtk-fugue) blowing + up to too many pages. */ + Real f = spacer.force (); + force[b * breaks.size () + c] = f - (f < 0 ? f*f*6 : 0); + + if (end < cols.size () && cols[end].break_permission_ == force_break) break; if (!spacer.fits ()) { Index: lily/include/constrained-breaking.hh =================================================================== RCS file: /sources/lilypond/lilypond/lily/include/constrained-breaking.hh,v retrieving revision 1.8 diff -u -r1.8 constrained-breaking.hh --- lily/include/constrained-breaking.hh 9 Jun 2006 02:20:22 -0000 1.8 +++ lily/include/constrained-breaking.hh 24 Jul 2006 09:21:46 -0000 @@ -4,7 +4,7 @@ source file of the GNU LilyPond music typesetter - (c) 2006 Han-Wen Nienhuys + (c) 2006 Joe Neeman */ #ifndef CONSTRAINED_BREAKING_HH @@ -12,10 +12,11 @@ #include "break-algorithm.hh" #include "lily-guile.hh" +#include "matrix.hh" struct Line_details { Real force_; - Real extent_; /* Y-extent of the system */ + Interval extent_; /* Y-extent of the system */ Real padding_; /* compulsory space after this system (if we're not last on a page) */ Real bottom_padding_; Real space_; /* spring length */ @@ -31,7 +32,6 @@ Line_details () { force_ = infinity_f; - extent_ = 0; padding_ = 0; bottom_padding_ = 0; space_ = 0; @@ -81,7 +81,8 @@ Constrained_breaking (); Constrained_breaking (vector const &start_col_posns); - vector get_solution(vsize start, vsize end, vsize sys_count); + vector get_solution (vsize start, vsize end, vsize sys_count); + vector get_best_solution (vsize start, vsize end); vector get_details (vsize start, vsize end, vsize sys_count); int get_max_systems (vsize start, vsize end); int get_min_systems (vsize start, vsize end); @@ -94,12 +95,11 @@ /* the (i,j)th entry is the configuration for breaking between columns i and j */ - vector lines_; - vsize lines_rank_; + Matrix lines_; /* the [i](j,k)th entry is the score for fitting the first k bars onto the first j systems, starting at the i'th allowed starting column */ - vector > state_; + vector > state_; vector start_; /* the columns at which we might be asked to start breaking */ vector starting_breakpoints_; /* the corresponding index in breaks_ */ @@ -108,7 +108,7 @@ vector breaks_; Column_x_positions space_line (vsize start_col, vsize end_col); - void prepare_solution (vsize start, vsize end, vsize sys_count, vsize *rank, vsize *brk); + vsize prepare_solution (vsize start, vsize end, vsize sys_count); Real combine_demerits (Real force, Real prev_force); Index: scm/define-grobs.scm =================================================================== RCS file: /sources/lilypond/lilypond/scm/define-grobs.scm,v retrieving revision 1.343 diff -u -r1.343 define-grobs.scm --- scm/define-grobs.scm 23 Jul 2006 10:25:20 -0000 1.343 +++ scm/define-grobs.scm 24 Jul 2006 09:21:48 -0000 @@ -1140,6 +1140,7 @@ (non-musical . #t) (line-break-permission . allow) + (page-break-permission . allow) ;; debugging stuff: print column number. ;; (font-size . -6) (font-name . "sans") (Y-extent . #f) Index: scm/layout-page-layout.scm =================================================================== RCS file: /sources/lilypond/lilypond/scm/layout-page-layout.scm,v retrieving revision 1.18 diff -u -r1.18 layout-page-layout.scm --- scm/layout-page-layout.scm 15 Jul 2006 10:32:44 -0000 1.18 +++ scm/layout-page-layout.scm 24 Jul 2006 09:56:55 -0000 @@ -127,18 +127,24 @@ (define (space-systems page-height lines ragged? paper) "Compute lines positions on page: return force and line positions as a pair. force is #f if lines do not fit on page." - (let* ((springs (map (lambda (prev-line line) + (let* ((empty-stencil (ly:make-stencil '() '(0 . 0) '(0 . 0))) + (empty-prob (ly:make-prob 'paper-system (list `(stencil . ,empty-stencil)))) + (cdr-lines (append (cdr lines) + (if (<= (length lines) 1) + (list empty-prob) + '()))) + (springs (map (lambda (prev-line line) (list (line-ideal-distance prev-line line paper) (/ 1.0 (line-next-space prev-line line paper)))) lines - (cdr lines))) + cdr-lines)) (rods (map (let ((i -1)) (lambda (prev-line line) (set! i (1+ i)) (list i (1+ i) (line-minimum-distance prev-line line paper)))) lines - (cdr lines))) + cdr-lines)) (last-line (car (last-pair lines))) (topskip (first-line-position (first lines) paper)) (space-to-fill (- page-height Index: scm/lily-library.scm =================================================================== RCS file: /sources/lilypond/lilypond/scm/lily-library.scm,v retrieving revision 1.65 diff -u -r1.65 lily-library.scm --- scm/lily-library.scm 28 May 2006 22:40:50 -0000 1.65 +++ scm/lily-library.scm 24 Jul 2006 09:21:48 -0000 @@ -383,7 +383,8 @@ (not (or (nan? (car i)) (inf? (car i)) (nan? (cdr i)) - (inf? (cdr i))))) + (inf? (cdr i)) + (> (car i) (cdr i))))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Index: scm/page.scm =================================================================== RCS file: /sources/lilypond/lilypond/scm/page.scm,v retrieving revision 1.12 diff -u -r1.12 page.scm --- scm/page.scm 9 Jun 2006 13:11:49 -0000 1.12 +++ scm/page.scm 24 Jul 2006 09:21:48 -0000 @@ -314,8 +314,10 @@ (foot (prop 'foot-stencil)) ) - (if (or (annotate? layout) - (ly:output-def-lookup layout 'annotate-systems #f)) + (if (and + (or (annotate? layout) + (ly:output-def-lookup layout 'annotate-systems #f)) + (pair? lines)) (begin (for-each (lambda (sys next-sys) @@ -386,9 +388,6 @@ (let* ((p-book (page-property page 'paper-book)) (layout (ly:paper-book-paper p-book)) - (scopes (ly:paper-book-scopes p-book)) - (number (page-page-number page)) - (last? (page-property page 'is-last)) (h (- (ly:output-def-lookup layout 'paper-height) (ly:output-def-lookup layout 'top-margin) (ly:output-def-lookup layout 'bottom-margin)))