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 Page_breaking, the start index (when we are dealing with the stuff
23 between a pair of breakpoints) refers to the break_ index of the end of
24 the previous page. So the system index of the start of the current page
25 could either be the same as the end of the previous page or one more than
28 /* Turn a break index into the sys index that starts the next page */
30 Page_breaking::next_system (Break_position const &break_pos) const
32 vsize sys = break_pos.sys_;
34 if (sys == VPOS) /* beginning of the book */
36 if (all_[sys].pscore_ && !break_pos.score_ender_)
37 return sys; /* the score overflows the previous page */
38 return sys + 1; /* this page starts with a new sys */
41 Page_breaking::Page_breaking (Paper_book *pb, Break_predicate is_break)
44 create_system_list ();
45 find_chunks_and_breaks (is_break);
48 Page_breaking::~Page_breaking ()
52 /* translate indices into breaks_ into start-end parameters for the line breaker */
54 Page_breaking::line_breaker_args (vsize sys,
55 Break_position const &start,
56 Break_position const &end,
57 vsize *line_breaker_start,
58 vsize *line_breaker_end)
60 assert (all_[sys].pscore_);
61 assert (next_system (start) <= sys && sys <= end.sys_);
63 if (start.sys_ == sys)
64 *line_breaker_start = start.score_break_;
66 *line_breaker_start = 0;
69 *line_breaker_end = end.score_break_;
71 *line_breaker_end = VPOS;
75 Page_breaking::break_into_pieces (vsize start_break, vsize end_break, Line_division const &div)
77 vector<Break_position> chunks = chunk_list (start_break, end_break);
78 bool ignore_div = false;
79 if (chunks.size () != div.size () + 1)
81 programming_error ("did not find a valid page breaking configuration");
85 for (vsize i = 0; i + 1 < chunks.size (); i++)
87 vsize sys = next_system (chunks[i]);
88 if (all_[sys].pscore_)
92 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
94 vector<Column_x_positions> pos = ignore_div
95 ? line_breaking_[sys].best_solution (start, end)
96 : line_breaking_[sys].solve (start, end, div[i]);
97 all_[sys].pscore_->root_system ()->break_into_pieces (pos);
103 Page_breaking::systems ()
106 for (vsize sys = 0; sys < all_.size (); sys++)
108 if (all_[sys].pscore_)
110 all_[sys].pscore_->root_system ()->do_break_substitution_and_fixup_refpoints ();
111 SCM lines = all_[sys].pscore_->root_system ()->get_broken_system_grobs ();
112 ret = scm_cons (lines, ret);
116 Prob *pb = all_[sys].prob_;
117 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
121 return scm_append (scm_reverse (ret));
125 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
127 vector<Break_position> chunks = chunk_list (start_break, end_break);
128 vector<Line_details> ret;
129 assert (chunks.size () == div.size () + 1);
131 SCM padding_scm = book_->paper_->c_variable ("page-breaking-between-system-padding");
132 if (!scm_is_number (padding_scm))
133 padding_scm = book_->paper_->c_variable ("between-system-padding");
134 Real padding = robust_scm2double (padding_scm, 0.0);
136 for (vsize i = 0; i + 1 < chunks.size (); i++)
138 vsize sys = next_system (chunks[i]);
139 if (all_[sys].pscore_)
143 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
145 vector<Line_details> details = line_breaking_[sys].line_details (start, end, div[i]);
146 ret.insert (ret.end (), details.begin (), details.end ());
150 assert (div[i] == 1);
151 ret.push_back (Line_details (all_[sys].prob_));
152 ret.back ().padding_ = padding;
159 Page_breaking::page_height (int page_num, bool last)
161 SCM mod = scm_c_resolve_module ("scm page");
162 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
163 SCM make_page = scm_c_module_lookup (mod, "make-page");
165 calc_height = scm_variable_ref (calc_height);
166 make_page = scm_variable_ref (make_page);
168 SCM page = scm_apply_0 (make_page, scm_list_n (
170 ly_symbol2scm ("page-number"), scm_from_int (page_num),
171 ly_symbol2scm ("is-last"), scm_from_bool (last),
173 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
174 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
178 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
180 Break_position const &pos = breaks_[breakpoint];
182 if (pos.sys_ == VPOS)
184 if (all_[pos.sys_].pscore_)
185 return pos.col_->get_property (str);
186 return all_[pos.sys_].prob_->get_property (str);
190 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
192 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
193 SCM page_module = scm_c_resolve_module ("scm page");
195 SCM make_page = scm_c_module_lookup (layout_module, "stretch-and-draw-page");
196 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
197 make_page = scm_variable_ref (make_page);
198 page_stencil = scm_variable_ref (page_stencil);
200 SCM book = book_->self_scm ();
201 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
202 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
203 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
206 for (vsize i = 0; i < lines_per_page.size (); i++)
208 SCM page_num = scm_from_int (i + first_page_number);
209 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
210 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
211 SCM line_count = scm_from_int (lines_per_page[i]);
212 SCM lines = scm_list_head (systems, line_count);
213 SCM page = scm_apply_0 (make_page,
214 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
216 scm_apply_1 (page_stencil, page, SCM_EOL);
217 ret = scm_cons (page, ret);
218 systems = scm_list_tail (systems, line_count);
220 ret = scm_reverse (ret);
224 /* The page-turn-page-breaker needs to have a line-breaker between any two
225 columns with non-NULL page-turn-permission.
227 The optimal-breaker needs to have a line-breaker between any two columns
228 with page-break-permission = 'force.
230 By using a grob predicate, we can accommodate both of these uses.
233 Page_breaking::create_system_list ()
235 SCM specs = book_->get_system_specs ();
236 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
238 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
240 SCM system_count = ps->layout ()->c_variable ("system-count");
242 if (scm_is_number (system_count))
243 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
244 scm_vector_to_list (ps->get_paper_systems ()),
247 all_.push_back (System_spec (ps));
251 Prob *pb = unsmob_prob (scm_car (s));
255 all_.push_back (System_spec (pb));
261 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
263 SCM force_sym = ly_symbol2scm ("force");
265 chunks_.push_back (Break_position ());
266 breaks_.push_back (Break_position ());
268 for (vsize i = 0; i < all_.size (); i++)
272 vector<Grob*> cols = all_[i].pscore_->root_system ()->used_columns ();
273 vector<vsize> line_breaker_columns;
274 line_breaker_columns.push_back (0);
276 for (vsize j = 1; j < cols.size (); j++)
278 bool last = j == cols.size () - 1;
279 bool break_point = is_break (cols[j]);
280 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
281 Break_position cur_pos = Break_position (i,
282 line_breaker_columns.size (),
286 if (break_point || (i == all_.size () - 1 && last))
287 breaks_.push_back (cur_pos);
288 if (chunk_end || last)
289 chunks_.push_back (cur_pos);
291 if ((break_point || chunk_end) && !last)
292 line_breaker_columns.push_back (j);
294 line_breaking_.push_back (Constrained_breaking (all_[i].pscore_, line_breaker_columns));
298 /* TODO: we want some way of applying Break_p to a prob? */
299 if (i == all_.size () - 1)
300 breaks_.push_back (Break_position (i));
302 chunks_.push_back (Break_position (i));
303 line_breaking_.push_back (Constrained_breaking (NULL));
308 vector<Break_position>
309 Page_breaking::chunk_list (vsize start_index, vsize end_index)
311 Break_position start = breaks_[start_index];
312 Break_position end = breaks_[end_index];
315 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
318 vector<Break_position> ret;
319 ret.push_back (start);
320 for (; i < chunks_.size () && chunks_[i] < end; i++)
321 ret.push_back (chunks_[i]);
327 Page_breaking::min_system_count (vsize start, vsize end)
329 vector<Break_position> chunks = chunk_list (start, end);
330 Line_division div = system_count_bounds (chunks, true);
333 for (vsize i = 0; i < div.size (); i++)
339 Page_breaking::max_system_count (vsize start, vsize end)
341 vector<Break_position> chunks = chunk_list (start, end);
342 Line_division div = system_count_bounds (chunks, false);
345 for (vsize i = 0; i < div.size (); i++)
350 Page_breaking::Line_division
351 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
353 assert (chunks.size () >= 2);
356 ret.resize (chunks.size () - 1, 1);
358 for (vsize i = 0; i + 1 < chunks.size (); i++)
360 vsize sys = next_system (chunks[i]);
361 if (all_[sys].pscore_)
365 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
367 ? line_breaking_[sys].min_system_count (start, end)
368 : line_breaking_[sys].max_system_count (start, end);
375 vector<Page_breaking::Line_division>
376 Page_breaking::line_divisions (vsize start,
379 Line_division lower_bound,
380 Line_division upper_bound)
382 vector<Break_position> chunks = chunk_list (start, end);
384 if (!lower_bound.size ())
385 lower_bound = system_count_bounds (chunks, true);
386 if (!upper_bound.size ())
387 upper_bound = system_count_bounds (chunks, false);
389 assert (lower_bound.size () == chunks.size () - 1);
390 assert (upper_bound.size () == chunks.size () - 1);
392 vector<Line_division> ret;
393 Line_division work_in_progress;
395 line_divisions_rec (system_count,
404 Page_breaking::line_divisions_rec (vsize system_count,
405 Line_division const &min_sys,
406 Line_division const &max_sys,
407 vector<Line_division > *result,
408 Line_division *cur_division)
410 vsize my_index = cur_division->size ();
411 vsize others_min = 0;
412 vsize others_max = 0;
414 for (vsize i = my_index + 1; i < min_sys.size (); i++)
416 others_min += min_sys[i];
417 others_max += max_sys[i];
419 others_max = min (others_max, system_count);
420 vsize real_min = max (min_sys[my_index], system_count - others_max);
421 vsize real_max = min (max_sys[my_index], system_count - others_min);
423 if (real_min > real_max || real_min <= 0)
425 /* this should never happen within a recursive call. If it happens
426 at all, it means that we were called with an unsolvable problem
427 and we should return an empty result */
428 assert (my_index == 0);
432 for (vsize i = real_min; i <= real_max; i++)
434 cur_division->push_back (i);
435 if (my_index == min_sys.size () - 1)
436 result->push_back (*cur_division);
438 line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
439 cur_division->pop_back ();