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-bottom"));
100 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
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 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
239 for (vsize i = 0; i < lines_per_page.size (); i++)
241 SCM page_num = scm_from_int (i + first_page_number);
242 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
243 SCM rag = scm_from_bool (ragged () || (to_boolean (last) && ragged_last ()));
244 SCM line_count = scm_from_int (lines_per_page[i]);
245 SCM lines = scm_list_head (systems, line_count);
246 SCM page = scm_apply_0 (make_page,
247 scm_list_n (book, lines, page_num, rag, last, SCM_UNDEFINED));
249 scm_apply_1 (page_stencil, page, SCM_EOL);
250 ret = scm_cons (page, ret);
251 systems = scm_list_tail (systems, line_count);
253 ret = scm_reverse (ret);
257 /* The page-turn-page-breaker needs to have a line-breaker between any two
258 columns with non-NULL page-turn-permission.
260 The optimal-breaker needs to have a line-breaker between any two columns
261 with page-break-permission = 'force.
263 By using a grob predicate, we can accommodate both of these uses.
266 Page_breaking::create_system_list ()
268 SCM specs = book_->get_system_specs ();
269 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
271 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
273 SCM system_count = ps->layout ()->c_variable ("system-count");
275 if (scm_is_number (system_count))
276 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
277 scm_vector_to_list (ps->get_paper_systems ()),
280 all_.push_back (System_spec (ps));
284 Prob *pb = unsmob_prob (scm_car (s));
288 all_.push_back (System_spec (pb));
294 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
296 SCM force_sym = ly_symbol2scm ("force");
298 chunks_.push_back (Break_position ());
299 breaks_.push_back (Break_position ());
301 for (vsize i = 0; i < all_.size (); i++)
305 vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
306 vector<vsize> line_breaker_columns;
307 line_breaker_columns.push_back (0);
309 for (vsize j = 1; j < cols.size (); j++)
311 bool last = j == cols.size () - 1;
312 bool break_point = is_break (cols[j]);
313 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
314 Break_position cur_pos = Break_position (i,
315 line_breaker_columns.size (),
319 if (break_point || (i == all_.size () - 1 && last))
320 breaks_.push_back (cur_pos);
321 if (chunk_end || last)
322 chunks_.push_back (cur_pos);
324 if ((break_point || chunk_end) && !last)
325 line_breaker_columns.push_back (j);
327 line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
331 /* TODO: we want some way of applying Break_p to a prob? */
332 if (i == all_.size () - 1)
333 breaks_.push_back (Break_position (i));
335 chunks_.push_back (Break_position (i));
336 line_breaking_.push_back (Constrained_breaking (NULL));
341 vector<Break_position>
342 Page_breaking::chunk_list (vsize start_index, vsize end_index)
344 Break_position start = breaks_[start_index];
345 Break_position end = breaks_[end_index];
348 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
351 vector<Break_position> ret;
352 ret.push_back (start);
353 for (; i < chunks_.size () && chunks_[i] < end; i++)
354 ret.push_back (chunks_[i]);
360 Page_breaking::min_system_count (vsize start, vsize end)
362 vector<Break_position> chunks = chunk_list (start, end);
363 Line_division div = system_count_bounds (chunks, true);
366 for (vsize i = 0; i < div.size (); i++)
372 Page_breaking::max_system_count (vsize start, vsize end)
374 vector<Break_position> chunks = chunk_list (start, end);
375 Line_division div = system_count_bounds (chunks, false);
378 for (vsize i = 0; i < div.size (); i++)
383 Page_breaking::Line_division
384 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
386 assert (chunks.size () >= 2);
389 ret.resize (chunks.size () - 1, 1);
391 for (vsize i = 0; i + 1 < chunks.size (); i++)
393 vsize sys = next_system (chunks[i]);
394 if (all_[sys].pscore_)
398 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
400 ? line_breaking_[sys].min_system_count (start, end)
401 : line_breaking_[sys].max_system_count (start, end);
409 Page_breaking::set_current_breakpoints (vsize start,
412 Line_division lower_bound,
413 Line_division upper_bound)
415 current_chunks_ = chunk_list (start, end);
416 current_start_breakpoint_ = start;
417 current_end_breakpoint_ = end;
418 clear_line_details_cache ();
420 if (!lower_bound.size ())
421 lower_bound = system_count_bounds (current_chunks_, true);
422 if (!upper_bound.size ())
423 upper_bound = system_count_bounds (current_chunks_, false);
425 assert (lower_bound.size () == current_chunks_.size () - 1);
426 assert (upper_bound.size () == current_chunks_.size () - 1);
428 Line_division work_in_progress;
429 current_configurations_.clear ();
430 line_divisions_rec (system_count,
435 /* we only consider a constant number of configurations. Otherwise,
436 this becomes slow when there are many small scores. The constant
437 5 is somewhat arbitrary. */
438 if (current_configurations_.size () > 5)
440 vector<pair<Real,vsize> > dems_and_indices;
442 for (vsize i = 0; i < current_configurations_.size (); i++)
444 cache_line_details (i);
446 for (vsize j = 0; j < cached_line_details_.size (); j++)
447 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
448 + cached_line_details_[j].break_penalty_;
450 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
452 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
454 vector<Line_division> best_5_configurations;
455 for (vsize i = 0; i < 5; i++)
456 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
458 clear_line_details_cache ();
459 current_configurations_ = best_5_configurations;
464 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
466 current_chunks_ = chunk_list (start, end);
467 current_start_breakpoint_ = start;
468 current_end_breakpoint_ = end;
469 clear_line_details_cache ();
472 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
474 vsize sys = next_system (current_chunks_[i]);
475 if (all_[sys].pscore_)
477 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
478 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
483 current_configurations_.clear ();
484 current_configurations_.push_back (div);
488 Page_breaking::current_configuration_count () const
490 return current_configurations_.size ();
494 Page_breaking::cache_line_details (vsize configuration_index)
496 if (cached_configuration_index_ != configuration_index)
498 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
499 if (!scm_is_number (padding_scm))
500 padding_scm = book_->paper_->c_variable ("between-system-padding");
501 Real padding = robust_scm2double (padding_scm, 0.0);
503 Line_division &div = current_configurations_[configuration_index];
504 uncompressed_line_details_.clear ();
505 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
507 vsize sys = next_system (current_chunks_[i]);
508 if (all_[sys].pscore_)
512 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
514 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
515 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
519 assert (div[i] == 1);
520 uncompressed_line_details_.push_back (Line_details (all_[sys].prob_));
521 uncompressed_line_details_.back ().padding_ = padding;
524 cached_line_details_ = compress_lines (uncompressed_line_details_);
529 Page_breaking::clear_line_details_cache ()
531 cached_configuration_index_ = VPOS;
532 cached_line_details_.clear ();
533 uncompressed_line_details_.clear ();
537 Page_breaking::line_divisions_rec (vsize system_count,
538 Line_division const &min_sys,
539 Line_division const &max_sys,
540 Line_division *cur_division)
542 vsize my_index = cur_division->size ();
543 vsize others_min = 0;
544 vsize others_max = 0;
546 for (vsize i = my_index + 1; i < min_sys.size (); i++)
548 others_min += min_sys[i];
549 others_max += max_sys[i];
551 others_max = min (others_max, system_count);
552 vsize real_min = max (min_sys[my_index], system_count - others_max);
553 vsize real_max = min (max_sys[my_index], system_count - others_min);
555 if (real_min > real_max || real_min <= 0)
557 /* this should never happen within a recursive call. If it happens
558 at all, it means that we were called with an unsolvable problem
559 and we should return an empty result */
560 assert (my_index == 0);
564 for (vsize i = real_min; i <= real_max; i++)
566 cur_division->push_back (i);
567 if (my_index == min_sys.size () - 1)
568 current_configurations_.push_back (*cur_division);
570 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
571 cur_division->pop_back ();
576 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
579 Real cur_rod_height = 0;
580 Real cur_spring_height = 0;
581 Real cur_page_height = page_height (first_page_num, false);
583 cache_line_details (configuration);
584 for (vsize i = 0; i < cached_line_details_.size (); i++)
586 Real ext_len = cached_line_details_[i].extent_.length ();
587 Real next_rod_height = cur_rod_height + ext_len
588 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
589 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
590 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
593 if ((next_height > cur_page_height && cur_rod_height > 0)
595 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
597 cur_rod_height = ext_len;
598 cur_spring_height = line_space (cached_line_details_[i]);
599 cur_page_height = page_height (first_page_num + ret, false);
604 cur_rod_height = next_rod_height;
605 cur_spring_height = next_spring_height;
609 /* there are two potential problems with the last page (because we didn't know
610 it was the last page until after we managed to fit all the systems to it):
611 - we are ragged-last but the last page has a compressed spring
612 - the value returned by page_height (num, true) is smaller than the
613 value returned by page_height (num, false) and it causes the page not to
616 In either case, we just need to add one more page. This is because the last
617 line will always fit on the extra page and by adding one more page to the
618 end, the previous page is no longer the last page, so our previous
619 calculations that treated it as a non-last page were ok.
622 cur_page_height = page_height (first_page_num + ret - 1, true);
623 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
624 if (cur_height > cur_page_height
625 /* don't increase the page count if the last page had only one system */
626 && cur_rod_height > cached_line_details_.back ().extent_.length ())
629 assert (ret <= cached_line_details_.size ());
634 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
637 assert (n >= min_page_count (configuration, first_page_num));
639 cache_line_details (configuration);
640 if (n > cached_line_details_.size ())
641 return Spacing_result ();
643 ret = space_systems_on_1_page (cached_line_details_,
644 page_height (first_page_num, last ()),
645 ragged () || (last () && ragged_last ()));
647 ret = space_systems_on_2_pages (configuration, first_page_num);
650 Page_spacer ps (cached_line_details_, first_page_num, this);
654 return finalize_spacing_result (configuration, ret);
658 Page_breaking::blank_page_penalty () const
660 SCM penalty_sym = last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
661 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
665 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
667 Spacing_result n_res;
668 Spacing_result m_res;
672 n_res = space_systems_on_n_pages (configuration, n, first_page_num);
673 m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
677 cache_line_details (configuration);
679 vsize min_p_count = min_page_count (configuration, first_page_num);
680 Page_spacer ps (cached_line_details_, first_page_num, this);
681 if (n >= min_p_count)
682 n_res = ps.solve (n);
683 if (n < cached_line_details_.size ())
684 m_res = ps.solve (n+1);
687 Real penalty = blank_page_penalty ();
688 n_res.demerits_ += penalty;
689 n_res.force_.back () += penalty;
691 if (m_res.demerits_ < n_res.demerits_)
697 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
699 vsize min_p_count = min_page_count (configuration, first_page_num);
700 Real odd_pages_penalty = blank_page_penalty ();
702 cache_line_details (configuration);
703 Page_spacer ps (cached_line_details_, first_page_num, this);
704 Spacing_result best = ps.solve (min_p_count);
705 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
706 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
708 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
710 Spacing_result cur = ps.solve (i);
711 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
712 if (cur.demerits_ < best.demerits_)
716 return finalize_spacing_result (configuration, best);
719 /* Calculate demerits and fix res.systems_per_page_ so that
720 it refers to the original line numbers, not the ones given by compress_lines (). */
722 Page_breaking::finalize_spacing_result (vsize configuration, Spacing_result res)
724 cache_line_details (configuration);
725 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
728 Real line_penalty = 0;
730 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
732 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
734 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
735 line_penalty += uncompressed_line_details_[i].break_penalty_;
738 for (vsize i = 0; i < res.force_.size (); i++)
740 Real f = res.force_[i];
741 if (isinf (f) && res.systems_per_page_[i] == 1)
747 /* for a while we tried averaging page and line forces across pages instead
748 of summing them, but it caused a problem: if there is a single page
749 with a very bad page force (for example because of a forced page break),
750 the page breaker will put in a _lot_ of pages so that the bad force
751 becomes averaged out over many pages. */
752 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
757 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
758 are by far the most common cases, we have special functions for them.
760 space_systems_on_1_page has a different calling convention than most of the
761 space_systems functions. This is because space_systems_on_1_page is (unlike
762 the other space_systems functions) sometimes called on subsets of a full
765 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
767 Page_spacing space (page_height);
770 for (vsize i = 0; i < lines.size (); i++)
771 space.append_system (lines[i]);
773 ret.systems_per_page_.push_back (lines.size ());
774 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
775 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
777 /* don't do finalize_spacing_result () because we are only an internal function */
782 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
784 Real page1_height = page_height (first_page_num, false);
785 Real page2_height = page_height (first_page_num+1, last ());
786 bool ragged1 = ragged ();
787 bool ragged2 = ragged () || (last () && ragged_last ());
789 /* if there is a forced break, this reduces to 2 1-page problems */
790 cache_line_details (configuration);
791 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
792 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
794 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
795 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
796 Spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
797 Spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
799 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
800 p1.force_.push_back (p2.force_[0]);
801 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
805 vector<Real> page1_force;
806 vector<Real> page2_force;
807 Page_spacing page1 (page1_height);
808 Page_spacing page2 (page2_height);
810 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
811 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
813 /* find the page 1 and page 2 forces for each page-breaking position */
814 for (vsize i = 0; i < page1_force.size (); i++)
816 page1.append_system (cached_line_details_[i]);
817 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
818 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
821 page2_force[page2_force.size () - 1 - i] =
822 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
824 page2_force[page2_force.size () - 1 - i] = page2.force_;
827 /* find the position that minimises the sum of the page forces */
828 vsize best_sys_count = 1;
829 Real best_demerits = infinity_f;
830 for (vsize i = 0; i < page1_force.size (); i++)
832 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
833 Real uneven = 2 * (page1_force[i] - page2_force[i]);
834 Real dem = uneven * uneven + f
835 + cached_line_details_[i+1].page_penalty_
836 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
837 if (dem < best_demerits)
840 best_sys_count = i+1;
845 ret.systems_per_page_.push_back (best_sys_count);
846 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
847 ret.force_.push_back (page1_force[best_sys_count-1]);
848 ret.force_.push_back (page2_force[best_sys_count-1]);
849 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
850 + cached_line_details_.back ().page_penalty_
851 + cached_line_details_.back ().turn_penalty_;
853 /* don't do finalize_spacing_result () because we are only an internal function */
858 Page_breaking::all_lines_stretched (vsize configuration)
860 cache_line_details (configuration);
861 for (vsize i = 0; i < cached_line_details_.size (); i++)
862 if (cached_line_details_[i].force_ < 0)
868 Page_breaking::Line_division
869 Page_breaking::current_configuration (vsize configuration_index) const
871 return current_configurations_[configuration_index];
874 bool Page_breaking::last () const
876 return current_end_breakpoint_ == breaks_.size () - 1;