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--2009 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 compressed
.compressed_lines_count_
= old
.compressed_lines_count_
+ 1;
41 compressed
.compressed_nontitle_lines_count_
=
42 old
.compressed_nontitle_lines_count_
+ (compressed
.title_
? 0 : 1);
44 compressed
.title_
= compressed
.title_
&& old
.title_
;
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
+= compressed
[j
].compressed_lines_count_
- 1;
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
)
101 ragged_
= to_boolean (pb
->paper_
->c_variable ("ragged-bottom"));
102 ragged_last_
= to_boolean (pb
->paper_
->c_variable ("ragged-last-bottom"));
103 page_top_space_
= robust_scm2double (pb
->paper_
->c_variable ("page-top-space"), 0);
104 systems_per_page_
= max (0, robust_scm2int (pb
->paper_
->c_variable ("systems-per-page"), 0));
105 max_systems_per_page_
= max (0, robust_scm2int (pb
->paper_
->c_variable ("max-systems-per-page"), 0));
106 min_systems_per_page_
= max (0, robust_scm2int (pb
->paper_
->c_variable ("min-systems-per-page"), 0));
108 if (systems_per_page_
&& (max_systems_per_page_
|| min_systems_per_page_
))
110 warning (_f ("ignoring min-systems-per-page and max-systems-per-page because systems-per-page was set"));
111 min_systems_per_page_
= max_systems_per_page_
= 0;
113 if (max_systems_per_page_
&& min_systems_per_page_
> max_systems_per_page_
)
115 warning (_f ("min-systems-per-page is larger than max-systems-per-page, ignoring both values"));
116 min_systems_per_page_
= max_systems_per_page_
= 0;
119 create_system_list ();
120 find_chunks_and_breaks (is_break
);
123 Page_breaking::~Page_breaking ()
128 Page_breaking::ragged () const
134 Page_breaking::ragged_last () const
140 Page_breaking::systems_per_page () const
142 return systems_per_page_
;
146 Page_breaking::max_systems_per_page () const
148 return max_systems_per_page_
;
152 Page_breaking::min_systems_per_page () const
154 return min_systems_per_page_
;
158 Page_breaking::page_top_space () const
160 return page_top_space_
;
164 Page_breaking::system_count () const
166 return system_count_
;
170 Page_breaking::too_many_lines (int line_count
) const
172 return max_systems_per_page () > 0 && line_count
> max_systems_per_page ();
176 Page_breaking::too_few_lines (int line_count
) const
178 return line_count
< min_systems_per_page ();
182 Page_breaking::line_count_penalty (int line_count
) const
184 if (too_many_lines (line_count
))
185 return (line_count
- max_systems_per_page ()) * TERRIBLE_SPACING_PENALTY
;
186 if (too_few_lines (line_count
))
187 return (min_systems_per_page () - line_count
) * TERRIBLE_SPACING_PENALTY
;
193 Page_breaking::line_count_status (int line_count
) const
195 if (too_many_lines (line_count
))
196 return SYSTEM_COUNT_TOO_MANY
;
197 if (too_few_lines (line_count
))
198 return SYSTEM_COUNT_TOO_FEW
;
200 return SYSTEM_COUNT_OK
;
203 /* translate indices into breaks_ into start-end parameters for the line breaker */
205 Page_breaking::line_breaker_args (vsize sys
,
206 Break_position
const &start
,
207 Break_position
const &end
,
208 vsize
*line_breaker_start
,
209 vsize
*line_breaker_end
)
211 assert (system_specs_
[sys
].pscore_
);
212 assert (next_system (start
) <= sys
&& sys
<= end
.system_spec_index_
);
214 if (start
.system_spec_index_
== sys
)
215 *line_breaker_start
= start
.score_break_
;
217 *line_breaker_start
= 0;
219 if (end
.system_spec_index_
== sys
)
220 *line_breaker_end
= end
.score_break_
;
222 *line_breaker_end
= VPOS
;
226 Page_breaking::break_into_pieces (vsize start_break
, vsize end_break
,
227 Line_division
const &div
)
229 vector
<Break_position
> chunks
= chunk_list (start_break
, end_break
);
230 bool ignore_div
= false;
231 if (chunks
.size () != div
.size () + 1)
233 programming_error ("did not find a valid page breaking configuration");
237 for (vsize i
= 0; i
+ 1 < chunks
.size (); i
++)
239 vsize sys
= next_system (chunks
[i
]);
240 if (system_specs_
[sys
].pscore_
)
244 line_breaker_args (sys
, chunks
[i
], chunks
[i
+1], &start
, &end
);
246 vector
<Column_x_positions
> pos
= ignore_div
247 ? line_breaking_
[sys
].best_solution (start
, end
)
248 : line_breaking_
[sys
].solve (start
, end
, div
[i
]);
249 system_specs_
[sys
].pscore_
->root_system ()->break_into_pieces (pos
);
255 Page_breaking::systems ()
258 for (vsize sys
= 0; sys
< system_specs_
.size (); sys
++)
260 if (system_specs_
[sys
].pscore_
)
262 system_specs_
[sys
].pscore_
->root_system ()
263 ->do_break_substitution_and_fixup_refpoints ();
264 SCM lines
= system_specs_
[sys
].pscore_
->root_system ()
265 ->get_broken_system_grobs ();
266 ret
= scm_cons (lines
, ret
);
270 Prob
*pb
= system_specs_
[sys
].prob_
;
271 ret
= scm_cons (scm_list_1 (pb
->self_scm ()), ret
);
275 return scm_append (scm_reverse (ret
));
279 Page_breaking::page_height (int page_num
, bool last
) const
281 bool last_part
= ly_scm2bool (book_
->paper_
->c_variable ("is-last-bookpart"));
282 SCM mod
= scm_c_resolve_module ("scm page");
283 SCM calc_height
= scm_c_module_lookup (mod
, "calc-printable-height");
284 SCM make_page
= scm_c_module_lookup (mod
, "make-page");
286 calc_height
= scm_variable_ref (calc_height
);
287 make_page
= scm_variable_ref (make_page
);
289 SCM page
= scm_apply_0 (make_page
, scm_list_n (
291 ly_symbol2scm ("page-number"), scm_from_int (page_num
),
292 ly_symbol2scm ("is-last-bookpart"), scm_from_bool (last_part
),
293 ly_symbol2scm ("is-bookpart-last-page"), scm_from_bool (last
),
295 SCM height
= scm_apply_1 (calc_height
, page
, SCM_EOL
);
296 return scm_to_double (height
) - page_top_space_
;
300 Page_breaking::breakpoint_property (vsize breakpoint
, char const *str
)
302 Break_position
const &pos
= breaks_
[breakpoint
];
304 if (pos
.system_spec_index_
== VPOS
)
306 if (system_specs_
[pos
.system_spec_index_
].pscore_
)
307 return pos
.col_
->get_property (str
);
308 return system_specs_
[pos
.system_spec_index_
].prob_
->get_property (str
);
312 Page_breaking::make_pages (vector
<vsize
> lines_per_page
, SCM systems
)
314 SCM layout_module
= scm_c_resolve_module ("scm layout-page-layout");
315 SCM page_module
= scm_c_resolve_module ("scm page");
317 SCM make_page
= scm_c_module_lookup (layout_module
, "stretch-and-draw-page");
318 SCM page_stencil
= scm_c_module_lookup (page_module
, "page-stencil");
319 make_page
= scm_variable_ref (make_page
);
320 page_stencil
= scm_variable_ref (page_stencil
);
322 SCM book
= book_
->self_scm ();
323 int first_page_number
324 = robust_scm2int (book_
->paper_
->c_variable ("first-page-number"), 1);
325 bool last_bookpart
= ly_scm2bool (book_
->paper_
->c_variable ("is-last-bookpart"));
327 SCM label_page_table
= book_
->top_paper ()->c_variable ("label-page-table");
328 if (label_page_table
== SCM_UNDEFINED
)
329 label_page_table
= SCM_EOL
;
331 for (vsize i
= 0; i
< lines_per_page
.size (); i
++)
333 SCM page_num
= scm_from_int (i
+ first_page_number
);
334 bool partbook_last_page
= (i
== lines_per_page
.size () - 1);
335 SCM rag
= scm_from_bool (ragged () || ( partbook_last_page
&& ragged_last ()));
336 SCM line_count
= scm_from_int (lines_per_page
[i
]);
337 SCM lines
= scm_list_head (systems
, line_count
);
338 SCM page
= scm_apply_0 (make_page
,
339 scm_list_n (book
, lines
, page_num
, rag
,
340 scm_from_bool (last_bookpart
),
341 scm_from_bool (partbook_last_page
),
344 for (SCM l
= lines
; scm_is_pair (l
) ; l
= scm_cdr (l
))
346 SCM labels
= SCM_EOL
;
347 if (Grob
* line
= unsmob_grob (scm_car (l
)))
349 System
*system
= dynamic_cast<System
*> (line
);
350 labels
= system
->get_property ("labels");
352 else if (Prob
*prob
= unsmob_prob (scm_car (l
)))
353 labels
= prob
->get_property ("labels");
355 for (SCM lbls
= labels
; scm_is_pair (lbls
) ; lbls
= scm_cdr (lbls
))
356 label_page_table
= scm_cons (scm_cons (scm_car (lbls
), page_num
),
360 scm_apply_1 (page_stencil
, page
, SCM_EOL
);
361 ret
= scm_cons (page
, ret
);
362 systems
= scm_list_tail (systems
, line_count
);
364 book_
->top_paper ()->set_variable (ly_symbol2scm ("label-page-table"), label_page_table
);
365 ret
= scm_reverse (ret
);
369 /* The page-turn-page-breaker needs to have a line-breaker between any two
370 columns with non-NULL page-turn-permission.
372 The optimal-breaker needs to have a line-breaker between any two columns
373 with page-break-permission = 'force.
375 By using a grob predicate, we can accommodate both of these uses.
378 Page_breaking::create_system_list ()
380 SCM specs
= book_
->get_system_specs ();
381 for (SCM s
= specs
; scm_is_pair (s
); s
= scm_cdr (s
))
383 if (Paper_score
*ps
= dynamic_cast<Paper_score
*> (unsmob_music_output (scm_car (s
))))
385 SCM system_count
= ps
->layout ()->c_variable ("system-count");
387 if (scm_is_number (system_count
))
388 s
= scm_append (scm_list_3 (scm_list_1 (scm_car (s
)),
389 scm_vector_to_list (ps
->get_paper_systems ()),
392 system_specs_
.push_back (System_spec (ps
));
396 Prob
*pb
= unsmob_prob (scm_car (s
));
400 system_specs_
.push_back (System_spec (pb
));
406 Page_breaking::find_chunks_and_breaks (Break_predicate is_break
)
408 SCM force_sym
= ly_symbol2scm ("force");
410 chunks_
.push_back (Break_position ());
411 breaks_
.push_back (Break_position ());
413 for (vsize i
= 0; i
< system_specs_
.size (); i
++)
415 if (system_specs_
[i
].pscore_
)
418 = system_specs_
[i
].pscore_
->root_system ()->used_columns ();
419 vector
<vsize
> line_breaker_columns
;
420 line_breaker_columns
.push_back (0);
422 for (vsize j
= 1; j
< cols
.size (); j
++)
424 bool last
= (j
== cols
.size () - 1);
425 bool break_point
= is_break (cols
[j
]);
426 bool chunk_end
= cols
[j
]->get_property ("page-break-permission") == force_sym
;
427 Break_position cur_pos
= Break_position (i
,
428 line_breaker_columns
.size (),
432 if (break_point
|| (i
== system_specs_
.size () - 1 && last
))
433 breaks_
.push_back (cur_pos
);
434 if (chunk_end
|| last
)
435 chunks_
.push_back (cur_pos
);
437 if ((break_point
|| chunk_end
) && !last
)
438 line_breaker_columns
.push_back (j
);
440 line_breaking_
.push_back (Constrained_breaking (system_specs_
[i
].pscore_
, line_breaker_columns
));
444 /* TODO: we want some way of applying Break_p to a prob? */
445 if (i
== system_specs_
.size () - 1)
446 breaks_
.push_back (Break_position (i
));
448 chunks_
.push_back (Break_position (i
));
450 /* FIXME: shouldn't we push a Null_breaker or similar dummy
452 line_breaking_
.push_back (Constrained_breaking (NULL
));
457 vector
<Break_position
>
458 Page_breaking::chunk_list (vsize start_index
, vsize end_index
)
460 Break_position start
= breaks_
[start_index
];
461 Break_position end
= breaks_
[end_index
];
464 for (; i
< chunks_
.size () && chunks_
[i
] <= start
; i
++)
467 vector
<Break_position
> ret
;
468 ret
.push_back (start
);
469 for (; i
< chunks_
.size () && chunks_
[i
] < end
; i
++)
470 ret
.push_back (chunks_
[i
]);
476 Page_breaking::min_system_count (vsize start
, vsize end
)
478 vector
<Break_position
> chunks
= chunk_list (start
, end
);
479 Line_division div
= system_count_bounds (chunks
, true);
482 for (vsize i
= 0; i
< div
.size (); i
++)
488 Page_breaking::max_system_count (vsize start
, vsize end
)
490 vector
<Break_position
> chunks
= chunk_list (start
, end
);
491 Line_division div
= system_count_bounds (chunks
, false);
494 for (vsize i
= 0; i
< div
.size (); i
++)
499 Page_breaking::Line_division
500 Page_breaking::system_count_bounds (vector
<Break_position
> const &chunks
,
503 assert (chunks
.size () >= 2);
506 ret
.resize (chunks
.size () - 1, 1);
508 for (vsize i
= 0; i
+ 1 < chunks
.size (); i
++)
510 vsize sys
= next_system (chunks
[i
]);
511 if (system_specs_
[sys
].pscore_
)
515 line_breaker_args (sys
, chunks
[i
], chunks
[i
+1], &start
, &end
);
517 ? line_breaking_
[sys
].min_system_count (start
, end
)
518 : line_breaking_
[sys
].max_system_count (start
, end
);
526 Page_breaking::set_current_breakpoints (vsize start
,
529 Line_division lower_bound
,
530 Line_division upper_bound
)
532 system_count_
= system_count
;
533 current_chunks_
= chunk_list (start
, end
);
534 current_start_breakpoint_
= start
;
535 current_end_breakpoint_
= end
;
536 clear_line_details_cache ();
538 if (!lower_bound
.size ())
539 lower_bound
= system_count_bounds (current_chunks_
, true);
540 if (!upper_bound
.size ())
541 upper_bound
= system_count_bounds (current_chunks_
, false);
543 assert (lower_bound
.size () == current_chunks_
.size () - 1);
544 assert (upper_bound
.size () == current_chunks_
.size () - 1);
546 Line_division work_in_progress
;
547 current_configurations_
.clear ();
548 line_divisions_rec (system_count
,
553 /* we only consider a constant number of configurations. Otherwise,
554 this becomes slow when there are many small scores. The constant
555 5 is somewhat arbitrary. */
556 if (current_configurations_
.size () > 5)
558 vector
<pair
<Real
,vsize
> > dems_and_indices
;
560 for (vsize i
= 0; i
< current_configurations_
.size (); i
++)
562 cache_line_details (i
);
564 for (vsize j
= 0; j
< cached_line_details_
.size (); j
++)
565 dem
+= cached_line_details_
[j
].force_
* cached_line_details_
[j
].force_
566 + cached_line_details_
[j
].break_penalty_
;
568 dems_and_indices
.push_back (pair
<Real
,vsize
> (dem
, i
));
570 vector_sort (dems_and_indices
, less
<pair
<Real
,vsize
> > ());
572 vector
<Line_division
> best_5_configurations
;
573 for (vsize i
= 0; i
< 5; i
++)
574 best_5_configurations
.push_back (current_configurations_
[dems_and_indices
[i
].second
]);
576 clear_line_details_cache ();
577 current_configurations_
= best_5_configurations
;
582 Page_breaking::set_to_ideal_line_configuration (vsize start
, vsize end
)
584 current_chunks_
= chunk_list (start
, end
);
585 current_start_breakpoint_
= start
;
586 current_end_breakpoint_
= end
;
587 clear_line_details_cache ();
591 for (vsize i
= 0; i
+1 < current_chunks_
.size (); i
++)
593 vsize sys
= next_system (current_chunks_
[i
]);
594 if (system_specs_
[sys
].pscore_
)
596 line_breaker_args (sys
, current_chunks_
[i
], current_chunks_
[i
+1], &start
, &end
);
597 div
.push_back (line_breaking_
[sys
].best_solution (start
, end
).size ());
602 system_count_
+= div
.back ();
604 current_configurations_
.clear ();
605 current_configurations_
.push_back (div
);
609 Page_breaking::current_configuration_count () const
611 return current_configurations_
.size ();
615 Page_breaking::cache_line_details (vsize configuration_index
)
617 if (cached_configuration_index_
!= configuration_index
)
619 cached_configuration_index_
= configuration_index
;
620 SCM padding_scm
= book_
->paper_
->c_variable ("page-breaking-between-system-padding");
621 if (!scm_is_number (padding_scm
))
622 padding_scm
= book_
->paper_
->c_variable ("between-system-padding");
623 Real padding
= robust_scm2double (padding_scm
, 0.0);
625 Line_division
&div
= current_configurations_
[configuration_index
];
626 uncompressed_line_details_
.clear ();
627 for (vsize i
= 0; i
+ 1 < current_chunks_
.size (); i
++)
629 vsize sys
= next_system (current_chunks_
[i
]);
630 if (system_specs_
[sys
].pscore_
)
634 line_breaker_args (sys
, current_chunks_
[i
], current_chunks_
[i
+1], &start
, &end
);
636 vector
<Line_details
> details
= line_breaking_
[sys
].line_details (start
, end
, div
[i
]);
637 uncompressed_line_details_
.insert (uncompressed_line_details_
.end (), details
.begin (), details
.end ());
641 assert (div
[i
] == 1);
642 uncompressed_line_details_
.push_back (Line_details (system_specs_
[sys
].prob_
));
643 uncompressed_line_details_
.back ().padding_
=
644 robust_scm2double (system_specs_
[sys
].prob_
->get_property ("next-padding"),
648 cached_line_details_
= compress_lines (uncompressed_line_details_
);
653 Page_breaking::clear_line_details_cache ()
655 cached_configuration_index_
= VPOS
;
656 cached_line_details_
.clear ();
657 uncompressed_line_details_
.clear ();
661 Page_breaking::line_divisions_rec (vsize system_count
,
662 Line_division
const &min_sys
,
663 Line_division
const &max_sys
,
664 Line_division
*cur_division
)
666 vsize my_index
= cur_division
->size ();
667 vsize others_min
= 0;
668 vsize others_max
= 0;
670 for (vsize i
= my_index
+ 1; i
< min_sys
.size (); i
++)
672 others_min
+= min_sys
[i
];
673 others_max
+= max_sys
[i
];
675 others_max
= min (others_max
, system_count
);
676 vsize real_min
= max (min_sys
[my_index
], system_count
- others_max
);
677 vsize real_max
= min (max_sys
[my_index
], system_count
- others_min
);
679 if (real_min
> real_max
|| real_min
<= 0)
681 /* this should never happen within a recursive call. If it happens
682 at all, it means that we were called with an unsolvable problem
683 and we should return an empty result */
684 assert (my_index
== 0);
688 for (vsize i
= real_min
; i
<= real_max
; i
++)
690 cur_division
->push_back (i
);
691 if (my_index
== min_sys
.size () - 1)
692 current_configurations_
.push_back (*cur_division
);
694 line_divisions_rec (system_count
- i
, min_sys
, max_sys
, cur_division
);
695 cur_division
->pop_back ();
700 Page_breaking::min_page_count (vsize configuration
, vsize first_page_num
)
703 Real cur_rod_height
= 0;
704 Real cur_spring_height
= 0;
705 Real cur_page_height
= page_height (first_page_num
, false);
708 cache_line_details (configuration
);
709 for (vsize i
= 0; i
< cached_line_details_
.size (); i
++)
711 Real ext_len
= cached_line_details_
[i
].extent_
.length ();
712 Real next_rod_height
= cur_rod_height
+ ext_len
713 + ((cur_rod_height
> 0) ? cached_line_details_
[i
].padding_
: 0);
714 Real next_spring_height
= cur_spring_height
+ cached_line_details_
[i
].space_
;
715 Real next_height
= next_rod_height
+ (ragged () ? next_spring_height
: 0);
716 int next_line_count
= line_count
+ cached_line_details_
[i
].compressed_nontitle_lines_count_
;
718 if ((!too_few_lines (line_count
) && (next_height
> cur_page_height
&& cur_rod_height
> 0))
719 || too_many_lines (next_line_count
)
721 && cached_line_details_
[i
-1].page_permission_
== ly_symbol2scm ("force")))
723 line_count
= cached_line_details_
[i
].compressed_nontitle_lines_count_
;
724 cur_rod_height
= ext_len
;
725 cur_spring_height
= cached_line_details_
[i
].space_
;
726 cur_page_height
= page_height (first_page_num
+ ret
, false);
731 cur_rod_height
= next_rod_height
;
732 cur_spring_height
= next_spring_height
;
733 line_count
= next_line_count
;
737 /* there are two potential problems with the last page (because we didn't know
738 it was the last page until after we managed to fit all the systems to it):
739 - we are ragged-last but the last page has a compressed spring
740 - the value returned by page_height (num, true) is smaller than the
741 value returned by page_height (num, false) and it causes the page not to
744 In either case, we just need to add one more page. This is because the last
745 line will always fit on the extra page and by adding one more page to the
746 end, the previous page is no longer the last page, so our previous
747 calculations that treated it as a non-last page were ok.
750 cur_page_height
= page_height (first_page_num
+ ret
- 1, true);
751 Real cur_height
= cur_rod_height
+ ((ragged_last () || ragged ()) ? cur_spring_height
: 0);
752 if (!too_few_lines (line_count
- cached_line_details_
.back ().compressed_nontitle_lines_count_
)
753 && cur_height
> cur_page_height
754 /* don't increase the page count if the last page had only one system */
755 && cur_rod_height
> cached_line_details_
.back ().extent_
.length ())
758 assert (ret
<= cached_line_details_
.size ());
762 // If systems_per_page_ is positive, we don't really try to space on N pages;
763 // we just put the requested number of systems on each page and penalize
764 // if the result doesn't have N pages.
766 Page_breaking::space_systems_on_n_pages (vsize configuration
, vsize n
, vsize first_page_num
)
768 Page_spacing_result ret
;
770 if (systems_per_page_
> 0)
772 Page_spacing_result ret
= space_systems_with_fixed_number_per_page (configuration
, first_page_num
);
773 ret
.demerits_
+= (ret
.force_
.size () == n
) ? 0 : BAD_SPACING_PENALTY
;
777 cache_line_details (configuration
);
778 bool valid_n
= (n
>= min_page_count (configuration
, first_page_num
)
779 && n
<= cached_line_details_
.size ());
782 programming_error ("number of pages is out of bounds");
784 if (n
== 1 && valid_n
)
785 ret
= space_systems_on_1_page (cached_line_details_
,
786 page_height (first_page_num
, is_last ()),
787 ragged () || (is_last () && ragged_last ()));
788 else if (n
== 2 && valid_n
)
789 ret
= space_systems_on_2_pages (configuration
, first_page_num
);
792 Page_spacer
ps (cached_line_details_
, first_page_num
, this);
796 return finalize_spacing_result (configuration
, ret
);
800 Page_breaking::blank_page_penalty () const
805 penalty_sym
= ly_symbol2scm ("blank-last-page-force");
806 else if (ends_score ())
807 penalty_sym
= ly_symbol2scm ("blank-after-score-page-force");
809 penalty_sym
= ly_symbol2scm ("blank-page-force");
811 Break_position
const &pos
= breaks_
[current_end_breakpoint_
];
812 if (Paper_score
*ps
= system_specs_
[pos
.system_spec_index_
].pscore_
)
813 return robust_scm2double (ps
->layout ()->lookup_variable (penalty_sym
), 0.0);
815 return robust_scm2double (book_
->paper_
->lookup_variable (penalty_sym
), 0.0);
818 // If systems_per_page_ is positive, we don't really try to space on N
819 // or N+1 pages; see the comment to space_systems_on_n_pages.
821 Page_breaking::space_systems_on_n_or_one_more_pages (vsize configuration
, vsize n
, vsize first_page_num
)
823 Page_spacing_result n_res
;
824 Page_spacing_result m_res
;
826 if (systems_per_page_
> 0)
828 Page_spacing_result ret
= space_systems_with_fixed_number_per_page (configuration
, first_page_num
);
829 ret
.demerits_
+= (ret
.force_
.size () == n
|| ret
.force_
.size () == (n
-1)) ? 0 : BAD_SPACING_PENALTY
;
833 cache_line_details (configuration
);
834 vsize min_p_count
= min_page_count (configuration
, first_page_num
);
835 bool valid_n
= n
>= min_p_count
|| n
<= cached_line_details_
.size ();
838 programming_error ("both page counts are out of bounds");
840 if (n
== 1 && valid_n
)
842 bool rag
= ragged () || (is_last () && ragged_last ());
843 Real height
= page_height (first_page_num
, is_last ());
845 if (1 >= min_p_count
)
846 n_res
= space_systems_on_1_page (cached_line_details_
, height
, rag
);
847 if (1 < cached_line_details_
.size ())
848 m_res
= space_systems_on_2_pages (configuration
, first_page_num
);
852 Page_spacer
ps (cached_line_details_
, first_page_num
, this);
854 if (n
>= min_p_count
|| !valid_n
)
855 n_res
= ps
.solve (n
);
856 if (n
< cached_line_details_
.size () || !valid_n
)
857 m_res
= ps
.solve (n
+1);
860 m_res
= finalize_spacing_result (configuration
, m_res
);
861 n_res
= finalize_spacing_result (configuration
, n_res
);
863 Real penalty
= blank_page_penalty ();
864 n_res
.demerits_
+= penalty
;
866 if (n_res
.force_
.size ())
867 n_res
.force_
.back () += penalty
;
869 return (m_res
.demerits_
< n_res
.demerits_
) ? m_res
: n_res
;
873 Page_breaking::space_systems_on_best_pages (vsize configuration
, vsize first_page_num
)
875 vsize min_p_count
= min_page_count (configuration
, first_page_num
);
876 Real odd_pages_penalty
= blank_page_penalty ();
878 cache_line_details (configuration
);
879 Page_spacer
ps (cached_line_details_
, first_page_num
, this);
880 Page_spacing_result best
= ps
.solve (min_p_count
);
881 best
.force_
.back () += (min_p_count
% 2) ? odd_pages_penalty
: 0;
882 best
.demerits_
+= (min_p_count
% 2) ? odd_pages_penalty
: 0;
884 for (vsize i
= min_p_count
+1; i
<= cached_line_details_
.size (); i
++)
886 Page_spacing_result cur
= ps
.solve (i
);
887 cur
.demerits_
+= (i
% 2) ? odd_pages_penalty
: 0;
888 if (cur
.demerits_
< best
.demerits_
)
892 return finalize_spacing_result (configuration
, best
);
896 Page_breaking::space_systems_with_fixed_number_per_page (vsize configuration
,
897 vsize first_page_num
)
899 Page_spacing_result res
;
900 Page_spacing
space (page_height (first_page_num
, false), page_top_space_
);
903 vsize page_first_line
= 0;
905 cache_line_details (configuration
);
906 while (line
< cached_line_details_
.size ())
910 space
.resize (page_height (first_page_num
+ page
, false));
912 int system_count_on_this_page
= 0;
913 while (system_count_on_this_page
< systems_per_page_
914 && line
< cached_line_details_
.size ())
916 Line_details
const &cur_line
= cached_line_details_
[line
];
917 space
.append_system (cur_line
);
918 system_count_on_this_page
+= cur_line
.compressed_nontitle_lines_count_
;
921 if (cur_line
.page_permission_
== ly_symbol2scm ("force"))
925 res
.systems_per_page_
.push_back (line
- page_first_line
);
927 res
.force_
.push_back (space
.force_
);
928 res
.penalty_
+= cached_line_details_
[line
-1].page_penalty_
;
929 if (system_count_on_this_page
!= systems_per_page_
)
931 res
.penalty_
+= TERRIBLE_SPACING_PENALTY
;
932 res
.system_count_status_
|= ((system_count_on_this_page
< systems_per_page_
))
933 ? SYSTEM_COUNT_TOO_FEW
: SYSTEM_COUNT_TOO_MANY
;
936 page_first_line
= line
;
939 /* Recalculate forces for the last page because we know now that is
940 really the last page. */
941 space
.resize (page_height (first_page_num
+ page
, true));
942 res
.force_
.back () = space
.force_
;
943 return finalize_spacing_result (configuration
, res
);
947 Page_breaking::pack_systems_on_least_pages (vsize configuration
, vsize first_page_num
)
949 // TODO: add support for min/max-systems-per-page.
950 Page_spacing_result res
;
952 vsize page_first_line
= 0;
953 Page_spacing
space (page_height (first_page_num
, false), page_top_space_
);
955 cache_line_details (configuration
);
956 for (vsize line
= 0; line
< cached_line_details_
.size (); line
++)
958 Real prev_force
= space
.force_
;
959 space
.append_system (cached_line_details_
[line
]);
960 if ((line
> page_first_line
)
961 && (isinf (space
.force_
)
963 && (cached_line_details_
[line
-1].page_permission_
== ly_symbol2scm ("force")))))
965 res
.systems_per_page_
.push_back (line
- page_first_line
);
966 res
.force_
.push_back (prev_force
);
967 res
.penalty_
+= cached_line_details_
[line
-1].page_penalty_
;
969 space
.resize (page_height (first_page_num
+ page
, false));
971 space
.append_system (cached_line_details_
[line
]);
972 page_first_line
= line
;
975 if (line
== cached_line_details_
.size () - 1)
977 /* This is the last line */
978 /* When the last page height was computed, we did not know yet that it
979 * was the last one. If the systems put on it don't fit anymore, the last
980 * system is moved to a new page */
981 space
.resize (page_height (first_page_num
+ page
, true));
982 if ((line
> page_first_line
) && (isinf (space
.force_
)))
984 res
.systems_per_page_
.push_back (line
- page_first_line
);
985 res
.force_
.push_back (prev_force
);
986 /* the last page containing the last line */
987 space
.resize (page_height (first_page_num
+ page
+ 1, true));
989 space
.append_system (cached_line_details_
[line
]);
990 res
.systems_per_page_
.push_back (1);
991 res
.force_
.push_back (space
.force_
);
992 res
.penalty_
+= cached_line_details_
[line
-1].page_penalty_
;
993 res
.penalty_
+= cached_line_details_
[line
].page_penalty_
;
997 res
.systems_per_page_
.push_back (line
+ 1 - page_first_line
);
998 res
.force_
.push_back (space
.force_
);
999 res
.penalty_
+= cached_line_details_
[line
].page_penalty_
;
1003 return finalize_spacing_result (configuration
, res
);
1006 /* Calculate demerits and fix res.systems_per_page_ so that
1007 it refers to the original line numbers, not the ones given by compress_lines (). */
1009 Page_breaking::finalize_spacing_result (vsize configuration
, Page_spacing_result res
)
1011 if (res
.force_
.empty ())
1014 cache_line_details (configuration
);
1015 res
.systems_per_page_
= uncompress_solution (res
.systems_per_page_
, cached_line_details_
);
1017 Real line_force
= 0;
1018 Real line_penalty
= 0;
1019 Real page_demerits
= res
.penalty_
;
1020 Real page_weighting
= robust_scm2double (book_
->paper_
->c_variable ("page-spacing-weight"), 10);
1022 for (vsize i
= 0; i
< uncompressed_line_details_
.size (); i
++)
1024 line_force
+= uncompressed_line_details_
[i
].force_
* uncompressed_line_details_
[i
].force_
;
1025 line_penalty
+= uncompressed_line_details_
[i
].break_penalty_
;
1028 for (vsize i
= 0; i
< res
.force_
.size (); i
++)
1030 Real f
= res
.force_
[i
];
1032 page_demerits
+= min(f
*f
, BAD_SPACING_PENALTY
);
1035 /* for a while we tried averaging page and line forces across pages instead
1036 of summing them, but it caused a problem: if there is a single page
1037 with a very bad page force (for example because of a forced page break),
1038 the page breaker will put in a _lot_ of pages so that the bad force
1039 becomes averaged out over many pages. */
1040 res
.demerits_
= line_force
+ line_penalty
+ page_demerits
* page_weighting
;
1045 /* the cases for page_count = 1 or 2 can be done in O (n) time. Since they
1046 are by far the most common cases, we have special functions for them.
1048 space_systems_on_1_page has a different calling convention than most of the
1049 space_systems functions. This is because space_systems_on_1_page is (unlike
1050 the other space_systems functions) sometimes called on subsets of a full
1053 Page_breaking::space_systems_on_1_page (vector
<Line_details
> const &lines
, Real page_height
, bool ragged
)
1055 Page_spacing
space (page_height
, page_top_space_
);
1056 Page_spacing_result ret
;
1059 for (vsize i
= 0; i
< lines
.size (); i
++)
1061 space
.append_system (lines
[i
]);
1062 line_count
+= lines
[i
].compressed_nontitle_lines_count_
;
1065 ret
.systems_per_page_
.push_back (lines
.size ());
1066 ret
.force_
.push_back (ragged
? min (space
.force_
, 0.0) : space
.force_
);
1067 ret
.penalty_
= line_count_penalty (line_count
) + lines
.back ().page_penalty_
+ lines
.back ().turn_penalty_
;
1068 ret
.system_count_status_
|= line_count_status (line_count
);
1070 /* don't do finalize_spacing_result () because we are only an internal function */
1075 Page_breaking::space_systems_on_2_pages (vsize configuration
, vsize first_page_num
)
1077 Real page1_height
= page_height (first_page_num
, false);
1078 Real page2_height
= page_height (first_page_num
+ 1, is_last ());
1079 bool ragged1
= ragged ();
1080 bool ragged2
= ragged () || (is_last () && ragged_last ());
1082 /* if there is a forced break, this reduces to 2 1-page problems */
1083 cache_line_details (configuration
);
1084 for (vsize i
= 0; i
+ 1 < cached_line_details_
.size (); i
++)
1085 if (cached_line_details_
[i
].page_permission_
== ly_symbol2scm ("force"))
1087 vector
<Line_details
> lines1 (cached_line_details_
.begin (), cached_line_details_
.begin () + i
+ 1);
1088 vector
<Line_details
> lines2 (cached_line_details_
.begin () + i
+ 1, cached_line_details_
.end ());
1089 Page_spacing_result p1
= space_systems_on_1_page (lines1
, page1_height
, ragged1
);
1090 Page_spacing_result p2
= space_systems_on_1_page (lines2
, page2_height
, ragged2
);
1092 p1
.systems_per_page_
.push_back (p2
.systems_per_page_
[0]);
1093 p1
.force_
.push_back (p2
.force_
[0]);
1094 p1
.penalty_
+= p2
.penalty_
- cached_line_details_
[i
].turn_penalty_
;
1098 vector
<Real
> page1_force
;
1099 vector
<Real
> page2_force
;
1101 // page1_penalty and page2_penalty store the penalties based
1102 // on min-systems-per-page and max-systems-per-page.
1103 vector
<Real
> page1_penalty
;
1104 vector
<Real
> page2_penalty
;
1106 // page1_status and page2_status keep track of whether the min-systems-per-page
1107 // and max-systems-per-page constraints are satisfied.
1108 vector
<int> page1_status
;
1109 vector
<int> page2_status
;
1111 Page_spacing
page1 (page1_height
, page_top_space_
);
1112 Page_spacing
page2 (page2_height
, page_top_space_
);
1113 int page1_line_count
= 0;
1114 int page2_line_count
= 0;
1116 page1_force
.resize (cached_line_details_
.size () - 1, infinity_f
);
1117 page2_force
.resize (cached_line_details_
.size () - 1, infinity_f
);
1118 page1_penalty
.resize (cached_line_details_
.size () - 1, infinity_f
);
1119 page2_penalty
.resize (cached_line_details_
.size () - 1, infinity_f
);
1120 page1_status
.resize (cached_line_details_
.size () - 1, 0);
1121 page2_status
.resize (cached_line_details_
.size () - 1, 0);
1123 /* find the page 1 and page 2 forces for each page-breaking position */
1124 for (vsize i
= 0; i
< page1_force
.size (); i
++)
1126 page1
.append_system (cached_line_details_
[i
]);
1127 page2
.prepend_system (cached_line_details_
[cached_line_details_
.size () - 1 - i
]);
1128 page1_line_count
+= cached_line_details_
[i
].compressed_nontitle_lines_count_
;
1129 page2_line_count
+= cached_line_details_
[cached_line_details_
.size () - 1 - i
].compressed_nontitle_lines_count_
;
1131 page1_force
[i
] = (ragged1
&& page1
.force_
< 0 && i
> 0) ? infinity_f
: page1
.force_
;
1132 page1_penalty
[i
] = line_count_penalty (page1_line_count
);
1133 page1_status
[i
] = line_count_status (page1_line_count
);
1136 page2_force
[page2_force
.size () - 1 - i
] =
1137 (page2
.force_
< 0 && i
+ 1 < page1_force
.size ()) ? infinity_f
: 0;
1139 page2_force
[page2_force
.size () - 1 - i
] = page2
.force_
;
1140 page2_penalty
[page2_penalty
.size () - 1 - i
] = line_count_penalty (page2_line_count
);
1141 page2_status
[page2_penalty
.size () - 1 - i
] = line_count_status (page2_line_count
);
1144 /* find the position that minimises the sum of the page forces */
1145 vsize best_sys_count
= 1;
1146 Real best_demerits
= infinity_f
;
1147 for (vsize i
= 0; i
< page1_force
.size (); i
++)
1149 Real f
= page1_force
[i
] * page1_force
[i
] + page2_force
[i
] * page2_force
[i
];
1151 // NOTE: we treat max-systems-per-page and min-systems-per-page as soft
1152 // constraints. That is, we penalize harshly when they don't happen
1153 // but we don't completely reject.
1155 + page1_penalty
[i
] + page2_penalty
[i
]
1156 + cached_line_details_
[i
+1].page_penalty_
1157 + cached_line_details_
.back ().page_penalty_
+ cached_line_details_
.back ().turn_penalty_
;
1158 if (dem
< best_demerits
)
1160 best_demerits
= dem
;
1161 best_sys_count
= i
+1;
1165 Page_spacing_result ret
;
1166 ret
.systems_per_page_
.push_back (best_sys_count
);
1167 ret
.systems_per_page_
.push_back (cached_line_details_
.size () - best_sys_count
);
1168 ret
.force_
.push_back (page1_force
[best_sys_count
-1]);
1169 ret
.force_
.push_back (page2_force
[best_sys_count
-1]);
1170 ret
.system_count_status_
= page1_status
[best_sys_count
-1] | page2_status
[best_sys_count
-1];
1171 ret
.penalty_
= cached_line_details_
[best_sys_count
-1].page_penalty_
1172 + cached_line_details_
.back ().page_penalty_
1173 + cached_line_details_
.back ().turn_penalty_
1174 + page1_penalty
[best_sys_count
-1] + page2_penalty
[best_sys_count
-1];
1176 /* don't do finalize_spacing_result () because we are only an internal function */
1181 Page_breaking::all_lines_stretched (vsize configuration
)
1183 cache_line_details (configuration
);
1184 for (vsize i
= 0; i
< cached_line_details_
.size (); i
++)
1185 if (cached_line_details_
[i
].force_
< 0)
1191 Page_breaking::Line_division
1192 Page_breaking::current_configuration (vsize configuration_index
) const
1194 return current_configurations_
[configuration_index
];
1198 Page_breaking::is_last () const
1200 return current_end_breakpoint_
== last_break_position ();
1204 Page_breaking::ends_score () const
1206 return breaks_
[current_end_breakpoint_
].score_ender_
;
1210 Page_breaking::last_break_position () const
1212 return breaks_
.size () - 1;