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"));
192 int first_page_number = robust_scm2int (book_->paper_->c_variable ("first-page-number"), 1);
195 for (vsize i = 0; i < lines_per_page.size (); i++)
197 SCM page_num = scm_from_int (i + first_page_number);
198 SCM last = scm_from_bool (i == lines_per_page.size () - 1);
199 SCM ragged = scm_from_bool (ragged_all || (to_boolean (last) && ragged_last));
200 SCM line_count = scm_from_int (lines_per_page[i]);
201 SCM lines = scm_list_head (systems, line_count);
202 SCM page = scm_apply_0 (make_page,
203 scm_list_n (book, lines, page_num, ragged, last, SCM_UNDEFINED));
205 scm_apply_1 (page_stencil, page, SCM_EOL);
206 ret = scm_cons (page, ret);
207 systems = scm_list_tail (systems, line_count);
209 ret = scm_reverse (ret);
211 if (to_boolean (book_->paper_->c_variable ("write-page-layout")))
212 scm_apply_1 (write_page_breaks, ret, SCM_EOL);
216 /* The page-turn-page-breaker needs to have a line-breaker between any two
217 columns with non-NULL page-turn-permission.
219 The optimal-breaker needs to have a line-breaker between any two columns
220 with page-break-permission = 'force.
222 By using a grob predicate, we can accommodate both of these uses.
225 Page_breaking::create_system_list ()
227 SCM specs = book_->get_system_specs ();
228 for (SCM s = specs; scm_is_pair (s); s = scm_cdr (s))
230 if (Paper_score *ps = dynamic_cast<Paper_score*> (unsmob_music_output (scm_car (s))))
232 SCM system_count = ps->layout ()->c_variable ("system-count");
234 if (scm_is_number (system_count))
235 s = scm_append (scm_list_3 (scm_list_1 (scm_car (s)),
236 scm_vector_to_list (ps->get_paper_systems ()),
239 all_.push_back (System_spec (ps));
243 Prob *pb = unsmob_prob (scm_car (s));
247 all_.push_back (System_spec (pb));
253 Page_breaking::find_chunks_and_breaks (Break_predicate is_break)
255 SCM force_sym = ly_symbol2scm ("force");
257 chunks_.push_back (Break_position ());
258 breaks_.push_back (Break_position ());
260 for (vsize i = 0; i < all_.size (); i++)
264 vector<Grob*> cols = all_[i].pscore_->root_system ()->columns ();
265 vector<vsize> line_breaker_columns;
266 line_breaker_columns.push_back (0);
268 for (vsize j = 1; j < cols.size (); j++)
270 bool last = j == cols.size () - 1;
271 bool break_point = is_break (cols[j]);
272 bool chunk_end = cols[j]->get_property ("page-break-permission") == force_sym;
273 Break_position cur_pos = Break_position (i,
274 line_breaker_columns.size (),
278 if (break_point || (i == all_.size () - 1 && last))
279 breaks_.push_back (cur_pos);
280 if (chunk_end || last)
281 chunks_.push_back (cur_pos);
283 if ((break_point || chunk_end) && !last)
284 line_breaker_columns.push_back (j);
286 line_breaking_.push_back (Constrained_breaking (line_breaker_columns));
287 line_breaking_.back ().set_pscore (all_[i].pscore_);
291 /* TODO: we want some way of applying Break_p to a prob? */
292 if (i == all_.size () - 1)
293 breaks_.push_back (Break_position (i));
295 chunks_.push_back (Break_position (i));
296 line_breaking_.push_back (Constrained_breaking ());
301 vector<Break_position>
302 Page_breaking::chunk_list (vsize start_index, vsize end_index)
304 Break_position start = breaks_[start_index];
305 Break_position end = breaks_[end_index];
308 for (i = 0; i < chunks_.size () && chunks_[i] <= start; i++)
311 vector<Break_position> ret;
312 ret.push_back (start);
313 for (; i < chunks_.size () && chunks_[i] < end; i++)
314 ret.push_back (chunks_[i]);
320 Page_breaking::min_system_count (vsize start, vsize end)
322 vector<Break_position> chunks = chunk_list (start, end);
323 Line_division div = system_count_bounds (chunks, true);
326 for (vsize i = 0; i < div.size (); i++)
332 Page_breaking::max_system_count (vsize start, vsize end)
334 vector<Break_position> chunks = chunk_list (start, end);
335 Line_division div = system_count_bounds (chunks, false);
338 for (vsize i = 0; i < div.size (); i++)
343 Page_breaking::Line_division
344 Page_breaking::system_count_bounds (vector<Break_position> const &chunks, bool min)
346 assert (chunks.size () >= 2);
349 ret.resize (chunks.size () - 1, 1);
351 for (vsize i = 0; i < chunks.size () - 1; i++)
353 vsize sys = next_system (chunks[i]);
354 if (all_[sys].pscore_)
358 line_breaker_args (sys, chunks[i], chunks[i+1], &start, &end);
360 ? line_breaking_[sys].get_min_systems (start, end)
361 : line_breaking_[sys].get_max_systems (start, end);
368 vector<Page_breaking::Line_division>
369 Page_breaking::line_divisions (vsize start,
372 Line_division lower_bound,
373 Line_division upper_bound)
375 vector<Break_position> chunks = chunk_list (start, end);
377 if (!lower_bound.size ())
378 lower_bound = system_count_bounds (chunks, true);
379 if (!upper_bound.size ())
380 upper_bound = system_count_bounds (chunks, false);
382 assert (lower_bound.size () == chunks.size () - 1);
383 assert (upper_bound.size () == chunks.size () - 1);
385 vector<Line_division> ret;
386 Line_division work_in_progress;
388 line_divisions_rec (system_count,
397 Page_breaking::line_divisions_rec (vsize system_count,
398 Line_division const &min_sys,
399 Line_division const &max_sys,
400 vector<Line_division > *result,
401 Line_division *cur_division)
403 vsize my_index = cur_division->size ();
404 vsize others_min = 0;
405 vsize others_max = 0;
407 for (vsize i = my_index + 1; i < min_sys.size (); i++)
409 others_min += min_sys[i];
410 others_max += max_sys[i];
412 others_max = min (others_max, system_count);
413 vsize real_min = max (min_sys[my_index], system_count - others_max);
414 vsize real_max = min (max_sys[my_index], system_count - others_min);
416 if (real_min > real_max || real_min <= 0)
418 /* this should never happen within a recursive call. If it happens
419 at all, it means that we were called with an unsolvable problem
420 and we should return an empty result */
421 assert (my_index == 0);
425 for (vsize i = real_min; i <= real_max; i++)
427 cur_division->push_back (i);
428 if (my_index == min_sys.size () - 1)
429 result->push_back (*cur_division);
431 line_divisions_rec (system_count - i, min_sys, max_sys, result, cur_division);
432 cur_division->pop_back ();