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@xs4all.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 make-page-from-systems
18 ;; utilities for writing custom page breaking functions
19 line-height line-next-space line-next-padding
20 line-minimum-distance line-ideal-distance
22 line-ideal-relative-position line-minimum-relative-position
23 line-minimum-position-on-page
24 page-maximum-space-to-fill page-maximum-space-left space-systems))
26 (define (stretch-and-draw-page paper-book systems page-number ragged last)
27 (define (stretchable? sys)
29 (ly:grob-property sys 'stretchable)))
31 (define (height-estimate sys)
34 (ly:grob-property sys 'pure-Y-extent)
35 (paper-system-extent sys Y))))
37 (define (max-stretch sys)
38 (if (stretchable? sys)
39 (ly:grob-property sys 'max-stretch)
42 (define (print-system sys)
47 (define (set-line-stretch! sorted-lines rest-height space-left)
48 (if (not (null? sorted-lines))
49 (let* ((line (first sorted-lines))
50 (height (height-estimate line))
51 (stretch (min (max-stretch line)
52 (if (positive? rest-height)
53 (/ (* height space-left) rest-height)
55 (if (stretchable? line)
56 (ly:system-stretch line stretch))
57 (set-line-stretch! (cdr sorted-lines)
58 (if (stretchable? line)
59 (- rest-height height)
61 (- space-left stretch)))))
63 (let* ((page (make-page paper-book
64 'page-number page-number
66 (paper (ly:paper-book-paper paper-book))
67 (height (page-printable-height page))
68 ; there is a certain amount of impreciseness going on here:
69 ; the system heights are estimated, we aren't using skyline distances
70 ; yet, etc. If we overstretch because of underestimation, the result
71 ; is very bad. So we stick in some extra space, just to be sure.
72 (buffer (/ height 10.0))
73 (total-system-height (apply + (map height-estimate systems)))
74 (height-left (- height total-system-height buffer)))
77 (set-line-stretch! (sort systems
79 (< (height-estimate s1)
80 (height-estimate s2))))
81 (apply + (map height-estimate
82 (filter stretchable? systems)))
83 (- (page-printable-height page)
84 total-system-height)))
86 (let* ((lines (map print-system systems))
87 (posns (if (null? lines)
89 (let* ((paper (ly:paper-book-paper paper-book))
90 (space-to-fill (page-maximum-space-to-fill
92 (spacing (space-systems space-to-fill lines ragged paper #f)))
93 (if (and (> (length lines) 1)
94 (or (not (car spacing)) (inf? (car spacing))))
96 (ly:warning (_ "Can't fit systems on page -- ignoring between-system-padding"))
97 (cdr (space-systems space-to-fill lines ragged paper #t)))
99 (page-set-property! page 'lines lines)
100 (page-set-property! page 'configuration posns)
103 (define (page-breaking-wrapper paper-book)
104 "Compute line and page breaks by calling the page-breaking paper variable,
105 then performs the post process function using the page-post-process paper
106 variable. Finally, return the pages."
107 (let* ((paper (ly:paper-book-paper paper-book))
108 (pages ((ly:output-def-lookup paper 'page-breaking) paper-book)))
109 ((ly:output-def-lookup paper 'page-post-process) paper pages)
112 (define (post-process-pages layout pages)
113 "If the write-page-layout paper variable is true, dumps page breaks
117 ((parser (ly:modules-lookup (list (current-module)) 'parser))
118 (output-name (ly:parser-output-name parser))
121 (if (ly:output-def-lookup layout 'write-page-layout #f)
122 (write-page-breaks pages output-name))))
125 ;;; Utilities for computing line distances and positions
127 (define (line-extent line)
128 "Return the extent of the line (its lowest and highest Y-coordinates)."
129 (paper-system-extent line Y))
131 (define (line-height line)
132 "Return the system height, that is the length of its vertical extent."
133 (interval-length (line-extent line)))
135 (define (line-next-space line next-line layout)
136 "Return space to use between `line' and `next-line'.
137 `next-line' can be #f, meaning that `line' is the last line."
138 (let* ((title (paper-system-title? line))
139 (next-title (and next-line (paper-system-title? next-line))))
140 (cond ((and title next-title)
141 (ly:output-def-lookup layout 'between-title-space))
143 (ly:output-def-lookup layout 'after-title-space))
145 (ly:output-def-lookup layout 'before-title-space))
149 (ly:output-def-lookup layout 'between-system-space))))))
151 (define (line-next-padding line next-line layout)
152 "Return padding to use between `line' and `next-line'.
153 `next-line' can be #f, meaning that `line' is the last line."
156 (ly:output-def-lookup layout 'between-system-padding)))
159 (define (line-minimum-distance line next-line layout ignore-padding)
160 "Minimum distance between `line' reference position and `next-line'
161 reference position. If next-line is #f, return #f."
163 (let ((padding (if ignore-padding
165 (line-next-padding line next-line layout))))
166 (if (or (ly:grob? line) (ly:grob? next-line))
168 (- (interval-start (line-extent line))
169 (interval-end (line-extent next-line)))))
171 (ly:paper-system-minimum-distance line next-line)))))))
173 (define (line-ideal-distance line next-line layout ignore-padding)
174 "Ideal distance between `line' reference position and `next-line'
175 reference position. If next-line is #f, return #f."
177 (+ (max 0 (- (+ (interval-end (paper-system-staff-extents next-line))
178 (if ignore-padding 0 (line-next-padding line next-line layout)))
179 (interval-start (paper-system-staff-extents line))))
180 (line-next-space line next-line layout))))
182 (define (first-line-position line layout)
183 "Position of the first line on page"
184 (max (+ (if (ly:prob-property? line 'is-title)
185 ;; do not use page-top-space if first line is a title
187 (ly:output-def-lookup layout 'page-top-space))
188 (interval-end (paper-system-staff-extents line)))
189 (interval-end (line-extent line))))
191 (define (line-ideal-relative-position line prev-line layout ignore-padding)
192 "Return ideal position of `line', relative to `prev-line' position.
193 `prev-line' can be #f, meaning that `line' is the first line."
195 ;; first line on page
196 (first-line-position line layout)
197 ;; not the first line on page
198 (max (line-minimum-distance prev-line line layout ignore-padding)
199 (line-ideal-distance prev-line line layout ignore-padding))))
201 (define (line-minimum-relative-position line prev-line layout ignore-padding)
202 "Return position of `line', relative to `prev-line' position.
203 `prev-line' can be #f, meaning that `line' is the first line."
205 ;; first line on page
206 (first-line-position line layout)
207 ;; not the first line on page
208 (line-minimum-distance prev-line line layout ignore-padding)))
210 (define (line-minimum-position-on-page line prev-line prev-position page)
211 "If `line' fits on `page' after `prev-line', which position on page is
212 `prev-position', then return the line's postion on page, otherwise #f.
213 `prev-line' can be #f, meaning that `line' is the first line."
214 (let* ((layout (ly:paper-book-paper (page-property page 'paper-book)))
215 (position (+ (line-minimum-relative-position line prev-line layout #f)
216 (if prev-line prev-position 0.0)))
217 (bottom-position (- position
218 (interval-start (line-extent line)))))
219 (and (or (not prev-line)
220 (< bottom-position (page-printable-height page)))
223 (define (page-maximum-space-to-fill page lines paper)
224 "Return the space between the first line top position and the last line
225 bottom position. This constitutes the maximum space to fill on `page'
227 (let ((last-line (car (last-pair lines))))
228 (- (page-printable-height page)
229 (first-line-position (first lines) paper)
230 (ly:prob-property last-line
232 (- (interval-start (line-extent last-line))))))
234 (define (page-maximum-space-left page)
235 (let ((paper (ly:paper-book-paper (page-property page 'paper-book))))
236 (let bottom-position ((lines (page-property page 'lines))
240 (page-printable-height page)
241 (let* ((line (first lines))
242 (position (line-minimum-position-on-page
243 line prev-line prev-position page)))
244 (if (null? (cdr lines))
246 (- (page-printable-height page)
248 (interval-start (line-extent line)))))
249 (bottom-position (cdr lines) line position)))))))
252 ;;; Utilities for distributing systems on a page
255 (define (space-systems space-to-fill lines ragged paper ignore-padding)
256 "Compute lines positions on page: return force and line positions as a pair.
257 force is #f if lines do not fit on page."
258 (let* ((empty-stencil (ly:make-stencil '() '(0 . 0) '(0 . 0)))
259 (empty-prob (ly:make-prob 'paper-system (list `(stencil . ,empty-stencil))))
260 (cdr-lines (append (cdr lines)
261 (if (<= (length lines) 1)
264 (springs (map (lambda (prev-line line)
265 (list (line-ideal-distance prev-line line paper ignore-padding)
266 (/ 1.0 (line-next-space prev-line line paper))))
269 (rods (map (let ((i -1))
270 (lambda (prev-line line)
273 (line-minimum-distance prev-line line paper ignore-padding))))
277 (ly:solve-spring-rod-problem springs rods space-to-fill ragged)))
278 (cons (car space-result)
279 (map (let ((topskip (first-line-position (first lines) paper)))
282 (cdr space-result)))))
286 ;;; Page breaking function
289 ;; Optimal distribution of
290 ;; lines over pages; line breaks are a given.
295 ;; - separate function for word-wrap style breaking?
296 ;; - ragged-bottom? ragged-last-bottom?
298 (define (get-path node done)
299 "Follow NODE.PREV, and return as an ascending list of pages. DONE
300 is what have collected so far, and has ascending page numbers."
302 (get-path (page-prev node) (cons node done))
305 (define (combine-penalties force user best-paths
306 inter-system-space force-equalization-factor)
307 (let* ((prev-force (if (null? best-paths)
309 (page-force (car best-paths))))
310 (prev-penalty (if (null? best-paths)
312 (page-penalty (car best-paths))))
313 (relative-force (/ force inter-system-space))
314 (abs-relative-force (abs relative-force)))
315 (+ (* abs-relative-force (+ abs-relative-force 1))
317 (* force-equalization-factor (/ (abs (- prev-force force))
321 (define (walk-paths done-lines best-paths current-lines last current-best
322 paper-book page-alist)
323 "Return the best optimal-page-break-node that contains
324 CURRENT-LINES. DONE-LINES.reversed ++ CURRENT-LINES is a consecutive
325 ascending range of lines, and BEST-PATHS contains the optimal breaks
326 corresponding to DONE-LINES.
328 CURRENT-BEST is the best result sofar, or #f."
329 (let* ((paper (ly:paper-book-paper paper-book))
330 (this-page (make-page
333 'page-number (if (null? best-paths)
334 (ly:output-def-lookup paper 'first-page-number)
335 (1+ (page-page-number (first best-paths))))))
336 (ragged-all (eq? #t (ly:output-def-lookup paper 'ragged-bottom)))
337 (ragged-last (eq? #t (ly:output-def-lookup paper 'ragged-last-bottom)))
338 (ragged (or ragged-all (and ragged-last last)))
339 (space-to-fill (page-maximum-space-to-fill this-page current-lines paper))
340 (vertical-spacing (space-systems space-to-fill current-lines ragged paper #f))
341 (satisfied-constraints (car vertical-spacing))
342 (force (if satisfied-constraints
343 (if (and last ragged-last)
345 satisfied-constraints)
347 (positions (cdr vertical-spacing))
348 (get-break-penalty (lambda (sys)
349 (ly:prob-property sys 'penalty 0.0)))
350 (user-nobreak-penalties (- (apply + (filter negative?
351 (map get-break-penalty
352 (cdr current-lines))))))
353 (user-penalty (+ (max (get-break-penalty (car current-lines)) 0.0)
354 user-nobreak-penalties))
355 (total-penalty (combine-penalties
356 force user-penalty best-paths
357 (ly:output-def-lookup paper 'between-system-space)
358 (ly:output-def-lookup paper 'verticalequalizationfactor 0.3)))
359 (new-best (if (or (not current-best)
360 (and satisfied-constraints
361 (< total-penalty (page-penalty current-best))))
364 (page-set-property! this-page
367 (list (cons 'prev (if (null? best-paths)
370 (cons 'lines current-lines)
372 (cons 'configuration positions)
373 (cons 'penalty total-penalty)))
379 "\nuser pen " user-penalty
380 "\nsatisfied-constraints" satisfied-constraints
381 "\nlast? " last "ragged?" ragged
382 "\nis-better " is-better " total-penalty " total-penalty "\n"
383 "\nconfig " positions
385 "\nlines: " current-lines "\n")))
387 (display (list "\nnew-best is " (page-lines new-best)
389 (if (null? best-paths)
391 (page-lines (car best-paths))))))
392 (if (and (pair? done-lines)
393 ;; if this page is too full, adding another line won't help
394 satisfied-constraints)
395 (walk-paths (cdr done-lines) (cdr best-paths)
396 (cons (car done-lines) current-lines)
398 paper-book page-alist)
401 (define (walk-lines done best-paths todo paper-book page-alist)
402 "Return the best page breaking as a single
403 page node for optimally breaking TODO ++
404 DONE.reversed. BEST-PATHS is a list of break nodes corresponding to
408 (let* ((this-line (car todo))
409 (last (null? (cdr todo)))
410 (next (walk-paths done best-paths (list this-line) last #f
411 paper-book page-alist)))
412 (walk-lines (cons this-line done)
413 (cons next best-paths)
418 (define-public (optimal-page-breaks paper-book)
419 "Return pages as a list starting with 1st page. Each page is a 'page Prob."
420 (let* ((paper (ly:paper-book-paper paper-book))
421 (lines (ly:paper-book-systems paper-book))
422 (page-alist (layout->page-init paper))
423 (force-equalization-factor (ly:output-def-lookup
424 paper 'verticalequalizationfactor 0.3)))
425 (ly:message (_ "Calculating page breaks..."))
426 (let* ((best-break-node (walk-lines '() '() lines paper-book page-alist))
427 (break-nodes (get-path best-break-node '())))
428 (page-set-property! (car (last-pair break-nodes)) 'is-last #t)
429 (if #f; (ly:get-option 'verbose)
432 "\nbreaks: " (map (lambda (node)
433 (ly:prob-property (car (page-lines node))
436 "\nsystems " (map page-lines break-nodes)
437 "\npenalties " (map page-penalty break-nodes)
438 "\nconfigs " (map page-configuration break-nodes)))))
439 ;; construct page stencils.
440 (for-each page-stencil break-nodes)