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,
437 /* we only consider a constant number of configurations. Otherwise,
438 this becomes slow when there are many small scores. The constant
439 5 is somewhat arbitrary. */
440 if (current_configurations_.size () > 5)
442 vector<pair<Real,vsize> > dems_and_indices;
444 for (vsize i = 0; i < current_configurations_.size (); i++)
446 cache_line_details (i);
448 for (vsize j = 0; j < cached_line_details_.size (); j++)
449 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
450 + cached_line_details_[j].break_penalty_;
452 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
454 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
456 vector<Line_division> best_5_configurations;
457 for (vsize i = 0; i < 5; i++)
458 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
460 clear_line_details_cache ();
461 current_configurations_ = best_5_configurations;
466 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
468 current_chunks_ = chunk_list (start, end);
469 current_start_breakpoint_ = start;
470 current_end_breakpoint_ = end;
471 clear_line_details_cache ();
474 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
476 vsize sys = next_system (current_chunks_[i]);
477 if (all_[sys].pscore_)
479 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
480 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
485 current_configurations_.clear ();
486 current_configurations_.push_back (div);
490 Page_breaking::current_configuration_count () const
492 return current_configurations_.size ();
496 Page_breaking::cache_line_details (vsize configuration_index)
498 if (cached_configuration_index_ != configuration_index)
500 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
501 if (!scm_is_number (padding_scm))
502 padding_scm = book_->paper_->c_variable ("between-system-padding");
503 Real padding = robust_scm2double (padding_scm, 0.0);
505 Line_division &div = current_configurations_[configuration_index];
506 uncompressed_line_details_.clear ();
507 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
509 vsize sys = next_system (current_chunks_[i]);
510 if (all_[sys].pscore_)
514 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
516 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
517 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
521 assert (div[i] == 1);
522 uncompressed_line_details_.push_back (Line_details (all_[sys].prob_));
523 uncompressed_line_details_.back ().padding_ = padding;
526 cached_line_details_ = compress_lines (uncompressed_line_details_);
531 Page_breaking::clear_line_details_cache ()
533 cached_configuration_index_ = VPOS;
534 cached_line_details_.clear ();
535 uncompressed_line_details_.clear ();
539 Page_breaking::line_divisions_rec (vsize system_count,
540 Line_division const &min_sys,
541 Line_division const &max_sys,
542 Line_division *cur_division)
544 vsize my_index = cur_division->size ();
545 vsize others_min = 0;
546 vsize others_max = 0;
548 for (vsize i = my_index + 1; i < min_sys.size (); i++)
550 others_min += min_sys[i];
551 others_max += max_sys[i];
553 others_max = min (others_max, system_count);
554 vsize real_min = max (min_sys[my_index], system_count - others_max);
555 vsize real_max = min (max_sys[my_index], system_count - others_min);
557 if (real_min > real_max || real_min <= 0)
559 /* this should never happen within a recursive call. If it happens
560 at all, it means that we were called with an unsolvable problem
561 and we should return an empty result */
562 assert (my_index == 0);
566 for (vsize i = real_min; i <= real_max; i++)
568 cur_division->push_back (i);
569 if (my_index == min_sys.size () - 1)
570 current_configurations_.push_back (*cur_division);
572 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
573 cur_division->pop_back ();
578 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
581 Real cur_rod_height = 0;
582 Real cur_spring_height = 0;
583 Real cur_page_height = page_height (first_page_num, false);
585 cache_line_details (configuration);
586 for (vsize i = 0; i < cached_line_details_.size (); i++)
588 Real ext_len = cached_line_details_[i].extent_.length ();
589 Real next_rod_height = cur_rod_height + ext_len
590 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
591 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
592 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
595 if ((next_height > cur_page_height && cur_rod_height > 0)
597 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
599 cur_rod_height = ext_len;
600 cur_spring_height = line_space (cached_line_details_[i]);
601 cur_page_height = page_height (first_page_num + ret, false);
606 cur_rod_height = next_rod_height;
607 cur_spring_height = next_spring_height;
611 /* there are two potential problems with the last page (because we didn't know
612 it was the last page until after we managed to fit all the systems to it):
613 - we are ragged-last but the last page has a compressed spring
614 - the value returned by page_height (num, true) is smaller than the
615 value returned by page_height (num, false) and it causes the page not to
618 In either case, we just need to add one more page. This is because the last
619 line will always fit on the extra page and by adding one more page to the
620 end, the previous page is no longer the last page, so our previous
621 calculations that treated it as a non-last page were ok.
624 cur_page_height = page_height (first_page_num + ret - 1, true);
625 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
626 if (cur_height > cur_page_height
627 /* don't increase the page count if the last page had only one system */
628 && cur_rod_height > cached_line_details_.back ().extent_.length ())
631 assert (ret <= cached_line_details_.size ());
636 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
639 assert (n >= min_page_count (configuration, first_page_num));
641 cache_line_details (configuration);
642 if (n > cached_line_details_.size ())
643 return Spacing_result ();
645 ret = space_systems_on_1_page (cached_line_details_,
646 page_height (first_page_num, last ()),
647 ragged () || (last () && ragged_last ()));
649 ret = space_systems_on_2_pages (configuration, first_page_num);
652 Page_spacer ps (cached_line_details_, first_page_num, this);
656 return finalize_spacing_result (configuration, ret);
660 Page_breaking::blank_page_penalty () const
662 SCM penalty_sym = last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
663 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
667 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
669 Spacing_result n_res;
670 Spacing_result m_res;
674 n_res = space_systems_on_n_pages (configuration, n, first_page_num);
675 m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
679 cache_line_details (configuration);
681 vsize min_p_count = min_page_count (configuration, first_page_num);
682 Page_spacer ps (cached_line_details_, first_page_num, this);
683 if (n >= min_p_count)
684 n_res = ps.solve (n);
685 if (n < cached_line_details_.size ())
686 m_res = ps.solve (n+1);
689 Real penalty = blank_page_penalty ();
690 n_res.demerits_ += penalty;
691 n_res.force_.back () += penalty;
693 if (m_res.demerits_ < n_res.demerits_)
699 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
701 vsize min_p_count = min_page_count (configuration, first_page_num);
702 Real odd_pages_penalty = blank_page_penalty ();
704 cache_line_details (configuration);
705 Page_spacer ps (cached_line_details_, first_page_num, this);
706 Spacing_result best = ps.solve (min_p_count);
707 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
708 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
710 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
712 Spacing_result cur = ps.solve (i);
713 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
714 if (cur.demerits_ < best.demerits_)
718 return finalize_spacing_result (configuration, best);
721 /* Calculate demerits and fix res.systems_per_page_ so that
722 it refers to the original line numbers, not the ones given by compress_lines (). */
724 Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res)
726 cache_line_details (configuration);
727 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
730 Real line_penalty = 0;
732 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
734 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
736 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
737 line_penalty += uncompressed_line_details_[i].break_penalty_;
740 for (vsize i = 0; i < res.force_.size (); i++)
742 Real f = res.force_[i];
743 if (isinf (f) && res.systems_per_page_[i] == 1)
749 /* for a while we tried averaging page and line forces across pages instead
750 of summing them, but it caused a problem: if there is a single page
751 with a very bad page force (for example because of a forced page break),
752 the page breaker will put in a _lot_ of pages so that the bad force
753 becomes averaged out over many pages. */
754 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
759 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
760 are by far the most common cases, we have special functions for them.
762 space_systems_on_1_page has a different calling convention than most of the
763 space_systems functions. This is because space_systems_on_1_page is (unlike
764 the other space_systems functions) sometimes called on subsets of a full
767 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
769 Page_spacing space (page_height);
772 for (vsize i = 0; i < lines.size (); i++)
773 space.append_system (lines[i]);
775 ret.systems_per_page_.push_back (lines.size ());
776 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
777 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
779 /* don't do finalize_spacing_result () because we are only an internal function */
784 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
786 Real page1_height = page_height (first_page_num, false);
787 Real page2_height = page_height (first_page_num+1, last ());
788 bool ragged1 = ragged ();
789 bool ragged2 = ragged () || (last () && ragged_last ());
791 /* if there is a forced break, this reduces to 2 1-page problems */
792 cache_line_details (configuration);
793 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
794 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
796 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
797 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
798 Spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
799 Spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
801 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
802 p1.force_.push_back (p2.force_[0]);
803 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
807 vector<Real> page1_force;
808 vector<Real> page2_force;
809 Page_spacing page1 (page1_height);
810 Page_spacing page2 (page2_height);
812 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
813 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
815 /* find the page 1 and page 2 forces for each page-breaking position */
816 for (vsize i = 0; i < page1_force.size (); i++)
818 page1.append_system (cached_line_details_[i]);
819 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
820 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
823 page2_force[page2_force.size () - 1 - i] =
824 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
826 page2_force[page2_force.size () - 1 - i] = page2.force_;
829 /* find the position that minimises the sum of the page forces */
830 vsize best_sys_count = 1;
831 Real best_demerits = infinity_f;
832 for (vsize i = 0; i < page1_force.size (); i++)
834 Real dem = page1_force[i] * page1_force[i]
835 + page2_force[i] * page2_force[i]
836 + cached_line_details_[i+1].page_penalty_
837 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
838 if (dem < best_demerits)
841 best_sys_count = i+1;
846 ret.systems_per_page_.push_back (best_sys_count);
847 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
848 ret.force_.push_back (page1_force[best_sys_count-1]);
849 ret.force_.push_back (page2_force[best_sys_count-1]);
850 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
851 + cached_line_details_.back ().page_penalty_
852 + cached_line_details_.back ().turn_penalty_;
854 /* don't do finalize_spacing_result () because we are only an internal function */
859 Page_breaking::all_lines_stretched (vsize configuration)
861 cache_line_details (configuration);
862 for (vsize i = 0; i < cached_line_details_.size (); i++)
863 if (cached_line_details_[i].force_ < 0)
869 Page_breaking::Line_division
870 Page_breaking::current_configuration (vsize configuration_index) const
872 return current_configurations_[configuration_index];
875 bool Page_breaking::last () const
877 return current_end_breakpoint_ == breaks_.size () - 1;