2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 Joe Neeman <joeneeman@gmail.com>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
21 This is a utility class for page-breaking algorithms. There are some complex
22 parts of this class, some of which are useful to understand if you intend
23 to write a page breaking algorithm (ie. a subclass of Page_breaking). Most
24 of these complexities were introduced in order to break the problem of
25 page-breaking into simpler subproblems and to hide some of the bookkeeping
26 complexities of page breaking from the page breaking algorithms.
29 There are several functions that actually distribute systems across pages
30 (for example, the space_systems_XXX and pack_systems_XXX functions). If
31 each of these functions had to handle \noPageBreak, it would be a mess.
32 Therefore, we handle \noPageBreak by "compressing" the list of systems
33 before doing any layout: we concatenate any two systems separated by a
34 \noPageBreak into a single system. The page-breaking functions can do their
35 magic without encountering a \noPageBreak; we then "uncompress" the systems
36 at the end. We almost always work with cached_line_details_, which are
40 The basic operation of a page breaking algorithm is to repeatedly request
41 some systems from the line-breaker and place those systems on some pages.
42 With each repetition, the page breaking algorithm asks the line-breaker for
43 some systems that it thinks will help it achieve a better layout. The
44 Page_breaking class provides functionality to facilitate this in the case
45 that the page breaking algorithm only cares about the number of systems.
47 Even if a page breaking algorithm only cares number of systems, there may
48 be many ways to satisfy its request. For example, in a piece with 2 scores
49 and a request for 10 systems, we could return 5 systems from each score or
50 4 from the first and 6 from the second. Even within a score, we might
51 want to try several different line breaking configurations with a fixed
52 system count; if there is a forced \pageBreak, for example, we might wish
53 to tweak the number of systems on both sides of the \pageBreak independently.
55 The Page_breaking class takes care of finding these configurations. It
56 divides the piece into "chunks" and sets up the line-breaker in such a way
57 that the number of systems in each chunk can be modified independently.
58 Chunks never cross score boundaries; each title and markup is its own chunk.
59 When a page breaking algorithm requests a number of systems, the Page_breaker
60 stores an array of potential configurations, which the page breaking
61 algorithm can iterate over using current_configuration(vsize).
64 A Line_division is simply a way of storing the exact way in which the
65 total number of systems is distributed among chunks. Note that a
66 Line_division may not (in fact, usually will not) describe all of the chunks
67 in the entire book. Rather, it will describe the subset of chunks that lie
68 between some fixed starting and ending point. This subset of chunks changes
69 whenever a page breaking algorithm asks to consider a different pair of
70 starting and ending breakpoints. In particular, a Line_division should be
71 discarded after a call to set_current_breakpoints, since that Line_division
72 refers to a subset of chunks which might be different from the current
73 subset of chunks under consideration.
76 #include "page-breaking.hh"
78 #include "international.hh"
80 #include "output-def.hh"
81 #include "page-layout-problem.hh"
82 #include "page-spacing.hh"
83 #include "paper-book.hh"
84 #include "paper-score.hh"
85 #include "paper-system.hh"
89 /* for each forbidden page break, merge the systems around it into one
91 static vector
<Line_details
>
92 compress_lines (const vector
<Line_details
> &orig
)
94 vector
<Line_details
> ret
;
96 for (vsize i
= 0; i
< orig
.size (); i
++)
98 if (ret
.size () && !scm_is_symbol (ret
.back ().page_permission_
))
100 Line_details
const &old
= ret
.back ();
101 Line_details compressed
= orig
[i
];
103 We must account for the padding between the lines that we are compressing.
104 The padding values come from "old," which is the upper system here. Note
105 the meaning of tight-spacing: if a system has tight-spacing, then the padding
106 _before_ it is ignored.
109 if (!orig
[i
].tight_spacing_
)
110 padding
= orig
[i
].title_
? old
.title_padding_
: old
.padding_
;
112 // FIXME: double check these. Doesn't foo.piggyback (bar) mean
113 // that foo goes on top?
114 // TODO: break out a Line_details::piggyback from here?
115 compressed
.shape_
= old
.shape_
.piggyback (orig
[i
].shape_
, padding
);
116 compressed
.refpoint_extent_
[UP
] = old
.refpoint_extent_
[UP
];
117 compressed
.refpoint_extent_
[DOWN
] += compressed
.shape_
.rest_
[UP
] - old
.shape_
.rest_
[UP
];
118 compressed
.space_
+= old
.space_
;
119 compressed
.inverse_hooke_
+= old
.inverse_hooke_
;
121 compressed
.compressed_lines_count_
= old
.compressed_lines_count_
+ 1;
122 compressed
.compressed_nontitle_lines_count_
=
123 old
.compressed_nontitle_lines_count_
+ (compressed
.title_
? 0 : 1);
125 // compressed.title_ is true if and only if the first of its
126 // compressed lines was a title.
127 compressed
.title_
= old
.title_
;
128 ret
.back () = compressed
;
132 ret
.push_back (orig
[i
]);
133 ret
.back ().force_
= 0;
139 /* translate the number of systems-per-page into something meaningful for
140 the uncompressed lines.
143 uncompress_solution (vector
<vsize
> const &systems_per_page
,
144 vector
<Line_details
> const &compressed
)
149 for (vsize i
= 0; i
< systems_per_page
.size (); i
++)
151 int compressed_count
= 0;
152 for (vsize j
= start_sys
; j
< start_sys
+ systems_per_page
[i
]; j
++)
153 compressed_count
+= compressed
[j
].compressed_lines_count_
- 1;
155 ret
.push_back (systems_per_page
[i
] + compressed_count
);
156 start_sys
+= systems_per_page
[i
];
161 /* for Page_breaking, the start index (when we are dealing with the stuff
162 between a pair of breakpoints) refers to the break_ index of the end of
163 the previous page. So the system index of the start of the current page
164 could either be the same as the end of the previous page or one more than
167 /* Turn a break index into the sys index that starts the next page */
169 Page_breaking::next_system (Break_position
const &break_pos
) const
171 vsize sys
= break_pos
.system_spec_index_
;
173 if (sys
== VPOS
) /* beginning of the book */
175 if (system_specs_
[sys
].pscore_
&& !break_pos
.score_ender_
)
176 return sys
; /* the score overflows the previous page */
177 return sys
+ 1; /* this page starts with a new System_spec */
180 Page_breaking::Page_breaking (Paper_book
*pb
, Break_predicate is_break
, Prob_break_predicate prob_break
)
184 paper_height_
= robust_scm2double (pb
->paper_
->c_variable ("paper-height"), 1.0);
185 ragged_
= to_boolean (pb
->paper_
->c_variable ("ragged-bottom"));
186 ragged_last_
= to_boolean (pb
->paper_
->c_variable ("ragged-last-bottom"));
187 systems_per_page_
= max (0, robust_scm2int (pb
->paper_
->c_variable ("systems-per-page"), 0));
188 max_systems_per_page_
= max (0, robust_scm2int (pb
->paper_
->c_variable ("max-systems-per-page"), 0));
189 min_systems_per_page_
= max (0, robust_scm2int (pb
->paper_
->c_variable ("min-systems-per-page"), 0));
190 orphan_penalty_
= robust_scm2int (pb
->paper_
->c_variable ("orphan-penalty"), 100000);
192 if (systems_per_page_
&& (max_systems_per_page_
|| min_systems_per_page_
))
194 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
195 min_systems_per_page_
= max_systems_per_page_
= 0;
197 if (max_systems_per_page_
&& min_systems_per_page_
> max_systems_per_page_
)
199 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
200 min_systems_per_page_
= max_systems_per_page_
= 0;
203 create_system_list ();
204 find_chunks_and_breaks (is_break
, prob_break
);
207 Page_breaking::~Page_breaking ()
212 Page_breaking::ragged () const
218 Page_breaking::ragged_last () const
224 Page_breaking::systems_per_page () const
226 return systems_per_page_
;
230 Page_breaking::max_systems_per_page () const
232 if (systems_per_page_
)
233 return systems_per_page_
;
234 return max_systems_per_page_
;
238 Page_breaking::min_systems_per_page () const
240 if (systems_per_page_
)
241 return systems_per_page_
;
242 return min_systems_per_page_
;
246 Page_breaking::system_count () const
248 return system_count_
;
252 Page_breaking::too_many_lines (int line_count
) const
254 return max_systems_per_page () > 0 && line_count
> max_systems_per_page ();
258 Page_breaking::too_few_lines (int line_count
) const
260 return line_count
< min_systems_per_page ();
264 Page_breaking::line_count_penalty (int line_count
) const
266 if (too_many_lines (line_count
))
267 return (line_count
- max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY
;
268 if (too_few_lines (line_count
))
269 return (min_systems_per_page () - line_count
) * TERRIBLE_SPACING_PENALTY
;
275 Page_breaking::line_count_status (int line_count
) const
277 if (too_many_lines (line_count
))
278 return SYSTEM_COUNT_TOO_MANY
;
279 if (too_few_lines (line_count
))
280 return SYSTEM_COUNT_TOO_FEW
;
282 return SYSTEM_COUNT_OK
;
285 /* translate indices into breaks_ into start-end parameters for the line breaker */
287 Page_breaking::line_breaker_args (vsize sys
,
288 Break_position
const &start
,
289 Break_position
const &end
,
290 vsize
*line_breaker_start
,
291 vsize
*line_breaker_end
)
293 assert (system_specs_
[sys
].pscore_
);
294 assert (next_system (start
) <= sys
&& sys
<= end
.system_spec_index_
);
296 if (start
.system_spec_index_
== sys
)
297 *line_breaker_start
= start
.score_break_
;
299 *line_breaker_start
= 0;
301 if (end
.system_spec_index_
== sys
)
302 *line_breaker_end
= end
.score_break_
;
304 *line_breaker_end
= VPOS
;
308 Page_breaking::break_into_pieces (vsize start_break
, vsize end_break
,
309 Line_division
const &div
)
311 vector
<Break_position
> chunks
= chunk_list (start_break
, end_break
);
312 bool ignore_div
= false;
313 if (chunks
.size () != div
.size () + 1)
315 programming_error ("did not find a valid page breaking configuration");
319 for (vsize i
= 0; i
+ 1 < chunks
.size (); i
++)
321 vsize sys
= next_system (chunks
[i
]);
322 if (system_specs_
[sys
].pscore_
)
326 line_breaker_args (sys
, chunks
[i
], chunks
[i
+1], &start
, &end
);
328 vector
<Column_x_positions
> pos
= ignore_div
329 ? line_breaking_
[sys
].best_solution (start
, end
)
330 : line_breaking_
[sys
].solve (start
, end
, div
[i
]);
331 system_specs_
[sys
].pscore_
->root_system ()->break_into_pieces (pos
);
337 Page_breaking::systems ()
340 for (vsize sys
= 0; sys
< system_specs_
.size (); sys
++)
342 if (system_specs_
[sys
].pscore_
)
344 system_specs_
[sys
].pscore_
->root_system ()
345 ->do_break_substitution_and_fixup_refpoints ();
346 SCM lines
= system_specs_
[sys
].pscore_
->root_system ()
347 ->get_broken_system_grobs ();
348 ret
= scm_cons (lines
, ret
);
350 else if (Prob
*pb
= system_specs_
[sys
].prob_
)
352 ret
= scm_cons (scm_list_1 (pb
->self_scm ()), ret
);
356 return scm_append (scm_reverse (ret
));
360 Page_breaking::make_page (int page_num
, bool last
) const
362 bool last_part
= ly_scm2bool (book_
->paper_
->c_variable ("is-last-bookpart"));
363 SCM mod
= scm_c_resolve_module ("scm page");
364 SCM make_page_scm
= scm_c_module_lookup (mod
, "make-page");
366 make_page_scm
= scm_variable_ref (make_page_scm
);
368 return scm_apply_0 (make_page_scm
,
369 scm_list_n (book_
->self_scm (),
370 ly_symbol2scm ("page-number"), scm_from_int (page_num
),
371 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part
),
372 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last
),
376 // Returns the total height of the paper, including margins and
377 // space for the header/footer. This is an upper bound on
378 // page_height, and it doesn't depend on the current page.
380 Page_breaking::paper_height () const
382 return paper_height_
;
386 Page_breaking::page_height (int page_num
, bool last
) const
388 // The caches allow us to store the page heights for any
389 // non-negative page numbers. We use a negative value in the
390 // cache to signal that that position has not yet been initialized.
391 // This means that we won't cache properly if page_num is negative or
392 // if calc_height returns a negative number. But that's likely to
393 // be rare, so it shouldn't affect performance.
394 vector
<Real
>& cache
= last
? last_page_height_cache_
: page_height_cache_
;
395 if (page_num
>= 0 && (int) cache
.size () > page_num
&& cache
[page_num
] >= 0)
396 return cache
[page_num
];
399 SCM mod
= scm_c_resolve_module ("scm page");
400 SCM page
= make_page (page_num
, last
);
401 SCM calc_height
= scm_c_module_lookup (mod
, "calc-printable-height");
402 calc_height
= scm_variable_ref (calc_height
);
404 SCM height_scm
= scm_apply_1 (calc_height
, page
, SCM_EOL
);
405 Real height
= scm_to_double (height_scm
);
409 if ((int) cache
.size () <= page_num
)
410 cache
.resize (page_num
+ 1, -1);
411 cache
[page_num
] = height
;
418 Page_breaking::breakpoint_property (vsize breakpoint
, char const *str
)
420 Break_position
const &pos
= breaks_
[breakpoint
];
422 if (pos
.system_spec_index_
== VPOS
)
424 if (system_specs_
[pos
.system_spec_index_
].pscore_
)
425 return pos
.col_
->get_property (str
);
426 return system_specs_
[pos
.system_spec_index_
].prob_
->get_property (str
);
430 Page_breaking::get_page_configuration (SCM systems
, int page_num
, bool ragged
, bool last
)
432 SCM dummy_page
= make_page (page_num
, last
);
433 Page_layout_problem
layout (book_
, dummy_page
, systems
);
434 return scm_is_pair (systems
) ? layout
.solution (ragged
) : SCM_EOL
;
438 Page_breaking::draw_page (SCM systems
, SCM configuration
, int page_num
, bool last
)
440 // Create a stencil for each system.
441 SCM paper_systems
= SCM_EOL
;
442 for (SCM s
= scm_reverse (systems
); scm_is_pair (s
); s
= scm_cdr (s
))
444 SCM paper_system
= scm_car (s
);
445 if (Grob
*g
= unsmob_grob (scm_car (s
)))
447 System
*sys
= dynamic_cast<System
*> (g
);
448 paper_system
= sys
->get_paper_system ();
451 paper_systems
= scm_cons (paper_system
, paper_systems
);
454 // Create the page and draw it.
455 SCM page
= make_page (page_num
, last
);
456 SCM page_module
= scm_c_resolve_module ("scm page");
457 SCM page_stencil
= scm_c_module_lookup (page_module
, "page-stencil");
458 page_stencil
= scm_variable_ref (page_stencil
);
460 Prob
*p
= unsmob_prob (page
);
461 p
->set_property ("lines", paper_systems
);
462 p
->set_property ("configuration", configuration
);
463 scm_apply_1 (page_stencil
, page
, SCM_EOL
);
469 Page_breaking::make_pages (vector
<vsize
> lines_per_page
, SCM systems
)
471 if (scm_is_null (systems
))
474 int first_page_number
475 = robust_scm2int (book_
->paper_
->c_variable ("first-page-number"), 1);
477 SCM label_page_table
= book_
->top_paper ()->c_variable ("label-page-table");
478 if (label_page_table
== SCM_UNDEFINED
)
479 label_page_table
= SCM_EOL
;
481 // Build a list of (systems . configuration) pairs. Note that we lay out
482 // the staves and find the configurations before drawing anything. Some
483 // grobs (like tuplet brackets) look at their neighbours while drawing
484 // themselves. If this happens before the neighbouring staves have
485 // been laid out, bad side-effects could happen (in particular,
486 // Align_interface::align_to_ideal_distances might be called).
487 SCM systems_and_configs
= SCM_EOL
;
489 for (vsize i
= 0; i
< lines_per_page
.size (); i
++)
491 int page_num
= i
+ first_page_number
;
492 bool bookpart_last_page
= (i
== lines_per_page
.size () - 1);
493 bool rag
= ragged () || (bookpart_last_page
&& ragged_last ());
494 SCM line_count
= scm_from_int (lines_per_page
[i
]);
495 SCM lines
= scm_list_head (systems
, line_count
);
496 SCM config
= get_page_configuration (lines
, page_num
, rag
, bookpart_last_page
);
498 systems_and_configs
= scm_cons (scm_cons (lines
, config
), systems_and_configs
);
499 systems
= scm_list_tail (systems
, line_count
);
502 // Now it's safe to make the pages.
503 int page_num
= first_page_number
+ lines_per_page
.size () - 1;
504 for (SCM s
= systems_and_configs
; scm_is_pair (s
); s
= scm_cdr (s
))
506 SCM lines
= scm_caar (s
);
507 SCM config
= scm_cdar (s
);
508 bool bookpart_last_page
= (s
== systems_and_configs
);
509 SCM page
= draw_page (lines
, config
, page_num
, bookpart_last_page
);
512 SCM page_num_scm
= scm_from_int (page_num
);
513 for (SCM l
= lines
; scm_is_pair (l
) ; l
= scm_cdr (l
))
515 SCM labels
= SCM_EOL
;
516 if (Grob
* line
= unsmob_grob (scm_car (l
)))
518 System
*system
= dynamic_cast<System
*> (line
);
519 labels
= system
->get_property ("labels");
521 else if (Prob
*prob
= unsmob_prob (scm_car (l
)))
522 labels
= prob
->get_property ("labels");
524 for (SCM lbls
= labels
; scm_is_pair (lbls
) ; lbls
= scm_cdr (lbls
))
525 label_page_table
= scm_cons (scm_cons (scm_car (lbls
), page_num_scm
),
529 ret
= scm_cons (page
, ret
);
533 // By reversing the table, we ensure that duplicated labels (eg. those
534 // straddling a page turn) will appear in the table with their last
536 label_page_table
= scm_reverse_x (label_page_table
, SCM_EOL
);
537 book_
->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table
);
541 /* The page-turn-page-breaker needs to have a line-breaker between any two
542 columns with non-NULL page-turn-permission.
544 The optimal-breaker needs to have a line-breaker between any two columns
545 with page-break-permission = 'force.
547 By using a grob predicate, we can accommodate both of these uses.
550 Page_breaking::create_system_list ()
552 SCM specs
= book_
->get_system_specs ();
553 for (SCM s
= specs
; scm_is_pair (s
); s
= scm_cdr (s
))
555 if (Paper_score
*ps
= dynamic_cast<Paper_score
*> (unsmob_music_output (scm_car (s
))))
557 system_specs_
.push_back (System_spec (ps
));
561 Prob
*pb
= unsmob_prob (scm_car (s
));
565 system_specs_
.push_back (System_spec (pb
));
568 if (!system_specs_
.size ())
569 system_specs_
.push_back (System_spec ());
573 Page_breaking::find_chunks_and_breaks (Break_predicate is_break
, Prob_break_predicate prob_is_break
)
575 SCM force_sym
= ly_symbol2scm ("force");
577 chunks_
.push_back (Break_position ());
578 breaks_
.push_back (Break_position ());
580 for (vsize i
= 0; i
< system_specs_
.size (); i
++)
582 if (system_specs_
[i
].pscore_
)
584 vector
<Grob
*> cols
= system_specs_
[i
].pscore_
->root_system ()->used_columns ();
585 vector
<Grob
*> forced_line_break_cols
;
587 SCM system_count
= system_specs_
[i
].pscore_
->layout ()->c_variable ("system-count");
588 if (scm_is_number (system_count
))
590 // With system-count given, the line configuration for
591 // this score is fixed. We need to ensure that chunk
592 // boundaries only occur at line breaks.
593 Constrained_breaking
breaking (system_specs_
[i
].pscore_
);
594 vector
<Line_details
> details
= breaking
.line_details (0, VPOS
, scm_to_int (system_count
));
596 for (vsize j
= 0; j
< details
.size (); j
++)
597 forced_line_break_cols
.push_back (details
[j
].last_column_
);
600 int last_forced_line_break_idx
= 0;
601 vsize forced_line_break_idx
= 0;
602 vector
<vsize
> line_breaker_columns
;
603 line_breaker_columns
.push_back (0);
605 for (vsize j
= 1; j
< cols
.size (); j
++)
607 if (forced_line_break_cols
.size ())
609 if (forced_line_break_idx
>= forced_line_break_cols
.size ()
610 || forced_line_break_cols
[forced_line_break_idx
] != cols
[j
])
613 forced_line_break_idx
++;
616 bool last
= (j
== cols
.size () - 1);
617 bool break_point
= is_break
&& is_break (cols
[j
]);
618 bool chunk_end
= cols
[j
]->get_property ("page-break-permission") == force_sym
;
619 Break_position cur_pos
= Break_position (i
,
620 line_breaker_columns
.size (),
624 // NOTE: even in the breaks_ list, forced_line_count_
625 // refers to the number of lines between a
626 // Break_position and the start of that /chunk/. This
627 // is needed for system_count_bounds to work correctly,
628 // since it mixes Break_positions from breaks_ and
630 if (scm_is_number (system_count
))
631 cur_pos
.forced_line_count_
= forced_line_break_idx
- last_forced_line_break_idx
;
633 if (break_point
|| (i
== system_specs_
.size () - 1 && last
))
634 breaks_
.push_back (cur_pos
);
635 if (chunk_end
|| last
)
637 chunks_
.push_back (cur_pos
);
638 last_forced_line_break_idx
= forced_line_break_idx
;
641 if ((break_point
|| chunk_end
) && !last
)
642 line_breaker_columns
.push_back (j
);
644 line_breaking_
.push_back (Constrained_breaking (system_specs_
[i
].pscore_
, line_breaker_columns
));
646 else if (system_specs_
[i
].prob_
)
648 bool break_point
= prob_is_break
&& prob_is_break (system_specs_
[i
].prob_
);
649 if (break_point
|| i
== system_specs_
.size () - 1)
650 breaks_
.push_back (Break_position (i
));
652 chunks_
.push_back (Break_position (i
));
654 /* FIXME: shouldn't we push a Null_breaker or similar dummy
656 line_breaking_
.push_back (Constrained_breaking (NULL
));
661 vector
<Break_position
>
662 Page_breaking::chunk_list (vsize start_index
, vsize end_index
)
664 Break_position start
= breaks_
[start_index
];
665 Break_position end
= breaks_
[end_index
];
668 for (; i
< chunks_
.size () && chunks_
[i
] <= start
; i
++)
671 vector
<Break_position
> ret
;
672 ret
.push_back (start
);
673 for (; i
< chunks_
.size () && chunks_
[i
] < end
; i
++)
674 ret
.push_back (chunks_
[i
]);
679 // Returns the minimum number of _non-title_ lines.
681 Page_breaking::min_system_count (vsize start
, vsize end
)
683 vector
<Break_position
> chunks
= chunk_list (start
, end
);
684 Line_division div
= system_count_bounds (chunks
, true);
687 for (vsize i
= 0; i
< div
.size (); i
++)
692 // Returns the maximum number of _non-title_ lines.
694 Page_breaking::max_system_count (vsize start
, vsize end
)
696 vector
<Break_position
> chunks
= chunk_list (start
, end
);
697 Line_division div
= system_count_bounds (chunks
, false);
700 for (vsize i
= 0; i
< div
.size (); i
++)
705 // The numbers returned by this function represent either
706 // the maximum or minimum number of _non-title_ lines
708 Page_breaking::Line_division
709 Page_breaking::system_count_bounds (vector
<Break_position
> const &chunks
,
712 assert (chunks
.size () >= 2);
715 ret
.resize (chunks
.size () - 1, 0);
717 for (vsize i
= 0; i
+ 1 < chunks
.size (); i
++)
719 vsize sys
= next_system (chunks
[i
]);
721 if (chunks
[i
+1].forced_line_count_
)
722 ret
[i
] = chunks
[i
+1].forced_line_count_
;
723 else if (system_specs_
[sys
].pscore_
)
727 line_breaker_args (sys
, chunks
[i
], chunks
[i
+1], &start
, &end
);
729 ? line_breaking_
[sys
].min_system_count (start
, end
)
730 : line_breaking_
[sys
].max_system_count (start
, end
);
738 Page_breaking::set_current_breakpoints (vsize start
,
741 Line_division lower_bound
,
742 Line_division upper_bound
)
744 system_count_
= system_count
;
745 current_chunks_
= chunk_list (start
, end
);
746 current_start_breakpoint_
= start
;
747 current_end_breakpoint_
= end
;
748 clear_line_details_cache ();
750 if (!lower_bound
.size ())
751 lower_bound
= system_count_bounds (current_chunks_
, true);
752 if (!upper_bound
.size ())
753 upper_bound
= system_count_bounds (current_chunks_
, false);
755 assert (lower_bound
.size () == current_chunks_
.size () - 1);
756 assert (upper_bound
.size () == current_chunks_
.size () - 1);
758 Line_division work_in_progress
;
759 current_configurations_
.clear ();
760 line_divisions_rec (system_count
,
765 /* we only consider a constant number of configurations. Otherwise,
766 this becomes slow when there are many small scores. The constant
767 5 is somewhat arbitrary. */
768 if (current_configurations_
.size () > 5)
770 vector
<pair
<Real
,vsize
> > dems_and_indices
;
772 for (vsize i
= 0; i
< current_configurations_
.size (); i
++)
774 cache_line_details (i
);
776 for (vsize j
= 0; j
< cached_line_details_
.size (); j
++)
777 dem
+= cached_line_details_
[j
].force_
* cached_line_details_
[j
].force_
778 + cached_line_details_
[j
].break_penalty_
;
780 dems_and_indices
.push_back (pair
<Real
,vsize
> (dem
, i
));
782 vector_sort (dems_and_indices
, less
<pair
<Real
,vsize
> > ());
784 vector
<Line_division
> best_5_configurations
;
785 for (vsize i
= 0; i
< 5; i
++)
786 best_5_configurations
.push_back (current_configurations_
[dems_and_indices
[i
].second
]);
788 clear_line_details_cache ();
789 current_configurations_
= best_5_configurations
;
794 Page_breaking::set_to_ideal_line_configuration (vsize start
, vsize end
)
796 current_chunks_
= chunk_list (start
, end
);
797 current_start_breakpoint_
= start
;
798 current_end_breakpoint_
= end
;
799 clear_line_details_cache ();
803 for (vsize i
= 0; i
+1 < current_chunks_
.size (); i
++)
805 vsize sys
= next_system (current_chunks_
[i
]);
807 if (current_chunks_
[i
+1].forced_line_count_
)
808 div
.push_back (current_chunks_
[i
+1].forced_line_count_
);
809 else if (system_specs_
[sys
].pscore_
)
811 line_breaker_args (sys
, current_chunks_
[i
], current_chunks_
[i
+1], &start
, &end
);
812 div
.push_back (line_breaking_
[sys
].best_solution (start
, end
).size ());
817 system_count_
+= div
.back ();
819 current_configurations_
.clear ();
820 current_configurations_
.push_back (div
);
824 Page_breaking::current_configuration_count () const
826 return current_configurations_
.size ();
830 Page_breaking::cache_line_details (vsize configuration_index
)
832 if (cached_configuration_index_
!= configuration_index
)
834 cached_configuration_index_
= configuration_index
;
836 Line_division
&div
= current_configurations_
[configuration_index
];
837 uncompressed_line_details_
.clear ();
838 for (vsize i
= 0; i
+ 1 < current_chunks_
.size (); i
++)
840 vsize sys
= next_system (current_chunks_
[i
]);
841 if (system_specs_
[sys
].pscore_
)
845 line_breaker_args (sys
, current_chunks_
[i
], current_chunks_
[i
+1], &start
, &end
);
847 vector
<Line_details
> details
= line_breaking_
[sys
].line_details (start
, end
, div
[i
]);
848 uncompressed_line_details_
.insert (uncompressed_line_details_
.end (), details
.begin (), details
.end ());
852 assert (div
[i
] == 0);
853 uncompressed_line_details_
.push_back (system_specs_
[sys
].prob_
854 ? Line_details (system_specs_
[sys
].prob_
, book_
->paper_
)
858 cached_line_details_
= compress_lines (uncompressed_line_details_
);
859 compute_line_heights ();
864 Page_breaking::clear_line_details_cache ()
866 cached_configuration_index_
= VPOS
;
867 cached_line_details_
.clear ();
868 uncompressed_line_details_
.clear ();
872 Page_breaking::line_divisions_rec (vsize system_count
,
873 Line_division
const &min_sys
,
874 Line_division
const &max_sys
,
875 Line_division
*cur_division
)
877 vsize my_index
= cur_division
->size ();
881 for (vsize i
= my_index
+ 1; i
< min_sys
.size (); i
++)
883 others_min
+= min_sys
[i
];
884 others_max
+= max_sys
[i
];
886 others_max
= min (others_max
, (int) system_count
);
887 int real_min
= max ((int) min_sys
[my_index
], (int) system_count
- others_max
);
888 int real_max
= min ((int) max_sys
[my_index
], (int) system_count
- others_min
);
890 if (real_min
> real_max
|| real_min
< 0)
892 /* this should never happen within a recursive call. If it happens
893 at all, it means that we were called with an unsolvable problem
894 and we should return an empty result */
895 assert (my_index
== 0);
899 for (int i
= real_min
; i
<= real_max
; i
++)
901 cur_division
->push_back (i
);
902 if (my_index
== min_sys
.size () - 1)
903 current_configurations_
.push_back (*cur_division
);
905 line_divisions_rec (system_count
- i
, min_sys
, max_sys
, cur_division
);
906 cur_division
->pop_back ();
911 Page_breaking::compute_line_heights ()
913 Real prev_hanging
= 0;
914 Real prev_hanging_begin
= 0;
915 Real prev_hanging_rest
= 0;
917 // refpoint_hanging is the y coordinate of the origin of this system.
918 // It may not be the same as refpoint_extent[UP], which is the
919 // refpoint of the first spaceable staff in this system.
920 Real prev_refpoint_hanging
= 0;
921 for (vsize i
= 0; i
< cached_line_details_
.size (); i
++)
923 Line_details
& cur
= cached_line_details_
[i
];
924 Line_shape shape
= cur
.shape_
;
925 Real a
= shape
.begin_
[UP
];
926 Real b
= shape
.rest_
[UP
];
927 bool title
= cur
.title_
;
928 Real refpoint_hanging
= max (prev_hanging_begin
+ a
, prev_hanging_rest
+ b
);
933 Line_details
const& prev
= cached_line_details_
[i
-1];
934 if (!cur
.tight_spacing_
)
936 ? prev
.title_padding_
938 Real min_dist
= title
939 ? prev
.title_min_distance_
940 : prev
.min_distance_
;
941 refpoint_hanging
= max (refpoint_hanging
+ padding
,
942 prev_refpoint_hanging
- prev
.refpoint_extent_
[DOWN
]
943 + cur
.refpoint_extent_
[UP
] + min_dist
);
946 Real hanging_begin
= refpoint_hanging
- shape
.begin_
[DOWN
];
947 Real hanging_rest
= refpoint_hanging
- shape
.rest_
[DOWN
];
948 Real hanging
= max (hanging_begin
, hanging_rest
);
949 cur
.tallness_
= hanging
- prev_hanging
;
950 prev_hanging
= hanging
;
951 prev_hanging_begin
= hanging_begin
;
952 prev_hanging_rest
= hanging_rest
;
953 prev_refpoint_hanging
= refpoint_hanging
;
958 Page_breaking::min_page_count (vsize configuration
, vsize first_page_num
)
961 vsize page_starter
= 0;
962 Real cur_rod_height
= 0;
963 Real cur_spring_height
= 0;
964 Real cur_page_height
= page_height (first_page_num
, false);
967 cache_line_details (configuration
);
969 if (cached_line_details_
.size ())
970 cur_page_height
-= min_whitespace_at_top_of_page (cached_line_details_
[0]);
972 for (vsize i
= 0; i
< cached_line_details_
.size (); i
++)
974 Line_details
const &cur
= cached_line_details_
[i
];
975 Line_details
const *const prev
= (i
> 0) ? &cached_line_details_
[i
-1] : 0;
977 if (cur_rod_height
> 0)
978 ext_len
= cur
.tallness_
;
980 ext_len
= cur
.full_height();
982 Real spring_len
= (i
> 0) ? prev
->spring_length (cur
) : 0;
983 Real next_rod_height
= cur_rod_height
+ ext_len
;
984 Real next_spring_height
= cur_spring_height
+ spring_len
;
985 Real next_height
= next_rod_height
+ (ragged () ? next_spring_height
: 0)
986 + min_whitespace_at_bottom_of_page (cur
);
987 int next_line_count
= line_count
+ cur
.compressed_nontitle_lines_count_
;
989 if ((!too_few_lines (line_count
) && (next_height
> cur_page_height
&& cur_rod_height
> 0))
990 || too_many_lines (next_line_count
)
991 || (prev
&& prev
->page_permission_
== ly_symbol2scm ("force")))
993 line_count
= cur
.compressed_nontitle_lines_count_
;
994 cur_rod_height
= cur
.full_height();
995 cur_spring_height
= 0;
998 cur_page_height
= page_height (first_page_num
+ ret
, false);
999 cur_page_height
-= min_whitespace_at_top_of_page (cur
);
1005 cur_rod_height
= next_rod_height
;
1006 cur_spring_height
= next_spring_height
;
1007 line_count
= next_line_count
;
1011 /* there are two potential problems with the last page (because we didn't know
1012 it was the last page until after we managed to fit all the systems to it):
1013 - we are ragged-last but the last page has a compressed spring
1014 - the value returned by page_height (num, true) is smaller than the
1015 value returned by page_height (num, false) and it causes the page not to
1018 In either case, we just need to add one more page. This is because the last
1019 line will always fit on the extra page and by adding one more page to the
1020 end, the previous page is no longer the last page, so our previous
1021 calculations that treated it as a non-last page were ok.
1026 cur_page_height
= page_height (first_page_num
+ ret
- 1, true);
1027 cur_page_height
-= min_whitespace_at_top_of_page (cached_line_details_
[page_starter
]);
1028 cur_page_height
-= min_whitespace_at_bottom_of_page (cached_line_details_
.back ());
1030 Real cur_height
= cur_rod_height
+ ((ragged_last () || ragged ()) ? cur_spring_height
: 0);
1031 if (!too_few_lines (line_count
- cached_line_details_
.back ().compressed_nontitle_lines_count_
)
1032 && cur_height
> cur_page_height
1033 /* don't increase the page count if the last page had only one system */
1034 && cur_rod_height
> cached_line_details_
.back ().full_height ())
1036 assert (ret
<= cached_line_details_
.size ());
1042 // If systems_per_page_ is positive, we don't really try to space on N pages;
1043 // we just put the requested number of systems on each page and penalize
1044 // if the result doesn't have N pages.
1046 Page_breaking::space_systems_on_n_pages (vsize configuration
, vsize n
, vsize first_page_num
)
1048 Page_spacing_result ret
;
1050 if (systems_per_page_
> 0)
1052 Page_spacing_result ret
= space_systems_with_fixed_number_per_page (configuration
, first_page_num
);
1053 ret
.demerits_
+= (ret
.force_
.size () == n
) ? 0 : BAD_SPACING_PENALTY
;
1057 cache_line_details (configuration
);
1058 bool valid_n
= (n
>= min_page_count (configuration
, first_page_num
)
1059 && n
<= cached_line_details_
.size ());
1062 programming_error ("number of pages is out of bounds");
1064 if (n
== 1 && valid_n
)
1065 ret
= space_systems_on_1_page (cached_line_details_
,
1066 page_height (first_page_num
, is_last ()),
1067 ragged () || (is_last () && ragged_last ()));
1068 else if (n
== 2 && valid_n
)
1069 ret
= space_systems_on_2_pages (configuration
, first_page_num
);
1072 Page_spacer
ps (cached_line_details_
, first_page_num
, this);
1076 return finalize_spacing_result (configuration
, ret
);
1080 Page_breaking::blank_page_penalty () const
1085 penalty_sym
= ly_symbol2scm ("blank-last-page-force");
1086 else if (ends_score ())
1087 penalty_sym
= ly_symbol2scm ("blank-after-score-page-force");
1089 penalty_sym
= ly_symbol2scm ("blank-page-force");
1091 Break_position
const &pos
= breaks_
[current_end_breakpoint_
];
1092 if (Paper_score
*ps
= system_specs_
[pos
.system_spec_index_
].pscore_
)
1093 return robust_scm2double (ps
->layout ()->lookup_variable (penalty_sym
), 0.0);
1095 return robust_scm2double (book_
->paper_
->lookup_variable (penalty_sym
), 0.0);
1098 // If systems_per_page_ is positive, we don't really try to space on N
1099 // or N+1 pages; see the comment to space_systems_on_n_pages.
1101 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration
, vsize n
, vsize first_page_num
,
1102 Real penalty_for_fewer_pages
)
1104 Page_spacing_result n_res
;
1105 Page_spacing_result m_res
;
1107 if (systems_per_page_
> 0)
1109 Page_spacing_result ret
= space_systems_with_fixed_number_per_page (configuration
, first_page_num
);
1110 ret
.demerits_
+= (ret
.force_
.size () == n
|| ret
.force_
.size () == (n
-1)) ? 0 : BAD_SPACING_PENALTY
;
1114 cache_line_details (configuration
);
1115 vsize min_p_count
= min_page_count (configuration
, first_page_num
);
1116 bool valid_n
= n
>= min_p_count
|| n
<= cached_line_details_
.size ();
1119 programming_error ("both page counts are out of bounds");
1121 if (n
== 1 && valid_n
)
1123 bool rag
= ragged () || (is_last () && ragged_last ());
1124 Real height
= page_height (first_page_num
, is_last ());
1126 if (1 >= min_p_count
)
1127 n_res
= space_systems_on_1_page (cached_line_details_
, height
, rag
);
1128 if (1 < cached_line_details_
.size ())
1129 m_res
= space_systems_on_2_pages (configuration
, first_page_num
);
1133 Page_spacer
ps (cached_line_details_
, first_page_num
, this);
1135 if (n
>= min_p_count
|| !valid_n
)
1136 n_res
= ps
.solve (n
);
1137 if (n
< cached_line_details_
.size () || !valid_n
)
1138 m_res
= ps
.solve (n
+1);
1141 m_res
= finalize_spacing_result (configuration
, m_res
);
1142 n_res
= finalize_spacing_result (configuration
, n_res
);
1144 Real page_spacing_weight
= robust_scm2double (book_
->paper_
->c_variable ("page-spacing-weight"), 10);
1145 n_res
.demerits_
+= penalty_for_fewer_pages
* page_spacing_weight
;
1147 if (n_res
.force_
.size ())
1148 n_res
.force_
.back () += penalty_for_fewer_pages
;
1150 return (m_res
.demerits_
< n_res
.demerits_
) ? m_res
: n_res
;
1154 Page_breaking::space_systems_on_best_pages (vsize configuration
, vsize first_page_num
)
1156 if (systems_per_page_
> 0)
1157 return space_systems_with_fixed_number_per_page (configuration
, first_page_num
);
1159 cache_line_details (configuration
);
1160 Page_spacer
ps (cached_line_details_
, first_page_num
, this);
1162 return finalize_spacing_result (configuration
, ps
.solve ());
1166 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration
,
1167 vsize first_page_num
)
1169 Page_spacing_result res
;
1170 Page_spacing
space (page_height (first_page_num
, false), this);
1173 vsize page_first_line
= 0;
1175 cache_line_details (configuration
);
1176 while (line
< cached_line_details_
.size ())
1180 space
.resize (page_height (first_page_num
+ page
, false));
1182 int system_count_on_this_page
= 0;
1183 while (system_count_on_this_page
< systems_per_page_
1184 && line
< cached_line_details_
.size ())
1186 Line_details
const &cur_line
= cached_line_details_
[line
];
1187 space
.append_system (cur_line
);
1188 system_count_on_this_page
+= cur_line
.compressed_nontitle_lines_count_
;
1191 if (cur_line
.page_permission_
== ly_symbol2scm ("force"))
1195 res
.systems_per_page_
.push_back (line
- page_first_line
);
1197 res
.force_
.push_back (space
.force_
);
1198 res
.penalty_
+= cached_line_details_
[line
-1].page_penalty_
;
1199 if (system_count_on_this_page
!= systems_per_page_
)
1201 res
.penalty_
+= abs (system_count_on_this_page
- systems_per_page_
) * TERRIBLE_SPACING_PENALTY
;
1202 res
.system_count_status_
|= ((system_count_on_this_page
< systems_per_page_
))
1203 ? SYSTEM_COUNT_TOO_FEW
: SYSTEM_COUNT_TOO_MANY
;
1206 page_first_line
= line
;
1209 /* Recalculate forces for the last page because we know now that is
1210 really the last page. */
1211 space
.resize (page_height (first_page_num
+ page
, true));
1212 res
.force_
.back () = space
.force_
;
1213 return finalize_spacing_result (configuration
, res
);
1217 Page_breaking::pack_systems_on_least_pages (vsize configuration
, vsize first_page_num
)
1219 // TODO: add support for min/max-systems-per-page.
1220 Page_spacing_result res
;
1222 vsize page_first_line
= 0;
1223 Page_spacing
space (page_height (first_page_num
, false), this);
1225 cache_line_details (configuration
);
1226 for (vsize line
= 0; line
< cached_line_details_
.size (); line
++)
1228 Real prev_force
= space
.force_
;
1229 space
.append_system (cached_line_details_
[line
]);
1230 if ((line
> page_first_line
)
1231 && (isinf (space
.force_
)
1233 && (cached_line_details_
[line
-1].page_permission_
== ly_symbol2scm ("force")))))
1235 res
.systems_per_page_
.push_back (line
- page_first_line
);
1236 res
.force_
.push_back (prev_force
);
1237 res
.penalty_
+= cached_line_details_
[line
-1].page_penalty_
;
1239 space
.resize (page_height (first_page_num
+ page
, false));
1241 space
.append_system (cached_line_details_
[line
]);
1242 page_first_line
= line
;
1245 if (line
== cached_line_details_
.size () - 1)
1247 /* This is the last line */
1248 /* When the last page height was computed, we did not know yet that it
1249 * was the last one. If the systems put on it don't fit anymore, the last
1250 * system is moved to a new page */
1251 space
.resize (page_height (first_page_num
+ page
, true));
1252 if ((line
> page_first_line
) && (isinf (space
.force_
)))
1254 res
.systems_per_page_
.push_back (line
- page_first_line
);
1255 res
.force_
.push_back (prev_force
);
1256 /* the last page containing the last line */
1257 space
.resize (page_height (first_page_num
+ page
+ 1, true));
1259 space
.append_system (cached_line_details_
[line
]);
1260 res
.systems_per_page_
.push_back (1);
1261 res
.force_
.push_back (space
.force_
);
1262 res
.penalty_
+= cached_line_details_
[line
-1].page_penalty_
;
1263 res
.penalty_
+= cached_line_details_
[line
].page_penalty_
;
1267 res
.systems_per_page_
.push_back (line
+ 1 - page_first_line
);
1268 res
.force_
.push_back (space
.force_
);
1269 res
.penalty_
+= cached_line_details_
[line
].page_penalty_
;
1273 return finalize_spacing_result (configuration
, res
);
1276 /* Calculate demerits and fix res.systems_per_page_ so that
1277 it refers to the original line numbers, not the ones given by compress_lines (). */
1279 Page_breaking::finalize_spacing_result (vsize configuration
, Page_spacing_result res
)
1281 if (res
.force_
.empty ())
1284 cache_line_details (configuration
);
1285 res
.systems_per_page_
= uncompress_solution (res
.systems_per_page_
, cached_line_details_
);
1287 Real line_force
= 0;
1288 Real line_penalty
= 0;
1289 Real page_demerits
= res
.penalty_
;
1290 Real page_weighting
= robust_scm2double (book_
->paper_
->c_variable ("page-spacing-weight"), 10);
1292 for (vsize i
= 0; i
< uncompressed_line_details_
.size (); i
++)
1294 line_force
+= uncompressed_line_details_
[i
].force_
* uncompressed_line_details_
[i
].force_
;
1295 line_penalty
+= uncompressed_line_details_
[i
].break_penalty_
;
1298 for (vsize i
= 0; i
< res
.force_
.size (); i
++)
1300 Real f
= res
.force_
[i
];
1302 page_demerits
+= min(f
*f
, BAD_SPACING_PENALTY
);
1305 /* for a while we tried averaging page and line forces across pages instead
1306 of summing them, but it caused a problem: if there is a single page
1307 with a very bad page force (for example because of a forced page break),
1308 the page breaker will put in a _lot_ of pages so that the bad force
1309 becomes averaged out over many pages. */
1310 res
.demerits_
= line_force
+ line_penalty
+ page_demerits
* page_weighting
;
1315 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1316 are by far the most common cases, we have special functions for them.
1318 space_systems_on_1_page has a different calling convention than most of the
1319 space_systems functions. This is because space_systems_on_1_page is (unlike
1320 the other space_systems functions) sometimes called on subsets of a full
1323 Page_breaking::space_systems_on_1_page (vector
<Line_details
> const &lines
, Real page_height
, bool ragged
)
1325 Page_spacing
space (page_height
, this);
1326 Page_spacing_result ret
;
1329 for (vsize i
= 0; i
< lines
.size (); i
++)
1331 space
.append_system (lines
[i
]);
1332 line_count
+= lines
[i
].compressed_nontitle_lines_count_
;
1335 ret
.systems_per_page_
.push_back (lines
.size ());
1336 ret
.force_
.push_back (ragged
? min (space
.force_
, 0.0) : space
.force_
);
1337 ret
.penalty_
= line_count_penalty (line_count
) + lines
.back ().page_penalty_
+ lines
.back ().turn_penalty_
;
1338 ret
.system_count_status_
|= line_count_status (line_count
);
1340 /* don't do finalize_spacing_result () because we are only an internal function */
1345 Page_breaking::space_systems_on_2_pages (vsize configuration
, vsize first_page_num
)
1347 Real page1_height
= page_height (first_page_num
, false);
1348 Real page2_height
= page_height (first_page_num
+ 1, is_last ());
1349 bool ragged1
= ragged ();
1350 bool ragged2
= ragged () || (is_last () && ragged_last ());
1352 /* if there is a forced break, this reduces to 2 1-page problems */
1353 cache_line_details (configuration
);
1354 for (vsize i
= 0; i
+ 1 < cached_line_details_
.size (); i
++)
1355 if (cached_line_details_
[i
].page_permission_
== ly_symbol2scm ("force"))
1357 vector
<Line_details
> lines1 (cached_line_details_
.begin (), cached_line_details_
.begin () + i
+ 1);
1358 vector
<Line_details
> lines2 (cached_line_details_
.begin () + i
+ 1, cached_line_details_
.end ());
1359 Page_spacing_result p1
= space_systems_on_1_page (lines1
, page1_height
, ragged1
);
1360 Page_spacing_result p2
= space_systems_on_1_page (lines2
, page2_height
, ragged2
);
1362 p1
.systems_per_page_
.push_back (p2
.systems_per_page_
[0]);
1363 p1
.force_
.push_back (p2
.force_
[0]);
1364 p1
.penalty_
+= p2
.penalty_
- cached_line_details_
[i
].turn_penalty_
;
1365 p1
.system_count_status_
|= p2
.system_count_status_
;
1369 vector
<Real
> page1_force
;
1370 vector
<Real
> page2_force
;
1372 // page1_penalty and page2_penalty store the penalties based
1373 // on min-systems-per-page and max-systems-per-page.
1374 vector
<Real
> page1_penalty
;
1375 vector
<Real
> page2_penalty
;
1377 // page1_status and page2_status keep track of whether the min-systems-per-page
1378 // and max-systems-per-page constraints are satisfied.
1379 vector
<int> page1_status
;
1380 vector
<int> page2_status
;
1382 Page_spacing
page1 (page1_height
, this);
1383 Page_spacing
page2 (page2_height
, this);
1384 int page1_line_count
= 0;
1385 int page2_line_count
= 0;
1387 page1_force
.resize (cached_line_details_
.size () - 1, infinity_f
);
1388 page2_force
.resize (cached_line_details_
.size () - 1, infinity_f
);
1389 page1_penalty
.resize (cached_line_details_
.size () - 1, infinity_f
);
1390 page2_penalty
.resize (cached_line_details_
.size () - 1, infinity_f
);
1391 page1_status
.resize (cached_line_details_
.size () - 1, 0);
1392 page2_status
.resize (cached_line_details_
.size () - 1, 0);
1394 /* find the page 1 and page 2 forces for each page-breaking position */
1395 for (vsize i
= 0; i
< page1_force
.size (); i
++)
1397 page1
.append_system (cached_line_details_
[i
]);
1398 page2
.prepend_system (cached_line_details_
[cached_line_details_
.size () - 1 - i
]);
1399 page1_line_count
+= cached_line_details_
[i
].compressed_nontitle_lines_count_
;
1400 page2_line_count
+= cached_line_details_
[cached_line_details_
.size () - 1 - i
].compressed_nontitle_lines_count_
;
1402 page1_force
[i
] = (ragged1
&& page1
.force_
< 0 && i
> 0) ? infinity_f
: page1
.force_
;
1403 page1_penalty
[i
] = line_count_penalty (page1_line_count
);
1404 page1_status
[i
] = line_count_status (page1_line_count
);
1407 page2_force
[page2_force
.size () - 1 - i
] =
1408 (page2
.force_
< 0 && i
+ 1 < page1_force
.size ()) ? infinity_f
: 0;
1410 page2_force
[page2_force
.size () - 1 - i
] = page2
.force_
;
1411 page2_penalty
[page2_penalty
.size () - 1 - i
] = line_count_penalty (page2_line_count
);
1412 page2_status
[page2_penalty
.size () - 1 - i
] = line_count_status (page2_line_count
);
1415 /* find the position that minimises the sum of the page forces */
1416 vsize best_sys_count
= 1;
1417 Real best_demerits
= infinity_f
;
1418 for (vsize i
= 0; i
< page1_force
.size (); i
++)
1420 Real f
= page1_force
[i
] * page1_force
[i
] + page2_force
[i
] * page2_force
[i
];
1422 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1423 // constraints. That is, we penalize harshly when they don't happen
1424 // but we don't completely reject.
1426 + page1_penalty
[i
] + page2_penalty
[i
]
1427 + cached_line_details_
[i
+1].page_penalty_
1428 + cached_line_details_
.back ().page_penalty_
+ cached_line_details_
.back ().turn_penalty_
;
1429 if (dem
< best_demerits
)
1431 best_demerits
= dem
;
1432 best_sys_count
= i
+1;
1436 Page_spacing_result ret
;
1437 ret
.systems_per_page_
.push_back (best_sys_count
);
1438 ret
.systems_per_page_
.push_back (cached_line_details_
.size () - best_sys_count
);
1439 ret
.force_
.push_back (page1_force
[best_sys_count
-1]);
1440 ret
.force_
.push_back (page2_force
[best_sys_count
-1]);
1441 ret
.system_count_status_
= page1_status
[best_sys_count
-1] | page2_status
[best_sys_count
-1];
1442 ret
.penalty_
= cached_line_details_
[best_sys_count
-1].page_penalty_
1443 + cached_line_details_
.back ().page_penalty_
1444 + cached_line_details_
.back ().turn_penalty_
1445 + page1_penalty
[best_sys_count
-1] + page2_penalty
[best_sys_count
-1];
1447 /* don't do finalize_spacing_result () because we are only an internal function */
1452 Page_breaking::all_lines_stretched (vsize configuration
)
1454 cache_line_details (configuration
);
1455 for (vsize i
= 0; i
< cached_line_details_
.size (); i
++)
1456 if (cached_line_details_
[i
].force_
< 0)
1462 Page_breaking::Line_division
1463 Page_breaking::current_configuration (vsize configuration_index
) const
1465 return current_configurations_
[configuration_index
];
1469 Page_breaking::is_last () const
1471 return current_end_breakpoint_
== last_break_position ();
1475 Page_breaking::ends_score () const
1477 return breaks_
[current_end_breakpoint_
].score_ender_
;
1481 Page_breaking::last_break_position () const
1483 return breaks_
.size () - 1;
1486 // This gives the minimum distance between the top of the
1487 // printable area (ie. the bottom of the top-margin) and
1488 // the extent box of the topmost system.
1490 Page_breaking::min_whitespace_at_top_of_page (Line_details
const &line
) const
1492 SCM first_system_spacing
= book_
->paper_
->c_variable ("top-system-spacing");
1494 first_system_spacing
= book_
->paper_
->c_variable ("top-markup-spacing");
1496 Real min_distance
= -infinity_f
;
1499 Page_layout_problem::read_spacing_spec (first_system_spacing
,
1501 ly_symbol2scm ("minimum-distance"));
1502 Page_layout_problem::read_spacing_spec (first_system_spacing
,
1504 ly_symbol2scm ("padding"));
1506 // FIXME: take into account the height of the header
1507 Real translate
= max (line
.shape_
.begin_
[UP
], line
.shape_
.rest_
[UP
]);
1508 return max (0.0, max (padding
, min_distance
- translate
));
1512 Page_breaking::min_whitespace_at_bottom_of_page (Line_details
const &line
) const
1514 SCM last_system_spacing
= book_
->paper_
->c_variable ("last-bottom-spacing");
1515 Real min_distance
= -infinity_f
;
1518 Page_layout_problem::read_spacing_spec (last_system_spacing
,
1520 ly_symbol2scm ("minimum-distance"));
1521 Page_layout_problem::read_spacing_spec (last_system_spacing
,
1523 ly_symbol2scm ("padding"));
1525 // FIXME: take into account the height of the footer
1526 Real translate
= min (line
.shape_
.begin_
[DOWN
], line
.shape_
.rest_
[DOWN
]);
1527 return max (0.0, max (padding
, min_distance
+ translate
));
1531 Page_breaking::orphan_penalty () const
1533 return orphan_penalty_
;