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-layout-problem.hh"
72 #include "page-spacing.hh"
73 #include "paper-book.hh"
74 #include "paper-score.hh"
75 #include "paper-system.hh"
79 /* for each forbidden page break, merge the systems around it into one
81 static vector<Line_details>
82 compress_lines (const vector<Line_details> &orig)
84 vector<Line_details> ret;
86 for (vsize i = 0; i < orig.size (); i++)
88 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
90 Line_details const &old = ret.back ();
91 Line_details compressed = orig[i];
92 compressed.extent_[DOWN] = old.extent_[DOWN];
93 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
94 compressed.space_ += old.space_;
95 compressed.inverse_hooke_ += old.inverse_hooke_;
97 compressed.compressed_lines_count_ = old.compressed_lines_count_ + 1;
98 compressed.compressed_nontitle_lines_count_ =
99 old.compressed_nontitle_lines_count_ + (compressed.title_ ? 0 : 1);
101 // compressed.title_ is true if and only if the first of its
102 // compressed lines was a title.
103 compressed.title_ = old.title_;
104 ret.back () = compressed;
108 ret.push_back (orig[i]);
109 ret.back ().force_ = 0;
115 /* translate the number of systems-per-page into something meaningful for
116 the uncompressed lines.
119 uncompress_solution (vector<vsize> const &systems_per_page,
120 vector<Line_details> const &compressed)
125 for (vsize i = 0; i < systems_per_page.size (); i++)
127 int compressed_count = 0;
128 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
129 compressed_count += compressed[j].compressed_lines_count_ - 1;
131 ret.push_back (systems_per_page[i] + compressed_count);
132 start_sys += systems_per_page[i];
137 /* for Page_breaking, the start index (when we are dealing with the stuff
138 between a pair of breakpoints) refers to the break_ index of the end of
139 the previous page. So the system index of the start of the current page
140 could either be the same as the end of the previous page or one more than
143 /* Turn a break index into the sys index that starts the next page */
145 Page_breaking::next_system (Break_position const &break_pos) const
147 vsize sys = break_pos.system_spec_index_;
149 if (sys == VPOS) /* beginning of the book */
151 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
152 return sys; /* the score overflows the previous page */
153 return sys + 1; /* this page starts with a new System_spec */
156 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
160 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
161 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
162 systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("systems-per-page"), 0));
163 max_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("max-systems-per-page"), 0));
164 min_systems_per_page_ = max (0, robust_scm2int (pb->paper_->c_variable ("min-systems-per-page"), 0));
166 if (systems_per_page_ && (max_systems_per_page_ || min_systems_per_page_))
168 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
169 min_systems_per_page_ = max_systems_per_page_ = 0;
171 if (max_systems_per_page_ && min_systems_per_page_ > max_systems_per_page_)
173 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
174 min_systems_per_page_ = max_systems_per_page_ = 0;
177 create_system_list ();
178 find_chunks_and_breaks (is_break);
181 Page_breaking::~Page_breaking ()
186 Page_breaking::ragged () const
192 Page_breaking::ragged_last () const
198 Page_breaking::systems_per_page () const
200 return systems_per_page_;
204 Page_breaking::max_systems_per_page () const
206 return max_systems_per_page_;
210 Page_breaking::min_systems_per_page () const
212 return min_systems_per_page_;
216 Page_breaking::system_count () const
218 return system_count_;
222 Page_breaking::too_many_lines (int line_count) const
224 return max_systems_per_page () > 0 && line_count > max_systems_per_page ();
228 Page_breaking::too_few_lines (int line_count) const
230 return line_count < min_systems_per_page ();
234 Page_breaking::line_count_penalty (int line_count) const
236 if (too_many_lines (line_count))
237 return (line_count - max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY;
238 if (too_few_lines (line_count))
239 return (min_systems_per_page () - line_count) * TERRIBLE_SPACING_PENALTY;
245 Page_breaking::line_count_status (int line_count) const
247 if (too_many_lines (line_count))
248 return SYSTEM_COUNT_TOO_MANY;
249 if (too_few_lines (line_count))
250 return SYSTEM_COUNT_TOO_FEW;
252 return SYSTEM_COUNT_OK;
255 /* translate indices into breaks_ into start-end parameters for the line breaker */
257 Page_breaking::line_breaker_args (vsize sys,
258 Break_position const &start,
259 Break_position const &end,
260 vsize *line_breaker_start,
261 vsize *line_breaker_end)
263 assert (system_specs_[sys].pscore_);
264 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
266 if (start.system_spec_index_ == sys)
267 *line_breaker_start = start.score_break_;
269 *line_breaker_start = 0;
271 if (end.system_spec_index_ == sys)
272 *line_breaker_end = end.score_break_;
274 *line_breaker_end = VPOS;
278 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
279 Line_division const &div)
281 vector<Break_position> chunks = chunk_list (start_break, end_break);
282 bool ignore_div = false;
283 if (chunks.size () != div.size () + 1)
285 programming_error ("did not find a valid page breaking configuration");
289 for (vsize i = 0; i + 1 < chunks.size (); i++)
291 vsize sys = next_system (chunks[i]);
292 if (system_specs_[sys].pscore_)
296 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
298 vector<Column_x_positions> pos = ignore_div
299 ? line_breaking_[sys].best_solution (start, end)
300 : line_breaking_[sys].solve (start, end, div[i]);
301 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
307 Page_breaking::systems ()
310 for (vsize sys = 0; sys < system_specs_.size (); sys++)
312 if (system_specs_[sys].pscore_)
314 system_specs_[sys].pscore_->root_system ()
315 ->do_break_substitution_and_fixup_refpoints ();
316 SCM lines = system_specs_[sys].pscore_->root_system ()
317 ->get_broken_system_grobs ();
318 ret = scm_cons (lines, ret);
322 Prob *pb = system_specs_[sys].prob_;
323 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
327 return scm_append (scm_reverse (ret));
331 Page_breaking::make_page (int page_num, bool last) const
333 bool last_part = ly_scm2bool (book_->paper_->c_variable ("is-last-bookpart"));
334 SCM mod = scm_c_resolve_module ("scm page");
335 SCM make_page_scm = scm_c_module_lookup (mod, "make-page");
337 make_page_scm = scm_variable_ref (make_page_scm);
339 return scm_apply_0 (make_page_scm,
340 scm_list_n (book_->self_scm (),
341 ly_symbol2scm ("page-number"), scm_from_int (page_num),
342 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part),
343 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last),
348 Page_breaking::page_height (int page_num, bool last) const
350 SCM mod = scm_c_resolve_module ("scm page");
351 SCM page = make_page (page_num, last);
352 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
353 calc_height = scm_variable_ref (calc_height);
355 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
356 return scm_to_double (height);
360 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
362 Break_position const &pos = breaks_[breakpoint];
364 if (pos.system_spec_index_ == VPOS)
366 if (system_specs_[pos.system_spec_index_].pscore_)
367 return pos.col_->get_property (str);
368 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
372 Page_breaking::get_page_configuration (SCM systems, int page_num, bool ragged, bool last)
374 SCM dummy_page = make_page (page_num, last);
375 Page_layout_problem layout (book_, dummy_page, systems);
376 return scm_is_pair (systems) ? layout.solution (ragged) : SCM_EOL;
380 Page_breaking::draw_page (SCM systems, SCM configuration, int page_num, bool last)
382 // Create a stencil for each system.
383 SCM paper_systems = SCM_EOL;
384 for (SCM s = scm_reverse (systems); scm_is_pair (s); s = scm_cdr (s))
386 SCM paper_system = scm_car (s);
387 if (Grob *g = unsmob_grob (scm_car (s)))
389 System *sys = dynamic_cast<System*> (g);
390 paper_system = sys->get_paper_system ();
393 paper_systems = scm_cons (paper_system, paper_systems);
396 // Create the page and draw it.
397 SCM page = make_page (page_num, last);
398 SCM page_module = scm_c_resolve_module ("scm page");
399 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
400 page_stencil = scm_variable_ref (page_stencil);
402 Prob *p = unsmob_prob (page);
403 p->set_property ("lines", paper_systems);
404 p->set_property ("configuration", configuration);
405 scm_apply_1 (page_stencil, page, SCM_EOL);
411 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
413 int first_page_number
414 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
416 SCM label_page_table = book_->top_paper ()->c_variable ("label-page-table");
417 if (label_page_table == SCM_UNDEFINED)
418 label_page_table = SCM_EOL;
420 // Build a list of (systems . configuration) pairs. Note that we lay out
421 // the staves and find the configurations before drawing anything. Some
422 // grobs (like tuplet brackets) look at their neighbours while drawing
423 // themselves. If this happens before the neighbouring staves have
424 // been laid out, bad side-effects could happen (in particular,
425 // Align_interface::align_to_ideal_distances might be called).
426 SCM systems_and_configs = SCM_EOL;
428 for (vsize i = 0; i < lines_per_page.size (); i++)
430 int page_num = i + first_page_number;
431 bool bookpart_last_page = (i == lines_per_page.size () - 1);
432 bool rag = ragged () || (bookpart_last_page && ragged_last ());
433 SCM line_count = scm_from_int (lines_per_page[i]);
434 SCM lines = scm_list_head (systems, line_count);
435 SCM config = get_page_configuration (lines, page_num, rag, bookpart_last_page);
437 systems_and_configs = scm_cons (scm_cons (lines, config), systems_and_configs);
438 systems = scm_list_tail (systems, line_count);
441 // Now it's safe to make the pages.
442 int page_num = first_page_number + lines_per_page.size () - 1;
443 for (SCM s = systems_and_configs; scm_is_pair (s); s = scm_cdr (s))
445 SCM lines = scm_caar (s);
446 SCM config = scm_cdar (s);
447 bool bookpart_last_page = (s == systems_and_configs);
448 SCM page = draw_page (lines, config, page_num, bookpart_last_page);
451 SCM page_num_scm = scm_from_int (page_num);
452 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
454 SCM labels = SCM_EOL;
455 if (Grob * line = unsmob_grob (scm_car (l)))
457 System *system = dynamic_cast<System*> (line);
458 labels = system->get_property ("labels");
460 else if (Prob *prob = unsmob_prob (scm_car (l)))
461 labels = prob->get_property ("labels");
463 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
464 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num_scm),
468 ret = scm_cons (page, ret);
471 book_->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
475 /* The page-turn-page-breaker needs to have a line-breaker between any two
476 columns with non-NULL page-turn-permission.
478 The optimal-breaker needs to have a line-breaker between any two columns
479 with page-break-permission = 'force.
481 By using a grob predicate, we can accommodate both of these uses.
484 Page_breaking::create_system_list ()
486 SCM specs = book_->get_system_specs ();
487 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
489 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
491 SCM system_count = ps->layout ()->c_variable ("system-count");
493 if (scm_is_number (system_count))
494 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
495 scm_vector_to_list (ps->get_paper_systems ()),
498 system_specs_.push_back (System_spec (ps));
502 Prob *pb = unsmob_prob (scm_car (s));
506 system_specs_.push_back (System_spec (pb));
512 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
514 SCM force_sym = ly_symbol2scm ("force");
516 chunks_.push_back (Break_position ());
517 breaks_.push_back (Break_position ());
519 for (vsize i = 0; i < system_specs_.size (); i++)
521 if (system_specs_[i].pscore_)
524 = system_specs_[i].pscore_->root_system ()->used_columns ();
525 vector<vsize> line_breaker_columns;
526 line_breaker_columns.push_back (0);
528 for (vsize j = 1; j < cols.size (); j++)
530 bool last = (j == cols.size () - 1);
531 bool break_point = is_break (cols[j]);
532 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
533 Break_position cur_pos = Break_position (i,
534 line_breaker_columns.size (),
538 if (break_point || (i == system_specs_.size () - 1 && last))
539 breaks_.push_back (cur_pos);
540 if (chunk_end || last)
541 chunks_.push_back (cur_pos);
543 if ((break_point || chunk_end) && !last)
544 line_breaker_columns.push_back (j);
546 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
550 /* TODO: we want some way of applying Break_p to a prob? */
551 if (i == system_specs_.size () - 1)
552 breaks_.push_back (Break_position (i));
554 chunks_.push_back (Break_position (i));
556 /* FIXME: shouldn't we push a Null_breaker or similar dummy
558 line_breaking_.push_back (Constrained_breaking (NULL));
563 vector<Break_position>
564 Page_breaking::chunk_list (vsize start_index, vsize end_index)
566 Break_position start = breaks_[start_index];
567 Break_position end = breaks_[end_index];
570 for (; i < chunks_.size () && chunks_[i] <= start; i++)
573 vector<Break_position> ret;
574 ret.push_back (start);
575 for (; i < chunks_.size () && chunks_[i] < end; i++)
576 ret.push_back (chunks_[i]);
582 Page_breaking::min_system_count (vsize start, vsize end)
584 vector<Break_position> chunks = chunk_list (start, end);
585 Line_division div = system_count_bounds (chunks, true);
588 for (vsize i = 0; i < div.size (); i++)
594 Page_breaking::max_system_count (vsize start, vsize end)
596 vector<Break_position> chunks = chunk_list (start, end);
597 Line_division div = system_count_bounds (chunks, false);
600 for (vsize i = 0; i < div.size (); i++)
605 Page_breaking::Line_division
606 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
609 assert (chunks.size () >= 2);
612 ret.resize (chunks.size () - 1, 1);
614 for (vsize i = 0; i + 1 < chunks.size (); i++)
616 vsize sys = next_system (chunks[i]);
617 if (system_specs_[sys].pscore_)
621 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
623 ? line_breaking_[sys].min_system_count (start, end)
624 : line_breaking_[sys].max_system_count (start, end);
632 Page_breaking::set_current_breakpoints (vsize start,
635 Line_division lower_bound,
636 Line_division upper_bound)
638 system_count_ = system_count;
639 current_chunks_ = chunk_list (start, end);
640 current_start_breakpoint_ = start;
641 current_end_breakpoint_ = end;
642 clear_line_details_cache ();
644 if (!lower_bound.size ())
645 lower_bound = system_count_bounds (current_chunks_, true);
646 if (!upper_bound.size ())
647 upper_bound = system_count_bounds (current_chunks_, false);
649 assert (lower_bound.size () == current_chunks_.size () - 1);
650 assert (upper_bound.size () == current_chunks_.size () - 1);
652 Line_division work_in_progress;
653 current_configurations_.clear ();
654 line_divisions_rec (system_count,
659 /* we only consider a constant number of configurations. Otherwise,
660 this becomes slow when there are many small scores. The constant
661 5 is somewhat arbitrary. */
662 if (current_configurations_.size () > 5)
664 vector<pair<Real,vsize> > dems_and_indices;
666 for (vsize i = 0; i < current_configurations_.size (); i++)
668 cache_line_details (i);
670 for (vsize j = 0; j < cached_line_details_.size (); j++)
671 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
672 + cached_line_details_[j].break_penalty_;
674 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
676 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
678 vector<Line_division> best_5_configurations;
679 for (vsize i = 0; i < 5; i++)
680 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
682 clear_line_details_cache ();
683 current_configurations_ = best_5_configurations;
688 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
690 current_chunks_ = chunk_list (start, end);
691 current_start_breakpoint_ = start;
692 current_end_breakpoint_ = end;
693 clear_line_details_cache ();
697 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
699 vsize sys = next_system (current_chunks_[i]);
700 if (system_specs_[sys].pscore_)
702 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
703 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
708 system_count_ += div.back ();
710 current_configurations_.clear ();
711 current_configurations_.push_back (div);
715 Page_breaking::current_configuration_count () const
717 return current_configurations_.size ();
721 Page_breaking::cache_line_details (vsize configuration_index)
723 if (cached_configuration_index_ != configuration_index)
725 cached_configuration_index_ = configuration_index;
727 SCM spacing_spec = book_->paper_->c_variable ("between-system-spacing");
728 SCM page_breaking_spacing_spec = book_->paper_->c_variable ("page-breaking-between-system-spacing");
729 Page_layout_problem::read_spacing_spec (spacing_spec, &padding, ly_symbol2scm ("padding"));
730 Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec, &padding, ly_symbol2scm ("padding"));
732 Line_division &div = current_configurations_[configuration_index];
733 uncompressed_line_details_.clear ();
734 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
736 vsize sys = next_system (current_chunks_[i]);
737 if (system_specs_[sys].pscore_)
741 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
743 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
744 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
748 assert (div[i] == 1);
749 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
750 uncompressed_line_details_.back ().padding_ =
751 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
755 cached_line_details_ = compress_lines (uncompressed_line_details_);
760 Page_breaking::clear_line_details_cache ()
762 cached_configuration_index_ = VPOS;
763 cached_line_details_.clear ();
764 uncompressed_line_details_.clear ();
768 Page_breaking::line_divisions_rec (vsize system_count,
769 Line_division const &min_sys,
770 Line_division const &max_sys,
771 Line_division *cur_division)
773 vsize my_index = cur_division->size ();
774 vsize others_min = 0;
775 vsize others_max = 0;
777 for (vsize i = my_index + 1; i < min_sys.size (); i++)
779 others_min += min_sys[i];
780 others_max += max_sys[i];
782 others_max = min (others_max, system_count);
783 vsize real_min = max (min_sys[my_index], system_count - others_max);
784 vsize real_max = min (max_sys[my_index], system_count - others_min);
786 if (real_min > real_max || real_min <= 0)
788 /* this should never happen within a recursive call. If it happens
789 at all, it means that we were called with an unsolvable problem
790 and we should return an empty result */
791 assert (my_index == 0);
795 for (vsize i = real_min; i <= real_max; i++)
797 cur_division->push_back (i);
798 if (my_index == min_sys.size () - 1)
799 current_configurations_.push_back (*cur_division);
801 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
802 cur_division->pop_back ();
807 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
810 vsize page_starter = 0;
811 Real cur_rod_height = 0;
812 Real cur_spring_height = 0;
813 Real cur_page_height = page_height (first_page_num, false);
816 cache_line_details (configuration);
818 if (cached_line_details_.size ())
819 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[0]);
821 for (vsize i = 0; i < cached_line_details_.size (); i++)
823 Real ext_len = cached_line_details_[i].extent_.length ();
824 Real next_rod_height = cur_rod_height + ext_len
825 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
826 Real next_spring_height = cur_spring_height + cached_line_details_[i].space_;
827 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0)
828 + min_whitespace_at_bottom_of_page (cached_line_details_[i]);
829 int next_line_count = line_count + cached_line_details_[i].compressed_nontitle_lines_count_;
831 if ((!too_few_lines (line_count) && (next_height > cur_page_height && cur_rod_height > 0))
832 || too_many_lines (next_line_count)
834 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
836 line_count = cached_line_details_[i].compressed_nontitle_lines_count_;
837 cur_rod_height = ext_len;
838 cur_spring_height = cached_line_details_[i].space_;
841 cur_page_height = page_height (first_page_num + ret, false);
842 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[i]);
848 cur_rod_height = next_rod_height;
849 cur_spring_height = next_spring_height;
850 line_count = next_line_count;
854 /* there are two potential problems with the last page (because we didn't know
855 it was the last page until after we managed to fit all the systems to it):
856 - we are ragged-last but the last page has a compressed spring
857 - the value returned by page_height (num, true) is smaller than the
858 value returned by page_height (num, false) and it causes the page not to
861 In either case, we just need to add one more page. This is because the last
862 line will always fit on the extra page and by adding one more page to the
863 end, the previous page is no longer the last page, so our previous
864 calculations that treated it as a non-last page were ok.
867 cur_page_height = page_height (first_page_num + ret - 1, true);
868 cur_page_height -= min_whitespace_at_top_of_page (cached_line_details_[page_starter]);
869 cur_page_height -= min_whitespace_at_bottom_of_page (cached_line_details_.back ());
871 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
872 if (!too_few_lines (line_count - cached_line_details_.back ().compressed_nontitle_lines_count_)
873 && cur_height > cur_page_height
874 /* don't increase the page count if the last page had only one system */
875 && cur_rod_height > cached_line_details_.back ().extent_.length ())
878 assert (ret <= cached_line_details_.size ());
882 // If systems_per_page_ is positive, we don't really try to space on N pages;
883 // we just put the requested number of systems on each page and penalize
884 // if the result doesn't have N pages.
886 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
888 Page_spacing_result ret;
890 if (systems_per_page_ > 0)
892 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
893 ret.demerits_ += (ret.force_.size () == n) ? 0 : BAD_SPACING_PENALTY;
897 cache_line_details (configuration);
898 bool valid_n = (n >= min_page_count (configuration, first_page_num)
899 && n <= cached_line_details_.size ());
902 programming_error ("number of pages is out of bounds");
904 if (n == 1 && valid_n)
905 ret = space_systems_on_1_page (cached_line_details_,
906 page_height (first_page_num, is_last ()),
907 ragged () || (is_last () && ragged_last ()));
908 else if (n == 2 && valid_n)
909 ret = space_systems_on_2_pages (configuration, first_page_num);
912 Page_spacer ps (cached_line_details_, first_page_num, this);
916 return finalize_spacing_result (configuration, ret);
920 Page_breaking::blank_page_penalty () const
925 penalty_sym = ly_symbol2scm ("blank-last-page-force");
926 else if (ends_score ())
927 penalty_sym = ly_symbol2scm ("blank-after-score-page-force");
929 penalty_sym = ly_symbol2scm ("blank-page-force");
931 Break_position const &pos = breaks_[current_end_breakpoint_];
932 if (Paper_score *ps = system_specs_[pos.system_spec_index_].pscore_)
933 return robust_scm2double (ps->layout ()->lookup_variable (penalty_sym), 0.0);
935 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
938 // If systems_per_page_ is positive, we don't really try to space on N
939 // or N+1 pages; see the comment to space_systems_on_n_pages.
941 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
943 Page_spacing_result n_res;
944 Page_spacing_result m_res;
946 if (systems_per_page_ > 0)
948 Page_spacing_result ret = space_systems_with_fixed_number_per_page (configuration, first_page_num);
949 ret.demerits_ += (ret.force_.size () == n || ret.force_.size () == (n-1)) ? 0 : BAD_SPACING_PENALTY;
953 cache_line_details (configuration);
954 vsize min_p_count = min_page_count (configuration, first_page_num);
955 bool valid_n = n >= min_p_count || n <= cached_line_details_.size ();
958 programming_error ("both page counts are out of bounds");
960 if (n == 1 && valid_n)
962 bool rag = ragged () || (is_last () && ragged_last ());
963 Real height = page_height (first_page_num, is_last ());
965 if (1 >= min_p_count)
966 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
967 if (1 < cached_line_details_.size ())
968 m_res = space_systems_on_2_pages (configuration, first_page_num);
972 Page_spacer ps (cached_line_details_, first_page_num, this);
974 if (n >= min_p_count || !valid_n)
975 n_res = ps.solve (n);
976 if (n < cached_line_details_.size () || !valid_n)
977 m_res = ps.solve (n+1);
980 m_res = finalize_spacing_result (configuration, m_res);
981 n_res = finalize_spacing_result (configuration, n_res);
983 Real penalty = blank_page_penalty ();
984 n_res.demerits_ += penalty;
986 if (n_res.force_.size ())
987 n_res.force_.back () += penalty;
989 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
993 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
995 vsize min_p_count = min_page_count (configuration, first_page_num);
996 Real odd_pages_penalty = blank_page_penalty ();
998 cache_line_details (configuration);
999 Page_spacer ps (cached_line_details_, first_page_num, this);
1000 Page_spacing_result best = ps.solve (min_p_count);
1001 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
1002 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
1004 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
1006 Page_spacing_result cur = ps.solve (i);
1007 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
1008 if (cur.demerits_ < best.demerits_)
1012 return finalize_spacing_result (configuration, best);
1016 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration,
1017 vsize first_page_num)
1019 Page_spacing_result res;
1020 Page_spacing space (page_height (first_page_num, false), this);
1023 vsize page_first_line = 0;
1025 cache_line_details (configuration);
1026 while (line < cached_line_details_.size ())
1030 space.resize (page_height (first_page_num + page, false));
1032 int system_count_on_this_page = 0;
1033 while (system_count_on_this_page < systems_per_page_
1034 && line < cached_line_details_.size ())
1036 Line_details const &cur_line = cached_line_details_[line];
1037 space.append_system (cur_line);
1038 system_count_on_this_page += cur_line.compressed_nontitle_lines_count_;
1041 if (cur_line.page_permission_ == ly_symbol2scm ("force"))
1045 res.systems_per_page_.push_back (line - page_first_line);
1047 res.force_.push_back (space.force_);
1048 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1049 if (system_count_on_this_page != systems_per_page_)
1051 res.penalty_ += TERRIBLE_SPACING_PENALTY;
1052 res.system_count_status_ |= ((system_count_on_this_page < systems_per_page_))
1053 ? SYSTEM_COUNT_TOO_FEW : SYSTEM_COUNT_TOO_MANY;
1056 page_first_line = line;
1059 /* Recalculate forces for the last page because we know now that is
1060 really the last page. */
1061 space.resize (page_height (first_page_num + page, true));
1062 res.force_.back () = space.force_;
1063 return finalize_spacing_result (configuration, res);
1067 Page_breaking::pack_systems_on_least_pages (vsize configuration, vsize first_page_num)
1069 // TODO: add support for min/max-systems-per-page.
1070 Page_spacing_result res;
1072 vsize page_first_line = 0;
1073 Page_spacing space (page_height (first_page_num, false), this);
1075 cache_line_details (configuration);
1076 for (vsize line = 0; line < cached_line_details_.size (); line++)
1078 Real prev_force = space.force_;
1079 space.append_system (cached_line_details_[line]);
1080 if ((line > page_first_line)
1081 && (isinf (space.force_)
1083 && (cached_line_details_[line-1].page_permission_ == ly_symbol2scm ("force")))))
1085 res.systems_per_page_.push_back (line - page_first_line);
1086 res.force_.push_back (prev_force);
1087 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1089 space.resize (page_height (first_page_num + page, false));
1091 space.append_system (cached_line_details_[line]);
1092 page_first_line = line;
1095 if (line == cached_line_details_.size () - 1)
1097 /* This is the last line */
1098 /* When the last page height was computed, we did not know yet that it
1099 * was the last one. If the systems put on it don't fit anymore, the last
1100 * system is moved to a new page */
1101 space.resize (page_height (first_page_num + page, true));
1102 if ((line > page_first_line) && (isinf (space.force_)))
1104 res.systems_per_page_.push_back (line - page_first_line);
1105 res.force_.push_back (prev_force);
1106 /* the last page containing the last line */
1107 space.resize (page_height (first_page_num + page + 1, true));
1109 space.append_system (cached_line_details_[line]);
1110 res.systems_per_page_.push_back (1);
1111 res.force_.push_back (space.force_);
1112 res.penalty_ += cached_line_details_[line-1].page_penalty_;
1113 res.penalty_ += cached_line_details_[line].page_penalty_;
1117 res.systems_per_page_.push_back (line + 1 - page_first_line);
1118 res.force_.push_back (space.force_);
1119 res.penalty_ += cached_line_details_[line].page_penalty_;
1123 return finalize_spacing_result (configuration, res);
1126 /* Calculate demerits and fix res.systems_per_page_ so that
1127 it refers to the original line numbers, not the ones given by compress_lines (). */
1129 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
1131 if (res.force_.empty ())
1134 cache_line_details (configuration);
1135 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
1137 Real line_force = 0;
1138 Real line_penalty = 0;
1139 Real page_demerits = res.penalty_;
1140 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
1142 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
1144 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
1145 line_penalty += uncompressed_line_details_[i].break_penalty_;
1148 for (vsize i = 0; i < res.force_.size (); i++)
1150 Real f = res.force_[i];
1152 page_demerits += min(f*f, BAD_SPACING_PENALTY);
1155 /* for a while we tried averaging page and line forces across pages instead
1156 of summing them, but it caused a problem: if there is a single page
1157 with a very bad page force (for example because of a forced page break),
1158 the page breaker will put in a _lot_ of pages so that the bad force
1159 becomes averaged out over many pages. */
1160 res.demerits_ = line_force + line_penalty + page_demerits * page_weighting;
1165 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1166 are by far the most common cases, we have special functions for them.
1168 space_systems_on_1_page has a different calling convention than most of the
1169 space_systems functions. This is because space_systems_on_1_page is (unlike
1170 the other space_systems functions) sometimes called on subsets of a full
1173 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
1175 Page_spacing space (page_height, this);
1176 Page_spacing_result ret;
1179 for (vsize i = 0; i < lines.size (); i++)
1181 space.append_system (lines[i]);
1182 line_count += lines[i].compressed_nontitle_lines_count_;
1185 ret.systems_per_page_.push_back (lines.size ());
1186 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
1187 ret.penalty_ = line_count_penalty (line_count) + lines.back ().page_penalty_ + lines.back ().turn_penalty_;
1188 ret.system_count_status_ |= line_count_status (line_count);
1190 /* don't do finalize_spacing_result () because we are only an internal function */
1195 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
1197 Real page1_height = page_height (first_page_num, false);
1198 Real page2_height = page_height (first_page_num + 1, is_last ());
1199 bool ragged1 = ragged ();
1200 bool ragged2 = ragged () || (is_last () && ragged_last ());
1202 /* if there is a forced break, this reduces to 2 1-page problems */
1203 cache_line_details (configuration);
1204 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
1205 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
1207 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
1208 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
1209 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
1210 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
1212 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
1213 p1.force_.push_back (p2.force_[0]);
1214 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
1218 vector<Real> page1_force;
1219 vector<Real> page2_force;
1221 // page1_penalty and page2_penalty store the penalties based
1222 // on min-systems-per-page and max-systems-per-page.
1223 vector<Real> page1_penalty;
1224 vector<Real> page2_penalty;
1226 // page1_status and page2_status keep track of whether the min-systems-per-page
1227 // and max-systems-per-page constraints are satisfied.
1228 vector<int> page1_status;
1229 vector<int> page2_status;
1231 Page_spacing page1 (page1_height, this);
1232 Page_spacing page2 (page2_height, this);
1233 int page1_line_count = 0;
1234 int page2_line_count = 0;
1236 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
1237 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
1238 page1_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1239 page2_penalty.resize (cached_line_details_.size () - 1, infinity_f);
1240 page1_status.resize (cached_line_details_.size () - 1, 0);
1241 page2_status.resize (cached_line_details_.size () - 1, 0);
1243 /* find the page 1 and page 2 forces for each page-breaking position */
1244 for (vsize i = 0; i < page1_force.size (); i++)
1246 page1.append_system (cached_line_details_[i]);
1247 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
1248 page1_line_count += cached_line_details_[i].compressed_nontitle_lines_count_;
1249 page2_line_count += cached_line_details_[cached_line_details_.size () - 1 - i].compressed_nontitle_lines_count_;
1251 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
1252 page1_penalty[i] = line_count_penalty (page1_line_count);
1253 page1_status[i] = line_count_status (page1_line_count);
1256 page2_force[page2_force.size () - 1 - i] =
1257 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
1259 page2_force[page2_force.size () - 1 - i] = page2.force_;
1260 page2_penalty[page2_penalty.size () - 1 - i] = line_count_penalty (page2_line_count);
1261 page2_status[page2_penalty.size () - 1 - i] = line_count_status (page2_line_count);
1264 /* find the position that minimises the sum of the page forces */
1265 vsize best_sys_count = 1;
1266 Real best_demerits = infinity_f;
1267 for (vsize i = 0; i < page1_force.size (); i++)
1269 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
1271 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1272 // constraints. That is, we penalize harshly when they don't happen
1273 // but we don't completely reject.
1275 + page1_penalty[i] + page2_penalty[i]
1276 + cached_line_details_[i+1].page_penalty_
1277 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
1278 if (dem < best_demerits)
1280 best_demerits = dem;
1281 best_sys_count = i+1;
1285 Page_spacing_result ret;
1286 ret.systems_per_page_.push_back (best_sys_count);
1287 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
1288 ret.force_.push_back (page1_force[best_sys_count-1]);
1289 ret.force_.push_back (page2_force[best_sys_count-1]);
1290 ret.system_count_status_ = page1_status[best_sys_count-1] | page2_status[best_sys_count-1];
1291 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
1292 + cached_line_details_.back ().page_penalty_
1293 + cached_line_details_.back ().turn_penalty_
1294 + page1_penalty[best_sys_count-1] + page2_penalty[best_sys_count-1];
1296 /* don't do finalize_spacing_result () because we are only an internal function */
1301 Page_breaking::all_lines_stretched (vsize configuration)
1303 cache_line_details (configuration);
1304 for (vsize i = 0; i < cached_line_details_.size (); i++)
1305 if (cached_line_details_[i].force_ < 0)
1311 Page_breaking::Line_division
1312 Page_breaking::current_configuration (vsize configuration_index) const
1314 return current_configurations_[configuration_index];
1318 Page_breaking::is_last () const
1320 return current_end_breakpoint_ == last_break_position ();
1324 Page_breaking::ends_score () const
1326 return breaks_[current_end_breakpoint_].score_ender_;
1330 Page_breaking::last_break_position () const
1332 return breaks_.size () - 1;
1335 // This gives the minimum distance between the top of the
1336 // printable area (ie. the bottom of the top-margin) and
1337 // the extent box of the topmost system.
1339 Page_breaking::min_whitespace_at_top_of_page (Line_details const &line) const
1341 SCM first_system_spacing = book_->paper_->c_variable ("first-system-spacing");
1343 first_system_spacing = book_->paper_->c_variable ("first-system-title-spacing");
1345 Real min_distance = -infinity_f;
1348 Page_layout_problem::read_spacing_spec (first_system_spacing,
1350 ly_symbol2scm ("minimum-distance"));
1351 Page_layout_problem::read_spacing_spec (first_system_spacing,
1353 ly_symbol2scm ("padding"));
1355 // FIXME: take into account the height of the header
1356 return max (0.0, max (padding, min_distance - line.extent_[UP]));
1360 Page_breaking::min_whitespace_at_bottom_of_page (Line_details const &line) const
1362 SCM last_system_spacing = book_->paper_->c_variable ("last-system-spacing");
1363 Real min_distance = -infinity_f;
1366 Page_layout_problem::read_spacing_spec (last_system_spacing,
1368 ly_symbol2scm ("minimum-distance"));
1369 Page_layout_problem::read_spacing_spec (last_system_spacing,
1371 ly_symbol2scm ("padding"));
1373 // FIXME: take into account the height of the footer
1374 return max (0.0, max (padding, min_distance + line.extent_[DOWN]));