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 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 assert (chunks.size () == div.size () + 1);
80 for (vsize i = 0; i < chunks.size () - 1; i++)
82 vsize sys = next_system (chunks[i]);
83 if (all_[sys].pscore_)
87 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
89 vector<Column_x_positions> pos = line_breaking_[sys].get_solution (start, end, div[i]);
90 all_[sys].pscore_->root_system ()->break_into_pieces (pos);
96 Page_breaking::systems ()
99 for (vsize sys = 0; sys < all_.size (); sys++)
101 if (all_[sys].pscore_)
103 SCM lines = all_[sys].pscore_->root_system ()->get_paper_systems ();
104 ret = scm_cons (scm_vector_to_list (lines), ret);
108 Prob *pb = all_[sys].prob_;
109 ret = scm_cons (scm_list_1 (pb->self_scm ()), ret);
113 return scm_append (scm_reverse (ret));
117 Page_breaking::line_details (vsize start_break, vsize end_break, Line_division const &div)
119 vector<Break_position> chunks = chunk_list (start_break, end_break);
120 vector<Line_details> ret;
121 assert (chunks.size () == div.size () + 1);
123 for (vsize i = 0; i < chunks.size () - 1; i++)
125 vsize sys = next_system (chunks[i]);
126 if (all_[sys].pscore_)
130 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
132 vector<Line_details> details = line_breaking_[sys].get_details (start, end, div[i]);
133 ret.insert (ret.end (), details.begin (), details.end ());
137 assert (div[i] == 1);
138 ret.push_back (Line_details (all_[sys].prob_));
145 Page_breaking::page_height (int page_num, bool last)
147 SCM mod = scm_c_resolve_module ("scm page");
148 SCM calc_height = scm_c_module_lookup (mod, "calc-printable-height");
149 SCM make_page = scm_c_module_lookup (mod, "make-page");
151 calc_height = scm_variable_ref (calc_height);
152 make_page = scm_variable_ref (make_page);
154 SCM page = scm_apply_0 (make_page, scm_list_n (
156 ly_symbol2scm ("page-number"), scm_from_int (page_num),
157 ly_symbol2scm ("is-last"), scm_from_bool (last),
159 SCM height = scm_apply_1 (calc_height, page, SCM_EOL);
160 return scm_to_double (height) - scm_to_double (book_->paper_->c_variable ("page-top-space"));
164 Page_breaking::breakpoint_property (vsize breakpoint, char const *str)
166 Break_position const &pos = breaks_[breakpoint];
168 if (pos.sys_ == VPOS)
170 if (all_[pos.sys_].pscore_)
171 return pos.col_->get_property (str);
172 return all_[pos.sys_].prob_->get_property (str);
176 Page_breaking::make_pages (vector<vsize> lines_per_page, SCM systems)
178 SCM layout_module = scm_c_resolve_module ("scm layout-page-layout");
179 SCM dump_module = scm_c_resolve_module ("scm layout-page-dump");
180 SCM page_module = scm_c_resolve_module ("scm page");
182 SCM make_page = scm_c_module_lookup (layout_module, "make-page-from-systems");
183 SCM write_page_breaks = scm_c_module_lookup (dump_module, "write-page-breaks");
184 SCM page_stencil = scm_c_module_lookup (page_module, "page-stencil");
185 make_page = scm_variable_ref (make_page);
186 write_page_breaks = scm_variable_ref (write_page_breaks);
187 page_stencil = scm_variable_ref (page_stencil);
189 SCM book = book_->self_scm ();
190 bool ragged_all = to_boolean (book_->paper_->c_variable ("ragged-bottom"));
191 bool ragged_last = to_boolean (book_->paper_->c_variable ("ragged-last-bottom"));
194 for (vsize i = 0; i < lines_per_page.size (); i++)
196 SCM page_num = scm_from_int (i + 1);
197 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
198 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
199 SCM line_count = scm_from_int (lines_per_page[i]);
200 SCM lines = scm_list_head (systems, line_count);
201 SCM page = scm_apply_0 (make_page,
202 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
204 scm_apply_1 (page_stencil, page, SCM_EOL);
205 ret = scm_cons (page, ret);
206 systems = scm_list_tail (systems, line_count);
208 ret = scm_reverse (ret);
210 if (to_boolean (book_->paper_->c_variable ("write-page-layout")))
211 scm_apply_1 (write_page_breaks, ret, SCM_EOL);
215 /* The page-turn-page-breaker needs to have a line-breaker between any two
216 columns with non-NULL page-turn-permission.
218 The optimal-breaker needs to have a line-breaker between any two columns
219 with page-break-permission = 'force.
221 By using a grob predicate, we can accommodate both of these uses.
224 Page_breaking::create_system_list ()
226 SCM specs = book_->get_system_specs ();
227 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
229 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
231 SCM system_count = ps->layout ()->c_variable ("system-count");
233 if (scm_is_number (system_count))
234 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
235 scm_vector_to_list (ps->get_paper_systems ()),
238 all_.push_back (System_spec (ps));
242 Prob *pb = unsmob_prob (scm_car (s));
246 all_.push_back (System_spec (pb));
252 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
254 SCM force_sym = ly_symbol2scm ("force");
256 chunks_.push_back (Break_position ());
257 breaks_.push_back (Break_position ());
259 for (vsize i = 0; i < all_.size (); i++)
263 vector<Grob*> cols = all_[i].pscore_->root_system ()->columns ();
264 vector<vsize> line_breaker_columns;
265 line_breaker_columns.push_back (0);
267 for (vsize j = 1; j < cols.size (); j++)
269 bool last = j == cols.size () - 1;
270 bool break_point = is_break (cols[j]);
271 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
272 Break_position cur_pos = Break_position (i,
273 line_breaker_columns.size (),
277 if (break_point || (i == all_.size () - 1 && last))
278 breaks_.push_back (cur_pos);
279 if (chunk_end || last)
280 chunks_.push_back (cur_pos);
282 if ((break_point || chunk_end) && !last)
283 line_breaker_columns.push_back (j);
285 line_breaking_.push_back (Constrained_breaking (line_breaker_columns));
286 line_breaking_.back ().set_pscore (all_[i].pscore_);
290 /* TODO: we want some way of applying Break_p to a prob? */
291 if (i == all_.size () - 1)
292 breaks_.push_back (Break_position (i));
294 chunks_.push_back (Break_position (i));
295 line_breaking_.push_back (Constrained_breaking ());
300 vector<Break_position>
301 Page_breaking::chunk_list (vsize start_index, vsize end_index)
303 Break_position start = breaks_[start_index];
304 Break_position end = breaks_[end_index];
307 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
310 vector<Break_position> ret;
311 ret.push_back (start);
312 for (; i < chunks_.size () && chunks_[i] < end; i++)
313 ret.push_back (chunks_[i]);
319 Page_breaking::min_system_count (vsize start, vsize end)
321 vector<Break_position> chunks = chunk_list (start, end);
322 Line_division div = system_count_bounds (chunks, true);
325 for (vsize i = 0; i < div.size (); i++)
331 Page_breaking::max_system_count (vsize start, vsize end)
333 vector<Break_position> chunks = chunk_list (start, end);
334 Line_division div = system_count_bounds (chunks, false);
337 for (vsize i = 0; i < div.size (); i++)
342 Page_breaking::Line_division
343 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
345 assert (chunks.size () >= 2);
348 ret.resize (chunks.size () - 1, 1);
350 for (vsize i = 0; i < chunks.size () - 1; i++)
352 vsize sys = next_system (chunks[i]);
353 if (all_[sys].pscore_)
357 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
359 ? line_breaking_[sys].get_min_systems (start, end)
360 : line_breaking_[sys].get_max_systems (start, end);
367 vector<Page_breaking::Line_division>
368 Page_breaking::line_divisions (vsize start,
371 Line_division lower_bound,
372 Line_division upper_bound)
374 vector<Break_position> chunks = chunk_list (start, end);
376 if (!lower_bound.size ())
377 lower_bound = system_count_bounds (chunks, true);
378 if (!upper_bound.size ())
379 upper_bound = system_count_bounds (chunks, false);
381 assert (lower_bound.size () == chunks.size () - 1);
382 assert (upper_bound.size () == chunks.size () - 1);
384 vector<Line_division> ret;
385 Line_division work_in_progress;
387 line_divisions_rec (system_count,
396 Page_breaking::line_divisions_rec (vsize system_count,
397 Line_division const &min_sys,
398 Line_division const &max_sys,
399 vector<Line_division > *result,
400 Line_division *cur_division)
402 vsize my_index = cur_division->size ();
403 vsize others_min = 0;
404 vsize others_max = 0;
406 for (vsize i = my_index + 1; i < min_sys.size (); i++)
408 others_min += min_sys[i];
409 others_max += max_sys[i];
411 others_max = min (others_max, system_count);
412 vsize real_min = max (min_sys[my_index], system_count - others_max);
413 vsize real_max = min (max_sys[my_index], system_count - others_min);
415 if (real_min > real_max || real_min <= 0)
417 /* this should never happen within a recursive call. If it happens
418 at all, it means that we were called with an unsolvable problem
419 and we should return an empty result */
420 assert (my_index == 0);
424 for (vsize i = real_min; i <= real_max; i++)
426 cur_division->push_back (i);
427 if (my_index == min_sys.size () - 1)
428 result->push_back (*cur_division);
430 line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
431 cur_division->pop_back ();