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)
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);
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)
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 (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 /* TODO: we want some way of applying Break_p to a prob? */
602 if (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_);
809 Page_breaking::clear_line_details_cache ()
811 cached_configuration_index_ = VPOS;
812 cached_line_details_.clear ();
813 uncompressed_line_details_.clear ();
817 Page_breaking::line_divisions_rec (vsize system_count,
818 Line_division const &min_sys,
819 Line_division const &max_sys,
820 Line_division *cur_division)
822 vsize my_index = cur_division->size ();
823 vsize others_min = 0;
824 vsize others_max = 0;
826 for (vsize i = my_index + 1; i < min_sys.size (); i++)
828 others_min += min_sys[i];
829 others_max += max_sys[i];
831 others_max = min (others_max, system_count);
832 vsize real_min = max (min_sys[my_index], system_count - others_max);
833 vsize real_max = min (max_sys[my_index], system_count - others_min);
835 if (real_min > real_max || real_min <= 0)
837 /* this should never happen within a recursive call. If it happens
838 at all, it means that we were called with an unsolvable problem
839 and we should return an empty result */
840 assert (my_index == 0);
844 for (vsize i = real_min; i <= real_max; i++)
846 cur_division->push_back (i);
847 if (my_index == min_sys.size () - 1)
848 current_configurations_.push_back (*cur_division);
850 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
851 cur_division->pop_back ();
856 Page_breaking::compute_line_heights ()
858 Real prev_hanging = 0;
859 Real prev_hanging_begin = 0;
860 Real prev_hanging_rest = 0;
861 Real prev_refpoint_hanging = 0;
862 for (vsize i = 0; i < cached_line_details_.size (); i++)
864 Line_shape shape = cached_line_details_[i].shape_;
865 Real a = shape.begin_[UP];
866 Real b = shape.rest_[UP];
867 bool title = cached_line_details_[i].title_;
868 Real refpoint_hanging = max (prev_hanging_begin + a, prev_hanging_rest + b);
873 if (!cached_line_details_[i].tight_spacing_)
875 ? cached_line_details_[i-1].title_padding_
876 : cached_line_details_[i-1].padding_;
877 Real min_dist = title
878 ? cached_line_details_[i-1].title_min_distance_
879 : cached_line_details_[i-1].min_distance_;
880 refpoint_hanging = max (refpoint_hanging + padding,
881 prev_refpoint_hanging + min_dist
882 + cached_line_details_[i].first_refpoint_offset_);
885 Real hanging_begin = refpoint_hanging - shape.begin_[DOWN];
886 Real hanging_rest = refpoint_hanging - shape.rest_[DOWN];
887 Real hanging = max (hanging_begin, hanging_rest);
888 cached_line_details_[i].tallness_ = hanging - prev_hanging;
889 prev_hanging = hanging;
890 prev_hanging_begin = hanging_begin;
891 prev_hanging_rest = hanging_rest;
892 prev_refpoint_hanging = refpoint_hanging;
897 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
900 vsize page_starter = 0;
901 Real cur_rod_height = 0;
902 Real cur_spring_height = 0;
903 Real cur_page_height = page_height (first_page_num, false);
906 cache_line_details (configuration);
907 compute_line_heights ();
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 vsize min_p_count = min_page_count (configuration, first_page_num);
1093 cache_line_details (configuration);
1094 Page_spacer ps (cached_line_details_, first_page_num, this);
1095 Page_spacing_result best = ps.solve (min_p_count);
1097 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1099 Page_spacing_result cur = ps.solve (i);
1100 if (cur.demerits_ < best.demerits_)
1104 Page_spacing_result ret = finalize_spacing_result (configuration, best);
1109 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1110 vsize first_page_num)
1112 Page_spacing_result res;
1113 Page_spacing space (page_height (first_page_num, false), this);
1116 vsize page_first_line = 0;
1118 cache_line_details (configuration);
1119 while (line < cached_line_details_.size ())
1123 space.resize (page_height (first_page_num + page, false));
1125 int system_count_on_this_page = 0;
1126 while (system_count_on_this_page < systems_per_page_
1127 && line < cached_line_details_.size ())
1129 Line_details const &cur_line = cached_line_details_[line];
1130 space.append_system (cur_line);
1131 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1134 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1138 res.systems_per_page_.push_back (line - page_first_line);
1140 res.force_.push_back (space.force_);
1141 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1142 if (system_count_on_this_page != systems_per_page_)
1144 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1145 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1146 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1149 page_first_line = line;
1152 /* Recalculate forces for the last page because we know now that is
1153 really the last page. */
1154 space.resize (page_height (first_page_num + page, true));
1155 res.force_.back () = space.force_;
1156 return finalize_spacing_result (configuration, res);
1160 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1162 // TODO: add support for min/max-systems-per-page.
1163 Page_spacing_result res;
1165 vsize page_first_line = 0;
1166 Page_spacing space (page_height (first_page_num, false), this);
1168 cache_line_details (configuration);
1169 compute_line_heights ();
1170 for (vsize line = 0; line < cached_line_details_.size (); line++)
1172 Real prev_force = space.force_;
1173 space.append_system (cached_line_details_[line]);
1174 if ((line > page_first_line)
1175 && (isinf (space.force_)
1177 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1179 res.systems_per_page_.push_back (line - page_first_line);
1180 res.force_.push_back (prev_force);
1181 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1183 space.resize (page_height (first_page_num + page, false));
1185 space.append_system (cached_line_details_[line]);
1186 page_first_line = line;
1189 if (line == cached_line_details_.size () - 1)
1191 /* This is the last line */
1192 /* When the last page height was computed, we did not know yet that it
1193 * was the last one. If the systems put on it don't fit anymore, the last
1194 * system is moved to a new page */
1195 space.resize (page_height (first_page_num + page, true));
1196 if ((line > page_first_line) && (isinf (space.force_)))
1198 res.systems_per_page_.push_back (line - page_first_line);
1199 res.force_.push_back (prev_force);
1200 /* the last page containing the last line */
1201 space.resize (page_height (first_page_num + page + 1, true));
1203 space.append_system (cached_line_details_[line]);
1204 res.systems_per_page_.push_back (1);
1205 res.force_.push_back (space.force_);
1206 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1207 res.penalty_ += cached_line_details_[line].page_penalty_;
1211 res.systems_per_page_.push_back (line + 1 - page_first_line);
1212 res.force_.push_back (space.force_);
1213 res.penalty_ += cached_line_details_[line].page_penalty_;
1217 return finalize_spacing_result (configuration, res);
1220 /* Calculate demerits and fix res.systems_per_page_ so that
1221 it refers to the original line numbers, not the ones given by compress_lines (). */
1223 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1225 if (res.force_.empty ())
1228 cache_line_details (configuration);
1229 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1231 Real line_force = 0;
1232 Real line_penalty = 0;
1233 Real page_demerits = res.penalty_;
1234 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1236 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1238 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1239 line_penalty += uncompressed_line_details_[i].break_penalty_;
1242 for (vsize i = 0; i < res.force_.size (); i++)
1244 Real f = res.force_[i];
1246 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1249 /* for a while we tried averaging page and line forces across pages instead
1250 of summing them, but it caused a problem: if there is a single page
1251 with a very bad page force (for example because of a forced page break),
1252 the page breaker will put in a _lot_ of pages so that the bad force
1253 becomes averaged out over many pages. */
1254 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1259 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1260 are by far the most common cases, we have special functions for them.
1262 space_systems_on_1_page has a different calling convention than most of the
1263 space_systems functions. This is because space_systems_on_1_page is (unlike
1264 the other space_systems functions) sometimes called on subsets of a full
1267 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1269 Page_spacing space (page_height, this);
1270 Page_spacing_result ret;
1273 for (vsize i = 0; i < lines.size (); i++)
1275 space.append_system (lines[i]);
1276 line_count += lines[i].compressed_nontitle_lines_count_;
1279 ret.systems_per_page_.push_back (lines.size ());
1280 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1281 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1282 ret.system_count_status_ |= line_count_status (line_count);
1284 /* don't do finalize_spacing_result () because we are only an internal function */
1289 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1291 Real page1_height = page_height (first_page_num, false);
1292 Real page2_height = page_height (first_page_num + 1, is_last ());
1293 bool ragged1 = ragged ();
1294 bool ragged2 = ragged () || (is_last () && ragged_last ());
1296 /* if there is a forced break, this reduces to 2 1-page problems */
1297 cache_line_details (configuration);
1298 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1299 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1301 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1302 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1303 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1304 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1306 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1307 p1.force_.push_back (p2.force_[0]);
1308 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1309 p1.system_count_status_ |= p2.system_count_status_;
1313 vector<Real> page1_force;
1314 vector<Real> page2_force;
1316 // page1_penalty and page2_penalty store the penalties based
1317 // on min-systems-per-page and max-systems-per-page.
1318 vector<Real> page1_penalty;
1319 vector<Real> page2_penalty;
1321 // page1_status and page2_status keep track of whether the min-systems-per-page
1322 // and max-systems-per-page constraints are satisfied.
1323 vector<int> page1_status;
1324 vector<int> page2_status;
1326 Page_spacing page1 (page1_height, this);
1327 Page_spacing page2 (page2_height, this);
1328 int page1_line_count = 0;
1329 int page2_line_count = 0;
1331 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1332 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1333 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1334 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1335 page1_status.resize (cached_line_details_.size () - 1, 0);
1336 page2_status.resize (cached_line_details_.size () - 1, 0);
1338 /* find the page 1 and page 2 forces for each page-breaking position */
1339 for (vsize i = 0; i < page1_force.size (); i++)
1341 page1.append_system (cached_line_details_[i]);
1342 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1343 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1344 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1346 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1347 page1_penalty[i] = line_count_penalty (page1_line_count);
1348 page1_status[i] = line_count_status (page1_line_count);
1351 page2_force[page2_force.size () - 1 - i] =
1352 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1354 page2_force[page2_force.size () - 1 - i] = page2.force_;
1355 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1356 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1359 /* find the position that minimises the sum of the page forces */
1360 vsize best_sys_count = 1;
1361 Real best_demerits = infinity_f;
1362 for (vsize i = 0; i < page1_force.size (); i++)
1364 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1366 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1367 // constraints. That is, we penalize harshly when they don't happen
1368 // but we don't completely reject.
1370 + page1_penalty[i] + page2_penalty[i]
1371 + cached_line_details_[i+1].page_penalty_
1372 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1373 if (dem < best_demerits)
1375 best_demerits = dem;
1376 best_sys_count = i+1;
1380 Page_spacing_result ret;
1381 ret.systems_per_page_.push_back (best_sys_count);
1382 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1383 ret.force_.push_back (page1_force[best_sys_count-1]);
1384 ret.force_.push_back (page2_force[best_sys_count-1]);
1385 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1386 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1387 + cached_line_details_.back ().page_penalty_
1388 + cached_line_details_.back ().turn_penalty_
1389 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1391 /* don't do finalize_spacing_result () because we are only an internal function */
1396 Page_breaking::all_lines_stretched (vsize configuration)
1398 cache_line_details (configuration);
1399 for (vsize i = 0; i < cached_line_details_.size (); i++)
1400 if (cached_line_details_[i].force_ < 0)
1406 Page_breaking::Line_division
1407 Page_breaking::current_configuration (vsize configuration_index) const
1409 return current_configurations_[configuration_index];
1413 Page_breaking::is_last () const
1415 return current_end_breakpoint_ == last_break_position ();
1419 Page_breaking::ends_score () const
1421 return breaks_[current_end_breakpoint_].score_ender_;
1425 Page_breaking::last_break_position () const
1427 return breaks_.size () - 1;
1430 // This gives the minimum distance between the top of the
1431 // printable area (ie. the bottom of the top-margin) and
1432 // the extent box of the topmost system.
1434 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1436 SCM first_system_spacing = book_->paper_->c_variable ("top-system-spacing");
1438 first_system_spacing = book_->paper_->c_variable ("top-title-spacing");
1440 Real min_distance = -infinity_f;
1443 Page_layout_problem::read_spacing_spec (first_system_spacing,
1445 ly_symbol2scm ("minimum-distance"));
1446 Page_layout_problem::read_spacing_spec (first_system_spacing,
1448 ly_symbol2scm ("padding"));
1450 // FIXME: take into account the height of the header
1451 Real translate = max (line.shape_.begin_[UP], line.shape_.rest_[UP]);
1452 return max (0.0, max (padding, min_distance - translate));
1456 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1458 SCM last_system_spacing = book_->paper_->c_variable ("bottom-system-spacing");
1459 Real min_distance = -infinity_f;
1462 Page_layout_problem::read_spacing_spec (last_system_spacing,
1464 ly_symbol2scm ("minimum-distance"));
1465 Page_layout_problem::read_spacing_spec (last_system_spacing,
1467 ly_symbol2scm ("padding"));
1469 // FIXME: take into account the height of the footer
1470 Real translate = min (line.shape_.begin_[DOWN], line.shape_.rest_[DOWN]);
1471 return max (0.0, max (padding, min_distance + translate));
1475 Page_breaking::orphan_penalty () const
1477 return orphan_penalty_;