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--2007 Joe Neeman <joeneeman@gmail.com>
10 #include "page-breaking.hh"
12 #include "international.hh"
14 #include "output-def.hh"
15 #include "page-spacing.hh"
16 #include "paper-book.hh"
17 #include "paper-score.hh"
18 #include "paper-system.hh"
22 /* for each forbidden page break, merge the systems around it into one system. */
23 static vector<Line_details>
24 compress_lines (const vector<Line_details> &orig)
26 vector<Line_details> ret;
28 for (vsize i = 0; i < orig.size (); i++)
30 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
32 Line_details const &old = ret.back ();
33 Line_details compressed = orig[i];
34 compressed.extent_[DOWN] = old.extent_[DOWN];
35 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
36 compressed.space_ += old.space_;
37 compressed.inverse_hooke_ += old.inverse_hooke_;
39 /* we don't need the force_ field for the vertical spacing,
40 so we use force_ = n to signal that the line was compressed,
41 reducing the number of lines by n (and force_ = 0 otherwise).
42 This makes uncompression much easier. */
43 compressed.force_ = old.force_ + 1;
44 ret.back () = compressed;
48 ret.push_back (orig[i]);
49 ret.back ().force_ = 0;
55 /* translate the number of systems-per-page into something meaningful for
56 the uncompressed lines.
59 uncompress_solution (vector<vsize> const &systems_per_page,
60 vector<Line_details> const &compressed)
65 for (vsize i = 0; i < systems_per_page.size (); i++)
67 int compressed_count = 0;
68 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
69 compressed_count += (int)compressed[j].force_;
71 ret.push_back (systems_per_page[i] + compressed_count);
72 start_sys += systems_per_page[i];
77 /* for Page_breaking, the start index (when we are dealing with the stuff
78 between a pair of breakpoints) refers to the break_ index of the end of
79 the previous page. So the system index of the start of the current page
80 could either be the same as the end of the previous page or one more than
83 /* Turn a break index into the sys index that starts the next page */
85 Page_breaking::next_system (Break_position const &break_pos) const
87 vsize sys = break_pos.sys_;
89 if (sys == VPOS) /* beginning of the book */
91 if (all_[sys].pscore_ && !break_pos.score_ender_)
92 return sys; /* the score overflows the previous page */
93 return sys + 1; /* this page starts with a new sys */
96 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
99 ragged_ = to_boolean (pb->paper_->c_variable ("ragged"));
100 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last"));
101 create_system_list ();
102 find_chunks_and_breaks (is_break);
105 Page_breaking::~Page_breaking ()
110 Page_breaking::ragged () const
116 Page_breaking::ragged_last () const
121 /* translate indices into breaks_ into start-end parameters for the line breaker */
123 Page_breaking::line_breaker_args (vsize sys,
124 Break_position const &start,
125 Break_position const &end,
126 vsize *line_breaker_start,
127 vsize *line_breaker_end)
129 assert (all_[sys].pscore_);
130 assert (next_system (start) <= sys && sys <= end.sys_);
132 if (start.sys_ == sys)
133 *line_breaker_start = start.score_break_;
135 *line_breaker_start = 0;
138 *line_breaker_end = end.score_break_;
140 *line_breaker_end = VPOS;
144 Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div)
146 vector<Break_position> chunks = chunk_list (start_break, end_break);
147 bool ignore_div = false;
148 if (chunks.size () != div.size () + 1)
150 programming_error ("did not find a valid page breaking configuration");
154 for (vsize i = 0; i + 1 < chunks.size (); i++)
156 vsize sys = next_system (chunks[i]);
157 if (all_[sys].pscore_)
161 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
163 vector<Column_x_positions> pos = ignore_div
164 ? line_breaking_[sys].best_solution (start, end)
165 : line_breaking_[sys].solve (start, end, div[i]);
166 all_[sys].pscore_->root_system ()->break_into_pieces (pos);
172 Page_breaking::systems ()
175 for (vsize sys = 0; sys < all_.size (); sys++)
177 if (all_[sys].pscore_)
179 all_[sys].pscore_->root_system ()->do_break_substitution_and_fixup_refpoints ();
180 SCM lines = all_[sys].pscore_->root_system ()->get_broken_system_grobs ();
181 ret = scm_cons (lines, ret);
185 Prob *pb = all_[sys].prob_;
186 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
190 return scm_append (scm_reverse (ret));
194 Page_breaking::page_height (int page_num, bool last) const
196 SCM mod = scm_c_resolve_module ("scm page");
197 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
198 SCM make_page = scm_c_module_lookup (mod, "make-page");
200 calc_height = scm_variable_ref (calc_height);
201 make_page = scm_variable_ref (make_page);
203 SCM page = scm_apply_0 (make_page, scm_list_n (
205 ly_symbol2scm ("page-number"), scm_from_int (page_num),
206 ly_symbol2scm ("is-last"), scm_from_bool (last),
208 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
209 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
213 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
215 Break_position const &pos = breaks_[breakpoint];
217 if (pos.sys_ == VPOS)
219 if (all_[pos.sys_].pscore_)
220 return pos.col_->get_property (str);
221 return all_[pos.sys_].prob_->get_property (str);
225 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
227 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
228 SCM page_module = scm_c_resolve_module ("scm page");
230 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
231 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
232 make_page = scm_variable_ref (make_page);
233 page_stencil = scm_variable_ref (page_stencil);
235 SCM book = book_->self_scm ();
236 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
237 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
238 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
241 for (vsize i = 0; i < lines_per_page.size (); i++)
243 SCM page_num = scm_from_int (i + first_page_number);
244 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
245 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
246 SCM line_count = scm_from_int (lines_per_page[i]);
247 SCM lines = scm_list_head (systems, line_count);
248 SCM page = scm_apply_0 (make_page,
249 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
251 scm_apply_1 (page_stencil, page, SCM_EOL);
252 ret = scm_cons (page, ret);
253 systems = scm_list_tail (systems, line_count);
255 ret = scm_reverse (ret);
259 /* The page-turn-page-breaker needs to have a line-breaker between any two
260 columns with non-NULL page-turn-permission.
262 The optimal-breaker needs to have a line-breaker between any two columns
263 with page-break-permission = 'force.
265 By using a grob predicate, we can accommodate both of these uses.
268 Page_breaking::create_system_list ()
270 SCM specs = book_->get_system_specs ();
271 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
273 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
275 SCM system_count = ps->layout ()->c_variable ("system-count");
277 if (scm_is_number (system_count))
278 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
279 scm_vector_to_list (ps->get_paper_systems ()),
282 all_.push_back (System_spec (ps));
286 Prob *pb = unsmob_prob (scm_car (s));
290 all_.push_back (System_spec (pb));
296 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
298 SCM force_sym = ly_symbol2scm ("force");
300 chunks_.push_back (Break_position ());
301 breaks_.push_back (Break_position ());
303 for (vsize i = 0; i < all_.size (); i++)
307 vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
308 vector<vsize> line_breaker_columns;
309 line_breaker_columns.push_back (0);
311 for (vsize j = 1; j < cols.size (); j++)
313 bool last = j == cols.size () - 1;
314 bool break_point = is_break (cols[j]);
315 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
316 Break_position cur_pos = Break_position (i,
317 line_breaker_columns.size (),
321 if (break_point || (i == all_.size () - 1 && last))
322 breaks_.push_back (cur_pos);
323 if (chunk_end || last)
324 chunks_.push_back (cur_pos);
326 if ((break_point || chunk_end) && !last)
327 line_breaker_columns.push_back (j);
329 line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
333 /* TODO: we want some way of applying Break_p to a prob? */
334 if (i == all_.size () - 1)
335 breaks_.push_back (Break_position (i));
337 chunks_.push_back (Break_position (i));
338 line_breaking_.push_back (Constrained_breaking (NULL));
343 vector<Break_position>
344 Page_breaking::chunk_list (vsize start_index, vsize end_index)
346 Break_position start = breaks_[start_index];
347 Break_position end = breaks_[end_index];
350 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
353 vector<Break_position> ret;
354 ret.push_back (start);
355 for (; i < chunks_.size () && chunks_[i] < end; i++)
356 ret.push_back (chunks_[i]);
362 Page_breaking::min_system_count (vsize start, vsize end)
364 vector<Break_position> chunks = chunk_list (start, end);
365 Line_division div = system_count_bounds (chunks, true);
368 for (vsize i = 0; i < div.size (); i++)
374 Page_breaking::max_system_count (vsize start, vsize end)
376 vector<Break_position> chunks = chunk_list (start, end);
377 Line_division div = system_count_bounds (chunks, false);
380 for (vsize i = 0; i < div.size (); i++)
385 Page_breaking::Line_division
386 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
388 assert (chunks.size () >= 2);
391 ret.resize (chunks.size () - 1, 1);
393 for (vsize i = 0; i + 1 < chunks.size (); i++)
395 vsize sys = next_system (chunks[i]);
396 if (all_[sys].pscore_)
400 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
402 ? line_breaking_[sys].min_system_count (start, end)
403 : line_breaking_[sys].max_system_count (start, end);
411 Page_breaking::set_current_breakpoints (vsize start,
414 Line_division lower_bound,
415 Line_division upper_bound)
417 current_chunks_ = chunk_list (start, end);
418 current_start_breakpoint_ = start;
419 current_end_breakpoint_ = end;
420 clear_line_details_cache ();
422 if (!lower_bound.size ())
423 lower_bound = system_count_bounds (current_chunks_, true);
424 if (!upper_bound.size ())
425 upper_bound = system_count_bounds (current_chunks_, false);
427 assert (lower_bound.size () == current_chunks_.size () - 1);
428 assert (upper_bound.size () == current_chunks_.size () - 1);
430 Line_division work_in_progress;
431 current_configurations_.clear ();
432 line_divisions_rec (system_count,
439 Page_breaking::current_configuration_count () const
441 return current_configurations_.size ();
445 Page_breaking::cache_line_details (vsize configuration_index)
447 if (cached_configuration_index_ != configuration_index)
449 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
450 if (!scm_is_number (padding_scm))
451 padding_scm = book_->paper_->c_variable ("between-system-padding");
452 Real padding = robust_scm2double (padding_scm, 0.0);
454 Line_division &div = current_configurations_[configuration_index];
455 cached_line_details_.clear ();
456 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
458 vsize sys = next_system (current_chunks_[i]);
459 if (all_[sys].pscore_)
463 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
465 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
466 cached_line_details_.insert (cached_line_details_.end (), details.begin (), details.end ());
470 assert (div[i] == 1);
471 cached_line_details_.push_back (Line_details (all_[sys].prob_));
472 cached_line_details_.back ().padding_ = padding;
475 cached_line_details_ = compress_lines (cached_line_details_);
480 Page_breaking::clear_line_details_cache ()
482 cached_configuration_index_ = VPOS;
483 cached_line_details_.clear ();
487 Page_breaking::line_divisions_rec (vsize system_count,
488 Line_division const &min_sys,
489 Line_division const &max_sys,
490 Line_division *cur_division)
492 vsize my_index = cur_division->size ();
493 vsize others_min = 0;
494 vsize others_max = 0;
496 for (vsize i = my_index + 1; i < min_sys.size (); i++)
498 others_min += min_sys[i];
499 others_max += max_sys[i];
501 others_max = min (others_max, system_count);
502 vsize real_min = max (min_sys[my_index], system_count - others_max);
503 vsize real_max = min (max_sys[my_index], system_count - others_min);
505 if (real_min > real_max || real_min <= 0)
507 /* this should never happen within a recursive call. If it happens
508 at all, it means that we were called with an unsolvable problem
509 and we should return an empty result */
510 assert (my_index == 0);
514 for (vsize i = real_min; i <= real_max; i++)
516 cur_division->push_back (i);
517 if (my_index == min_sys.size () - 1)
518 current_configurations_.push_back (*cur_division);
520 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
521 cur_division->pop_back ();
526 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
529 Real cur_rod_height = 0;
530 Real cur_spring_height = 0;
531 Real cur_page_height = page_height (first_page_num, false);
533 cache_line_details (configuration);
534 for (vsize i = 0; i < cached_line_details_.size (); i++)
536 Real ext_len = cached_line_details_[i].extent_.length ();
537 Real next_rod_height = cur_rod_height + ext_len
538 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
539 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
540 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
543 if ((next_height > cur_page_height && cur_rod_height > 0)
544 || (i + 1 < cached_line_details_.size ()
545 && cached_line_details_[i].page_permission_ == ly_symbol2scm ("force")))
547 cur_rod_height = ext_len;
548 cur_spring_height = line_space (cached_line_details_[i]);
549 cur_page_height = page_height (first_page_num + ret, false);
554 cur_rod_height = next_rod_height;
555 cur_spring_height = next_spring_height;
559 /* there are two potential problems with the last page (because we didn't know
560 it was the last page until after we managed to fit all the systems to it):
561 - we are ragged-last but the last page has a compressed spring
562 - the value returned by page_height (num, true) is smaller than the
563 value returned by page_height (num, false) and it causes the page not to
566 In either case, we just need to add one more page. This is because the last
567 line will always fit on the extra page and by adding one more page to the
568 end, the previous page is no longer the last page, so our previous
569 calculations that treated it as a non-last page were ok.
572 cur_page_height = page_height (first_page_num + ret - 1, true);
573 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
574 if (cur_height > cur_page_height
575 /* don't increase the page count if the last page had only one system */
576 && cur_rod_height > cached_line_details_.back ().extent_.length ())
582 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
585 assert (n >= min_page_count (configuration, first_page_num));
587 cache_line_details (configuration);
588 if (n > cached_line_details_.size ())
589 return Spacing_result ();
591 ret = space_systems_on_1_page (cached_line_details_,
592 page_height (first_page_num, last ()),
593 ragged () || (last () && ragged_last ()));
595 ret = space_systems_on_2_pages (configuration, first_page_num);
598 Page_spacer ps (cached_line_details_, first_page_num, this);
602 return finalize_spacing_result (configuration, ret);
606 Page_breaking::blank_page_penalty () const
608 SCM penalty_sym = last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
609 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
613 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
615 Spacing_result n_res = space_systems_on_n_pages (configuration, n, first_page_num);
616 Spacing_result m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
617 Real penalty = blank_page_penalty ();
618 n_res.demerits_ += penalty;
619 n_res.force_.back () += penalty;
621 if (n_res.demerits_ < m_res.demerits_)
627 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
629 vsize min_p_count = min_page_count (configuration, first_page_num);
630 Real odd_pages_penalty = blank_page_penalty ();
632 cache_line_details (configuration);
633 Page_spacer ps (cached_line_details_, first_page_num, this);
634 Spacing_result best = ps.solve (min_p_count);
635 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
636 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
638 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
640 Spacing_result cur = ps.solve (i);
641 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
642 if (cur.demerits_ < best.demerits_)
646 return finalize_spacing_result (configuration, best);
649 /* Calculate demerits and fix res.systems_per_page_ so that
650 it refers to the original line numbers, not the ones given by compress_lines (). */
652 Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res)
654 cache_line_details (configuration);
655 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
658 Real line_penalty = 0;
660 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
662 for (vsize i = 0; i < cached_line_details_.size (); i++)
664 line_force += cached_line_details_[i].force_ * cached_line_details_[i].force_;
665 line_penalty += cached_line_details_[i].break_penalty_;
668 for (vsize i = 0; i < res.force_.size (); i++)
669 page_force += res.force_[i] * res.force_[i];
671 /* for a while we tried averaging page and line forces across pages instead
672 of summing them, but it caused a problem: if there is a single page
673 with a very bad page force (for example because of a forced page break),
674 the page breaker will put in a _lot_ of pages so that the bad force
675 becomes averaged out over many pages. */
676 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
681 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
682 are by far the most common cases, we have special functions for them.
684 space_systems_on_1_page has a different calling convention than most of the
685 space_systems functions. This is because space_systems_on_1_page is (unlike
686 the other space_systems functions) sometimes called on subsets of a full
689 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
691 Page_spacing space (page_height);
694 for (vsize i = 0; i < lines.size (); i++)
695 space.append_system (lines[i]);
697 ret.systems_per_page_.push_back (lines.size ());
698 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
699 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
701 /* don't do finalize_spacing_result () because we are only an internal function */
706 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
708 Real page1_height = page_height (first_page_num, false);
709 Real page2_height = page_height (first_page_num+1, last ());
710 bool ragged1 = ragged ();
711 bool ragged2 = ragged () || (last () && ragged_last ());
713 /* if there is a forced break, this reduces to 2 1-page problems */
714 cache_line_details (configuration);
715 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
716 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
718 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
719 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
720 Spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
721 Spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
723 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
724 p1.force_.push_back (p2.force_[0]);
725 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
729 vector<Real> page1_force;
730 vector<Real> page2_force;
731 Page_spacing page1 (page1_height);
732 Page_spacing page2 (page2_height);
734 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
735 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
737 /* find the page 1 and page 2 forces for each page-breaking position */
738 for (vsize i = 0; i < page1_force.size (); i++)
740 page1.append_system (cached_line_details_[i]);
741 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
742 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
745 page2_force[page2_force.size () - 1 - i] =
746 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
748 page2_force[page2_force.size () - 1 - i] = page2.force_;
751 /* find the position that minimises the sum of the page forces */
752 vsize best_sys_count = 1;
753 Real best_demerits = infinity_f;
754 for (vsize i = 0; i < page1_force.size (); i++)
756 Real dem = page1_force[i] * page1_force[i]
757 + page2_force[i] * page2_force[i]
758 + cached_line_details_[i+1].page_penalty_
759 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
760 if (dem < best_demerits)
763 best_sys_count = i+1;
768 ret.systems_per_page_.push_back (best_sys_count);
769 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
770 ret.force_.push_back (page1_force[best_sys_count-1]);
771 ret.force_.push_back (page2_force[best_sys_count-1]);
772 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
773 + cached_line_details_.back ().page_penalty_
774 + cached_line_details_.back ().turn_penalty_;
776 /* don't do finalize_spacing_result () because we are only an internal function */
781 Page_breaking::all_lines_stretched (vsize configuration)
783 cache_line_details (configuration);
784 for (vsize i = 0; i < cached_line_details_.size (); i++)
785 if (cached_line_details_[i].force_ < 0)
791 Page_breaking::Line_division
792 Page_breaking::current_configuration (vsize configuration_index) const
794 return current_configurations_[configuration_index];
797 bool Page_breaking::last () const
799 return current_end_breakpoint_ == breaks_.size () - 1;