2 page-breaking.cc -- implement a superclass and utility
3 functions shared by various page-breaking algorithms
5 source file of the GNU LilyPond music typesetter
7 (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
10 #include "page-breaking.hh"
12 #include "international.hh"
14 #include "output-def.hh"
15 #include "page-spacing.hh"
16 #include "paper-book.hh"
17 #include "paper-score.hh"
18 #include "paper-system.hh"
22 /* for each forbidden page break, merge the systems around it into one
24 static vector<Line_details>
25 compress_lines (const vector<Line_details> &orig)
27 vector<Line_details> ret;
29 for (vsize i = 0; i < orig.size (); i++)
31 if (ret.size () && !scm_is_symbol (ret.back ().page_permission_))
33 Line_details const &old = ret.back ();
34 Line_details compressed = orig[i];
35 compressed.extent_[DOWN] = old.extent_[DOWN];
36 compressed.extent_[UP] = old.extent_[UP] + orig[i].extent_.length () + old.padding_;
37 compressed.space_ += old.space_;
38 compressed.inverse_hooke_ += old.inverse_hooke_;
40 /* we don't need the force_ field for the vertical spacing,
41 so we use force_ = n to signal that the line was compressed,
42 reducing the number of lines by n (and force_ = 0 otherwise).
43 This makes uncompression much easier. */
44 compressed.force_ = old.force_ + 1;
45 ret.back () = compressed;
49 ret.push_back (orig[i]);
50 ret.back ().force_ = 0;
56 /* translate the number of systems-per-page into something meaningful for
57 the uncompressed lines.
60 uncompress_solution (vector<vsize> const &systems_per_page,
61 vector<Line_details> const &compressed)
66 for (vsize i = 0; i < systems_per_page.size (); i++)
68 int compressed_count = 0;
69 for (vsize j = start_sys; j < start_sys + systems_per_page[i]; j++)
70 compressed_count += (int)compressed[j].force_;
72 ret.push_back (systems_per_page[i] + compressed_count);
73 start_sys += systems_per_page[i];
78 /* for Page_breaking, the start index (when we are dealing with the stuff
79 between a pair of breakpoints) refers to the break_ index of the end of
80 the previous page. So the system index of the start of the current page
81 could either be the same as the end of the previous page or one more than
84 /* Turn a break index into the sys index that starts the next page */
86 Page_breaking::next_system (Break_position const &break_pos) const
88 vsize sys = break_pos.system_spec_index_;
90 if (sys == VPOS) /* beginning of the book */
92 if (system_specs_[sys].pscore_ && !break_pos.score_ender_)
93 return sys; /* the score overflows the previous page */
94 return sys + 1; /* this page starts with a new System_spec */
97 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
100 ragged_ = to_boolean (pb->paper_->c_variable ("ragged-bottom"));
101 ragged_last_ = to_boolean (pb->paper_->c_variable ("ragged-last-bottom"));
102 create_system_list ();
103 find_chunks_and_breaks (is_break);
106 Page_breaking::~Page_breaking ()
111 Page_breaking::ragged () const
117 Page_breaking::ragged_last () const
122 /* translate indices into breaks_ into start-end parameters for the line breaker */
124 Page_breaking::line_breaker_args (vsize sys,
125 Break_position const &start,
126 Break_position const &end,
127 vsize *line_breaker_start,
128 vsize *line_breaker_end)
130 assert (system_specs_[sys].pscore_);
131 assert (next_system (start) <= sys && sys <= end.system_spec_index_);
133 if (start.system_spec_index_ == sys)
134 *line_breaker_start = start.score_break_;
136 *line_breaker_start = 0;
138 if (end.system_spec_index_ == sys)
139 *line_breaker_end = end.score_break_;
141 *line_breaker_end = VPOS;
145 Page_breaking::break_into_pieces (vsize start_break, vsize end_break,
146 Line_division const &div)
148 vector<Break_position> chunks = chunk_list (start_break, end_break);
149 bool ignore_div = false;
150 if (chunks.size () != div.size () + 1)
152 programming_error ("did not find a valid page breaking configuration");
156 for (vsize i = 0; i + 1 < chunks.size (); i++)
158 vsize sys = next_system (chunks[i]);
159 if (system_specs_[sys].pscore_)
163 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
165 vector<Column_x_positions> pos = ignore_div
166 ? line_breaking_[sys].best_solution (start, end)
167 : line_breaking_[sys].solve (start, end, div[i]);
168 system_specs_[sys].pscore_->root_system ()->break_into_pieces (pos);
174 Page_breaking::systems ()
177 for (vsize sys = 0; sys < system_specs_.size (); sys++)
179 if (system_specs_[sys].pscore_)
181 system_specs_[sys].pscore_->root_system ()
182 ->do_break_substitution_and_fixup_refpoints ();
183 SCM lines = system_specs_[sys].pscore_->root_system ()
184 ->get_broken_system_grobs ();
185 ret = scm_cons (lines, ret);
189 Prob *pb = system_specs_[sys].prob_;
190 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
194 return scm_append (scm_reverse (ret));
198 Page_breaking::page_height (int page_num, bool last) const
200 SCM mod = scm_c_resolve_module ("scm page");
201 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
202 SCM make_page = scm_c_module_lookup (mod, "make-page");
204 calc_height = scm_variable_ref (calc_height);
205 make_page = scm_variable_ref (make_page);
207 SCM page = scm_apply_0 (make_page, scm_list_n (
209 ly_symbol2scm ("page-number"), scm_from_int (page_num),
210 ly_symbol2scm ("is-last"), scm_from_bool (last),
212 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
213 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
217 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
219 Break_position const &pos = breaks_[breakpoint];
221 if (pos.system_spec_index_ == VPOS)
223 if (system_specs_[pos.system_spec_index_].pscore_)
224 return pos.col_->get_property (str);
225 return system_specs_[pos.system_spec_index_].prob_->get_property (str);
229 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
231 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
232 SCM page_module = scm_c_resolve_module ("scm page");
234 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
235 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
236 make_page = scm_variable_ref (make_page);
237 page_stencil = scm_variable_ref (page_stencil);
239 SCM book = book_->self_scm ();
240 int first_page_number
241 = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
243 SCM label_page_table = SCM_EOL;
245 for (vsize i = 0; i < lines_per_page.size (); i++)
247 SCM page_num = scm_from_int (i + first_page_number);
248 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
249 SCM rag = scm_from_bool (ragged () || (to_boolean (last)
251 SCM line_count = scm_from_int (lines_per_page[i]);
252 SCM lines = scm_list_head (systems, line_count);
253 SCM page = scm_apply_0 (make_page,
254 scm_list_n (book, lines, page_num,
255 rag, last, SCM_UNDEFINED));
258 for (SCM l = lines ; scm_is_pair (l) ; l = scm_cdr (l))
260 SCM labels = SCM_EOL;
261 if (Grob * line = unsmob_grob (scm_car (l)))
263 System *system = dynamic_cast<System*> (line);
264 labels = system->get_property ("labels");
266 else if (Prob *prob = unsmob_prob (scm_car (l)))
267 labels = prob->get_property ("labels");
269 for (SCM lbls = labels ; scm_is_pair (lbls) ; lbls = scm_cdr (lbls))
270 label_page_table = scm_cons (scm_cons (scm_car (lbls), page_num),
274 scm_apply_1 (page_stencil, page, SCM_EOL);
275 ret = scm_cons (page, ret);
276 systems = scm_list_tail (systems, line_count);
278 book_->paper_->set_variable (ly_symbol2scm ("label-page-table"), label_page_table);
279 ret = scm_reverse (ret);
283 /* The page-turn-page-breaker needs to have a line-breaker between any two
284 columns with non-NULL page-turn-permission.
286 The optimal-breaker needs to have a line-breaker between any two columns
287 with page-break-permission = 'force.
289 By using a grob predicate, we can accommodate both of these uses.
292 Page_breaking::create_system_list ()
294 SCM specs = book_->get_system_specs ();
295 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
297 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
299 SCM system_count = ps->layout ()->c_variable ("system-count");
301 if (scm_is_number (system_count))
302 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
303 scm_vector_to_list (ps->get_paper_systems ()),
306 system_specs_.push_back (System_spec (ps));
310 Prob *pb = unsmob_prob (scm_car (s));
314 system_specs_.push_back (System_spec (pb));
320 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
322 SCM force_sym = ly_symbol2scm ("force");
324 chunks_.push_back (Break_position ());
325 breaks_.push_back (Break_position ());
327 for (vsize i = 0; i < system_specs_.size (); i++)
329 if (system_specs_[i].pscore_)
332 = system_specs_[i].pscore_->root_system ()->used_columns ();
333 vector<vsize> line_breaker_columns;
334 line_breaker_columns.push_back (0);
336 for (vsize j = 1; j < cols.size (); j++)
338 bool last = (j == cols.size () - 1);
339 bool break_point = is_break (cols[j]);
340 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
341 Break_position cur_pos = Break_position (i,
342 line_breaker_columns.size (),
346 if (break_point || (i == system_specs_.size () - 1 && last))
347 breaks_.push_back (cur_pos);
348 if (chunk_end || last)
349 chunks_.push_back (cur_pos);
351 if ((break_point || chunk_end) && !last)
352 line_breaker_columns.push_back (j);
354 line_breaking_.push_back (Constrained_breaking (system_specs_[i].pscore_, line_breaker_columns));
358 /* TODO: we want some way of applying Break_p to a prob? */
359 if (i == system_specs_.size () - 1)
360 breaks_.push_back (Break_position (i));
362 chunks_.push_back (Break_position (i));
364 /* FIXME: shouldn't we push a Null_breaker or similar dummy
366 line_breaking_.push_back (Constrained_breaking (NULL));
371 vector<Break_position>
372 Page_breaking::chunk_list (vsize start_index, vsize end_index)
374 Break_position start = breaks_[start_index];
375 Break_position end = breaks_[end_index];
378 for (; i < chunks_.size () && chunks_[i] <= start; i++)
381 vector<Break_position> ret;
382 ret.push_back (start);
383 for (; i < chunks_.size () && chunks_[i] < end; i++)
384 ret.push_back (chunks_[i]);
390 Page_breaking::min_system_count (vsize start, vsize end)
392 vector<Break_position> chunks = chunk_list (start, end);
393 Line_division div = system_count_bounds (chunks, true);
396 for (vsize i = 0; i < div.size (); i++)
402 Page_breaking::max_system_count (vsize start, vsize end)
404 vector<Break_position> chunks = chunk_list (start, end);
405 Line_division div = system_count_bounds (chunks, false);
408 for (vsize i = 0; i < div.size (); i++)
413 Page_breaking::Line_division
414 Page_breaking::system_count_bounds (vector<Break_position> const &chunks,
417 assert (chunks.size () >= 2);
420 ret.resize (chunks.size () - 1, 1);
422 for (vsize i = 0; i + 1 < chunks.size (); i++)
424 vsize sys = next_system (chunks[i]);
425 if (system_specs_[sys].pscore_)
429 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
431 ? line_breaking_[sys].min_system_count (start, end)
432 : line_breaking_[sys].max_system_count (start, end);
440 Page_breaking::set_current_breakpoints (vsize start,
443 Line_division lower_bound,
444 Line_division upper_bound)
446 current_chunks_ = chunk_list (start, end);
447 current_start_breakpoint_ = start;
448 current_end_breakpoint_ = end;
449 clear_line_details_cache ();
451 if (!lower_bound.size ())
452 lower_bound = system_count_bounds (current_chunks_, true);
453 if (!upper_bound.size ())
454 upper_bound = system_count_bounds (current_chunks_, false);
456 assert (lower_bound.size () == current_chunks_.size () - 1);
457 assert (upper_bound.size () == current_chunks_.size () - 1);
459 Line_division work_in_progress;
460 current_configurations_.clear ();
461 line_divisions_rec (system_count,
466 /* we only consider a constant number of configurations. Otherwise,
467 this becomes slow when there are many small scores. The constant
468 5 is somewhat arbitrary. */
469 if (current_configurations_.size () > 5)
471 vector<pair<Real,vsize> > dems_and_indices;
473 for (vsize i = 0; i < current_configurations_.size (); i++)
475 cache_line_details (i);
477 for (vsize j = 0; j < cached_line_details_.size (); j++)
478 dem += cached_line_details_[j].force_ * cached_line_details_[j].force_
479 + cached_line_details_[j].break_penalty_;
481 dems_and_indices.push_back (pair<Real,vsize> (dem, i));
483 vector_sort (dems_and_indices, less<pair<Real,vsize> > ());
485 vector<Line_division> best_5_configurations;
486 for (vsize i = 0; i < 5; i++)
487 best_5_configurations.push_back (current_configurations_[dems_and_indices[i].second]);
489 clear_line_details_cache ();
490 current_configurations_ = best_5_configurations;
495 Page_breaking::set_to_ideal_line_configuration (vsize start, vsize end)
497 current_chunks_ = chunk_list (start, end);
498 current_start_breakpoint_ = start;
499 current_end_breakpoint_ = end;
500 clear_line_details_cache ();
503 for (vsize i = 0; i+1 < current_chunks_.size (); i++)
505 vsize sys = next_system (current_chunks_[i]);
506 if (system_specs_[sys].pscore_)
508 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
509 div.push_back (line_breaking_[sys].best_solution (start, end).size ());
514 current_configurations_.clear ();
515 current_configurations_.push_back (div);
519 Page_breaking::current_configuration_count () const
521 return current_configurations_.size ();
525 Page_breaking::cache_line_details (vsize configuration_index)
527 if (cached_configuration_index_ != configuration_index)
529 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
530 if (!scm_is_number (padding_scm))
531 padding_scm = book_->paper_->c_variable ("between-system-padding");
532 Real padding = robust_scm2double (padding_scm, 0.0);
534 Line_division &div = current_configurations_[configuration_index];
535 uncompressed_line_details_.clear ();
536 for (vsize i = 0; i + 1 < current_chunks_.size (); i++)
538 vsize sys = next_system (current_chunks_[i]);
539 if (system_specs_[sys].pscore_)
543 line_breaker_args (sys, current_chunks_[i], current_chunks_[i+1], &start, &end);
545 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
546 uncompressed_line_details_.insert (uncompressed_line_details_.end (), details.begin (), details.end ());
550 assert (div[i] == 1);
551 uncompressed_line_details_.push_back (Line_details (system_specs_[sys].prob_));
552 uncompressed_line_details_.back ().padding_ = padding;
555 cached_line_details_ = compress_lines (uncompressed_line_details_);
560 Page_breaking::clear_line_details_cache ()
562 cached_configuration_index_ = VPOS;
563 cached_line_details_.clear ();
564 uncompressed_line_details_.clear ();
568 Page_breaking::line_divisions_rec (vsize system_count,
569 Line_division const &min_sys,
570 Line_division const &max_sys,
571 Line_division *cur_division)
573 vsize my_index = cur_division->size ();
574 vsize others_min = 0;
575 vsize others_max = 0;
577 for (vsize i = my_index + 1; i < min_sys.size (); i++)
579 others_min += min_sys[i];
580 others_max += max_sys[i];
582 others_max = min (others_max, system_count);
583 vsize real_min = max (min_sys[my_index], system_count - others_max);
584 vsize real_max = min (max_sys[my_index], system_count - others_min);
586 if (real_min > real_max || real_min <= 0)
588 /* this should never happen within a recursive call. If it happens
589 at all, it means that we were called with an unsolvable problem
590 and we should return an empty result */
591 assert (my_index == 0);
595 for (vsize i = real_min; i <= real_max; i++)
597 cur_division->push_back (i);
598 if (my_index == min_sys.size () - 1)
599 current_configurations_.push_back (*cur_division);
601 line_divisions_rec (system_count - i, min_sys, max_sys, cur_division);
602 cur_division->pop_back ();
607 Page_breaking::min_page_count (vsize configuration, vsize first_page_num)
610 Real cur_rod_height = 0;
611 Real cur_spring_height = 0;
612 Real cur_page_height = page_height (first_page_num, false);
614 cache_line_details (configuration);
615 for (vsize i = 0; i < cached_line_details_.size (); i++)
617 Real ext_len = cached_line_details_[i].extent_.length ();
618 Real next_rod_height = cur_rod_height + ext_len
619 + ((cur_rod_height > 0) ? cached_line_details_[i].padding_: 0);
620 Real next_spring_height = cur_spring_height + line_space (cached_line_details_[i]);
621 Real next_height = next_rod_height + (ragged () ? next_spring_height : 0);
624 if ((next_height > cur_page_height && cur_rod_height > 0)
626 && cached_line_details_[i-1].page_permission_ == ly_symbol2scm ("force")))
628 cur_rod_height = ext_len;
629 cur_spring_height = line_space (cached_line_details_[i]);
630 cur_page_height = page_height (first_page_num + ret, false);
635 cur_rod_height = next_rod_height;
636 cur_spring_height = next_spring_height;
640 /* there are two potential problems with the last page (because we didn't know
641 it was the last page until after we managed to fit all the systems to it):
642 - we are ragged-last but the last page has a compressed spring
643 - the value returned by page_height (num, true) is smaller than the
644 value returned by page_height (num, false) and it causes the page not to
647 In either case, we just need to add one more page. This is because the last
648 line will always fit on the extra page and by adding one more page to the
649 end, the previous page is no longer the last page, so our previous
650 calculations that treated it as a non-last page were ok.
653 cur_page_height = page_height (first_page_num + ret - 1, true);
654 Real cur_height = cur_rod_height + ((ragged_last () || ragged ()) ? cur_spring_height : 0);
655 if (cur_height > cur_page_height
656 /* don't increase the page count if the last page had only one system */
657 && cur_rod_height > cached_line_details_.back ().extent_.length ())
660 assert (ret <= cached_line_details_.size ());
665 Page_breaking::space_systems_on_n_pages (vsize configuration, vsize n, vsize first_page_num)
667 Page_spacing_result ret;
668 assert (n >= min_page_count (configuration, first_page_num));
670 cache_line_details (configuration);
671 if (n > cached_line_details_.size ())
672 return Page_spacing_result ();
674 ret = space_systems_on_1_page (cached_line_details_,
675 page_height (first_page_num, is_last ()),
676 ragged () || (is_last () && ragged_last ()));
678 ret = space_systems_on_2_pages (configuration, first_page_num);
681 Page_spacer ps (cached_line_details_, first_page_num, this);
685 return finalize_spacing_result (configuration, ret);
689 Page_breaking::blank_page_penalty () const
691 SCM penalty_sym = is_last () ? ly_symbol2scm ("blank-last-page-force") : ly_symbol2scm ("blank-page-force");
692 return robust_scm2double (book_->paper_->lookup_variable (penalty_sym), 0.0);
696 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration, vsize n, vsize first_page_num)
698 Page_spacing_result n_res;
699 Page_spacing_result m_res;
701 cache_line_details (configuration);
702 vsize min_p_count = min_page_count (configuration, first_page_num);
706 bool rag = ragged () || (is_last () && ragged_last ());
707 Real height = page_height (first_page_num, is_last ());
709 if (1 >= min_p_count)
710 n_res = space_systems_on_1_page (cached_line_details_, height, rag);
711 if (1 < cached_line_details_.size ())
712 m_res = space_systems_on_2_pages (configuration, first_page_num);
716 Page_spacer ps (cached_line_details_, first_page_num, this);
718 if (n >= min_p_count)
719 n_res = ps.solve (n);
720 if (n < cached_line_details_.size ())
721 m_res = ps.solve (n+1);
724 m_res = finalize_spacing_result (configuration, m_res);
725 n_res = finalize_spacing_result (configuration, n_res);
727 Real penalty = blank_page_penalty ();
728 n_res.demerits_ += penalty;
730 if (n_res.force_.size ())
731 n_res.force_.back () += penalty;
733 return (m_res.demerits_ < n_res.demerits_) ? m_res : n_res;
737 Page_breaking::space_systems_on_best_pages (vsize configuration, vsize first_page_num)
739 vsize min_p_count = min_page_count (configuration, first_page_num);
740 Real odd_pages_penalty = blank_page_penalty ();
742 cache_line_details (configuration);
743 Page_spacer ps (cached_line_details_, first_page_num, this);
744 Page_spacing_result best = ps.solve (min_p_count);
745 best.force_.back () += (min_p_count % 2) ? odd_pages_penalty : 0;
746 best.demerits_ += (min_p_count % 2) ? odd_pages_penalty : 0;
748 for (vsize i = min_p_count+1; i <= cached_line_details_.size (); i++)
750 Page_spacing_result cur = ps.solve (i);
751 cur.demerits_ += (i % 2) ? odd_pages_penalty : 0;
752 if (cur.demerits_ < best.demerits_)
756 return finalize_spacing_result (configuration, best);
759 /* Calculate demerits and fix res.systems_per_page_ so that
760 it refers to the original line numbers, not the ones given by compress_lines (). */
762 Page_breaking::finalize_spacing_result (vsize configuration, Page_spacing_result res)
764 if (res.force_.empty ())
767 cache_line_details (configuration);
768 res.systems_per_page_ = uncompress_solution (res.systems_per_page_, cached_line_details_);
771 Real line_penalty = 0;
773 Real page_weighting = robust_scm2double (book_->paper_->c_variable ("page-spacing-weight"), 10);
775 for (vsize i = 0; i < uncompressed_line_details_.size (); i++)
777 line_force += uncompressed_line_details_[i].force_ * uncompressed_line_details_[i].force_;
778 line_penalty += uncompressed_line_details_[i].break_penalty_;
781 for (vsize i = 0; i < res.force_.size (); i++)
783 Real f = res.force_[i];
784 if (isinf (f) && res.systems_per_page_[i] == 1)
790 /* for a while we tried averaging page and line forces across pages instead
791 of summing them, but it caused a problem: if there is a single page
792 with a very bad page force (for example because of a forced page break),
793 the page breaker will put in a _lot_ of pages so that the bad force
794 becomes averaged out over many pages. */
795 res.demerits_ = line_force + line_penalty + (page_force + res.penalty_) * page_weighting;
800 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
801 are by far the most common cases, we have special functions for them.
803 space_systems_on_1_page has a different calling convention than most of the
804 space_systems functions. This is because space_systems_on_1_page is (unlike
805 the other space_systems functions) sometimes called on subsets of a full
808 Page_breaking::space_systems_on_1_page (vector<Line_details> const &lines, Real page_height, bool ragged)
810 Page_spacing space (page_height);
811 Page_spacing_result ret;
813 for (vsize i = 0; i < lines.size (); i++)
814 space.append_system (lines[i]);
816 ret.systems_per_page_.push_back (lines.size ());
817 ret.force_.push_back (ragged ? min (space.force_, 0.0) : space.force_);
818 ret.penalty_ = lines.back ().page_penalty_ + lines.back ().turn_penalty_;
820 /* don't do finalize_spacing_result () because we are only an internal function */
825 Page_breaking::space_systems_on_2_pages (vsize configuration, vsize first_page_num)
827 Real page1_height = page_height (first_page_num, false);
828 Real page2_height = page_height (first_page_num + 1, is_last ());
829 bool ragged1 = ragged ();
830 bool ragged2 = ragged () || (is_last () && ragged_last ());
832 /* if there is a forced break, this reduces to 2 1-page problems */
833 cache_line_details (configuration);
834 for (vsize i = 0; i + 1 < cached_line_details_.size (); i++)
835 if (cached_line_details_[i].page_permission_ == ly_symbol2scm ("force"))
837 vector<Line_details> lines1 (cached_line_details_.begin (), cached_line_details_.begin () + i + 1);
838 vector<Line_details> lines2 (cached_line_details_.begin () + i + 1, cached_line_details_.end ());
839 Page_spacing_result p1 = space_systems_on_1_page (lines1, page1_height, ragged1);
840 Page_spacing_result p2 = space_systems_on_1_page (lines2, page2_height, ragged2);
842 p1.systems_per_page_.push_back (p2.systems_per_page_[0]);
843 p1.force_.push_back (p2.force_[0]);
844 p1.penalty_ += p2.penalty_ - cached_line_details_[i].turn_penalty_;
848 vector<Real> page1_force;
849 vector<Real> page2_force;
850 Page_spacing page1 (page1_height);
851 Page_spacing page2 (page2_height);
853 page1_force.resize (cached_line_details_.size () - 1, infinity_f);
854 page2_force.resize (cached_line_details_.size () - 1, infinity_f);
856 /* find the page 1 and page 2 forces for each page-breaking position */
857 for (vsize i = 0; i < page1_force.size (); i++)
859 page1.append_system (cached_line_details_[i]);
860 page2.prepend_system (cached_line_details_[cached_line_details_.size () - 1 - i]);
861 page1_force[i] = (ragged1 && page1.force_ < 0 && i > 0) ? infinity_f : page1.force_;
864 page2_force[page2_force.size () - 1 - i] =
865 (page2.force_ < 0 && i + 1 < page1_force.size ()) ? infinity_f : 0;
867 page2_force[page2_force.size () - 1 - i] = page2.force_;
870 /* find the position that minimises the sum of the page forces */
871 vsize best_sys_count = 1;
872 Real best_demerits = infinity_f;
873 for (vsize i = 0; i < page1_force.size (); i++)
875 Real f = page1_force[i] * page1_force[i] + page2_force[i] * page2_force[i];
876 Real uneven = 2 * (page1_force[i] - page2_force[i]);
877 Real dem = uneven * uneven + f
878 + cached_line_details_[i+1].page_penalty_
879 + cached_line_details_.back ().page_penalty_ + cached_line_details_.back ().turn_penalty_;
880 if (dem < best_demerits)
883 best_sys_count = i+1;
887 Page_spacing_result ret;
888 ret.systems_per_page_.push_back (best_sys_count);
889 ret.systems_per_page_.push_back (cached_line_details_.size () - best_sys_count);
890 ret.force_.push_back (page1_force[best_sys_count-1]);
891 ret.force_.push_back (page2_force[best_sys_count-1]);
892 ret.penalty_ = cached_line_details_[best_sys_count-1].page_penalty_
893 + cached_line_details_.back ().page_penalty_
894 + cached_line_details_.back ().turn_penalty_;
896 /* don't do finalize_spacing_result () because we are only an internal function */
901 Page_breaking::all_lines_stretched (vsize configuration)
903 cache_line_details (configuration);
904 for (vsize i = 0; i < cached_line_details_.size (); i++)
905 if (cached_line_details_[i].force_ < 0)
911 Page_breaking::Line_division
912 Page_breaking::current_configuration (vsize configuration_index) const
914 return current_configurations_[configuration_index];
918 Page_breaking::is_last () const
920 return current_end_breakpoint_ == last_break_position ();
924 Page_breaking::last_break_position () const
926 return breaks_.size () - 1;