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
24 static vector<Line_details>
25 compress_lines (const vector<Line_details> &orig)
27 vector<Line_details> ret;
29 for (vsize i = 0; i < orig.size (); i++)
31 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
33 Line_details const &old = ret.back ();
34 Line_details compressed = orig[i];
35 compressed.extent_[DOWN] = old.extent_[DOWN];
36 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
37 compressed.space_ += old.space_;
38 compressed.inverse_hooke_ += old.inverse_hooke_;
40 /* we don't need the force_ field for the vertical spacing,
41 so we use force_ = n to signal that the line was compressed,
42 reducing the number of lines by n (and force_ = 0 otherwise).
43 This makes uncompression much easier. */
44 compressed.force_ = old.force_ + 1;
45 ret.back () = compressed;
49 ret.push_back (orig[i]);
50 ret.back ().force_ = 0;
56 /* translate the number of systems-per-page into something meaningful for
57 the uncompressed lines.
60 uncompress_solution (vector<vsize> const &systems_per_page,
61 vector<Line_details> const &compressed)
66 for (vsize i = 0; i < systems_per_page.size (); i++)
68 int compressed_count = 0;
69 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
70 compressed_count += (int)compressed[j].force_;
72 ret.push_back (systems_per_page[i] + compressed_count);
73 start_sys += systems_per_page[i];
78 /* for Page_breaking, the start index (when we are dealing with the stuff
79 between a pair of breakpoints) refers to the break_ index of the end of
80 the previous page. So the system index of the start of the current page
81 could either be the same as the end of the previous page or one more than
84 /* Turn a break index into the sys index that starts the next page */
86 Page_breaking::next_system (Break_position const &break_pos) const
88 vsize sys = break_pos.system_spec_index_;
90 if (sys == VPOS) /* beginning of the book */
92 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
93 return sys; /* the score overflows the previous page */
94 return sys + 1; /* this page starts with a new System_spec */
97 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
100 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
101 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
102 create_system_list ();
103 find_chunks_and_breaks (is_break);
106 Page_breaking::~Page_breaking ()
111 Page_breaking::ragged () const
117 Page_breaking::ragged_last () const
122 /* translate indices into breaks_ into start-end parameters for the line breaker */
124 Page_breaking::line_breaker_args (vsize sys,
125 Break_position const &start,
126 Break_position const &end,
127 vsize *line_breaker_start,
128 vsize *line_breaker_end)
130 assert (system_specs_[sys].pscore_);
131 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
133 if (start.system_spec_index_ == sys)
134 *line_breaker_start = start.score_break_;
136 *line_breaker_start = 0;
138 if (end.system_spec_index_ == sys)
139 *line_breaker_end = end.score_break_;
141 *line_breaker_end = VPOS;
145 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
146 Line_division const &div)
148 vector<Break_position> chunks = chunk_list (start_break, end_break);
149 bool ignore_div = false;
150 if (chunks.size () != div.size () + 1)
152 programming_error ("did not find a valid page breaking configuration");
156 for (vsize i = 0; i + 1 < chunks.size (); i++)
158 vsize sys = next_system (chunks[i]);
159 if (system_specs_[sys].pscore_)
163 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
165 vector<Column_x_positions> pos = ignore_div
166 ? line_breaking_[sys].best_solution (start, end)
167 : line_breaking_[sys].solve (start, end, div[i]);
168 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
174 Page_breaking::systems ()
177 for (vsize sys = 0; sys < system_specs_.size (); sys++)
179 if (system_specs_[sys].pscore_)
181 system_specs_[sys].pscore_->root_system ()
182 ->do_break_substitution_and_fixup_refpoints ();
183 SCM lines = system_specs_[sys].pscore_->root_system ()
184 ->get_broken_system_grobs ();
185 ret = scm_cons (lines, ret);
189 Prob *pb = system_specs_[sys].prob_;
190 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
194 return scm_append (scm_reverse (ret));
198 Page_breaking::page_height (int page_num, bool last) const
200 SCM mod = scm_c_resolve_module ("scm page");
201 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
202 SCM make_page = scm_c_module_lookup (mod, "make-page");
204 calc_height = scm_variable_ref (calc_height);
205 make_page = scm_variable_ref (make_page);
207 SCM page = scm_apply_0 (make_page, scm_list_n (
209 ly_symbol2scm ("page-number"), scm_from_int (page_num),
210 ly_symbol2scm ("is-last"), scm_from_bool (last),
212 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
213 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
217 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
219 Break_position const &pos = breaks_[breakpoint];
221 if (pos.system_spec_index_ == VPOS)
223 if (system_specs_[pos.system_spec_index_].pscore_)
224 return pos.col_->get_property (str);
225 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
229 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
231 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
232 SCM page_module = scm_c_resolve_module ("scm page");
234 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
235 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
236 make_page = scm_variable_ref (make_page);
237 page_stencil = scm_variable_ref (page_stencil);
239 SCM book = book_->self_scm ();
240 int first_page_number
241 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
243 SCM label_page_table = SCM_EOL;
245 for (vsize i = 0; i < lines_per_page.size (); i++)
247 SCM page_num = scm_from_int (i + first_page_number);
248 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
249 SCM rag = scm_from_bool (ragged () || (to_boolean (last)
251 SCM line_count = scm_from_int (lines_per_page[i]);
252 SCM lines = scm_list_head (systems, line_count);
253 SCM page = scm_apply_0 (make_page,
254 scm_list_n (book, lines, page_num,
255 rag, last, SCM_UNDEFINED));
258 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
260 SCM labels = SCM_EOL;
261 if (Grob * line = unsmob_grob (scm_car (l)))
263 System *system = dynamic_cast<System*> (line);
264 labels = system->get_property ("labels");
266 else if (Prob *prob = unsmob_prob (scm_car (l)))
267 labels = prob->get_property ("labels");
269 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
270 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
274 scm_apply_1 (page_stencil, page, SCM_EOL);
275 ret = scm_cons (page, ret);
276 systems = scm_list_tail (systems, line_count);
278 book_->paper_->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
279 ret = scm_reverse (ret);
283 /* The page-turn-page-breaker needs to have a line-breaker between any two
284 columns with non-NULL page-turn-permission.
286 The optimal-breaker needs to have a line-breaker between any two columns
287 with page-break-permission = 'force.
289 By using a grob predicate, we can accommodate both of these uses.
292 Page_breaking::create_system_list ()
294 SCM specs = book_->get_system_specs ();
295 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
297 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
299 SCM system_count = ps->layout ()->c_variable ("system-count");
301 if (scm_is_number (system_count))
302 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
303 scm_vector_to_list (ps->get_paper_systems ()),
306 system_specs_.push_back (System_spec (ps));
310 Prob *pb = unsmob_prob (scm_car (s));
314 system_specs_.push_back (System_spec (pb));
320 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
322 SCM force_sym = ly_symbol2scm ("force");
324 chunks_.push_back (Break_position ());
325 breaks_.push_back (Break_position ());
327 for (vsize i = 0; i < system_specs_.size (); i++)
329 if (system_specs_[i].pscore_)
332 = system_specs_[i].pscore_->root_system ()->used_columns ();
333 vector<vsize> line_breaker_columns;
334 line_breaker_columns.push_back (0);
336 for (vsize j = 1; j < cols.size (); j++)
338 bool last = (j == cols.size () - 1);
339 bool break_point = is_break (cols[j]);
340 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
341 Break_position cur_pos = Break_position (i,
342 line_breaker_columns.size (),
346 if (break_point || (i == system_specs_.size () - 1 && last))
347 breaks_.push_back (cur_pos);
348 if (chunk_end || last)
349 chunks_.push_back (cur_pos);
351 if ((break_point || chunk_end) && !last)
352 line_breaker_columns.push_back (j);
354 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
358 /* TODO: we want some way of applying Break_p to a prob? */
359 if (i == system_specs_.size () - 1)
360 breaks_.push_back (Break_position (i));
362 chunks_.push_back (Break_position (i));
364 /* FIXME: shouldn't we push a Null_breaker or similar dummy
366 line_breaking_.push_back (Constrained_breaking (NULL));
371 vector<Break_position>
372 Page_breaking::chunk_list (vsize start_index, vsize end_index)
374 Break_position start = breaks_[start_index];
375 Break_position end = breaks_[end_index];
378 for (; i < chunks_.size () && chunks_[i] <= start; i++)
381 vector<Break_position> ret;
382 ret.push_back (start);
383 for (; i < chunks_.size () && chunks_[i] < end; i++)
384 ret.push_back (chunks_[i]);
390 Page_breaking::min_system_count (vsize start, vsize end)
392 vector<Break_position> chunks = chunk_list (start, end);
393 Line_division div = system_count_bounds (chunks, true);
396 for (vsize i = 0; i < div.size (); i++)
402 Page_breaking::max_system_count (vsize start, vsize end)
404 vector<Break_position> chunks = chunk_list (start, end);
405 Line_division div = system_count_bounds (chunks, false);
408 for (vsize i = 0; i < div.size (); i++)
413 Page_breaking::Line_division
414 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
417 assert (chunks.size () >= 2);
420 ret.resize (chunks.size () - 1, 1);
422 for (vsize i = 0; i + 1 < chunks.size (); i++)
424 vsize sys = next_system (chunks[i]);
425 if (system_specs_[sys].pscore_)
429 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
431 ? line_breaking_[sys].min_system_count (start, end)
432 : line_breaking_[sys].max_system_count (start, end);
440 Page_breaking::set_current_breakpoints (vsize start,
443 Line_division lower_bound,
444 Line_division upper_bound)
446 current_chunks_ = chunk_list (start, end);
447 current_start_breakpoint_ = start;
448 current_end_breakpoint_ = end;
449 clear_line_details_cache ();
451 if (!lower_bound.size ())
452 lower_bound = system_count_bounds (current_chunks_, true);
453 if (!upper_bound.size ())
454 upper_bound = system_count_bounds (current_chunks_, false);
456 assert (lower_bound.size () == current_chunks_.size () - 1);
457 assert (upper_bound.size () == current_chunks_.size () - 1);
459 Line_division work_in_progress;
460 current_configurations_.clear ();
461 line_divisions_rec (system_count,
466 /* we only consider a constant number of configurations. Otherwise,
467 this becomes slow when there are many small scores. The constant
468 5 is somewhat arbitrary. */
469 if (current_configurations_.size () > 5)
471 vector<pair<Real,vsize> > dems_and_indices;
473 for (vsize i = 0; i < current_configurations_.size (); i++)
475 cache_line_details (i);
477 for (vsize j = 0; j < cached_line_details_.size (); j++)
478 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
479 + cached_line_details_[j].break_penalty_;
481 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
483 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
485 vector<Line_division> best_5_configurations;
486 for (vsize i = 0; i < 5; i++)
487 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
489 clear_line_details_cache ();
490 current_configurations_ = best_5_configurations;
495 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
497 current_chunks_ = chunk_list (start, end);
498 current_start_breakpoint_ = start;
499 current_end_breakpoint_ = end;
500 clear_line_details_cache ();
503 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
505 vsize sys = next_system (current_chunks_[i]);
506 if (system_specs_[sys].pscore_)
508 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
509 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
514 current_configurations_.clear ();
515 current_configurations_.push_back (div);
519 Page_breaking::current_configuration_count () const
521 return current_configurations_.size ();
525 Page_breaking::cache_line_details (vsize configuration_index)
527 if (cached_configuration_index_ != configuration_index)
529 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
530 if (!scm_is_number (padding_scm))
531 padding_scm = book_->paper_->c_variable ("between-system-padding");
532 Real padding = robust_scm2double (padding_scm, 0.0);
534 Line_division &div = current_configurations_[configuration_index];
535 uncompressed_line_details_.clear ();
536 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
538 vsize sys = next_system (current_chunks_[i]);
539 if (system_specs_[sys].pscore_)
543 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
545 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
546 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
550 assert (div[i] == 1);
551 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
552 uncompressed_line_details_.back ().padding_ =
553 robust_scm2double (system_specs_[sys].prob_->get_property ("next-padding"),
557 cached_line_details_ = compress_lines (uncompressed_line_details_);
562 Page_breaking::clear_line_details_cache ()
564 cached_configuration_index_ = VPOS;
565 cached_line_details_.clear ();
566 uncompressed_line_details_.clear ();
570 Page_breaking::line_divisions_rec (vsize system_count,
571 Line_division const &min_sys,
572 Line_division const &max_sys,
573 Line_division *cur_division)
575 vsize my_index = cur_division->size ();
576 vsize others_min = 0;
577 vsize others_max = 0;
579 for (vsize i = my_index + 1; i < min_sys.size (); i++)
581 others_min += min_sys[i];
582 others_max += max_sys[i];
584 others_max = min (others_max, system_count);
585 vsize real_min = max (min_sys[my_index], system_count - others_max);
586 vsize real_max = min (max_sys[my_index], system_count - others_min);
588 if (real_min > real_max || real_min <= 0)
590 /* this should never happen within a recursive call. If it happens
591 at all, it means that we were called with an unsolvable problem
592 and we should return an empty result */
593 assert (my_index == 0);
597 for (vsize i = real_min; i <= real_max; i++)
599 cur_division->push_back (i);
600 if (my_index == min_sys.size () - 1)
601 current_configurations_.push_back (*cur_division);
603 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
604 cur_division->pop_back ();
609 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
612 Real cur_rod_height = 0;
613 Real cur_spring_height = 0;
614 Real cur_page_height = page_height (first_page_num, false);
616 cache_line_details (configuration);
617 for (vsize i = 0; i < cached_line_details_.size (); i++)
619 Real ext_len = cached_line_details_[i].extent_.length ();
620 Real next_rod_height = cur_rod_height + ext_len
621 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
622 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
623 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
626 if ((next_height > cur_page_height && cur_rod_height > 0)
628 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
630 cur_rod_height = ext_len;
631 cur_spring_height = line_space (cached_line_details_[i]);
632 cur_page_height = page_height (first_page_num + ret, false);
637 cur_rod_height = next_rod_height;
638 cur_spring_height = next_spring_height;
642 /* there are two potential problems with the last page (because we didn't know
643 it was the last page until after we managed to fit all the systems to it):
644 - we are ragged-last but the last page has a compressed spring
645 - the value returned by page_height (num, true) is smaller than the
646 value returned by page_height (num, false) and it causes the page not to
649 In either case, we just need to add one more page. This is because the last
650 line will always fit on the extra page and by adding one more page to the
651 end, the previous page is no longer the last page, so our previous
652 calculations that treated it as a non-last page were ok.
655 cur_page_height = page_height (first_page_num + ret - 1, true);
656 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
657 if (cur_height > cur_page_height
658 /* don't increase the page count if the last page had only one system */
659 && cur_rod_height > cached_line_details_.back ().extent_.length ())
662 assert (ret <= cached_line_details_.size ());
667 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
669 Page_spacing_result ret;
670 assert (n >= min_page_count (configuration, first_page_num));
672 cache_line_details (configuration);
673 if (n > cached_line_details_.size ())
674 return Page_spacing_result ();
676 ret = space_systems_on_1_page (cached_line_details_,
677 page_height (first_page_num, is_last ()),
678 ragged () || (is_last () && ragged_last ()));
680 ret = space_systems_on_2_pages (configuration, first_page_num);
683 Page_spacer ps (cached_line_details_, first_page_num, this);
687 return finalize_spacing_result (configuration, ret);
691 Page_breaking::blank_page_penalty () const
693 SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
694 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
698 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
700 Page_spacing_result n_res;
701 Page_spacing_result m_res;
703 cache_line_details (configuration);
704 vsize min_p_count = min_page_count (configuration, first_page_num);
708 bool rag = ragged () || (is_last () && ragged_last ());
709 Real height = page_height (first_page_num, is_last ());
711 if (1 >= min_p_count)
712 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
713 if (1 < cached_line_details_.size ())
714 m_res = space_systems_on_2_pages (configuration, first_page_num);
718 Page_spacer ps (cached_line_details_, first_page_num, this);
720 if (n >= min_p_count)
721 n_res = ps.solve (n);
722 if (n < cached_line_details_.size ())
723 m_res = ps.solve (n+1);
726 m_res = finalize_spacing_result (configuration, m_res);
727 n_res = finalize_spacing_result (configuration, n_res);
729 Real penalty = blank_page_penalty ();
730 n_res.demerits_ += penalty;
732 if (n_res.force_.size ())
733 n_res.force_.back () += penalty;
735 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
739 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
741 vsize min_p_count = min_page_count (configuration, first_page_num);
742 Real odd_pages_penalty = blank_page_penalty ();
744 cache_line_details (configuration);
745 Page_spacer ps (cached_line_details_, first_page_num, this);
746 Page_spacing_result best = ps.solve (min_p_count);
747 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
748 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
750 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
752 Page_spacing_result cur = ps.solve (i);
753 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
754 if (cur.demerits_ < best.demerits_)
758 return finalize_spacing_result (configuration, best);
761 /* Calculate demerits and fix res.systems_per_page_ so that
762 it refers to the original line numbers, not the ones given by compress_lines (). */
764 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
766 if (res.force_.empty ())
769 cache_line_details (configuration);
770 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
773 Real line_penalty = 0;
775 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
777 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
779 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
780 line_penalty += uncompressed_line_details_[i].break_penalty_;
783 for (vsize i = 0; i < res.force_.size (); i++)
785 Real f = res.force_[i];
786 if (isinf (f) && res.systems_per_page_[i] == 1)
792 /* for a while we tried averaging page and line forces across pages instead
793 of summing them, but it caused a problem: if there is a single page
794 with a very bad page force (for example because of a forced page break),
795 the page breaker will put in a _lot_ of pages so that the bad force
796 becomes averaged out over many pages. */
797 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
802 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
803 are by far the most common cases, we have special functions for them.
805 space_systems_on_1_page has a different calling convention than most of the
806 space_systems functions. This is because space_systems_on_1_page is (unlike
807 the other space_systems functions) sometimes called on subsets of a full
810 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
812 Page_spacing space (page_height);
813 Page_spacing_result ret;
815 for (vsize i = 0; i < lines.size (); i++)
816 space.append_system (lines[i]);
818 ret.systems_per_page_.push_back (lines.size ());
819 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
820 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
822 /* don't do finalize_spacing_result () because we are only an internal function */
827 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
829 Real page1_height = page_height (first_page_num, false);
830 Real page2_height = page_height (first_page_num + 1, is_last ());
831 bool ragged1 = ragged ();
832 bool ragged2 = ragged () || (is_last () && ragged_last ());
834 /* if there is a forced break, this reduces to 2 1-page problems */
835 cache_line_details (configuration);
836 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
837 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
839 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
840 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
841 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
842 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
844 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
845 p1.force_.push_back (p2.force_[0]);
846 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
850 vector<Real> page1_force;
851 vector<Real> page2_force;
852 Page_spacing page1 (page1_height);
853 Page_spacing page2 (page2_height);
855 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
856 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
858 /* find the page 1 and page 2 forces for each page-breaking position */
859 for (vsize i = 0; i < page1_force.size (); i++)
861 page1.append_system (cached_line_details_[i]);
862 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
863 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
866 page2_force[page2_force.size () - 1 - i] =
867 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
869 page2_force[page2_force.size () - 1 - i] = page2.force_;
872 /* find the position that minimises the sum of the page forces */
873 vsize best_sys_count = 1;
874 Real best_demerits = infinity_f;
875 for (vsize i = 0; i < page1_force.size (); i++)
877 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
878 Real uneven = 2 * (page1_force[i] - page2_force[i]);
879 Real dem = uneven * uneven + f
880 + cached_line_details_[i+1].page_penalty_
881 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
882 if (dem < best_demerits)
885 best_sys_count = i+1;
889 Page_spacing_result ret;
890 ret.systems_per_page_.push_back (best_sys_count);
891 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
892 ret.force_.push_back (page1_force[best_sys_count-1]);
893 ret.force_.push_back (page2_force[best_sys_count-1]);
894 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
895 + cached_line_details_.back ().page_penalty_
896 + cached_line_details_.back ().turn_penalty_;
898 /* don't do finalize_spacing_result () because we are only an internal function */
903 Page_breaking::all_lines_stretched (vsize configuration)
905 cache_line_details (configuration);
906 for (vsize i = 0; i < cached_line_details_.size (); i++)
907 if (cached_line_details_[i].force_ < 0)
913 Page_breaking::Line_division
914 Page_breaking::current_configuration (vsize configuration_index) const
916 return current_configurations_[configuration_index];
920 Page_breaking::is_last () const
922 return current_end_breakpoint_ == last_break_position ();
926 Page_breaking::last_break_position () const
928 return breaks_.size () - 1;