2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2010 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 compressed.shape_ = old.shape_.piggyback (orig[i].shape_, padding);
113 compressed.first_refpoint_offset_ += compressed.shape_.rest_[UP] - old.shape_.rest_[UP];
114 compressed.space_ += old.space_;
115 compressed.inverse_hooke_ += old.inverse_hooke_;
117 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
118 compressed.compressed_nontitle_lines_count_ =
119 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
121 // compressed.title_ is true if and only if the first of its
122 // compressed lines was a title.
123 compressed.title_ = old.title_;
124 ret.back () = compressed;
128 ret.push_back (orig[i]);
129 ret.back ().force_ = 0;
135 /* translate the number of systems-per-page into something meaningful for
136 the uncompressed lines.
139 uncompress_solution (vector<vsize> const &systems_per_page,
140 vector<Line_details> const &compressed)
145 for (vsize i = 0; i < systems_per_page.size (); i++)
147 int compressed_count = 0;
148 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
149 compressed_count += compressed[j].compressed_lines_count_ - 1;
151 ret.push_back (systems_per_page[i] + compressed_count);
152 start_sys += systems_per_page[i];
157 /* for Page_breaking, the start index (when we are dealing with the stuff
158 between a pair of breakpoints) refers to the break_ index of the end of
159 the previous page. So the system index of the start of the current page
160 could either be the same as the end of the previous page or one more than
163 /* Turn a break index into the sys index that starts the next page */
165 Page_breaking::next_system (Break_position const &break_pos) const
167 vsize sys = break_pos.system_spec_index_;
169 if (sys == VPOS) /* beginning of the book */
171 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
172 return sys; /* the score overflows the previous page */
173 return sys + 1; /* this page starts with a new System_spec */
176 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break, Prob_break_predicate prob_break)
180 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
181 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
182 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
183 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
184 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
185 orphan_penalty_ = robust_scm2int (pb->paper_->c_variable ("orphan-penalty"), 100000);
187 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
189 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
190 min_systems_per_page_ = max_systems_per_page_ = 0;
192 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
194 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
195 min_systems_per_page_ = max_systems_per_page_ = 0;
198 create_system_list ();
199 find_chunks_and_breaks (is_break, prob_break);
202 Page_breaking::~Page_breaking ()
207 Page_breaking::ragged () const
213 Page_breaking::ragged_last () const
219 Page_breaking::systems_per_page () const
221 return systems_per_page_;
225 Page_breaking::max_systems_per_page () const
227 return max_systems_per_page_;
231 Page_breaking::min_systems_per_page () const
233 return min_systems_per_page_;
237 Page_breaking::system_count () const
239 return system_count_;
243 Page_breaking::too_many_lines (int line_count) const
245 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
249 Page_breaking::too_few_lines (int line_count) const
251 return line_count < min_systems_per_page ();
255 Page_breaking::line_count_penalty (int line_count) const
257 if (too_many_lines (line_count))
258 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
259 if (too_few_lines (line_count))
260 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
266 Page_breaking::line_count_status (int line_count) const
268 if (too_many_lines (line_count))
269 return SYSTEM_COUNT_TOO_MANY;
270 if (too_few_lines (line_count))
271 return SYSTEM_COUNT_TOO_FEW;
273 return SYSTEM_COUNT_OK;
276 /* translate indices into breaks_ into start-end parameters for the line breaker */
278 Page_breaking::line_breaker_args (vsize sys,
279 Break_position const &start,
280 Break_position const &end,
281 vsize *line_breaker_start,
282 vsize *line_breaker_end)
284 assert (system_specs_[sys].pscore_);
285 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
287 if (start.system_spec_index_ == sys)
288 *line_breaker_start = start.score_break_;
290 *line_breaker_start = 0;
292 if (end.system_spec_index_ == sys)
293 *line_breaker_end = end.score_break_;
295 *line_breaker_end = VPOS;
299 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
300 Line_division const &div)
302 vector<Break_position> chunks = chunk_list (start_break, end_break);
303 bool ignore_div = false;
304 if (chunks.size () != div.size () + 1)
306 programming_error ("did not find a valid page breaking configuration");
310 for (vsize i = 0; i + 1 < chunks.size (); i++)
312 vsize sys = next_system (chunks[i]);
313 if (system_specs_[sys].pscore_)
317 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
319 vector<Column_x_positions> pos = ignore_div
320 ? line_breaking_[sys].best_solution (start, end)
321 : line_breaking_[sys].solve (start, end, div[i]);
322 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
328 Page_breaking::systems ()
331 for (vsize sys = 0; sys < system_specs_.size (); sys++)
333 if (system_specs_[sys].pscore_)
335 system_specs_[sys].pscore_->root_system ()
336 ->do_break_substitution_and_fixup_refpoints ();
337 SCM lines = system_specs_[sys].pscore_->root_system ()
338 ->get_broken_system_grobs ();
339 ret = scm_cons (lines, ret);
343 Prob *pb = system_specs_[sys].prob_;
344 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
348 return scm_append (scm_reverse (ret));
352 Page_breaking::make_page (int page_num, bool last) const
354 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
355 SCM mod = scm_c_resolve_module ("scm page");
356 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
358 make_page_scm = scm_variable_ref (make_page_scm);
360 return scm_apply_0 (make_page_scm,
361 scm_list_n (book_->self_scm (),
362 ly_symbol2scm ("page-number"), scm_from_int (page_num),
363 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
364 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
369 Page_breaking::page_height (int page_num, bool last) const
371 SCM mod = scm_c_resolve_module ("scm page");
372 SCM page = make_page (page_num, last);
373 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
374 calc_height = scm_variable_ref (calc_height);
376 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
377 return scm_to_double (height);
381 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
383 Break_position const &pos = breaks_[breakpoint];
385 if (pos.system_spec_index_ == VPOS)
387 if (system_specs_[pos.system_spec_index_].pscore_)
388 return pos.col_->get_property (str);
389 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
393 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
395 SCM dummy_page = make_page (page_num, last);
396 Page_layout_problem layout (book_, dummy_page, systems);
397 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
401 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
403 // Create a stencil for each system.
404 SCM paper_systems = SCM_EOL;
405 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
407 SCM paper_system = scm_car (s);
408 if (Grob *g = unsmob_grob (scm_car (s)))
410 System *sys = dynamic_cast<System*> (g);
411 paper_system = sys->get_paper_system ();
414 paper_systems = scm_cons (paper_system, paper_systems);
417 // Create the page and draw it.
418 SCM page = make_page (page_num, last);
419 SCM page_module = scm_c_resolve_module ("scm page");
420 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
421 page_stencil = scm_variable_ref (page_stencil);
423 Prob *p = unsmob_prob (page);
424 p->set_property ("lines", paper_systems);
425 p->set_property ("configuration", configuration);
426 scm_apply_1 (page_stencil, page, SCM_EOL);
432 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
434 int first_page_number
435 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
437 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
438 if (label_page_table == SCM_UNDEFINED)
439 label_page_table = SCM_EOL;
441 // Build a list of (systems . configuration) pairs. Note that we lay out
442 // the staves and find the configurations before drawing anything. Some
443 // grobs (like tuplet brackets) look at their neighbours while drawing
444 // themselves. If this happens before the neighbouring staves have
445 // been laid out, bad side-effects could happen (in particular,
446 // Align_interface::align_to_ideal_distances might be called).
447 SCM systems_and_configs = SCM_EOL;
449 for (vsize i = 0; i < lines_per_page.size (); i++)
451 int page_num = i + first_page_number;
452 bool bookpart_last_page = (i == lines_per_page.size () - 1);
453 bool rag = ragged () || (bookpart_last_page && ragged_last ());
454 SCM line_count = scm_from_int (lines_per_page[i]);
455 SCM lines = scm_list_head (systems, line_count);
456 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
458 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
459 systems = scm_list_tail (systems, line_count);
462 // Now it's safe to make the pages.
463 int page_num = first_page_number + lines_per_page.size () - 1;
464 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
466 SCM lines = scm_caar (s);
467 SCM config = scm_cdar (s);
468 bool bookpart_last_page = (s == systems_and_configs);
469 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
472 SCM page_num_scm = scm_from_int (page_num);
473 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
475 SCM labels = SCM_EOL;
476 if (Grob * line = unsmob_grob (scm_car (l)))
478 System *system = dynamic_cast<System*> (line);
479 labels = system->get_property ("labels");
481 else if (Prob *prob = unsmob_prob (scm_car (l)))
482 labels = prob->get_property ("labels");
484 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
485 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
489 ret = scm_cons (page, ret);
492 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
496 /* The page-turn-page-breaker needs to have a line-breaker between any two
497 columns with non-NULL page-turn-permission.
499 The optimal-breaker needs to have a line-breaker between any two columns
500 with page-break-permission = 'force.
502 By using a grob predicate, we can accommodate both of these uses.
505 Page_breaking::create_system_list ()
507 SCM specs = book_->get_system_specs ();
508 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
510 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
512 system_specs_.push_back (System_spec (ps));
516 Prob *pb = unsmob_prob (scm_car (s));
520 system_specs_.push_back (System_spec (pb));
526 Page_breaking::find_chunks_and_breaks (Break_predicate is_break, Prob_break_predicate prob_is_break)
528 SCM force_sym = ly_symbol2scm ("force");
530 chunks_.push_back (Break_position ());
531 breaks_.push_back (Break_position ());
533 for (vsize i = 0; i < system_specs_.size (); i++)
535 if (system_specs_[i].pscore_)
537 vector<Grob*> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
538 vector<Grob*> forced_line_break_cols;
540 SCM system_count = system_specs_[i].pscore_->layout ()->c_variable ("system-count");
541 if (scm_is_number (system_count))
543 // With system-count given, the line configuration for
544 // this score is fixed. We need to ensure that chunk
545 // boundaries only occur at line breaks.
546 Constrained_breaking breaking (system_specs_[i].pscore_);
547 vector<Line_details> details = breaking.line_details (0, VPOS, scm_to_int (system_count));
549 for (vsize j = 0; j < details.size (); j++)
550 forced_line_break_cols.push_back (details[j].last_column_);
553 int last_forced_line_break_idx = 0;
554 vsize forced_line_break_idx = 0;
555 vector<vsize> line_breaker_columns;
556 line_breaker_columns.push_back (0);
558 for (vsize j = 1; j < cols.size (); j++)
560 if (forced_line_break_cols.size ())
562 if (forced_line_break_idx >= forced_line_break_cols.size ()
563 || forced_line_break_cols[forced_line_break_idx] != cols[j])
566 forced_line_break_idx++;
569 bool last = (j == cols.size () - 1);
570 bool break_point = is_break && is_break (cols[j]);
571 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
572 Break_position cur_pos = Break_position (i,
573 line_breaker_columns.size (),
577 // NOTE: even in the breaks_ list, forced_line_count_
578 // refers to the number of lines between a
579 // Break_position and the start of that /chunk/. This
580 // is needed for system_count_bounds to work correctly,
581 // since it mixes Break_positions from breaks_ and
583 if (scm_is_number (system_count))
584 cur_pos.forced_line_count_ = forced_line_break_idx - last_forced_line_break_idx;
586 if (break_point || (i == system_specs_.size () - 1 && last))
587 breaks_.push_back (cur_pos);
588 if (chunk_end || last)
590 chunks_.push_back (cur_pos);
591 last_forced_line_break_idx = forced_line_break_idx;
594 if ((break_point || chunk_end) && !last)
595 line_breaker_columns.push_back (j);
597 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
601 bool break_point = prob_is_break && prob_is_break (system_specs_[i].prob_);
602 if (break_point || i == system_specs_.size () - 1)
603 breaks_.push_back (Break_position (i));
605 chunks_.push_back (Break_position (i));
607 /* FIXME: shouldn't we push a Null_breaker or similar dummy
609 line_breaking_.push_back (Constrained_breaking (NULL));
614 vector<Break_position>
615 Page_breaking::chunk_list (vsize start_index, vsize end_index)
617 Break_position start = breaks_[start_index];
618 Break_position end = breaks_[end_index];
621 for (; i < chunks_.size () && chunks_[i] <= start; i++)
624 vector<Break_position> ret;
625 ret.push_back (start);
626 for (; i < chunks_.size () && chunks_[i] < end; i++)
627 ret.push_back (chunks_[i]);
633 Page_breaking::min_system_count (vsize start, vsize end)
635 vector<Break_position> chunks = chunk_list (start, end);
636 Line_division div = system_count_bounds (chunks, true);
639 for (vsize i = 0; i < div.size (); i++)
645 Page_breaking::max_system_count (vsize start, vsize end)
647 vector<Break_position> chunks = chunk_list (start, end);
648 Line_division div = system_count_bounds (chunks, false);
651 for (vsize i = 0; i < div.size (); i++)
656 Page_breaking::Line_division
657 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
660 assert (chunks.size () >= 2);
663 ret.resize (chunks.size () - 1, 1);
665 for (vsize i = 0; i + 1 < chunks.size (); i++)
667 vsize sys = next_system (chunks[i]);
669 if (chunks[i+1].forced_line_count_)
670 ret[i] = chunks[i+1].forced_line_count_;
671 else if (system_specs_[sys].pscore_)
675 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
677 ? line_breaking_[sys].min_system_count (start, end)
678 : line_breaking_[sys].max_system_count (start, end);
686 Page_breaking::set_current_breakpoints (vsize start,
689 Line_division lower_bound,
690 Line_division upper_bound)
692 system_count_ = system_count;
693 current_chunks_ = chunk_list (start, end);
694 current_start_breakpoint_ = start;
695 current_end_breakpoint_ = end;
696 clear_line_details_cache ();
698 if (!lower_bound.size ())
699 lower_bound = system_count_bounds (current_chunks_, true);
700 if (!upper_bound.size ())
701 upper_bound = system_count_bounds (current_chunks_, false);
703 assert (lower_bound.size () == current_chunks_.size () - 1);
704 assert (upper_bound.size () == current_chunks_.size () - 1);
706 Line_division work_in_progress;
707 current_configurations_.clear ();
708 line_divisions_rec (system_count,
713 /* we only consider a constant number of configurations. Otherwise,
714 this becomes slow when there are many small scores. The constant
715 5 is somewhat arbitrary. */
716 if (current_configurations_.size () > 5)
718 vector<pair<Real,vsize> > dems_and_indices;
720 for (vsize i = 0; i < current_configurations_.size (); i++)
722 cache_line_details (i);
724 for (vsize j = 0; j < cached_line_details_.size (); j++)
725 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
726 + cached_line_details_[j].break_penalty_;
728 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
730 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
732 vector<Line_division> best_5_configurations;
733 for (vsize i = 0; i < 5; i++)
734 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
736 clear_line_details_cache ();
737 current_configurations_ = best_5_configurations;
742 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
744 current_chunks_ = chunk_list (start, end);
745 current_start_breakpoint_ = start;
746 current_end_breakpoint_ = end;
747 clear_line_details_cache ();
751 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
753 vsize sys = next_system (current_chunks_[i]);
755 if (current_chunks_[i+1].forced_line_count_)
756 div.push_back (current_chunks_[i+1].forced_line_count_);
757 else if (system_specs_[sys].pscore_)
759 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
760 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
765 system_count_ += div.back ();
767 current_configurations_.clear ();
768 current_configurations_.push_back (div);
772 Page_breaking::current_configuration_count () const
774 return current_configurations_.size ();
778 Page_breaking::cache_line_details (vsize configuration_index)
780 if (cached_configuration_index_ != configuration_index)
782 cached_configuration_index_ = configuration_index;
784 Line_division &div = current_configurations_[configuration_index];
785 uncompressed_line_details_.clear ();
786 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
788 vsize sys = next_system (current_chunks_[i]);
789 if (system_specs_[sys].pscore_)
793 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
795 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
796 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
800 assert (div[i] == 1);
801 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_, book_->paper_));
804 cached_line_details_ = compress_lines (uncompressed_line_details_);
805 compute_line_heights ();
810 Page_breaking::clear_line_details_cache ()
812 cached_configuration_index_ = VPOS;
813 cached_line_details_.clear ();
814 uncompressed_line_details_.clear ();
818 Page_breaking::line_divisions_rec (vsize system_count,
819 Line_division const &min_sys,
820 Line_division const &max_sys,
821 Line_division *cur_division)
823 vsize my_index = cur_division->size ();
824 vsize others_min = 0;
825 vsize others_max = 0;
827 for (vsize i = my_index + 1; i < min_sys.size (); i++)
829 others_min += min_sys[i];
830 others_max += max_sys[i];
832 others_max = min (others_max, system_count);
833 vsize real_min = max (min_sys[my_index], system_count - others_max);
834 vsize real_max = min (max_sys[my_index], system_count - others_min);
836 if (real_min > real_max || real_min <= 0)
838 /* this should never happen within a recursive call. If it happens
839 at all, it means that we were called with an unsolvable problem
840 and we should return an empty result */
841 assert (my_index == 0);
845 for (vsize i = real_min; i <= real_max; i++)
847 cur_division->push_back (i);
848 if (my_index == min_sys.size () - 1)
849 current_configurations_.push_back (*cur_division);
851 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
852 cur_division->pop_back ();
857 Page_breaking::compute_line_heights ()
859 Real prev_hanging = 0;
860 Real prev_hanging_begin = 0;
861 Real prev_hanging_rest = 0;
862 Real prev_refpoint_hanging = 0;
863 for (vsize i = 0; i < cached_line_details_.size (); i++)
865 Line_shape shape = cached_line_details_[i].shape_;
866 Real a = shape.begin_[UP];
867 Real b = shape.rest_[UP];
868 bool title = cached_line_details_[i].title_;
869 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
874 if (!cached_line_details_[i].tight_spacing_)
876 ? cached_line_details_[i-1].title_padding_
877 : cached_line_details_[i-1].padding_;
878 Real min_dist = title
879 ? cached_line_details_[i-1].title_min_distance_
880 : cached_line_details_[i-1].min_distance_;
881 refpoint_hanging = max (refpoint_hanging + padding,
882 prev_refpoint_hanging + min_dist
883 + cached_line_details_[i].first_refpoint_offset_);
886 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
887 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
888 Real hanging = max (hanging_begin, hanging_rest);
889 cached_line_details_[i].tallness_ = hanging - prev_hanging;
890 prev_hanging = hanging;
891 prev_hanging_begin = hanging_begin;
892 prev_hanging_rest = hanging_rest;
893 prev_refpoint_hanging = refpoint_hanging;
898 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
901 vsize page_starter = 0;
902 Real cur_rod_height = 0;
903 Real cur_spring_height = 0;
904 Real cur_page_height = page_height (first_page_num, false);
907 cache_line_details (configuration);
909 if (cached_line_details_.size ())
910 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
912 for (vsize i = 0; i < cached_line_details_.size (); i++)
915 if (cur_rod_height > 0)
916 ext_len = cached_line_details_[i].tallness_;
918 ext_len = cached_line_details_[i].full_height();
920 Real next_rod_height = cur_rod_height + ext_len;
921 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
922 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
923 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
924 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
926 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
927 || too_many_lines (next_line_count)
929 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
931 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
932 cur_rod_height = cached_line_details_[i].full_height();
933 cur_spring_height = cached_line_details_[i].space_;
936 cur_page_height = page_height (first_page_num + ret, false);
937 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
943 cur_rod_height = next_rod_height;
944 cur_spring_height = next_spring_height;
945 line_count = next_line_count;
949 /* there are two potential problems with the last page (because we didn't know
950 it was the last page until after we managed to fit all the systems to it):
951 - we are ragged-last but the last page has a compressed spring
952 - the value returned by page_height (num, true) is smaller than the
953 value returned by page_height (num, false) and it causes the page not to
956 In either case, we just need to add one more page. This is because the last
957 line will always fit on the extra page and by adding one more page to the
958 end, the previous page is no longer the last page, so our previous
959 calculations that treated it as a non-last page were ok.
962 cur_page_height = page_height (first_page_num + ret - 1, true);
963 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
964 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
966 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
967 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
968 && cur_height > cur_page_height
969 /* don't increase the page count if the last page had only one system */
970 && cur_rod_height > cached_line_details_.back ().full_height ())
973 assert (ret <= cached_line_details_.size ());
977 // If systems_per_page_ is positive, we don't really try to space on N pages;
978 // we just put the requested number of systems on each page and penalize
979 // if the result doesn't have N pages.
981 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
983 Page_spacing_result ret;
985 if (systems_per_page_ > 0)
987 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
988 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
992 cache_line_details (configuration);
993 bool valid_n = (n >= min_page_count (configuration, first_page_num)
994 && n <= cached_line_details_.size ());
997 programming_error ("number of pages is out of bounds");
999 if (n == 1 && valid_n)
1000 ret = space_systems_on_1_page (cached_line_details_,
1001 page_height (first_page_num, is_last ()),
1002 ragged () || (is_last () && ragged_last ()));
1003 else if (n == 2 && valid_n)
1004 ret = space_systems_on_2_pages (configuration, first_page_num);
1007 Page_spacer ps (cached_line_details_, first_page_num, this);
1011 return finalize_spacing_result (configuration, ret);
1015 Page_breaking::blank_page_penalty () const
1020 penalty_sym = ly_symbol2scm ("blank-last-page-force");
1021 else if (ends_score ())
1022 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
1024 penalty_sym = ly_symbol2scm ("blank-page-force");
1026 Break_position const &pos = breaks_[current_end_breakpoint_];
1027 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
1028 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
1030 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
1033 // If systems_per_page_ is positive, we don't really try to space on N
1034 // or N+1 pages; see the comment to space_systems_on_n_pages.
1036 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num,
1037 Real penalty_for_fewer_pages)
1039 Page_spacing_result n_res;
1040 Page_spacing_result m_res;
1042 if (systems_per_page_ > 0)
1044 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
1045 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
1049 cache_line_details (configuration);
1050 vsize min_p_count = min_page_count (configuration, first_page_num);
1051 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
1054 programming_error ("both page counts are out of bounds");
1056 if (n == 1 && valid_n)
1058 bool rag = ragged () || (is_last () && ragged_last ());
1059 Real height = page_height (first_page_num, is_last ());
1061 if (1 >= min_p_count)
1062 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
1063 if (1 < cached_line_details_.size ())
1064 m_res = space_systems_on_2_pages (configuration, first_page_num);
1068 Page_spacer ps (cached_line_details_, first_page_num, this);
1070 if (n >= min_p_count || !valid_n)
1071 n_res = ps.solve (n);
1072 if (n < cached_line_details_.size () || !valid_n)
1073 m_res = ps.solve (n+1);
1076 m_res = finalize_spacing_result (configuration, m_res);
1077 n_res = finalize_spacing_result (configuration, n_res);
1079 Real page_spacing_weight = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1080 n_res.demerits_ += penalty_for_fewer_pages * page_spacing_weight;
1082 if (n_res.force_.size ())
1083 n_res.force_.back () += penalty_for_fewer_pages;
1085 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
1089 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
1091 cache_line_details (configuration);
1092 Page_spacer ps (cached_line_details_, first_page_num, this);
1094 return finalize_spacing_result (configuration, ps.solve ());
1098 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1099 vsize first_page_num)
1101 Page_spacing_result res;
1102 Page_spacing space (page_height (first_page_num, false), this);
1105 vsize page_first_line = 0;
1107 cache_line_details (configuration);
1108 while (line < cached_line_details_.size ())
1112 space.resize (page_height (first_page_num + page, false));
1114 int system_count_on_this_page = 0;
1115 while (system_count_on_this_page < systems_per_page_
1116 && line < cached_line_details_.size ())
1118 Line_details const &cur_line = cached_line_details_[line];
1119 space.append_system (cur_line);
1120 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1123 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1127 res.systems_per_page_.push_back (line - page_first_line);
1129 res.force_.push_back (space.force_);
1130 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1131 if (system_count_on_this_page != systems_per_page_)
1133 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1134 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1135 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1138 page_first_line = line;
1141 /* Recalculate forces for the last page because we know now that is
1142 really the last page. */
1143 space.resize (page_height (first_page_num + page, true));
1144 res.force_.back () = space.force_;
1145 return finalize_spacing_result (configuration, res);
1149 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1151 // TODO: add support for min/max-systems-per-page.
1152 Page_spacing_result res;
1154 vsize page_first_line = 0;
1155 Page_spacing space (page_height (first_page_num, false), this);
1157 cache_line_details (configuration);
1158 for (vsize line = 0; line < cached_line_details_.size (); line++)
1160 Real prev_force = space.force_;
1161 space.append_system (cached_line_details_[line]);
1162 if ((line > page_first_line)
1163 && (isinf (space.force_)
1165 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1167 res.systems_per_page_.push_back (line - page_first_line);
1168 res.force_.push_back (prev_force);
1169 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1171 space.resize (page_height (first_page_num + page, false));
1173 space.append_system (cached_line_details_[line]);
1174 page_first_line = line;
1177 if (line == cached_line_details_.size () - 1)
1179 /* This is the last line */
1180 /* When the last page height was computed, we did not know yet that it
1181 * was the last one. If the systems put on it don't fit anymore, the last
1182 * system is moved to a new page */
1183 space.resize (page_height (first_page_num + page, true));
1184 if ((line > page_first_line) && (isinf (space.force_)))
1186 res.systems_per_page_.push_back (line - page_first_line);
1187 res.force_.push_back (prev_force);
1188 /* the last page containing the last line */
1189 space.resize (page_height (first_page_num + page + 1, true));
1191 space.append_system (cached_line_details_[line]);
1192 res.systems_per_page_.push_back (1);
1193 res.force_.push_back (space.force_);
1194 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1195 res.penalty_ += cached_line_details_[line].page_penalty_;
1199 res.systems_per_page_.push_back (line + 1 - page_first_line);
1200 res.force_.push_back (space.force_);
1201 res.penalty_ += cached_line_details_[line].page_penalty_;
1205 return finalize_spacing_result (configuration, res);
1208 /* Calculate demerits and fix res.systems_per_page_ so that
1209 it refers to the original line numbers, not the ones given by compress_lines (). */
1211 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1213 if (res.force_.empty ())
1216 cache_line_details (configuration);
1217 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1219 Real line_force = 0;
1220 Real line_penalty = 0;
1221 Real page_demerits = res.penalty_;
1222 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1224 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1226 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1227 line_penalty += uncompressed_line_details_[i].break_penalty_;
1230 for (vsize i = 0; i < res.force_.size (); i++)
1232 Real f = res.force_[i];
1234 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1237 /* for a while we tried averaging page and line forces across pages instead
1238 of summing them, but it caused a problem: if there is a single page
1239 with a very bad page force (for example because of a forced page break),
1240 the page breaker will put in a _lot_ of pages so that the bad force
1241 becomes averaged out over many pages. */
1242 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1247 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1248 are by far the most common cases, we have special functions for them.
1250 space_systems_on_1_page has a different calling convention than most of the
1251 space_systems functions. This is because space_systems_on_1_page is (unlike
1252 the other space_systems functions) sometimes called on subsets of a full
1255 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1257 Page_spacing space (page_height, this);
1258 Page_spacing_result ret;
1261 for (vsize i = 0; i < lines.size (); i++)
1263 space.append_system (lines[i]);
1264 line_count += lines[i].compressed_nontitle_lines_count_;
1267 ret.systems_per_page_.push_back (lines.size ());
1268 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1269 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1270 ret.system_count_status_ |= line_count_status (line_count);
1272 /* don't do finalize_spacing_result () because we are only an internal function */
1277 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1279 Real page1_height = page_height (first_page_num, false);
1280 Real page2_height = page_height (first_page_num + 1, is_last ());
1281 bool ragged1 = ragged ();
1282 bool ragged2 = ragged () || (is_last () && ragged_last ());
1284 /* if there is a forced break, this reduces to 2 1-page problems */
1285 cache_line_details (configuration);
1286 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1287 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1289 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1290 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1291 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1292 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1294 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1295 p1.force_.push_back (p2.force_[0]);
1296 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1297 p1.system_count_status_ |= p2.system_count_status_;
1301 vector<Real> page1_force;
1302 vector<Real> page2_force;
1304 // page1_penalty and page2_penalty store the penalties based
1305 // on min-systems-per-page and max-systems-per-page.
1306 vector<Real> page1_penalty;
1307 vector<Real> page2_penalty;
1309 // page1_status and page2_status keep track of whether the min-systems-per-page
1310 // and max-systems-per-page constraints are satisfied.
1311 vector<int> page1_status;
1312 vector<int> page2_status;
1314 Page_spacing page1 (page1_height, this);
1315 Page_spacing page2 (page2_height, this);
1316 int page1_line_count = 0;
1317 int page2_line_count = 0;
1319 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1320 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1321 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1322 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1323 page1_status.resize (cached_line_details_.size () - 1, 0);
1324 page2_status.resize (cached_line_details_.size () - 1, 0);
1326 /* find the page 1 and page 2 forces for each page-breaking position */
1327 for (vsize i = 0; i < page1_force.size (); i++)
1329 page1.append_system (cached_line_details_[i]);
1330 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1331 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1332 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1334 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1335 page1_penalty[i] = line_count_penalty (page1_line_count);
1336 page1_status[i] = line_count_status (page1_line_count);
1339 page2_force[page2_force.size () - 1 - i] =
1340 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1342 page2_force[page2_force.size () - 1 - i] = page2.force_;
1343 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1344 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1347 /* find the position that minimises the sum of the page forces */
1348 vsize best_sys_count = 1;
1349 Real best_demerits = infinity_f;
1350 for (vsize i = 0; i < page1_force.size (); i++)
1352 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1354 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1355 // constraints. That is, we penalize harshly when they don't happen
1356 // but we don't completely reject.
1358 + page1_penalty[i] + page2_penalty[i]
1359 + cached_line_details_[i+1].page_penalty_
1360 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1361 if (dem < best_demerits)
1363 best_demerits = dem;
1364 best_sys_count = i+1;
1368 Page_spacing_result ret;
1369 ret.systems_per_page_.push_back (best_sys_count);
1370 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1371 ret.force_.push_back (page1_force[best_sys_count-1]);
1372 ret.force_.push_back (page2_force[best_sys_count-1]);
1373 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1374 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1375 + cached_line_details_.back ().page_penalty_
1376 + cached_line_details_.back ().turn_penalty_
1377 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1379 /* don't do finalize_spacing_result () because we are only an internal function */
1384 Page_breaking::all_lines_stretched (vsize configuration)
1386 cache_line_details (configuration);
1387 for (vsize i = 0; i < cached_line_details_.size (); i++)
1388 if (cached_line_details_[i].force_ < 0)
1394 Page_breaking::Line_division
1395 Page_breaking::current_configuration (vsize configuration_index) const
1397 return current_configurations_[configuration_index];
1401 Page_breaking::is_last () const
1403 return current_end_breakpoint_ == last_break_position ();
1407 Page_breaking::ends_score () const
1409 return breaks_[current_end_breakpoint_].score_ender_;
1413 Page_breaking::last_break_position () const
1415 return breaks_.size () - 1;
1418 // This gives the minimum distance between the top of the
1419 // printable area (ie. the bottom of the top-margin) and
1420 // the extent box of the topmost system.
1422 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1424 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1426 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1428 Real min_distance = -infinity_f;
1431 Page_layout_problem::read_spacing_spec (first_system_spacing,
1433 ly_symbol2scm ("minimum-distance"));
1434 Page_layout_problem::read_spacing_spec (first_system_spacing,
1436 ly_symbol2scm ("padding"));
1438 // FIXME: take into account the height of the header
1439 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1440 return max (0.0, max (padding, min_distance - translate));
1444 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1446 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1447 Real min_distance = -infinity_f;
1450 Page_layout_problem::read_spacing_spec (last_system_spacing,
1452 ly_symbol2scm ("minimum-distance"));
1453 Page_layout_problem::read_spacing_spec (last_system_spacing,
1455 ly_symbol2scm ("padding"));
1457 // FIXME: take into account the height of the footer
1458 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1459 return max (0.0, max (padding, min_distance + translate));
1463 Page_breaking::orphan_penalty () const
1465 return orphan_penalty_;