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 sys */
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_)
312 vector<Grob*> cols = system_specs_[i].pscore_->root_system ()->used_columns ();
313 vector<vsize> line_breaker_columns;
314 line_breaker_columns.push_back (0);
316 for (vsize j = 1; j < cols.size (); j++)
318 bool last = j == cols.size () - 1;
319 bool break_point = is_break (cols[j]);
320 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
321 Break_position cur_pos = Break_position (i,
322 line_breaker_columns.size (),
326 if (break_point || (i == system_specs_.size () - 1 && last))
327 breaks_.push_back (cur_pos);
328 if (chunk_end || last)
329 chunks_.push_back (cur_pos);
331 if ((break_point || chunk_end) && !last)
332 line_breaker_columns.push_back (j);
334 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
338 /* TODO: we want some way of applying Break_p to a prob? */
339 if (i == system_specs_.size () - 1)
340 breaks_.push_back (Break_position (i));
342 chunks_.push_back (Break_position (i));
343 line_breaking_.push_back (Constrained_breaking (NULL));
348 vector<Break_position>
349 Page_breaking::chunk_list (vsize start_index, vsize end_index)
351 Break_position start = breaks_[start_index];
352 Break_position end = breaks_[end_index];
355 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
358 vector<Break_position> ret;
359 ret.push_back (start);
360 for (; i < chunks_.size () && chunks_[i] < end; i++)
361 ret.push_back (chunks_[i]);
367 Page_breaking::min_system_count (vsize start, vsize end)
369 vector<Break_position> chunks = chunk_list (start, end);
370 Line_division div = system_count_bounds (chunks, true);
373 for (vsize i = 0; i < div.size (); i++)
379 Page_breaking::max_system_count (vsize start, vsize end)
381 vector<Break_position> chunks = chunk_list (start, end);
382 Line_division div = system_count_bounds (chunks, false);
385 for (vsize i = 0; i < div.size (); i++)
390 Page_breaking::Line_division
391 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
394 assert (chunks.size () >= 2);
397 ret.resize (chunks.size () - 1, 1);
399 for (vsize i = 0; i + 1 < chunks.size (); i++)
401 vsize sys = next_system (chunks[i]);
402 if (system_specs_[sys].pscore_)
406 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
408 ? line_breaking_[sys].min_system_count (start, end)
409 : line_breaking_[sys].max_system_count (start, end);
417 Page_breaking::set_current_breakpoints (vsize start,
420 Line_division lower_bound,
421 Line_division upper_bound)
423 current_chunks_ = chunk_list (start, end);
424 current_start_breakpoint_ = start;
425 current_end_breakpoint_ = end;
426 clear_line_details_cache ();
428 if (!lower_bound.size ())
429 lower_bound = system_count_bounds (current_chunks_, true);
430 if (!upper_bound.size ())
431 upper_bound = system_count_bounds (current_chunks_, false);
433 assert (lower_bound.size () == current_chunks_.size () - 1);
434 assert (upper_bound.size () == current_chunks_.size () - 1);
436 Line_division work_in_progress;
437 current_configurations_.clear ();
438 line_divisions_rec (system_count,
443 /* we only consider a constant number of configurations. Otherwise,
444 this becomes slow when there are many small scores. The constant
445 5 is somewhat arbitrary. */
446 if (current_configurations_.size () > 5)
448 vector<pair<Real,vsize> > dems_and_indices;
450 for (vsize i = 0; i < current_configurations_.size (); i++)
452 cache_line_details (i);
454 for (vsize j = 0; j < cached_line_details_.size (); j++)
455 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
456 + cached_line_details_[j].break_penalty_;
458 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
460 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
462 vector<Line_division> best_5_configurations;
463 for (vsize i = 0; i < 5; i++)
464 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
466 clear_line_details_cache ();
467 current_configurations_ = best_5_configurations;
472 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
474 current_chunks_ = chunk_list (start, end);
475 current_start_breakpoint_ = start;
476 current_end_breakpoint_ = end;
477 clear_line_details_cache ();
480 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
482 vsize sys = next_system (current_chunks_[i]);
483 if (system_specs_[sys].pscore_)
485 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
486 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
491 current_configurations_.clear ();
492 current_configurations_.push_back (div);
496 Page_breaking::current_configuration_count () const
498 return current_configurations_.size ();
502 Page_breaking::cache_line_details (vsize configuration_index)
504 if (cached_configuration_index_ != configuration_index)
506 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
507 if (!scm_is_number (padding_scm))
508 padding_scm = book_->paper_->c_variable ("between-system-padding");
509 Real padding = robust_scm2double (padding_scm, 0.0);
511 Line_division &div = current_configurations_[configuration_index];
512 uncompressed_line_details_.clear ();
513 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
515 vsize sys = next_system (current_chunks_[i]);
516 if (system_specs_[sys].pscore_)
520 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
522 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
523 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
527 assert (div[i] == 1);
528 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
529 uncompressed_line_details_.back ().padding_ = padding;
532 cached_line_details_ = compress_lines (uncompressed_line_details_);
537 Page_breaking::clear_line_details_cache ()
539 cached_configuration_index_ = VPOS;
540 cached_line_details_.clear ();
541 uncompressed_line_details_.clear ();
545 Page_breaking::line_divisions_rec (vsize system_count,
546 Line_division const &min_sys,
547 Line_division const &max_sys,
548 Line_division *cur_division)
550 vsize my_index = cur_division->size ();
551 vsize others_min = 0;
552 vsize others_max = 0;
554 for (vsize i = my_index + 1; i < min_sys.size (); i++)
556 others_min += min_sys[i];
557 others_max += max_sys[i];
559 others_max = min (others_max, system_count);
560 vsize real_min = max (min_sys[my_index], system_count - others_max);
561 vsize real_max = min (max_sys[my_index], system_count - others_min);
563 if (real_min > real_max || real_min <= 0)
565 /* this should never happen within a recursive call. If it happens
566 at all, it means that we were called with an unsolvable problem
567 and we should return an empty result */
568 assert (my_index == 0);
572 for (vsize i = real_min; i <= real_max; i++)
574 cur_division->push_back (i);
575 if (my_index == min_sys.size () - 1)
576 current_configurations_.push_back (*cur_division);
578 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
579 cur_division->pop_back ();
584 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
587 Real cur_rod_height = 0;
588 Real cur_spring_height = 0;
589 Real cur_page_height = page_height (first_page_num, false);
591 cache_line_details (configuration);
592 for (vsize i = 0; i < cached_line_details_.size (); i++)
594 Real ext_len = cached_line_details_[i].extent_.length ();
595 Real next_rod_height = cur_rod_height + ext_len
596 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
597 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
598 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
601 if ((next_height > cur_page_height && cur_rod_height > 0)
603 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
605 cur_rod_height = ext_len;
606 cur_spring_height = line_space (cached_line_details_[i]);
607 cur_page_height = page_height (first_page_num + ret, false);
612 cur_rod_height = next_rod_height;
613 cur_spring_height = next_spring_height;
617 /* there are two potential problems with the last page (because we didn't know
618 it was the last page until after we managed to fit all the systems to it):
619 - we are ragged-last but the last page has a compressed spring
620 - the value returned by page_height (num, true) is smaller than the
621 value returned by page_height (num, false) and it causes the page not to
624 In either case, we just need to add one more page. This is because the last
625 line will always fit on the extra page and by adding one more page to the
626 end, the previous page is no longer the last page, so our previous
627 calculations that treated it as a non-last page were ok.
630 cur_page_height = page_height (first_page_num + ret - 1, true);
631 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
632 if (cur_height > cur_page_height
633 /* don't increase the page count if the last page had only one system */
634 && cur_rod_height > cached_line_details_.back ().extent_.length ())
637 assert (ret <= cached_line_details_.size ());
642 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
645 assert (n >= min_page_count (configuration, first_page_num));
647 cache_line_details (configuration);
648 if (n > cached_line_details_.size ())
649 return Spacing_result ();
651 ret = space_systems_on_1_page (cached_line_details_,
652 page_height (first_page_num, is_last ()),
653 ragged () || (is_last () && ragged_last ()));
655 ret = space_systems_on_2_pages (configuration, first_page_num);
658 Page_spacer ps (cached_line_details_, first_page_num, this);
662 return finalize_spacing_result (configuration, ret);
666 Page_breaking::blank_page_penalty () const
668 SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
669 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
673 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
675 Spacing_result n_res;
676 Spacing_result m_res;
680 n_res = space_systems_on_n_pages (configuration, n, first_page_num);
681 m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
685 cache_line_details (configuration);
687 vsize min_p_count = min_page_count (configuration, first_page_num);
688 Page_spacer ps (cached_line_details_, first_page_num, this);
689 if (n >= min_p_count)
690 n_res = ps.solve (n);
691 if (n < cached_line_details_.size ())
692 m_res = ps.solve (n+1);
695 Real penalty = blank_page_penalty ();
696 n_res.demerits_ += penalty;
697 n_res.force_.back () += penalty;
699 if (m_res.demerits_ < n_res.demerits_)
705 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
707 vsize min_p_count = min_page_count (configuration, first_page_num);
708 Real odd_pages_penalty = blank_page_penalty ();
710 cache_line_details (configuration);
711 Page_spacer ps (cached_line_details_, first_page_num, this);
712 Spacing_result best = ps.solve (min_p_count);
713 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
714 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
716 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
718 Spacing_result cur = ps.solve (i);
719 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
720 if (cur.demerits_ < best.demerits_)
724 return finalize_spacing_result (configuration, best);
727 /* Calculate demerits and fix res.systems_per_page_ so that
728 it refers to the original line numbers, not the ones given by compress_lines (). */
730 Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res)
732 cache_line_details (configuration);
733 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
736 Real line_penalty = 0;
738 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
740 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
742 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
743 line_penalty += uncompressed_line_details_[i].break_penalty_;
746 for (vsize i = 0; i < res.force_.size (); i++)
748 Real f = res.force_[i];
749 if (isinf (f) && res.systems_per_page_[i] == 1)
755 /* for a while we tried averaging page and line forces across pages instead
756 of summing them, but it caused a problem: if there is a single page
757 with a very bad page force (for example because of a forced page break),
758 the page breaker will put in a _lot_ of pages so that the bad force
759 becomes averaged out over many pages. */
760 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
765 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
766 are by far the most common cases, we have special functions for them.
768 space_systems_on_1_page has a different calling convention than most of the
769 space_systems functions. This is because space_systems_on_1_page is (unlike
770 the other space_systems functions) sometimes called on subsets of a full
773 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
775 Page_spacing space (page_height);
778 for (vsize i = 0; i < lines.size (); i++)
779 space.append_system (lines[i]);
781 ret.systems_per_page_.push_back (lines.size ());
782 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
783 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
785 /* don't do finalize_spacing_result () because we are only an internal function */
790 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
792 Real page1_height = page_height (first_page_num, false);
793 Real page2_height = page_height (first_page_num + 1, is_last ());
794 bool ragged1 = ragged ();
795 bool ragged2 = ragged () || (is_last () && ragged_last ());
797 /* if there is a forced break, this reduces to 2 1-page problems */
798 cache_line_details (configuration);
799 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
800 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
802 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
803 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
804 Spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
805 Spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
807 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
808 p1.force_.push_back (p2.force_[0]);
809 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
813 vector<Real> page1_force;
814 vector<Real> page2_force;
815 Page_spacing page1 (page1_height);
816 Page_spacing page2 (page2_height);
818 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
819 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
821 /* find the page 1 and page 2 forces for each page-breaking position */
822 for (vsize i = 0; i < page1_force.size (); i++)
824 page1.append_system (cached_line_details_[i]);
825 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
826 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
829 page2_force[page2_force.size () - 1 - i] =
830 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
832 page2_force[page2_force.size () - 1 - i] = page2.force_;
835 /* find the position that minimises the sum of the page forces */
836 vsize best_sys_count = 1;
837 Real best_demerits = infinity_f;
838 for (vsize i = 0; i < page1_force.size (); i++)
840 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
841 Real uneven = 2 * (page1_force[i] - page2_force[i]);
842 Real dem = uneven * uneven + f
843 + cached_line_details_[i+1].page_penalty_
844 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
845 if (dem < best_demerits)
848 best_sys_count = i+1;
853 ret.systems_per_page_.push_back (best_sys_count);
854 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
855 ret.force_.push_back (page1_force[best_sys_count-1]);
856 ret.force_.push_back (page2_force[best_sys_count-1]);
857 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
858 + cached_line_details_.back ().page_penalty_
859 + cached_line_details_.back ().turn_penalty_;
861 /* don't do finalize_spacing_result () because we are only an internal function */
866 Page_breaking::all_lines_stretched (vsize configuration)
868 cache_line_details (configuration);
869 for (vsize i = 0; i < cached_line_details_.size (); i++)
870 if (cached_line_details_[i].force_ < 0)
876 Page_breaking::Line_division
877 Page_breaking::current_configuration (vsize configuration_index) const
879 return current_configurations_[configuration_index];
883 Page_breaking::is_last () const
885 return current_end_breakpoint_ == last_break_position ();
889 Page_breaking::last_break_position () const
891 return breaks_.size () - 1;