2 page-breaking.cc -- implement a superclass and utility
3 functions shared by various page-breaking algorithms
5 source file of the GNU LilyPond music typesetter
7 (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
11 This is a utility class for page-breaking algorithms. There are some complex
12 parts of this class, some of which are useful to understand if you intend
13 to write a page breaking algorithm (ie. a subclass of Page_breaking). Most
14 of these complexities were introduced in order to break the problem of
15 page-breaking into simpler subproblems and to hide some of the bookkeeping
16 complexities of page breaking from the page breaking algorithms.
19 There are several functions that actually distribute systems across pages
20 (for example, the space_systems_XXX and pack_systems_XXX functions). If
21 each of these functions had to handle \noPageBreak, it would be a mess.
22 Therefore, we handle \noPageBreak by "compressing" the list of systems
23 before doing any layout: we concatenate any two systems separated by a
24 \noPageBreak into a single system. The page-breaking functions can do their
25 magic without encountering a \noPageBreak; we then "uncompress" the systems
26 at the end. We almost always work with cached_line_details_, which are
30 The basic operation of a page breaking algorithm is to repeatedly request
31 some systems from the line-breaker and place those systems on some pages.
32 With each repetition, the page breaking algorithm asks the line-breaker for
33 some systems that it thinks will help it achieve a better layout. The
34 Page_breaking class provides functionality to facilitate this in the case
35 that the page breaking algorithm only cares about the number of systems.
37 Even if a page breaking algorithm only cares number of systems, there may
38 be many ways to satisfy its request. For example, in a piece with 2 scores
39 and a request for 10 systems, we could return 5 systems from each score or
40 4 from the first and 6 from the second. Even within a score, we might
41 want to try several different line breaking configurations with a fixed
42 system count; if there is a forced \pageBreak, for example, we might wish
43 to tweak the number of systems on both sides of the \pageBreak independently.
45 The Page_breaking class takes care of finding these configurations. It
46 divides the piece into "chunks" and sets up the line-breaker in such a way
47 that the number of systems in each chunk can be modified independently.
48 Chunks never cross score boundaries; each title and markup is its own chunk.
49 When a page breaking algorithm requests a number of systems, the Page_breaker
50 stores an array of potential configurations, which the page breaking
51 algorithm can iterate over using current_configuration(vsize).
54 A Line_division is simply a way of storing the exact way in which the
55 total number of systems is distributed among chunks. Note that a
56 Line_division may not (in fact, usually will not) describe all of the chunks
57 in the entire book. Rather, it will describe the subset of chunks that lie
58 between some fixed starting and ending point. This subset of chunks changes
59 whenever a page breaking algorithm asks to consider a different pair of
60 starting and ending breakpoints. In particular, a Line_division should be
61 discarded after a call to set_current_breakpoints, since that Line_division
62 refers to a subset of chunks which might be different from the current
63 subset of chunks under consideration.
66 #include "page-breaking.hh"
68 #include "international.hh"
70 #include "output-def.hh"
71 #include "page-spacing.hh"
72 #include "paper-book.hh"
73 #include "paper-score.hh"
74 #include "paper-system.hh"
78 /* for each forbidden page break, merge the systems around it into one
80 static vector<Line_details>
81 compress_lines (const vector<Line_details> &orig)
83 vector<Line_details> ret;
85 for (vsize i = 0; i < orig.size (); i++)
87 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
89 Line_details const &old = ret.back ();
90 Line_details compressed = orig[i];
91 compressed.extent_[DOWN] = old.extent_[DOWN];
92 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
93 compressed.space_ += old.space_;
94 compressed.inverse_hooke_ += old.inverse_hooke_;
96 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
97 compressed.compressed_nontitle_lines_count_ =
98 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
100 compressed.title_ = compressed.title_ && old.title_;
101 ret.back () = compressed;
105 ret.push_back (orig[i]);
106 ret.back ().force_ = 0;
112 /* translate the number of systems-per-page into something meaningful for
113 the uncompressed lines.
116 uncompress_solution (vector<vsize> const &systems_per_page,
117 vector<Line_details> const &compressed)
122 for (vsize i = 0; i < systems_per_page.size (); i++)
124 int compressed_count = 0;
125 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
126 compressed_count += compressed[j].compressed_lines_count_ - 1;
128 ret.push_back (systems_per_page[i] + compressed_count);
129 start_sys += systems_per_page[i];
134 /* for Page_breaking, the start index (when we are dealing with the stuff
135 between a pair of breakpoints) refers to the break_ index of the end of
136 the previous page. So the system index of the start of the current page
137 could either be the same as the end of the previous page or one more than
140 /* Turn a break index into the sys index that starts the next page */
142 Page_breaking::next_system (Break_position const &break_pos) const
144 vsize sys = break_pos.system_spec_index_;
146 if (sys == VPOS) /* beginning of the book */
148 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
149 return sys; /* the score overflows the previous page */
150 return sys + 1; /* this page starts with a new System_spec */
153 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
157 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
158 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
159 page_top_space_ = robust_scm2double (pb->paper_->c_variable ("page-top-space"), 0);
160 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
161 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
162 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
164 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
166 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
167 min_systems_per_page_ = max_systems_per_page_ = 0;
169 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
171 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
172 min_systems_per_page_ = max_systems_per_page_ = 0;
175 create_system_list ();
176 find_chunks_and_breaks (is_break);
179 Page_breaking::~Page_breaking ()
184 Page_breaking::ragged () const
190 Page_breaking::ragged_last () const
196 Page_breaking::systems_per_page () const
198 return systems_per_page_;
202 Page_breaking::max_systems_per_page () const
204 return max_systems_per_page_;
208 Page_breaking::min_systems_per_page () const
210 return min_systems_per_page_;
214 Page_breaking::page_top_space () const
216 return page_top_space_;
220 Page_breaking::system_count () const
222 return system_count_;
226 Page_breaking::too_many_lines (int line_count) const
228 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
232 Page_breaking::too_few_lines (int line_count) const
234 return line_count < min_systems_per_page ();
238 Page_breaking::line_count_penalty (int line_count) const
240 if (too_many_lines (line_count))
241 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
242 if (too_few_lines (line_count))
243 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
249 Page_breaking::line_count_status (int line_count) const
251 if (too_many_lines (line_count))
252 return SYSTEM_COUNT_TOO_MANY;
253 if (too_few_lines (line_count))
254 return SYSTEM_COUNT_TOO_FEW;
256 return SYSTEM_COUNT_OK;
259 /* translate indices into breaks_ into start-end parameters for the line breaker */
261 Page_breaking::line_breaker_args (vsize sys,
262 Break_position const &start,
263 Break_position const &end,
264 vsize *line_breaker_start,
265 vsize *line_breaker_end)
267 assert (system_specs_[sys].pscore_);
268 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
270 if (start.system_spec_index_ == sys)
271 *line_breaker_start = start.score_break_;
273 *line_breaker_start = 0;
275 if (end.system_spec_index_ == sys)
276 *line_breaker_end = end.score_break_;
278 *line_breaker_end = VPOS;
282 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
283 Line_division const &div)
285 vector<Break_position> chunks = chunk_list (start_break, end_break);
286 bool ignore_div = false;
287 if (chunks.size () != div.size () + 1)
289 programming_error ("did not find a valid page breaking configuration");
293 for (vsize i = 0; i + 1 < chunks.size (); i++)
295 vsize sys = next_system (chunks[i]);
296 if (system_specs_[sys].pscore_)
300 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
302 vector<Column_x_positions> pos = ignore_div
303 ? line_breaking_[sys].best_solution (start, end)
304 : line_breaking_[sys].solve (start, end, div[i]);
305 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
311 Page_breaking::systems ()
314 for (vsize sys = 0; sys < system_specs_.size (); sys++)
316 if (system_specs_[sys].pscore_)
318 system_specs_[sys].pscore_->root_system ()
319 ->do_break_substitution_and_fixup_refpoints ();
320 SCM lines = system_specs_[sys].pscore_->root_system ()
321 ->get_broken_system_grobs ();
322 ret = scm_cons (lines, ret);
326 Prob *pb = system_specs_[sys].prob_;
327 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
331 return scm_append (scm_reverse (ret));
335 Page_breaking::page_height (int page_num, bool last) const
337 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
338 SCM mod = scm_c_resolve_module ("scm page");
339 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
340 SCM make_page = scm_c_module_lookup (mod, "make-page");
342 calc_height = scm_variable_ref (calc_height);
343 make_page = scm_variable_ref (make_page);
345 SCM page = scm_apply_0 (make_page, scm_list_n (
347 ly_symbol2scm ("page-number"), scm_from_int (page_num),
348 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
349 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
351 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
352 return scm_to_double (height) - page_top_space_;
356 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
358 Break_position const &pos = breaks_[breakpoint];
360 if (pos.system_spec_index_ == VPOS)
362 if (system_specs_[pos.system_spec_index_].pscore_)
363 return pos.col_->get_property (str);
364 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
368 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
370 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
371 SCM page_module = scm_c_resolve_module ("scm page");
373 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
374 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
375 make_page = scm_variable_ref (make_page);
376 page_stencil = scm_variable_ref (page_stencil);
378 SCM book = book_->self_scm ();
379 int first_page_number
380 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
381 bool last_bookpart = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
383 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
384 if (label_page_table == SCM_UNDEFINED)
385 label_page_table = SCM_EOL;
387 for (vsize i = 0; i < lines_per_page.size (); i++)
389 SCM page_num = scm_from_int (i + first_page_number);
390 bool partbook_last_page = (i == lines_per_page.size () - 1);
391 SCM rag = scm_from_bool (ragged () || ( partbook_last_page && ragged_last ()));
392 SCM line_count = scm_from_int (lines_per_page[i]);
393 SCM lines = scm_list_head (systems, line_count);
394 SCM page = scm_apply_0 (make_page,
395 scm_list_n (book, lines, page_num, rag,
396 scm_from_bool (last_bookpart),
397 scm_from_bool (partbook_last_page),
400 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
402 SCM labels = SCM_EOL;
403 if (Grob * line = unsmob_grob (scm_car (l)))
405 System *system = dynamic_cast<System*> (line);
406 labels = system->get_property ("labels");
408 else if (Prob *prob = unsmob_prob (scm_car (l)))
409 labels = prob->get_property ("labels");
411 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
412 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
416 scm_apply_1 (page_stencil, page, SCM_EOL);
417 ret = scm_cons (page, ret);
418 systems = scm_list_tail (systems, line_count);
420 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
421 ret = scm_reverse (ret);
425 /* The page-turn-page-breaker needs to have a line-breaker between any two
426 columns with non-NULL page-turn-permission.
428 The optimal-breaker needs to have a line-breaker between any two columns
429 with page-break-permission = 'force.
431 By using a grob predicate, we can accommodate both of these uses.
434 Page_breaking::create_system_list ()
436 SCM specs = book_->get_system_specs ();
437 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
439 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
441 SCM system_count = ps->layout ()->c_variable ("system-count");
443 if (scm_is_number (system_count))
444 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
445 scm_vector_to_list (ps->get_paper_systems ()),
448 system_specs_.push_back (System_spec (ps));
452 Prob *pb = unsmob_prob (scm_car (s));
456 system_specs_.push_back (System_spec (pb));
462 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
464 SCM force_sym = ly_symbol2scm ("force");
466 chunks_.push_back (Break_position ());
467 breaks_.push_back (Break_position ());
469 for (vsize i = 0; i < system_specs_.size (); i++)
471 if (system_specs_[i].pscore_)
474 = system_specs_[i].pscore_->root_system ()->used_columns ();
475 vector<vsize> line_breaker_columns;
476 line_breaker_columns.push_back (0);
478 for (vsize j = 1; j < cols.size (); j++)
480 bool last = (j == cols.size () - 1);
481 bool break_point = is_break (cols[j]);
482 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
483 Break_position cur_pos = Break_position (i,
484 line_breaker_columns.size (),
488 if (break_point || (i == system_specs_.size () - 1 && last))
489 breaks_.push_back (cur_pos);
490 if (chunk_end || last)
491 chunks_.push_back (cur_pos);
493 if ((break_point || chunk_end) && !last)
494 line_breaker_columns.push_back (j);
496 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
500 /* TODO: we want some way of applying Break_p to a prob? */
501 if (i == system_specs_.size () - 1)
502 breaks_.push_back (Break_position (i));
504 chunks_.push_back (Break_position (i));
506 /* FIXME: shouldn't we push a Null_breaker or similar dummy
508 line_breaking_.push_back (Constrained_breaking (NULL));
513 vector<Break_position>
514 Page_breaking::chunk_list (vsize start_index, vsize end_index)
516 Break_position start = breaks_[start_index];
517 Break_position end = breaks_[end_index];
520 for (; i < chunks_.size () && chunks_[i] <= start; i++)
523 vector<Break_position> ret;
524 ret.push_back (start);
525 for (; i < chunks_.size () && chunks_[i] < end; i++)
526 ret.push_back (chunks_[i]);
532 Page_breaking::min_system_count (vsize start, vsize end)
534 vector<Break_position> chunks = chunk_list (start, end);
535 Line_division div = system_count_bounds (chunks, true);
538 for (vsize i = 0; i < div.size (); i++)
544 Page_breaking::max_system_count (vsize start, vsize end)
546 vector<Break_position> chunks = chunk_list (start, end);
547 Line_division div = system_count_bounds (chunks, false);
550 for (vsize i = 0; i < div.size (); i++)
555 Page_breaking::Line_division
556 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
559 assert (chunks.size () >= 2);
562 ret.resize (chunks.size () - 1, 1);
564 for (vsize i = 0; i + 1 < chunks.size (); i++)
566 vsize sys = next_system (chunks[i]);
567 if (system_specs_[sys].pscore_)
571 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
573 ? line_breaking_[sys].min_system_count (start, end)
574 : line_breaking_[sys].max_system_count (start, end);
582 Page_breaking::set_current_breakpoints (vsize start,
585 Line_division lower_bound,
586 Line_division upper_bound)
588 system_count_ = system_count;
589 current_chunks_ = chunk_list (start, end);
590 current_start_breakpoint_ = start;
591 current_end_breakpoint_ = end;
592 clear_line_details_cache ();
594 if (!lower_bound.size ())
595 lower_bound = system_count_bounds (current_chunks_, true);
596 if (!upper_bound.size ())
597 upper_bound = system_count_bounds (current_chunks_, false);
599 assert (lower_bound.size () == current_chunks_.size () - 1);
600 assert (upper_bound.size () == current_chunks_.size () - 1);
602 Line_division work_in_progress;
603 current_configurations_.clear ();
604 line_divisions_rec (system_count,
609 /* we only consider a constant number of configurations. Otherwise,
610 this becomes slow when there are many small scores. The constant
611 5 is somewhat arbitrary. */
612 if (current_configurations_.size () > 5)
614 vector<pair<Real,vsize> > dems_and_indices;
616 for (vsize i = 0; i < current_configurations_.size (); i++)
618 cache_line_details (i);
620 for (vsize j = 0; j < cached_line_details_.size (); j++)
621 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
622 + cached_line_details_[j].break_penalty_;
624 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
626 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
628 vector<Line_division> best_5_configurations;
629 for (vsize i = 0; i < 5; i++)
630 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
632 clear_line_details_cache ();
633 current_configurations_ = best_5_configurations;
638 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
640 current_chunks_ = chunk_list (start, end);
641 current_start_breakpoint_ = start;
642 current_end_breakpoint_ = end;
643 clear_line_details_cache ();
647 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
649 vsize sys = next_system (current_chunks_[i]);
650 if (system_specs_[sys].pscore_)
652 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
653 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
658 system_count_ += div.back ();
660 current_configurations_.clear ();
661 current_configurations_.push_back (div);
665 Page_breaking::current_configuration_count () const
667 return current_configurations_.size ();
671 Page_breaking::cache_line_details (vsize configuration_index)
673 if (cached_configuration_index_ != configuration_index)
675 cached_configuration_index_ = configuration_index;
676 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
677 if (!scm_is_number (padding_scm))
678 padding_scm = book_->paper_->c_variable ("between-system-padding");
679 Real padding = robust_scm2double (padding_scm, 0.0);
681 Line_division &div = current_configurations_[configuration_index];
682 uncompressed_line_details_.clear ();
683 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
685 vsize sys = next_system (current_chunks_[i]);
686 if (system_specs_[sys].pscore_)
690 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
692 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
693 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
697 assert (div[i] == 1);
698 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
699 uncompressed_line_details_.back ().padding_ =
700 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
704 cached_line_details_ = compress_lines (uncompressed_line_details_);
709 Page_breaking::clear_line_details_cache ()
711 cached_configuration_index_ = VPOS;
712 cached_line_details_.clear ();
713 uncompressed_line_details_.clear ();
717 Page_breaking::line_divisions_rec (vsize system_count,
718 Line_division const &min_sys,
719 Line_division const &max_sys,
720 Line_division *cur_division)
722 vsize my_index = cur_division->size ();
723 vsize others_min = 0;
724 vsize others_max = 0;
726 for (vsize i = my_index + 1; i < min_sys.size (); i++)
728 others_min += min_sys[i];
729 others_max += max_sys[i];
731 others_max = min (others_max, system_count);
732 vsize real_min = max (min_sys[my_index], system_count - others_max);
733 vsize real_max = min (max_sys[my_index], system_count - others_min);
735 if (real_min > real_max || real_min <= 0)
737 /* this should never happen within a recursive call. If it happens
738 at all, it means that we were called with an unsolvable problem
739 and we should return an empty result */
740 assert (my_index == 0);
744 for (vsize i = real_min; i <= real_max; i++)
746 cur_division->push_back (i);
747 if (my_index == min_sys.size () - 1)
748 current_configurations_.push_back (*cur_division);
750 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
751 cur_division->pop_back ();
756 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
759 Real cur_rod_height = 0;
760 Real cur_spring_height = 0;
761 Real cur_page_height = page_height (first_page_num, false);
764 cache_line_details (configuration);
766 // If the first line on a page has titles, allow them some extra space.
767 if (cached_line_details_.size ()
768 && cached_line_details_[0].compressed_nontitle_lines_count_ < cached_line_details_[0].compressed_lines_count_)
769 cur_page_height += page_top_space ();
771 for (vsize i = 0; i < cached_line_details_.size (); i++)
773 Real ext_len = cached_line_details_[i].extent_.length ();
774 Real next_rod_height = cur_rod_height + ext_len
775 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
776 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
777 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
778 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
780 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
781 || too_many_lines (next_line_count)
783 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
785 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
786 cur_rod_height = ext_len;
787 cur_spring_height = cached_line_details_[i].space_;
788 cur_page_height = page_height (first_page_num + ret, false);
790 if (cached_line_details_[i].compressed_nontitle_lines_count_ < cached_line_details_[i].compressed_lines_count_)
791 cur_page_height += page_top_space ();
796 cur_rod_height = next_rod_height;
797 cur_spring_height = next_spring_height;
798 line_count = next_line_count;
802 /* there are two potential problems with the last page (because we didn't know
803 it was the last page until after we managed to fit all the systems to it):
804 - we are ragged-last but the last page has a compressed spring
805 - the value returned by page_height (num, true) is smaller than the
806 value returned by page_height (num, false) and it causes the page not to
809 In either case, we just need to add one more page. This is because the last
810 line will always fit on the extra page and by adding one more page to the
811 end, the previous page is no longer the last page, so our previous
812 calculations that treated it as a non-last page were ok.
815 cur_page_height = page_height (first_page_num + ret - 1, true);
816 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
817 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
818 && cur_height > cur_page_height
819 /* don't increase the page count if the last page had only one system */
820 && cur_rod_height > cached_line_details_.back ().extent_.length ())
823 assert (ret <= cached_line_details_.size ());
827 // If systems_per_page_ is positive, we don't really try to space on N pages;
828 // we just put the requested number of systems on each page and penalize
829 // if the result doesn't have N pages.
831 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
833 Page_spacing_result ret;
835 if (systems_per_page_ > 0)
837 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
838 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
842 cache_line_details (configuration);
843 bool valid_n = (n >= min_page_count (configuration, first_page_num)
844 && n <= cached_line_details_.size ());
847 programming_error ("number of pages is out of bounds");
849 if (n == 1 && valid_n)
850 ret = space_systems_on_1_page (cached_line_details_,
851 page_height (first_page_num, is_last ()),
852 ragged () || (is_last () && ragged_last ()));
853 else if (n == 2 && valid_n)
854 ret = space_systems_on_2_pages (configuration, first_page_num);
857 Page_spacer ps (cached_line_details_, first_page_num, this);
861 return finalize_spacing_result (configuration, ret);
865 Page_breaking::blank_page_penalty () const
870 penalty_sym = ly_symbol2scm ("blank-last-page-force");
871 else if (ends_score ())
872 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
874 penalty_sym = ly_symbol2scm ("blank-page-force");
876 Break_position const &pos = breaks_[current_end_breakpoint_];
877 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
878 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
880 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
883 // If systems_per_page_ is positive, we don't really try to space on N
884 // or N+1 pages; see the comment to space_systems_on_n_pages.
886 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
888 Page_spacing_result n_res;
889 Page_spacing_result m_res;
891 if (systems_per_page_ > 0)
893 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
894 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
898 cache_line_details (configuration);
899 vsize min_p_count = min_page_count (configuration, first_page_num);
900 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
903 programming_error ("both page counts are out of bounds");
905 if (n == 1 && valid_n)
907 bool rag = ragged () || (is_last () && ragged_last ());
908 Real height = page_height (first_page_num, is_last ());
910 if (1 >= min_p_count)
911 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
912 if (1 < cached_line_details_.size ())
913 m_res = space_systems_on_2_pages (configuration, first_page_num);
917 Page_spacer ps (cached_line_details_, first_page_num, this);
919 if (n >= min_p_count || !valid_n)
920 n_res = ps.solve (n);
921 if (n < cached_line_details_.size () || !valid_n)
922 m_res = ps.solve (n+1);
925 m_res = finalize_spacing_result (configuration, m_res);
926 n_res = finalize_spacing_result (configuration, n_res);
928 Real penalty = blank_page_penalty ();
929 n_res.demerits_ += penalty;
931 if (n_res.force_.size ())
932 n_res.force_.back () += penalty;
934 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
938 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
940 vsize min_p_count = min_page_count (configuration, first_page_num);
941 Real odd_pages_penalty = blank_page_penalty ();
943 cache_line_details (configuration);
944 Page_spacer ps (cached_line_details_, first_page_num, this);
945 Page_spacing_result best = ps.solve (min_p_count);
946 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
947 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
949 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
951 Page_spacing_result cur = ps.solve (i);
952 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
953 if (cur.demerits_ < best.demerits_)
957 return finalize_spacing_result (configuration, best);
961 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
962 vsize first_page_num)
964 Page_spacing_result res;
965 Page_spacing space (page_height (first_page_num, false), page_top_space_);
968 vsize page_first_line = 0;
970 cache_line_details (configuration);
971 while (line < cached_line_details_.size ())
975 space.resize (page_height (first_page_num + page, false));
977 int system_count_on_this_page = 0;
978 while (system_count_on_this_page < systems_per_page_
979 && line < cached_line_details_.size ())
981 Line_details const &cur_line = cached_line_details_[line];
982 space.append_system (cur_line);
983 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
986 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
990 res.systems_per_page_.push_back (line - page_first_line);
992 res.force_.push_back (space.force_);
993 res.penalty_ += cached_line_details_[line-1].page_penalty_;
994 if (system_count_on_this_page != systems_per_page_)
996 res.penalty_ += TERRIBLE_SPACING_PENALTY;
997 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
998 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1001 page_first_line = line;
1004 /* Recalculate forces for the last page because we know now that is
1005 really the last page. */
1006 space.resize (page_height (first_page_num + page, true));
1007 res.force_.back () = space.force_;
1008 return finalize_spacing_result (configuration, res);
1012 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1014 // TODO: add support for min/max-systems-per-page.
1015 Page_spacing_result res;
1017 vsize page_first_line = 0;
1018 Page_spacing space (page_height (first_page_num, false), page_top_space_);
1020 cache_line_details (configuration);
1021 for (vsize line = 0; line < cached_line_details_.size (); line++)
1023 Real prev_force = space.force_;
1024 space.append_system (cached_line_details_[line]);
1025 if ((line > page_first_line)
1026 && (isinf (space.force_)
1028 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1030 res.systems_per_page_.push_back (line - page_first_line);
1031 res.force_.push_back (prev_force);
1032 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1034 space.resize (page_height (first_page_num + page, false));
1036 space.append_system (cached_line_details_[line]);
1037 page_first_line = line;
1040 if (line == cached_line_details_.size () - 1)
1042 /* This is the last line */
1043 /* When the last page height was computed, we did not know yet that it
1044 * was the last one. If the systems put on it don't fit anymore, the last
1045 * system is moved to a new page */
1046 space.resize (page_height (first_page_num + page, true));
1047 if ((line > page_first_line) && (isinf (space.force_)))
1049 res.systems_per_page_.push_back (line - page_first_line);
1050 res.force_.push_back (prev_force);
1051 /* the last page containing the last line */
1052 space.resize (page_height (first_page_num + page + 1, true));
1054 space.append_system (cached_line_details_[line]);
1055 res.systems_per_page_.push_back (1);
1056 res.force_.push_back (space.force_);
1057 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1058 res.penalty_ += cached_line_details_[line].page_penalty_;
1062 res.systems_per_page_.push_back (line + 1 - page_first_line);
1063 res.force_.push_back (space.force_);
1064 res.penalty_ += cached_line_details_[line].page_penalty_;
1068 return finalize_spacing_result (configuration, res);
1071 /* Calculate demerits and fix res.systems_per_page_ so that
1072 it refers to the original line numbers, not the ones given by compress_lines (). */
1074 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1076 if (res.force_.empty ())
1079 cache_line_details (configuration);
1080 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1082 Real line_force = 0;
1083 Real line_penalty = 0;
1084 Real page_demerits = res.penalty_;
1085 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1087 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1089 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1090 line_penalty += uncompressed_line_details_[i].break_penalty_;
1093 for (vsize i = 0; i < res.force_.size (); i++)
1095 Real f = res.force_[i];
1097 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1100 /* for a while we tried averaging page and line forces across pages instead
1101 of summing them, but it caused a problem: if there is a single page
1102 with a very bad page force (for example because of a forced page break),
1103 the page breaker will put in a _lot_ of pages so that the bad force
1104 becomes averaged out over many pages. */
1105 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1110 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1111 are by far the most common cases, we have special functions for them.
1113 space_systems_on_1_page has a different calling convention than most of the
1114 space_systems functions. This is because space_systems_on_1_page is (unlike
1115 the other space_systems functions) sometimes called on subsets of a full
1118 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1120 Page_spacing space (page_height, page_top_space_);
1121 Page_spacing_result ret;
1124 for (vsize i = 0; i < lines.size (); i++)
1126 space.append_system (lines[i]);
1127 line_count += lines[i].compressed_nontitle_lines_count_;
1130 ret.systems_per_page_.push_back (lines.size ());
1131 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1132 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1133 ret.system_count_status_ |= line_count_status (line_count);
1135 /* don't do finalize_spacing_result () because we are only an internal function */
1140 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1142 Real page1_height = page_height (first_page_num, false);
1143 Real page2_height = page_height (first_page_num + 1, is_last ());
1144 bool ragged1 = ragged ();
1145 bool ragged2 = ragged () || (is_last () && ragged_last ());
1147 /* if there is a forced break, this reduces to 2 1-page problems */
1148 cache_line_details (configuration);
1149 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1150 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1152 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1153 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1154 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1155 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1157 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1158 p1.force_.push_back (p2.force_[0]);
1159 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1163 vector<Real> page1_force;
1164 vector<Real> page2_force;
1166 // page1_penalty and page2_penalty store the penalties based
1167 // on min-systems-per-page and max-systems-per-page.
1168 vector<Real> page1_penalty;
1169 vector<Real> page2_penalty;
1171 // page1_status and page2_status keep track of whether the min-systems-per-page
1172 // and max-systems-per-page constraints are satisfied.
1173 vector<int> page1_status;
1174 vector<int> page2_status;
1176 Page_spacing page1 (page1_height, page_top_space_);
1177 Page_spacing page2 (page2_height, page_top_space_);
1178 int page1_line_count = 0;
1179 int page2_line_count = 0;
1181 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1182 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1183 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1184 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1185 page1_status.resize (cached_line_details_.size () - 1, 0);
1186 page2_status.resize (cached_line_details_.size () - 1, 0);
1188 /* find the page 1 and page 2 forces for each page-breaking position */
1189 for (vsize i = 0; i < page1_force.size (); i++)
1191 page1.append_system (cached_line_details_[i]);
1192 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1193 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1194 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1196 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1197 page1_penalty[i] = line_count_penalty (page1_line_count);
1198 page1_status[i] = line_count_status (page1_line_count);
1201 page2_force[page2_force.size () - 1 - i] =
1202 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1204 page2_force[page2_force.size () - 1 - i] = page2.force_;
1205 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1206 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1209 /* find the position that minimises the sum of the page forces */
1210 vsize best_sys_count = 1;
1211 Real best_demerits = infinity_f;
1212 for (vsize i = 0; i < page1_force.size (); i++)
1214 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1216 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1217 // constraints. That is, we penalize harshly when they don't happen
1218 // but we don't completely reject.
1220 + page1_penalty[i] + page2_penalty[i]
1221 + cached_line_details_[i+1].page_penalty_
1222 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1223 if (dem < best_demerits)
1225 best_demerits = dem;
1226 best_sys_count = i+1;
1230 Page_spacing_result ret;
1231 ret.systems_per_page_.push_back (best_sys_count);
1232 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1233 ret.force_.push_back (page1_force[best_sys_count-1]);
1234 ret.force_.push_back (page2_force[best_sys_count-1]);
1235 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1236 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1237 + cached_line_details_.back ().page_penalty_
1238 + cached_line_details_.back ().turn_penalty_
1239 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1241 /* don't do finalize_spacing_result () because we are only an internal function */
1246 Page_breaking::all_lines_stretched (vsize configuration)
1248 cache_line_details (configuration);
1249 for (vsize i = 0; i < cached_line_details_.size (); i++)
1250 if (cached_line_details_[i].force_ < 0)
1256 Page_breaking::Line_division
1257 Page_breaking::current_configuration (vsize configuration_index) const
1259 return current_configurations_[configuration_index];
1263 Page_breaking::is_last () const
1265 return current_end_breakpoint_ == last_break_position ();
1269 Page_breaking::ends_score () const
1271 return breaks_[current_end_breakpoint_].score_ender_;
1275 Page_breaking::last_break_position () const
1277 return breaks_.size () - 1;