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 stretchable-line?
24 page-maximum-space-to-fill page-maximum-space-left space-systems))
26 (define (page-breaking-wrapper paper-book)
27 "Compute line and page breaks by calling the page-breaking paper variable,
28 then performs the post process function using the page-post-process paper
29 variable. Finally, return the pages."
30 (let* ((paper (ly:paper-book-paper paper-book))
31 (pages ((ly:output-def-lookup paper 'page-breaking) paper-book)))
32 ((ly:output-def-lookup paper 'page-post-process) paper pages)
35 (define (post-process-pages layout pages)
36 "If the write-page-layout paper variable is true, dumps page breaks
38 (if (ly:output-def-lookup layout 'write-page-layout #f)
39 (write-page-breaks pages)))
42 ;;; Utilities for computing line distances and positions
44 (define (line-height line)
45 "Return the system height, that is the length of its vertical extent."
46 (interval-length (paper-system-extent line Y)))
48 (define (line-next-space line next-line layout)
49 "Return space to use between `line' and `next-line'.
50 `next-line' can be #f, meaning that `line' is the last line."
51 (let* ((title (paper-system-title? line))
52 (next-title (and next-line (paper-system-title? next-line))))
53 (cond ((and title next-title)
54 (ly:output-def-lookup layout 'between-title-space))
56 (ly:output-def-lookup layout 'after-title-space))
58 (ly:output-def-lookup layout 'before-title-space))
62 (ly:output-def-lookup layout 'between-system-space))))))
64 (define (line-next-padding line next-line layout)
65 "Return padding to use between `line' and `next-line'.
66 `next-line' can be #f, meaning that `line' is the last line."
69 (ly:output-def-lookup layout 'between-system-padding)))
72 (define (line-minimum-distance line next-line layout ignore-padding)
73 "Minimum distance between `line' reference position and `next-line'
74 reference position. If next-line is #f, return #f."
76 (let ((non-skyline-distance (- (interval-end (paper-system-extent next-line Y))
77 (interval-start (paper-system-extent line Y)))))
78 (max 0 (+ (ly:prob-property next-line 'skyline-distance non-skyline-distance)
79 (if ignore-padding 0 (line-next-padding line next-line layout)))))))
81 (define (line-ideal-distance line next-line layout ignore-padding)
82 "Ideal distance between `line' reference position and `next-line'
83 reference position. If next-line is #f, return #f."
85 (+ (max 0 (- (+ (interval-end (paper-system-staff-extents next-line))
86 (if ignore-padding 0 (line-next-padding line next-line layout)))
87 (interval-start (paper-system-staff-extents line))))
88 (line-next-space line next-line layout))))
90 (define (first-line-position line layout)
91 "Position of the first line on page"
92 (max (+ (ly:output-def-lookup layout 'page-top-space)
93 (interval-end (paper-system-staff-extents line)))
94 (interval-end (paper-system-extent line Y))))
96 (define (line-ideal-relative-position line prev-line layout ignore-padding)
97 "Return ideal position of `line', relative to `prev-line' position.
98 `prev-line' can be #f, meaning that `line' is the first line."
100 ;; first line on page
101 (first-line-position line layout)
102 ;; not the first line on page
103 (max (line-minimum-distance prev-line line layout ignore-padding)
104 (line-ideal-distance prev-line line layout ignore-padding))))
106 (define (line-minimum-relative-position line prev-line layout ignore-padding)
107 "Return position of `line', relative to `prev-line' position.
108 `prev-line' can be #f, meaning that `line' is the first line."
110 ;; first line on page
111 (first-line-position line layout)
112 ;; not the first line on page
113 (line-minimum-distance prev-line line layout ignore-padding)))
115 (define (line-minimum-position-on-page line prev-line prev-position page)
116 "If `line' fits on `page' after `prev-line', which position on page is
117 `prev-position', then return the line's postion on page, otherwise #f.
118 `prev-line' can be #f, meaning that `line' is the first line."
119 (let* ((layout (ly:paper-book-paper (page-property page 'paper-book)))
120 (position (+ (line-minimum-relative-position line prev-line layout #f)
121 (if prev-line prev-position 0.0)))
122 (bottom-position (- position
123 (interval-start (paper-system-extent line Y)))))
124 (and (or (not prev-line)
125 (< bottom-position (page-printable-height page)))
128 (define (stretchable-line? line)
129 "Say whether a system can be stretched."
130 (not (or (ly:prob-property? line 'is-title)
131 (let ((system-extent (paper-system-staff-extents line)))
132 (= (interval-start system-extent)
133 (interval-end system-extent))))))
135 (define (page-maximum-space-to-fill page lines paper)
136 "Return the space between the first line top position and the last line
137 bottom position. This constitutes the maximum space to fill on `page'
139 (let ((last-line (car (last-pair lines))))
140 (- (page-printable-height page)
141 (first-line-position (first lines) paper)
142 (ly:prob-property last-line
144 (- (interval-start (paper-system-extent last-line Y))))))
146 (define (page-maximum-space-left page)
147 (let ((paper (ly:paper-book-paper (page-property page 'paper-book))))
148 (let bottom-position ((lines (page-property page 'lines))
152 (page-printable-height page)
153 (let* ((line (first lines))
154 (position (line-minimum-position-on-page
155 line prev-line prev-position page)))
156 (if (null? (cdr lines))
158 (- (page-printable-height page)
160 (interval-start (paper-system-extent line Y)))))
161 (bottom-position (cdr lines) line position)))))))
164 ;;; Utilities for distributing systems on a page
167 (define (space-systems space-to-fill lines ragged paper ignore-padding)
168 "Compute lines positions on page: return force and line positions as a pair.
169 force is #f if lines do not fit on page."
170 (let* ((empty-stencil (ly:make-stencil '() '(0 . 0) '(0 . 0)))
171 (empty-prob (ly:make-prob 'paper-system (list `(stencil . ,empty-stencil))))
172 (cdr-lines (append (cdr lines)
173 (if (<= (length lines) 1)
176 (springs (map (lambda (prev-line line)
177 (list (line-ideal-distance prev-line line paper ignore-padding)
178 (/ 1.0 (line-next-space prev-line line paper))))
181 (rods (map (let ((i -1))
182 (lambda (prev-line line)
185 (line-minimum-distance prev-line line paper ignore-padding))))
189 (ly:solve-spring-rod-problem springs rods space-to-fill ragged)))
190 (cons (car space-result)
191 (map (let ((topskip (first-line-position (first lines) paper)))
194 (cdr space-result)))))
196 (define (make-page-from-systems paper-book lines page-number ragged last)
197 "Return a new page, filled with `lines'."
198 (let* ((page (make-page paper-book
200 'page-number page-number
202 (posns (if (null? lines)
204 (let* ((paper (ly:paper-book-paper paper-book))
205 (space-to-fill (page-maximum-space-to-fill
207 (spacing (space-systems space-to-fill lines ragged paper #f)))
208 (if (or (not (car spacing)) (inf? (car spacing)))
209 (cdr (space-systems space-to-fill lines ragged paper #t))
211 (page-set-property! page 'configuration posns)
215 ;;; Page breaking function
218 ;; Optimal distribution of
219 ;; lines over pages; line breaks are a given.
224 ;; - separate function for word-wrap style breaking?
225 ;; - ragged-bottom? ragged-last-bottom?
227 (define (get-path node done)
228 "Follow NODE.PREV, and return as an ascending list of pages. DONE
229 is what have collected so far, and has ascending page numbers."
231 (get-path (page-prev node) (cons node done))
234 (define (combine-penalties force user best-paths
235 inter-system-space force-equalization-factor)
236 (let* ((prev-force (if (null? best-paths)
238 (page-force (car best-paths))))
239 (prev-penalty (if (null? best-paths)
241 (page-penalty (car best-paths))))
242 (relative-force (/ force inter-system-space))
243 (abs-relative-force (abs relative-force)))
244 (+ (* abs-relative-force (+ abs-relative-force 1))
246 (* force-equalization-factor (/ (abs (- prev-force force))
250 (define (walk-paths done-lines best-paths current-lines last current-best
251 paper-book page-alist)
252 "Return the best optimal-page-break-node that contains
253 CURRENT-LINES. DONE-LINES.reversed ++ CURRENT-LINES is a consecutive
254 ascending range of lines, and BEST-PATHS contains the optimal breaks
255 corresponding to DONE-LINES.
257 CURRENT-BEST is the best result sofar, or #f."
258 (let* ((paper (ly:paper-book-paper paper-book))
259 (this-page (make-page
262 'page-number (if (null? best-paths)
263 (ly:output-def-lookup paper 'first-page-number)
264 (1+ (page-page-number (first best-paths))))))
265 (ragged-all (eq? #t (ly:output-def-lookup paper 'ragged-bottom)))
266 (ragged-last (eq? #t (ly:output-def-lookup paper 'ragged-last-bottom)))
267 (ragged (or ragged-all (and ragged-last last)))
268 (space-to-fill (page-maximum-space-to-fill this-page current-lines paper))
269 (vertical-spacing (space-systems space-to-fill current-lines ragged paper #f))
270 (satisfied-constraints (car vertical-spacing))
271 (force (if satisfied-constraints
272 (if (and last ragged-last)
274 satisfied-constraints)
276 (positions (cdr vertical-spacing))
277 (get-break-penalty (lambda (sys)
278 (ly:prob-property sys 'penalty 0.0)))
279 (user-nobreak-penalties (- (apply + (filter negative?
280 (map get-break-penalty
281 (cdr current-lines))))))
282 (user-penalty (+ (max (get-break-penalty (car current-lines)) 0.0)
283 user-nobreak-penalties))
284 (total-penalty (combine-penalties
285 force user-penalty best-paths
286 (ly:output-def-lookup paper 'between-system-space)
287 (ly:output-def-lookup paper 'verticalequalizationfactor 0.3)))
288 (new-best (if (or (not current-best)
289 (and satisfied-constraints
290 (< total-penalty (page-penalty current-best))))
293 (page-set-property! this-page
296 (list (cons 'prev (if (null? best-paths)
299 (cons 'lines current-lines)
301 (cons 'configuration positions)
302 (cons 'penalty total-penalty)))
308 "\nuser pen " user-penalty
309 "\nsatisfied-constraints" satisfied-constraints
310 "\nlast? " last "ragged?" ragged
311 "\nis-better " is-better " total-penalty " total-penalty "\n"
312 "\nconfig " positions
314 "\nlines: " current-lines "\n")))
316 (display (list "\nnew-best is " (page-lines new-best)
318 (if (null? best-paths)
320 (page-lines (car best-paths))))))
321 (if (and (pair? done-lines)
322 ;; if this page is too full, adding another line won't help
323 satisfied-constraints)
324 (walk-paths (cdr done-lines) (cdr best-paths)
325 (cons (car done-lines) current-lines)
327 paper-book page-alist)
330 (define (walk-lines done best-paths todo paper-book page-alist)
331 "Return the best page breaking as a single
332 page node for optimally breaking TODO ++
333 DONE.reversed. BEST-PATHS is a list of break nodes corresponding to
337 (let* ((this-line (car todo))
338 (last (null? (cdr todo)))
339 (next (walk-paths done best-paths (list this-line) last #f
340 paper-book page-alist)))
341 (walk-lines (cons this-line done)
342 (cons next best-paths)
347 (define-public (optimal-page-breaks paper-book)
348 "Return pages as a list starting with 1st page. Each page is a 'page Prob."
349 (let* ((paper (ly:paper-book-paper paper-book))
350 (lines (ly:paper-book-systems paper-book))
351 (page-alist (layout->page-init paper))
352 (force-equalization-factor (ly:output-def-lookup
353 paper 'verticalequalizationfactor 0.3)))
354 (ly:message (_ "Calculating page breaks..."))
355 (let* ((best-break-node (walk-lines '() '() lines paper-book page-alist))
356 (break-nodes (get-path best-break-node '())))
357 (page-set-property! (car (last-pair break-nodes)) 'is-last #t)
358 (if #f; (ly:get-option 'verbose)
361 "\nbreaks: " (map (lambda (node)
362 (ly:prob-property (car (page-lines node))
365 "\nsystems " (map page-lines break-nodes)
366 "\npenalties " (map page-penalty break-nodes)
367 "\nconfigs " (map page-configuration break-nodes)))))
368 ;; construct page stencils.
369 (for-each page-stencil break-nodes)