From a732d02103df02d413b35dae436c38db538e9fd1 Mon Sep 17 00:00:00 2001 From: Joe Neeman Date: Mon, 24 Jul 2006 11:50:27 +0000 Subject: [PATCH] * 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 --- ChangeLog | 28 ++++++ flower/include/flower-proto.hh | 2 +- lily/constrained-breaking.cc | 142 +++++++++++++++++---------- lily/hara-kiri-group-spanner.cc | 6 +- lily/include/constrained-breaking.hh | 16 +-- lily/simple-spacer.cc | 28 +++--- scm/define-grobs.scm | 1 + scm/layout-page-layout.scm | 12 ++- scm/lily-library.scm | 3 +- scm/page.scm | 9 +- 10 files changed, 159 insertions(+), 88 deletions(-) diff --git a/ChangeLog b/ChangeLog index dff065315a..f0d2e72c0e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -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?): also 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 diff --git a/flower/include/flower-proto.hh b/flower/include/flower-proto.hh index 0d82d8bbc7..384d8b89c8 100644 --- a/flower/include/flower-proto.hh +++ b/flower/include/flower-proto.hh @@ -19,7 +19,7 @@ using namespace std; template struct Interval_t; template struct PQueue; - +template class Matrix; typedef Interval_t Interval; diff --git a/lily/constrained-breaking.cc b/lily/constrained-breaking.cc index c9753b1a0a..e3b07fab3b 100644 --- a/lily/constrained-breaking.cc +++ b/lily/constrained-breaking.cc @@ -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 @@ Constrained_breaking::calc_subproblem (vsize start, vsize sys, vsize brk) 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 @@ Constrained_breaking::calc_subproblem (vsize start, vsize sys, vsize brk) 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 @@ vector 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 @@ Constrained_breaking::resize (vsize systems) 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 @@ Constrained_breaking::resize (vsize systems) 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 @@ Constrained_breaking::resize (vsize systems) 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 @@ Constrained_breaking::resize (vsize systems) 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 @@ Constrained_breaking::get_solution (vsize start, vsize end, vsize sys_count) { 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 @@ Constrained_breaking::get_solution (vsize start, vsize end, vsize sys_count) /* 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 @@ Constrained_breaking::get_solution (vsize start, vsize end, vsize sys_count) 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 @@ Constrained_breaking::get_min_systems (vsize start, vsize end) { 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 @@ Constrained_breaking::get_max_systems (vsize start, vsize end) 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 @@ Constrained_breaking::prepare_solution (vsize start, vsize end, vsize sys_count, 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 () diff --git a/lily/hara-kiri-group-spanner.cc b/lily/hara-kiri-group-spanner.cc index 4c9cc03963..bc59b12ae7 100644 --- a/lily/hara-kiri-group-spanner.cc +++ b/lily/hara-kiri-group-spanner.cc @@ -78,9 +78,9 @@ Hara_kiri_group_spanner::request_suicide (Grob *me, int start, int end) 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); diff --git a/lily/include/constrained-breaking.hh b/lily/include/constrained-breaking.hh index ca662e854e..59f0a26a9d 100644 --- a/lily/include/constrained-breaking.hh +++ b/lily/include/constrained-breaking.hh @@ -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 @@ struct Line_details { Line_details () { force_ = infinity_f; - extent_ = 0; padding_ = 0; bottom_padding_ = 0; space_ = 0; @@ -81,7 +81,8 @@ public: 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 @@ private: /* 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 @@ private: 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); diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc index 3532c03606..3b3eaed3ba 100644 --- a/lily/simple-spacer.cc +++ b/lily/simple-spacer.cc @@ -147,18 +147,13 @@ Simple_spacer::solve (Real line_len, bool ragged) 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 @@ Simple_spacer::spring_positions () const 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 @@ get_line_forces (vector const &icols, vector breaks, 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 @@ get_line_forces (vector const &icols, vector breaks, } } 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 ()) { diff --git a/scm/define-grobs.scm b/scm/define-grobs.scm index a8e3c092c4..b0d023b2be 100644 --- a/scm/define-grobs.scm +++ b/scm/define-grobs.scm @@ -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) diff --git a/scm/layout-page-layout.scm b/scm/layout-page-layout.scm index f00fbf1ca0..8756062384 100644 --- a/scm/layout-page-layout.scm +++ b/scm/layout-page-layout.scm @@ -127,18 +127,24 @@ is what have collected so far, and has ascending page numbers." (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 diff --git a/scm/lily-library.scm b/scm/lily-library.scm index d178c6926c..bb7e7a32a8 100644 --- a/scm/lily-library.scm +++ b/scm/lily-library.scm @@ -383,7 +383,8 @@ found." (not (or (nan? (car i)) (inf? (car i)) (nan? (cdr i)) - (inf? (cdr i))))) + (inf? (cdr i)) + (> (car i) (cdr i))))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; diff --git a/scm/page.scm b/scm/page.scm index a572e44102..258589ae53 100644 --- a/scm/page.scm +++ b/scm/page.scm @@ -314,8 +314,10 @@ create offsets. (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 @@ create offsets. (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))) -- 2.39.2