1 ;;;; layout-page-layout.scm -- page breaking and page layout
3 ;;;; source file of the GNU LilyPond music typesetter
5 ;;;; (c) 2004--2006 Jan Nieuwenhuizen <janneke@gnu.org>
6 ;;;; Han-Wen Nienhuys <hanwen@cs.uu.nl>
8 (define-module (scm layout-page-layout)
9 #:use-module (srfi srfi-1)
10 #:use-module (oop goops describe)
11 #:use-module (oop goops)
12 #:use-module (scm paper-system)
13 #:use-module (scm page)
14 #:use-module (scm layout-page-dump)
16 #:export (post-process-pages optimal-page-breaks))
18 (define (post-process-pages layout pages)
19 (if (ly:output-def-lookup layout 'write-page-layout #f)
20 (write-page-breaks pages)))
23 ;;; Utilities for computing line distances and positions
25 (define (line-next-space line next-line layout)
26 "Return space to use between `line' and `next-line'.
27 `next-line' can be #f, meaning that `line' is the last line."
28 (let* ((title? (paper-system-title? line))
29 (next-title? (and next-line (paper-system-title? next-line))))
30 (cond ((and title? next-title?)
31 (ly:output-def-lookup layout 'between-title-space))
33 (ly:output-def-lookup layout 'after-title-space))
35 (ly:output-def-lookup layout 'before-title-space))
39 (ly:output-def-lookup layout 'between-system-space))))))
41 (define (line-next-padding line next-line layout)
42 "Return padding to use between `line' and `next-line'.
43 `next-line' can be #f, meaning that `line' is the last line."
46 (ly:output-def-lookup layout 'between-system-padding)))
49 (define (line-minimum-distance line next-line layout)
50 "Minimum distance between `line' reference position and `next-line'
51 reference position. If next-line is #f, return #f."
53 (max 0 (- (+ (interval-end (paper-system-extent next-line Y))
54 (line-next-padding line next-line layout))
55 (interval-start (paper-system-extent line Y))))))
57 (define (line-ideal-distance line next-line layout)
58 "Ideal distance between `line' reference position and `next-line'
59 reference position. If next-line is #f, return #f."
61 (+ (max 0 (- (+ (interval-end (paper-system-staff-extents next-line))
62 (line-next-padding line next-line layout))
63 (interval-start (paper-system-staff-extents line))))
64 (line-next-space line next-line layout))))
66 (define (first-line-position line layout)
67 "Position of the first line on page"
68 (max (+ (ly:output-def-lookup layout 'page-top-space)
69 (interval-end (paper-system-staff-extents line)))
70 (interval-end (paper-system-extent line Y))))
72 (define (line-ideal-relative-position line prev-line layout)
73 "Return ideal position of `line', relative to `prev-line' position.
74 `prev-line' can be #f, meaning that `line' is the first line."
77 (first-line-position line layout)
78 ;; not the first line on page
79 (max (line-minimum-distance prev-line line layout)
80 (line-ideal-distance prev-line line layout))))
82 (define (line-minimum-relative-position line prev-line layout)
83 "Return position of `line', relative to `prev-line' position.
84 `prev-line' can be #f, meaning that `line' is the first line."
87 (first-line-position line layout)
88 ;; not the first line on page
89 (line-minimum-distance prev-line line layout)))
92 ;;; Page breaking functions
95 ;; Optimal distribution of
96 ;; lines over pages; line breaks are a given.
101 ;; - separate function for word-wrap style breaking?
102 ;; - ragged-bottom? ragged-last-bottom?
104 (define (get-path node done)
105 "Follow NODE.PREV, and return as an ascending list of pages. DONE
106 is what have collected so far, and has ascending page numbers."
108 (get-path (page-prev node) (cons node done))
111 (define (combine-penalties force user best-paths
112 inter-system-space force-equalization-factor)
113 (let* ((prev-force (if (null? best-paths)
115 (page-force (car best-paths))))
116 (prev-penalty (if (null? best-paths)
118 (page-penalty (car best-paths))))
119 (relative-force (/ force inter-system-space))
120 (abs-relative-force (abs relative-force)))
121 (+ (* abs-relative-force (+ abs-relative-force 1))
123 (* force-equalization-factor (/ (abs (- prev-force force))
127 (define (space-systems page-height lines ragged? paper)
128 "Compute lines positions on page: return force and line positions as a pair.
129 force is #f if lines do not fit on page."
130 (let* ((empty-stencil (ly:make-stencil '() '(0 . 0) '(0 . 0)))
131 (empty-prob (ly:make-prob 'paper-system (list `(stencil . ,empty-stencil))))
132 (cdr-lines (append (cdr lines)
133 (if (<= (length lines) 1)
136 (springs (map (lambda (prev-line line)
137 (list (line-ideal-distance prev-line line paper)
138 (/ 1.0 (line-next-space prev-line line paper))))
141 (rods (map (let ((i -1))
142 (lambda (prev-line line)
145 (line-minimum-distance prev-line line paper))))
148 (last-line (car (last-pair lines)))
149 (topskip (first-line-position (first lines) paper))
150 (space-to-fill (- page-height
152 (ly:prob-property last-line
154 (- (interval-start (paper-system-extent
157 (ly:solve-spring-rod-problem springs rods space-to-fill ragged?)))
158 (cons (car space-result)
161 (cdr space-result)))))
163 (define (walk-paths done-lines best-paths current-lines last? current-best
164 paper-book page-alist)
165 "Return the best optimal-page-break-node that contains
166 CURRENT-LINES. DONE-LINES.reversed ++ CURRENT-LINES is a consecutive
167 ascending range of lines, and BEST-PATHS contains the optimal breaks
168 corresponding to DONE-LINES.
170 CURRENT-BEST is the best result sofar, or #f."
171 (let* ((paper (ly:paper-book-paper paper-book))
172 (this-page (make-page
174 'paper-book paper-book
176 'page-number (if (null? best-paths)
177 (ly:output-def-lookup paper 'first-page-number)
178 (1+ (page-page-number (first best-paths))))))
179 (ragged-all? (eq? #t (ly:output-def-lookup paper 'ragged-bottom)))
180 (ragged-last? (eq? #t (ly:output-def-lookup paper 'ragged-last-bottom)))
181 (ragged? (or ragged-all? (and ragged-last? last?)))
182 (height (page-printable-height this-page))
183 (vertical-spacing (space-systems height current-lines ragged? paper))
184 (satisfied-constraints (car vertical-spacing))
185 (force (if satisfied-constraints
186 (if (and last? ragged-last?)
188 satisfied-constraints)
190 (positions (cdr vertical-spacing))
191 (get-break-penalty (lambda (sys)
192 (ly:prob-property sys 'penalty 0.0)))
193 (user-nobreak-penalties (- (apply + (filter negative?
194 (map get-break-penalty
195 (cdr current-lines))))))
196 (user-penalty (+ (max (get-break-penalty (car current-lines)) 0.0)
197 user-nobreak-penalties))
198 (total-penalty (combine-penalties
199 force user-penalty best-paths
200 (ly:output-def-lookup paper 'between-system-space)
201 (ly:output-def-lookup paper 'verticalequalizationfactor 0.3)))
202 (new-best (if (or (not current-best)
203 (and satisfied-constraints
204 (< total-penalty (page-penalty current-best))))
207 (page-set-property! this-page
210 (list (cons 'prev (if (null? best-paths)
213 (cons 'lines current-lines)
215 (cons 'configuration positions)
216 (cons 'penalty total-penalty)))
222 "\nuser pen " user-penalty
223 "\nsatisfied-constraints" satisfied-constraints
224 "\nlast? " last? "ragged?" ragged?
225 "\nis-better " is-better " total-penalty " total-penalty "\n"
226 "\nconfig " positions
228 "\nlines: " current-lines "\n")))
230 (display (list "\nnew-best is " (page-lines new-best)
232 (if (null? best-paths)
234 (page-lines (car best-paths))))))
235 (if (and (pair? done-lines)
236 ;; if this page is too full, adding another line won't help
237 satisfied-constraints)
238 (walk-paths (cdr done-lines) (cdr best-paths)
239 (cons (car done-lines) current-lines)
241 paper-book page-alist)
244 (define (walk-lines done best-paths todo paper-book page-alist)
245 "Return the best page breaking as a single
246 page node for optimally breaking TODO ++
247 DONE.reversed. BEST-PATHS is a list of break nodes corresponding to
251 (let* ((this-line (car todo))
252 (last? (null? (cdr todo)))
253 (next (walk-paths done best-paths (list this-line) last? #f
254 paper-book page-alist)))
255 (walk-lines (cons this-line done)
256 (cons next best-paths)
261 (define-public (optimal-page-breaks lines paper-book)
262 "Return pages as a list starting with 1st page. Each page is a 'page Prob."
263 (let* ((paper (ly:paper-book-paper paper-book))
264 (page-alist (layout->page-init paper))
265 (force-equalization-factor (ly:output-def-lookup
266 paper 'verticalequalizationfactor 0.3)))
267 (ly:message (_ "Calculating page breaks..."))
268 (let* ((best-break-node (walk-lines '() '() lines paper-book page-alist))
269 (break-nodes (get-path best-break-node '())))
270 (page-set-property! (car (last-pair break-nodes)) 'is-last #t)
271 (if #f; (ly:get-option 'verbose)
274 "\nbreaks: " (map (lambda (node)
275 (ly:prob-property (car (page-lines node))
278 "\nsystems " (map page-lines break-nodes)
279 "\npenalties " (map page-penalty break-nodes)
280 "\nconfigs " (map page-configuration break-nodes)))))
281 ;; construct page stencils.
282 (for-each page-stencil break-nodes)
283 (post-process-pages paper break-nodes)