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);
244 for (vsize i = 0; i < lines_per_page.size (); i++)
246 SCM page_num = scm_from_int (i + first_page_number);
247 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
248 SCM rag = scm_from_bool (ragged () || (to_boolean (last)
250 SCM line_count = scm_from_int (lines_per_page[i]);
251 SCM lines = scm_list_head (systems, line_count);
252 SCM page = scm_apply_0 (make_page,
253 scm_list_n (book, lines, page_num,
254 rag, last, SCM_UNDEFINED));
256 scm_apply_1 (page_stencil, page, SCM_EOL);
257 ret = scm_cons (page, ret);
258 systems = scm_list_tail (systems, line_count);
260 ret = scm_reverse (ret);
264 /* The page-turn-page-breaker needs to have a line-breaker between any two
265 columns with non-NULL page-turn-permission.
267 The optimal-breaker needs to have a line-breaker between any two columns
268 with page-break-permission = 'force.
270 By using a grob predicate, we can accommodate both of these uses.
273 Page_breaking::create_system_list ()
275 SCM specs = book_->get_system_specs ();
276 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
278 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
280 SCM system_count = ps->layout ()->c_variable ("system-count");
282 if (scm_is_number (system_count))
283 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
284 scm_vector_to_list (ps->get_paper_systems ()),
287 system_specs_.push_back (System_spec (ps));
291 Prob *pb = unsmob_prob (scm_car (s));
295 system_specs_.push_back (System_spec (pb));
301 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
303 SCM force_sym = ly_symbol2scm ("force");
305 chunks_.push_back (Break_position ());
306 breaks_.push_back (Break_position ());
308 for (vsize i = 0; i < system_specs_.size (); i++)
310 if (system_specs_[i].pscore_)
313 = system_specs_[i].pscore_->root_system ()->used_columns ();
314 vector<vsize> line_breaker_columns;
315 line_breaker_columns.push_back (0);
317 for (vsize j = 1; j < cols.size (); j++)
319 bool last = (j == cols.size () - 1);
320 bool break_point = is_break (cols[j]);
321 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
322 Break_position cur_pos = Break_position (i,
323 line_breaker_columns.size (),
327 if (break_point || (i == system_specs_.size () - 1 && last))
328 breaks_.push_back (cur_pos);
329 if (chunk_end || last)
330 chunks_.push_back (cur_pos);
332 if ((break_point || chunk_end) && !last)
333 line_breaker_columns.push_back (j);
335 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
339 /* TODO: we want some way of applying Break_p to a prob? */
340 if (i == system_specs_.size () - 1)
341 breaks_.push_back (Break_position (i));
343 chunks_.push_back (Break_position (i));
345 /* FIXME: shouldn't we push a Null_breaker or similar dummy
347 line_breaking_.push_back (Constrained_breaking (NULL));
352 vector<Break_position>
353 Page_breaking::chunk_list (vsize start_index, vsize end_index)
355 Break_position start = breaks_[start_index];
356 Break_position end = breaks_[end_index];
359 for (; i < chunks_.size () && chunks_[i] <= start; i++)
362 vector<Break_position> ret;
363 ret.push_back (start);
364 for (; i < chunks_.size () && chunks_[i] < end; i++)
365 ret.push_back (chunks_[i]);
371 Page_breaking::min_system_count (vsize start, vsize end)
373 vector<Break_position> chunks = chunk_list (start, end);
374 Line_division div = system_count_bounds (chunks, true);
377 for (vsize i = 0; i < div.size (); i++)
383 Page_breaking::max_system_count (vsize start, vsize end)
385 vector<Break_position> chunks = chunk_list (start, end);
386 Line_division div = system_count_bounds (chunks, false);
389 for (vsize i = 0; i < div.size (); i++)
394 Page_breaking::Line_division
395 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
398 assert (chunks.size () >= 2);
401 ret.resize (chunks.size () - 1, 1);
403 for (vsize i = 0; i + 1 < chunks.size (); i++)
405 vsize sys = next_system (chunks[i]);
406 if (system_specs_[sys].pscore_)
410 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
412 ? line_breaking_[sys].min_system_count (start, end)
413 : line_breaking_[sys].max_system_count (start, end);
421 Page_breaking::set_current_breakpoints (vsize start,
424 Line_division lower_bound,
425 Line_division upper_bound)
427 current_chunks_ = chunk_list (start, end);
428 current_start_breakpoint_ = start;
429 current_end_breakpoint_ = end;
430 clear_line_details_cache ();
432 if (!lower_bound.size ())
433 lower_bound = system_count_bounds (current_chunks_, true);
434 if (!upper_bound.size ())
435 upper_bound = system_count_bounds (current_chunks_, false);
437 assert (lower_bound.size () == current_chunks_.size () - 1);
438 assert (upper_bound.size () == current_chunks_.size () - 1);
440 Line_division work_in_progress;
441 current_configurations_.clear ();
442 line_divisions_rec (system_count,
447 /* we only consider a constant number of configurations. Otherwise,
448 this becomes slow when there are many small scores. The constant
449 5 is somewhat arbitrary. */
450 if (current_configurations_.size () > 5)
452 vector<pair<Real,vsize> > dems_and_indices;
454 for (vsize i = 0; i < current_configurations_.size (); i++)
456 cache_line_details (i);
458 for (vsize j = 0; j < cached_line_details_.size (); j++)
459 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
460 + cached_line_details_[j].break_penalty_;
462 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
464 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
466 vector<Line_division> best_5_configurations;
467 for (vsize i = 0; i < 5; i++)
468 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
470 clear_line_details_cache ();
471 current_configurations_ = best_5_configurations;
476 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
478 current_chunks_ = chunk_list (start, end);
479 current_start_breakpoint_ = start;
480 current_end_breakpoint_ = end;
481 clear_line_details_cache ();
484 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
486 vsize sys = next_system (current_chunks_[i]);
487 if (system_specs_[sys].pscore_)
489 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
490 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
495 current_configurations_.clear ();
496 current_configurations_.push_back (div);
500 Page_breaking::current_configuration_count () const
502 return current_configurations_.size ();
506 Page_breaking::cache_line_details (vsize configuration_index)
508 if (cached_configuration_index_ != configuration_index)
510 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
511 if (!scm_is_number (padding_scm))
512 padding_scm = book_->paper_->c_variable ("between-system-padding");
513 Real padding = robust_scm2double (padding_scm, 0.0);
515 Line_division &div = current_configurations_[configuration_index];
516 uncompressed_line_details_.clear ();
517 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
519 vsize sys = next_system (current_chunks_[i]);
520 if (system_specs_[sys].pscore_)
524 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
526 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
527 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
531 assert (div[i] == 1);
532 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
533 uncompressed_line_details_.back ().padding_ = padding;
536 cached_line_details_ = compress_lines (uncompressed_line_details_);
541 Page_breaking::clear_line_details_cache ()
543 cached_configuration_index_ = VPOS;
544 cached_line_details_.clear ();
545 uncompressed_line_details_.clear ();
549 Page_breaking::line_divisions_rec (vsize system_count,
550 Line_division const &min_sys,
551 Line_division const &max_sys,
552 Line_division *cur_division)
554 vsize my_index = cur_division->size ();
555 vsize others_min = 0;
556 vsize others_max = 0;
558 for (vsize i = my_index + 1; i < min_sys.size (); i++)
560 others_min += min_sys[i];
561 others_max += max_sys[i];
563 others_max = min (others_max, system_count);
564 vsize real_min = max (min_sys[my_index], system_count - others_max);
565 vsize real_max = min (max_sys[my_index], system_count - others_min);
567 if (real_min > real_max || real_min <= 0)
569 /* this should never happen within a recursive call. If it happens
570 at all, it means that we were called with an unsolvable problem
571 and we should return an empty result */
572 assert (my_index == 0);
576 for (vsize i = real_min; i <= real_max; i++)
578 cur_division->push_back (i);
579 if (my_index == min_sys.size () - 1)
580 current_configurations_.push_back (*cur_division);
582 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
583 cur_division->pop_back ();
588 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
591 Real cur_rod_height = 0;
592 Real cur_spring_height = 0;
593 Real cur_page_height = page_height (first_page_num, false);
595 cache_line_details (configuration);
596 for (vsize i = 0; i < cached_line_details_.size (); i++)
598 Real ext_len = cached_line_details_[i].extent_.length ();
599 Real next_rod_height = cur_rod_height + ext_len
600 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
601 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
602 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
605 if ((next_height > cur_page_height && cur_rod_height > 0)
607 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
609 cur_rod_height = ext_len;
610 cur_spring_height = line_space (cached_line_details_[i]);
611 cur_page_height = page_height (first_page_num + ret, false);
616 cur_rod_height = next_rod_height;
617 cur_spring_height = next_spring_height;
621 /* there are two potential problems with the last page (because we didn't know
622 it was the last page until after we managed to fit all the systems to it):
623 - we are ragged-last but the last page has a compressed spring
624 - the value returned by page_height (num, true) is smaller than the
625 value returned by page_height (num, false) and it causes the page not to
628 In either case, we just need to add one more page. This is because the last
629 line will always fit on the extra page and by adding one more page to the
630 end, the previous page is no longer the last page, so our previous
631 calculations that treated it as a non-last page were ok.
634 cur_page_height = page_height (first_page_num + ret - 1, true);
635 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
636 if (cur_height > cur_page_height
637 /* don't increase the page count if the last page had only one system */
638 && cur_rod_height > cached_line_details_.back ().extent_.length ())
641 assert (ret <= cached_line_details_.size ());
646 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
648 Page_spacing_result ret;
649 assert (n >= min_page_count (configuration, first_page_num));
651 cache_line_details (configuration);
652 if (n > cached_line_details_.size ())
653 return Page_spacing_result ();
655 ret = space_systems_on_1_page (cached_line_details_,
656 page_height (first_page_num, is_last ()),
657 ragged () || (is_last () && ragged_last ()));
659 ret = space_systems_on_2_pages (configuration, first_page_num);
662 Page_spacer ps (cached_line_details_, first_page_num, this);
666 return finalize_spacing_result (configuration, ret);
670 Page_breaking::blank_page_penalty () const
672 SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
673 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
677 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
679 Page_spacing_result n_res;
680 Page_spacing_result m_res;
684 n_res = space_systems_on_n_pages (configuration, n, first_page_num);
685 m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
689 cache_line_details (configuration);
691 vsize min_p_count = min_page_count (configuration, first_page_num);
692 Page_spacer ps (cached_line_details_, first_page_num, this);
693 if (n >= min_p_count)
694 n_res = ps.solve (n);
695 if (n < cached_line_details_.size ())
696 m_res = ps.solve (n+1);
699 Real penalty = blank_page_penalty ();
700 n_res.demerits_ += penalty;
701 n_res.force_.back () += penalty;
703 if (m_res.demerits_ < n_res.demerits_)
709 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
711 vsize min_p_count = min_page_count (configuration, first_page_num);
712 Real odd_pages_penalty = blank_page_penalty ();
714 cache_line_details (configuration);
715 Page_spacer ps (cached_line_details_, first_page_num, this);
716 Page_spacing_result best = ps.solve (min_p_count);
717 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
718 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
720 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
722 Page_spacing_result cur = ps.solve (i);
723 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
724 if (cur.demerits_ < best.demerits_)
728 return finalize_spacing_result (configuration, best);
731 /* Calculate demerits and fix res.systems_per_page_ so that
732 it refers to the original line numbers, not the ones given by compress_lines (). */
734 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
736 cache_line_details (configuration);
737 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
740 Real line_penalty = 0;
742 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
744 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
746 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
747 line_penalty += uncompressed_line_details_[i].break_penalty_;
750 for (vsize i = 0; i < res.force_.size (); i++)
752 Real f = res.force_[i];
753 if (isinf (f) && res.systems_per_page_[i] == 1)
759 /* for a while we tried averaging page and line forces across pages instead
760 of summing them, but it caused a problem: if there is a single page
761 with a very bad page force (for example because of a forced page break),
762 the page breaker will put in a _lot_ of pages so that the bad force
763 becomes averaged out over many pages. */
764 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
769 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
770 are by far the most common cases, we have special functions for them.
772 space_systems_on_1_page has a different calling convention than most of the
773 space_systems functions. This is because space_systems_on_1_page is (unlike
774 the other space_systems functions) sometimes called on subsets of a full
777 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
779 Page_spacing space (page_height);
780 Page_spacing_result ret;
782 for (vsize i = 0; i < lines.size (); i++)
783 space.append_system (lines[i]);
785 ret.systems_per_page_.push_back (lines.size ());
786 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
787 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
789 /* don't do finalize_spacing_result () because we are only an internal function */
794 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
796 Real page1_height = page_height (first_page_num, false);
797 Real page2_height = page_height (first_page_num + 1, is_last ());
798 bool ragged1 = ragged ();
799 bool ragged2 = ragged () || (is_last () && ragged_last ());
801 /* if there is a forced break, this reduces to 2 1-page problems */
802 cache_line_details (configuration);
803 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
804 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
806 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
807 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
808 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
809 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
811 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
812 p1.force_.push_back (p2.force_[0]);
813 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
817 vector<Real> page1_force;
818 vector<Real> page2_force;
819 Page_spacing page1 (page1_height);
820 Page_spacing page2 (page2_height);
822 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
823 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
825 /* find the page 1 and page 2 forces for each page-breaking position */
826 for (vsize i = 0; i < page1_force.size (); i++)
828 page1.append_system (cached_line_details_[i]);
829 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
830 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
833 page2_force[page2_force.size () - 1 - i] =
834 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
836 page2_force[page2_force.size () - 1 - i] = page2.force_;
839 /* find the position that minimises the sum of the page forces */
840 vsize best_sys_count = 1;
841 Real best_demerits = infinity_f;
842 for (vsize i = 0; i < page1_force.size (); i++)
844 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
845 Real uneven = 2 * (page1_force[i] - page2_force[i]);
846 Real dem = uneven * uneven + f
847 + cached_line_details_[i+1].page_penalty_
848 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
849 if (dem < best_demerits)
852 best_sys_count = i+1;
856 Page_spacing_result ret;
857 ret.systems_per_page_.push_back (best_sys_count);
858 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
859 ret.force_.push_back (page1_force[best_sys_count-1]);
860 ret.force_.push_back (page2_force[best_sys_count-1]);
861 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
862 + cached_line_details_.back ().page_penalty_
863 + cached_line_details_.back ().turn_penalty_;
865 /* don't do finalize_spacing_result () because we are only an internal function */
870 Page_breaking::all_lines_stretched (vsize configuration)
872 cache_line_details (configuration);
873 for (vsize i = 0; i < cached_line_details_.size (); i++)
874 if (cached_line_details_[i].force_ < 0)
880 Page_breaking::Line_division
881 Page_breaking::current_configuration (vsize configuration_index) const
883 return current_configurations_[configuration_index];
887 Page_breaking::is_last () const
889 return current_end_breakpoint_ == last_break_position ();
893 Page_breaking::last_break_position () const
895 return breaks_.size () - 1;