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 /* for Page_breaking, the start index (when we are dealing with the stuff
57 between a pair of breakpoints) refers to the break_ index of the end of
58 the previous page. So the system index of the start of the current page
59 could either be the same as the end of the previous page or one more than
62 /* Turn a break index into the sys index that starts the next page */
64 Page_breaking::next_system (Break_position const &break_pos) const
66 vsize sys = break_pos.system_spec_index_;
68 if (sys == VPOS) /* beginning of the book */
70 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
71 return sys; /* the score overflows the previous page */
72 return sys + 1; /* this page starts with a new System_spec */
75 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
78 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
79 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
80 create_system_list ();
81 find_chunks_and_breaks (is_break);
84 Page_breaking::~Page_breaking ()
89 Page_breaking::ragged () const
95 Page_breaking::ragged_last () const
100 /* translate indices into breaks_ into start-end parameters for the line breaker */
102 Page_breaking::line_breaker_args (vsize sys,
103 Break_position const &start,
104 Break_position const &end,
105 vsize *line_breaker_start,
106 vsize *line_breaker_end)
108 assert (system_specs_[sys].pscore_);
109 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
111 if (start.system_spec_index_ == sys)
112 *line_breaker_start = start.score_break_;
114 *line_breaker_start = 0;
116 if (end.system_spec_index_ == sys)
117 *line_breaker_end = end.score_break_;
119 *line_breaker_end = VPOS;
123 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
124 Line_division const &div)
126 vector<Break_position> chunks = chunk_list (start_break, end_break);
127 bool ignore_div = false;
128 if (chunks.size () != div.size () + 1)
130 programming_error ("did not find a valid page breaking configuration");
134 for (vsize i = 0; i + 1 < chunks.size (); i++)
136 vsize sys = next_system (chunks[i]);
137 if (system_specs_[sys].pscore_)
141 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
143 vector<Column_x_positions> pos = ignore_div
144 ? line_breaking_[sys].best_solution (start, end)
145 : line_breaking_[sys].solve (start, end, div[i]);
146 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
152 Page_breaking::systems ()
155 for (vsize sys = 0; sys < system_specs_.size (); sys++)
157 if (system_specs_[sys].pscore_)
159 system_specs_[sys].pscore_->root_system ()
160 ->do_break_substitution_and_fixup_refpoints ();
161 SCM lines = system_specs_[sys].pscore_->root_system ()
162 ->get_broken_system_grobs ();
163 ret = scm_cons (lines, ret);
167 Prob *pb = system_specs_[sys].prob_;
168 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
172 return scm_append (scm_reverse (ret));
176 Page_breaking::page_height (int page_num, bool last) const
178 SCM mod = scm_c_resolve_module ("scm page");
179 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
180 SCM make_page = scm_c_module_lookup (mod, "make-page");
182 calc_height = scm_variable_ref (calc_height);
183 make_page = scm_variable_ref (make_page);
185 SCM page = scm_apply_0 (make_page, scm_list_n (
187 ly_symbol2scm ("page-number"), scm_from_int (page_num),
188 ly_symbol2scm ("is-last"), scm_from_bool (last),
190 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
191 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
195 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
197 Break_position const &pos = breaks_[breakpoint];
199 if (pos.system_spec_index_ == VPOS)
201 if (system_specs_[pos.system_spec_index_].pscore_)
202 return pos.col_->get_property (str);
203 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
207 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
209 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
210 SCM page_module = scm_c_resolve_module ("scm page");
212 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
213 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
214 make_page = scm_variable_ref (make_page);
215 page_stencil = scm_variable_ref (page_stencil);
217 SCM book = book_->self_scm ();
218 int first_page_number
219 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
222 for (vsize i = 0; i < lines_per_page.size (); i++)
224 SCM page_num = scm_from_int (i + first_page_number);
225 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
226 SCM rag = scm_from_bool (ragged () || (to_boolean (last)
228 SCM line_count = scm_from_int (lines_per_page[i]);
229 SCM lines = scm_list_head (systems, line_count);
230 SCM page = scm_apply_0 (make_page,
231 scm_list_n (book, lines, page_num,
232 rag, last, SCM_UNDEFINED));
234 scm_apply_1 (page_stencil, page, SCM_EOL);
235 ret = scm_cons (page, ret);
236 systems = scm_list_tail (systems, line_count);
238 ret = scm_reverse (ret);
242 /* The page-turn-page-breaker needs to have a line-breaker between any two
243 columns with non-NULL page-turn-permission.
245 The optimal-breaker needs to have a line-breaker between any two columns
246 with page-break-permission = 'force.
248 By using a grob predicate, we can accommodate both of these uses.
251 Page_breaking::create_system_list ()
253 SCM specs = book_->get_system_specs ();
254 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
256 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
258 SCM system_count = ps->layout ()->c_variable ("system-count");
260 if (scm_is_number (system_count))
261 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
262 scm_vector_to_list (ps->get_paper_systems ()),
265 system_specs_.push_back (System_spec (ps));
269 Prob *pb = unsmob_prob (scm_car (s));
273 system_specs_.push_back (System_spec (pb));
279 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
281 SCM force_sym = ly_symbol2scm ("force");
283 chunks_.push_back (Break_position ());
284 breaks_.push_back (Break_position ());
286 for (vsize i = 0; i < system_specs_.size (); i++)
288 if (system_specs_[i].pscore_)
291 = system_specs_[i].pscore_->root_system ()->used_columns ();
292 vector<vsize> line_breaker_columns;
293 line_breaker_columns.push_back (0);
295 for (vsize j = 1; j < cols.size (); j++)
297 bool last = (j == cols.size () - 1);
298 bool break_point = is_break (cols[j]);
299 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
300 Break_position cur_pos = Break_position (i,
301 line_breaker_columns.size (),
305 if (break_point || (i == system_specs_.size () - 1 && last))
306 breaks_.push_back (cur_pos);
307 if (chunk_end || last)
308 chunks_.push_back (cur_pos);
310 if ((break_point || chunk_end) && !last)
311 line_breaker_columns.push_back (j);
313 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
317 /* TODO: we want some way of applying Break_p to a prob? */
318 if (i == system_specs_.size () - 1)
319 breaks_.push_back (Break_position (i));
321 chunks_.push_back (Break_position (i));
323 /* FIXME: shouldn't we push a Null_breaker or similar dummy
325 line_breaking_.push_back (Constrained_breaking (NULL));
330 vector<Break_position>
331 Page_breaking::chunk_list (vsize start_index, vsize end_index)
333 Break_position start = breaks_[start_index];
334 Break_position end = breaks_[end_index];
337 for (; i < chunks_.size () && chunks_[i] <= start; i++)
340 vector<Break_position> ret;
341 ret.push_back (start);
342 for (; i < chunks_.size () && chunks_[i] < end; i++)
343 ret.push_back (chunks_[i]);
349 Page_breaking::min_system_count (vsize start, vsize end)
351 vector<Break_position> chunks = chunk_list (start, end);
352 Line_division div = system_count_bounds (chunks, true);
355 for (vsize i = 0; i < div.size (); i++)
361 Page_breaking::max_system_count (vsize start, vsize end)
363 vector<Break_position> chunks = chunk_list (start, end);
364 Line_division div = system_count_bounds (chunks, false);
367 for (vsize i = 0; i < div.size (); i++)
372 Page_breaking::Line_division
373 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
376 assert (chunks.size () >= 2);
379 ret.resize (chunks.size () - 1, 1);
381 for (vsize i = 0; i + 1 < chunks.size (); i++)
383 vsize sys = next_system (chunks[i]);
384 if (system_specs_[sys].pscore_)
388 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
390 ? line_breaking_[sys].min_system_count (start, end)
391 : line_breaking_[sys].max_system_count (start, end);
399 Page_breaking::set_current_breakpoints (vsize start,
402 Line_division lower_bound,
403 Line_division upper_bound)
405 current_chunks_ = chunk_list (start, end);
406 current_start_breakpoint_ = start;
407 current_end_breakpoint_ = end;
408 clear_line_details_cache ();
410 if (!lower_bound.size ())
411 lower_bound = system_count_bounds (current_chunks_, true);
412 if (!upper_bound.size ())
413 upper_bound = system_count_bounds (current_chunks_, false);
415 assert (lower_bound.size () == current_chunks_.size () - 1);
416 assert (upper_bound.size () == current_chunks_.size () - 1);
418 Line_division work_in_progress;
419 current_configurations_.clear ();
420 line_divisions_rec (system_count,
425 /* we only consider a constant number of configurations. Otherwise,
426 this becomes slow when there are many small scores. The constant
427 5 is somewhat arbitrary. */
428 if (current_configurations_.size () > 5)
430 vector<pair<Real,vsize> > dems_and_indices;
432 for (vsize i = 0; i < current_configurations_.size (); i++)
434 cache_line_details (i);
436 for (vsize j = 0; j < cached_line_details_.size (); j++)
437 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
438 + cached_line_details_[j].break_penalty_;
440 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
442 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
444 vector<Line_division> best_5_configurations;
445 for (vsize i = 0; i < 5; i++)
446 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
448 clear_line_details_cache ();
449 current_configurations_ = best_5_configurations;
454 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
456 current_chunks_ = chunk_list (start, end);
457 current_start_breakpoint_ = start;
458 current_end_breakpoint_ = end;
459 clear_line_details_cache ();
462 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
464 vsize sys = next_system (current_chunks_[i]);
465 if (system_specs_[sys].pscore_)
467 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
468 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
473 current_configurations_.clear ();
474 current_configurations_.push_back (div);
478 Page_breaking::current_configuration_count () const
480 return current_configurations_.size ();
484 Page_breaking::cache_line_details (vsize configuration_index)
486 if (cached_configuration_index_ != configuration_index)
488 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
489 if (!scm_is_number (padding_scm))
490 padding_scm = book_->paper_->c_variable ("between-system-padding");
491 Real padding = robust_scm2double (padding_scm, 0.0);
493 Line_division &div = current_configurations_[configuration_index];
494 uncompressed_line_details_.clear ();
495 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
497 vsize sys = next_system (current_chunks_[i]);
498 if (system_specs_[sys].pscore_)
502 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
504 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
505 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
509 assert (div[i] == 1);
510 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
511 uncompressed_line_details_.back ().padding_ = padding;
514 cached_line_details_ = compress_lines (uncompressed_line_details_);
519 Page_breaking::clear_line_details_cache ()
521 cached_configuration_index_ = VPOS;
522 cached_line_details_.clear ();
523 uncompressed_line_details_.clear ();
527 Page_breaking::line_divisions_rec (vsize system_count,
528 Line_division const &min_sys,
529 Line_division const &max_sys,
530 Line_division *cur_division)
532 vsize my_index = cur_division->size ();
533 vsize others_min = 0;
534 vsize others_max = 0;
536 for (vsize i = my_index + 1; i < min_sys.size (); i++)
538 others_min += min_sys[i];
539 others_max += max_sys[i];
541 others_max = min (others_max, system_count);
542 vsize real_min = max (min_sys[my_index], system_count - others_max);
543 vsize real_max = min (max_sys[my_index], system_count - others_min);
545 if (real_min > real_max || real_min <= 0)
547 /* this should never happen within a recursive call. If it happens
548 at all, it means that we were called with an unsolvable problem
549 and we should return an empty result */
550 assert (my_index == 0);
554 for (vsize i = real_min; i <= real_max; i++)
556 cur_division->push_back (i);
557 if (my_index == min_sys.size () - 1)
558 current_configurations_.push_back (*cur_division);
560 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
561 cur_division->pop_back ();
566 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
569 Real cur_rod_height = 0;
570 Real cur_spring_height = 0;
571 Real cur_page_height = page_height (first_page_num, false);
573 cache_line_details (configuration);
574 for (vsize i = 0; i < cached_line_details_.size (); i++)
576 Real ext_len = cached_line_details_[i].extent_.length ();
577 Real next_rod_height = cur_rod_height + ext_len
578 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
579 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
580 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
583 if ((next_height > cur_page_height && cur_rod_height > 0)
585 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
587 cur_rod_height = ext_len;
588 cur_spring_height = line_space (cached_line_details_[i]);
589 cur_page_height = page_height (first_page_num + ret, false);
594 cur_rod_height = next_rod_height;
595 cur_spring_height = next_spring_height;
599 /* there are two potential problems with the last page (because we didn't know
600 it was the last page until after we managed to fit all the systems to it):
601 - we are ragged-last but the last page has a compressed spring
602 - the value returned by page_height (num, true) is smaller than the
603 value returned by page_height (num, false) and it causes the page not to
606 In either case, we just need to add one more page. This is because the last
607 line will always fit on the extra page and by adding one more page to the
608 end, the previous page is no longer the last page, so our previous
609 calculations that treated it as a non-last page were ok.
612 cur_page_height = page_height (first_page_num + ret - 1, true);
613 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
614 if (cur_height > cur_page_height
615 /* don't increase the page count if the last page had only one system */
616 && cur_rod_height > cached_line_details_.back ().extent_.length ())
619 assert (ret <= cached_line_details_.size ());
624 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
626 Page_spacing_result ret;
627 assert (n >= min_page_count (configuration, first_page_num));
629 cache_line_details (configuration);
630 if (n > cached_line_details_.size ())
631 return Page_spacing_result ();
634 ret = space_systems_on_1_page (cached_line_details_,
635 page_height (first_page_num, is_last ()),
636 ragged () || (is_last () && ragged_last ()));
638 uncompress_page_spacing_results (&ret);
642 ret = space_systems_on_2_pages (configuration, first_page_num);
643 uncompress_page_spacing_results (&ret);
647 Page_spacer ps (cached_line_details_, first_page_num, this);
651 return finalize_spacing_result (configuration, ret);
655 Page_breaking::blank_page_penalty () const
657 SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
658 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
662 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
664 Page_spacing_result n_res;
665 Page_spacing_result m_res;
669 n_res = space_systems_on_n_pages (configuration, n, first_page_num);
670 m_res = space_systems_on_n_pages (configuration, n+1, first_page_num);
674 cache_line_details (configuration);
676 vsize min_p_count = min_page_count (configuration, first_page_num);
677 Page_spacer ps (cached_line_details_, first_page_num, this);
678 if (n >= min_p_count)
680 n_res = ps.solve (n);
681 uncompress_page_spacing_results (&n_res);
683 if (n < cached_line_details_.size ())
685 m_res = ps.solve (n+1);
686 uncompress_page_spacing_results (&m_res);
691 Real penalty = blank_page_penalty ();
692 n_res.demerits_ += penalty;
693 n_res.force_.back () += penalty;
695 if (m_res.demerits_ < n_res.demerits_)
701 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
703 vsize min_p_count = min_page_count (configuration, first_page_num);
704 Real odd_pages_penalty = blank_page_penalty ();
706 cache_line_details (configuration);
707 Page_spacer ps (cached_line_details_, first_page_num, this);
708 Page_spacing_result best = ps.solve (min_p_count);
709 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
710 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
712 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
714 Page_spacing_result cur = ps.solve (i);
715 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
716 if (cur.demerits_ < best.demerits_)
720 return finalize_spacing_result (configuration, best);
725 /* translate the number of systems-per-page into something meaningful for
726 the uncompressed lines.
729 uncompress_solution (vector<vsize> const &systems_per_page,
730 vector<Line_details> const &compressed)
735 for (vsize i = 0; i < systems_per_page.size (); i++)
737 int compressed_count = 0;
738 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
739 compressed_count += (int)compressed[j].force_;
741 ret.push_back (systems_per_page[i] + compressed_count);
742 start_sys += systems_per_page[i];
748 Page_breaking::uncompress_page_spacing_results (Page_spacing_result *res)
750 res->systems_per_page_ = uncompress_solution (res->systems_per_page_, cached_line_details_);
753 /* Calculate demerits and fix res.systems_per_page_ so that
754 it refers to the original line numbers, not the ones given by compress_lines (). */
756 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
758 cache_line_details (configuration);
759 uncompress_page_spacing_results (&res);
762 Real line_penalty = 0;
764 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
766 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
768 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
769 line_penalty += uncompressed_line_details_[i].break_penalty_;
772 for (vsize i = 0; i < res.force_.size (); i++)
774 Real f = res.force_[i];
775 if (isinf (f) && res.systems_per_page_[i] == 1)
781 /* for a while we tried averaging page and line forces across pages instead
782 of summing them, but it caused a problem: if there is a single page
783 with a very bad page force (for example because of a forced page break),
784 the page breaker will put in a _lot_ of pages so that the bad force
785 becomes averaged out over many pages. */
786 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
790 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
791 are by far the most common cases, we have special functions for them.
793 space_systems_on_1_page has a different calling convention than most of the
794 space_systems functions. This is because space_systems_on_1_page is (unlike
795 the other space_systems functions) sometimes called on subsets of a full
798 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
800 Page_spacing space (page_height);
801 Page_spacing_result ret;
803 for (vsize i = 0; i < lines.size (); i++)
804 space.append_system (lines[i]);
806 ret.systems_per_page_.push_back (lines.size ());
807 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
808 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
810 /* don't do finalize_spacing_result () because we are only an internal function */
815 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
817 Real page1_height = page_height (first_page_num, false);
818 Real page2_height = page_height (first_page_num + 1, is_last ());
819 bool ragged1 = ragged ();
820 bool ragged2 = ragged () || (is_last () && ragged_last ());
822 /* if there is a forced break, this reduces to 2 1-page problems */
823 cache_line_details (configuration);
824 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
825 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
827 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
828 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
829 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
830 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
832 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
833 p1.force_.push_back (p2.force_[0]);
834 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
838 vector<Real> page1_force;
839 vector<Real> page2_force;
840 Page_spacing page1 (page1_height);
841 Page_spacing page2 (page2_height);
843 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
844 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
846 /* find the page 1 and page 2 forces for each page-breaking position */
847 for (vsize i = 0; i < page1_force.size (); i++)
849 page1.append_system (cached_line_details_[i]);
850 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
851 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
854 page2_force[page2_force.size () - 1 - i] =
855 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
857 page2_force[page2_force.size () - 1 - i] = page2.force_;
860 /* find the position that minimises the sum of the page forces */
861 vsize best_sys_count = 1;
862 Real best_demerits = infinity_f;
863 for (vsize i = 0; i < page1_force.size (); i++)
865 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
866 Real uneven = 2 * (page1_force[i] - page2_force[i]);
867 Real dem = uneven * uneven + f
868 + cached_line_details_[i+1].page_penalty_
869 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
870 if (dem < best_demerits)
873 best_sys_count = i+1;
877 Page_spacing_result ret;
878 ret.systems_per_page_.push_back (best_sys_count);
879 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
880 ret.force_.push_back (page1_force[best_sys_count-1]);
881 ret.force_.push_back (page2_force[best_sys_count-1]);
882 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
883 + cached_line_details_.back ().page_penalty_
884 + cached_line_details_.back ().turn_penalty_;
886 /* don't do finalize_spacing_result () because we are only an internal function */
891 Page_breaking::all_lines_stretched (vsize configuration)
893 cache_line_details (configuration);
894 for (vsize i = 0; i < cached_line_details_.size (); i++)
895 if (cached_line_details_[i].force_ < 0)
901 Page_breaking::Line_division
902 Page_breaking::current_configuration (vsize configuration_index) const
904 return current_configurations_[configuration_index];
908 Page_breaking::is_last () const
910 return current_end_breakpoint_ == last_break_position ();
914 Page_breaking::last_break_position () const
916 return breaks_.size () - 1;