2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 Joe Neeman <joeneeman@gmail.com>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
20 #include "constrained-breaking.hh"
22 #include "international.hh"
24 #include "output-def.hh"
25 #include "page-layout-problem.hh"
26 #include "paper-column.hh"
27 #include "paper-score.hh"
28 #include "simple-spacer.hh"
33 We use the following optimal substructure. Let W (A) be our weight function.
35 Let A_{k, n} = (a_{k, n, 1}, ... a_{k, n, k}) be the optimal set of line breaks
36 for k systems and n potential breakpoints. a_{k, n, k} = n (it is the end of
39 Then A_{k+1, m} is contructed from
40 min_ {k < j < m} ( W (A_{k, j} :: m) )
41 where by A::m we denote appending m to the list A
45 The above algorithm makes it easy to end at a point before the end of the
46 score (just find A_{k, m} for some m < breaks_.size () - 1). However, we must
47 add information for starting at a point after the beginning. One constructor
48 allows the specification of a list of starting columns, start_. We then have
49 start_.size () different solution arrays. state_[i] is the array for the
50 solution starting at column number start_[i].
52 The indices "start" and "end" refer to the index in the start_ array of the
53 desired starting and ending columns.
55 each solution array looks like
56 a_{1,1,1} a_{2,1,2} a_{3,1,3} . . .
57 X a_{2,2,2} a_{3,2,3} . . .
61 where the X's mark invalid solutions (can't have more systems than
62 breakpoints). Note that each value is of the form a_{x, n, x}. This is because
63 a breakpoint of the form a_{x, n, x-1} will also be called a_{x-1, m, x-1} for
64 some m < n. Each cell in the array stores the value of its m (ie. the
65 ending breakpoint of the previous line) as "prev_".
67 For finding A_{sys, brk}, let "me" be the (sys_count, brk) cell in our
68 solution array (state_[start][sys * rank + brk]).
70 Then A_{sys, brk} = A_{sys - 1, me.prev_} :: me
74 start and sys here are indexed from 0.
75 brk is indexed from starting_breakpoints_[start]
76 (for brk, starting_breakpoints_[start] is the beginning
77 of the piece; the smallest value we should ever see here is
78 starting_breakpoints_[start] + 1) */
80 Constrained_breaking::calc_subproblem (vsize start
, vsize sys
, vsize brk
)
82 assert (sys
< systems_
);
83 assert (start
< start_
.size ());
84 assert (brk
< breaks_
.size ());
86 bool found_something
= false;
87 vsize start_col
= starting_breakpoints_
[start
];
88 Matrix
<Constrained_break_node
> &st
= state_
[start
];
89 vsize max_index
= brk
- start_col
;
90 for (vsize j
=max_index
; j
-- > sys
;)
92 if (0 == sys
&& j
> 0)
93 continue; /* the first line cannot have its first break after the beginning */
95 Line_details
const &cur
= lines_
.at (brk
, j
+ start_col
);
96 if (isinf (cur
.force_
))
104 prev_f
= st
.at (j
, sys
-1).details_
.force_
;
105 prev_dem
= st
.at (j
, sys
-1).demerits_
;
107 if (isinf (prev_dem
))
110 Real dem
= combine_demerits (cur
.force_
, prev_f
) + prev_dem
+ cur
.break_penalty_
;
111 Constrained_break_node
&n
= st
.at (max_index
, sys
);
112 if (dem
< n
.demerits_
)
114 found_something
= true;
120 return found_something
;
125 Constrained_breaking::space_line (vsize i
, vsize j
)
127 bool ragged_right
= to_boolean (pscore_
->layout ()->c_variable ("ragged-right"));
128 bool ragged_last
= to_boolean (pscore_
->layout ()->c_variable ("ragged-last"));
129 Column_x_positions col
;
131 vector
<Grob
*> line (all_
.begin () + breaks_
[i
],
132 all_
.begin () + breaks_
[j
] + 1);
133 Interval line_dims
= line_dimensions_int (pscore_
->layout (), i
);
134 bool last
= j
== breaks_
.size () - 1;
135 bool ragged
= ragged_right
|| (last
&& ragged_last
);
137 /* As a special case, if there is only one line in the score and ragged-right
138 hasn't been specifically forbidden and the line is stretched, use
141 && lines_
.at (i
, j
).force_
>= 0
142 && !scm_is_bool (pscore_
->layout ()->c_variable ("ragged-right"))
143 && !scm_is_bool (pscore_
->layout ()->c_variable ("ragged-last")))
146 return get_line_configuration (line
, line_dims
[RIGHT
] - line_dims
[LEFT
], line_dims
[LEFT
], ragged
);
150 Constrained_breaking::resize (vsize systems
)
154 if (pscore_
&& systems_
> valid_systems_
)
156 for (vsize i
= 0; i
< state_
.size (); i
++)
157 state_
[i
].resize (breaks_
.size () - starting_breakpoints_
[i
], systems_
, Constrained_break_node ());
159 /* fill out the matrices */
160 for (vsize i
= 0; i
< state_
.size (); i
++)
161 for (vsize j
= valid_systems_
; j
< systems_
; j
++)
162 for (vsize k
= starting_breakpoints_
[i
] + j
+ 1; k
< breaks_
.size (); k
++)
163 if (!calc_subproblem (i
, j
, k
))
164 break; /* if we couldn't break this, it is too cramped already */
165 valid_systems_
= systems_
;
169 vector
<Column_x_positions
>
170 Constrained_breaking::solve (vsize start
, vsize end
, vsize sys_count
)
172 vsize start_brk
= starting_breakpoints_
[start
];
173 vsize end_brk
= prepare_solution (start
, end
, sys_count
);
175 Matrix
<Constrained_break_node
> const &st
= state_
[start
];
176 vector
<Column_x_positions
> ret
;
178 /* find the first solution that satisfies constraints */
179 for (vsize sys
= sys_count
-1; sys
!= VPOS
; sys
--)
181 for (vsize brk
= end_brk
; brk
!= VPOS
; brk
--)
183 if (!isinf (st
.at (brk
, sys
).details_
.force_
))
187 brk
= st
.at (brk
, sys
).prev_
;
189 warning (_ ("cannot find line breaking that satisfies constraints"));
190 ret
.push_back (space_line (brk
, end_brk
));
193 /* build up the good part of the solution */
194 for (vsize cur_sys
= sys
; cur_sys
!= VPOS
; cur_sys
--)
196 vsize prev_brk
= st
.at (brk
, cur_sys
).prev_
;
197 assert (brk
!= VPOS
);
198 ret
.push_back (space_line (prev_brk
+ start_brk
, brk
+ start_brk
));
206 /* if we get to here, just put everything on one line */
207 warning (_ ("cannot find line breaking that satisfies constraints"));
208 ret
.push_back (space_line (0, end_brk
));
212 vector
<Column_x_positions
>
213 Constrained_breaking::best_solution (vsize start
, vsize end
)
215 vsize min_systems
= min_system_count (start
, end
);
216 vsize max_systems
= max_system_count (start
, end
);
217 Real best_demerits
= infinity_f
;
218 vector
<Column_x_positions
> best_so_far
;
220 for (vsize i
= min_systems
; i
<= max_systems
; i
++)
222 vsize brk
= prepare_solution (start
, end
, i
);
223 Real dem
= state_
[start
].at (brk
, i
-1).demerits_
;
225 if (dem
< best_demerits
)
228 best_so_far
= solve (start
, end
, i
);
232 vector
<Column_x_positions
> cur
= solve (start
, end
, i
);
233 bool too_many_lines
= true;
235 for (vsize j
= 0; j
< cur
.size (); j
++)
236 if (cur
[j
].force_
< 0)
238 too_many_lines
= false;
245 if (best_so_far
.size ())
247 return solve (start
, end
, max_systems
);
250 std::vector
<Line_details
>
251 Constrained_breaking::line_details (vsize start
, vsize end
, vsize sys_count
)
253 vsize end_brk
= prepare_solution (start
, end
, sys_count
);
254 Matrix
<Constrained_break_node
> const &st
= state_
[start
];
255 vector
<Line_details
> ret
;
257 /* This loop structure is C&Ped from solve(). */
258 /* find the first solution that satisfies constraints */
259 for (vsize sys
= sys_count
-1; sys
!= VPOS
; sys
--)
261 for (vsize brk
= end_brk
; brk
!= VPOS
; brk
--)
263 if (!isinf (st
.at (brk
, sys
).details_
.force_
))
268 During initialize(), we only fill out a
269 Line_details for lines that are valid (ie. not too
270 long), otherwise line breaking becomes O(n^3).
271 In case sys_count is such that no valid solution
272 is found, we need to fill in the Line_details.
274 Line_details details
;
275 brk
= st
.at (brk
, sys
).prev_
;
277 fill_line_details (&details
, brk
, end_brk
);
278 ret
.push_back (details
);
281 /* build up the good part of the solution */
282 for (vsize cur_sys
= sys
; cur_sys
!= VPOS
; cur_sys
--)
284 vsize prev_brk
= st
.at (brk
, cur_sys
).prev_
;
285 assert (brk
!= VPOS
);
286 ret
.push_back (st
.at (brk
, cur_sys
).details_
);
295 /* if we get to here, just put everything on one line */
296 Line_details details
;
297 fill_line_details (&details
, 0, end_brk
);
298 ret
.push_back (details
);
303 Constrained_breaking::min_system_count (vsize start
, vsize end
)
306 vsize brk
= prepare_solution (start
, end
, 1);
307 vsize rank
= breaks_
.size () - starting_breakpoints_
[start
];
308 Matrix
<Constrained_break_node
> const &st
= state_
[start
];
310 /* sys_count < rank : rank is the # of breakpoints, we can't have more systems */
311 for (sys_count
= 0; sys_count
< rank
; sys_count
++)
313 if (sys_count
>= valid_systems_
)
315 resize (sys_count
+ 3);
317 if (!isinf (st
.at (brk
, sys_count
).details_
.force_
))
318 return sys_count
+ 1;
320 /* no possible breaks satisfy constraints */
325 Constrained_breaking::max_system_count (vsize start
, vsize end
)
327 vsize brk
= (end
>= start_
.size ()) ? breaks_
.size () - 1 : starting_breakpoints_
[end
];
328 return brk
- starting_breakpoints_
[start
];
332 Constrained_breaking::prepare_solution (vsize start
, vsize end
, vsize sys_count
)
334 assert (start
< start_
.size () && (end
== VPOS
|| end
<= start_
.size ()));
335 assert (start
< end
);
338 if (end
== start_
.size ())
342 brk
= end
== VPOS
? breaks_
.size () - 1 : starting_breakpoints_
[end
];
343 brk
-= starting_breakpoints_
[start
];
347 Constrained_breaking::Constrained_breaking (Paper_score
*ps
)
349 valid_systems_
= systems_
= 0;
350 start_
.push_back (0);
355 Constrained_breaking::Constrained_breaking (Paper_score
*ps
, vector
<vsize
> const &start
)
358 valid_systems_
= systems_
= 0;
364 min_permission (SCM perm1
, SCM perm2
)
366 if (perm1
== ly_symbol2scm ("force"))
368 if (perm1
== ly_symbol2scm ("allow")
369 && perm2
!= ly_symbol2scm ("force"))
374 /* find the forces for all possible lines and cache ragged_ and ragged_right_ */
376 Constrained_breaking::initialize ()
381 ragged_right_
= to_boolean (pscore_
->layout ()->c_variable ("ragged-right"));
382 ragged_last_
= to_boolean (pscore_
->layout ()->c_variable ("ragged-last"));
383 system_system_space_
= 0;
384 system_markup_space_
= 0;
385 system_system_padding_
= 0;
386 system_system_min_distance_
= 0;
387 score_system_padding_
= 0;
388 score_system_min_distance_
= 0;
389 score_markup_padding_
= 0;
390 score_markup_min_distance_
= 0;
392 Output_def
*l
= pscore_
->layout ();
394 SCM spacing_spec
= l
->c_variable ("system-system-spacing");
395 SCM between_scores_spec
= l
->c_variable ("score-system-spacing");
396 SCM title_spec
= l
->c_variable ("score-markup-spacing");
397 SCM page_breaking_spacing_spec
= l
->c_variable ("page-breaking-system-system-spacing");
399 Page_layout_problem::read_spacing_spec (spacing_spec
,
400 &system_system_space_
,
401 ly_symbol2scm ("basic-distance"));
402 Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec
,
403 &system_system_space_
,
404 ly_symbol2scm ("basic-distance"));
405 Page_layout_problem::read_spacing_spec (title_spec
,
406 &system_markup_space_
,
407 ly_symbol2scm ("basic-distance"));
409 Page_layout_problem::read_spacing_spec (spacing_spec
,
410 &system_system_padding_
,
411 ly_symbol2scm ("padding"));
412 Page_layout_problem::read_spacing_spec (between_scores_spec
,
413 &score_system_padding_
,
414 ly_symbol2scm ("padding"));
415 Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec
,
416 &system_system_padding_
,
417 ly_symbol2scm ("padding"));
418 Page_layout_problem::read_spacing_spec (title_spec
,
419 &score_markup_padding_
,
420 ly_symbol2scm ("padding"));
422 Page_layout_problem::read_spacing_spec (between_scores_spec
,
423 &score_system_min_distance_
,
424 ly_symbol2scm ("minimum-distance"));
425 Page_layout_problem::read_spacing_spec (spacing_spec
,
426 &system_system_min_distance_
,
427 ly_symbol2scm ("minimum-distance"));
428 Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec
,
429 &system_system_min_distance_
,
430 ly_symbol2scm ("minimum-distance"));
431 Page_layout_problem::read_spacing_spec (title_spec
,
432 &score_markup_min_distance_
,
433 ly_symbol2scm ("minimum-distance"));
435 Interval first_line
= line_dimensions_int (pscore_
->layout (), 0);
436 Interval other_lines
= line_dimensions_int (pscore_
->layout (), 1);
437 /* do all the rod/spring problems */
438 breaks_
= pscore_
->get_break_indices ();
439 all_
= pscore_
->root_system ()->used_columns ();
440 lines_
.resize (breaks_
.size (), breaks_
.size (), Line_details ());
441 vector
<Real
> forces
= get_line_forces (all_
,
442 other_lines
.length (),
443 other_lines
.length () - first_line
.length (),
445 for (vsize i
= 0; i
+ 1 < breaks_
.size (); i
++)
447 for (vsize j
= i
+ 1; j
< breaks_
.size (); j
++)
449 bool last
= j
== breaks_
.size () - 1;
450 bool ragged
= ragged_right_
|| (last
&& ragged_last_
);
451 Line_details
&line
= lines_
.at (j
, i
);
453 line
.force_
= forces
[i
*breaks_
.size () + j
];
454 if (ragged
&& last
&& !isinf (line
.force_
))
455 line
.force_
= (line
.force_
< 0 && j
> i
+ 1) ? infinity_f
: 0;
456 if (isinf (line
.force_
))
459 fill_line_details (&line
, i
, j
);
463 /* work out all the starting indices */
464 for (vsize i
= 0; i
< start_
.size (); i
++)
467 for (j
= 0; j
+ 1 < breaks_
.size () && breaks_
[j
] < start_
[i
]; j
++)
469 starting_breakpoints_
.push_back (j
);
470 start_
[i
] = breaks_
[j
];
472 state_
.resize (start_
.size ());
476 Fills out all of the information contained in a Line_details,
477 except for information about horizontal spacing.
480 Constrained_breaking::fill_line_details (Line_details
*const out
, vsize start
, vsize end
)
482 int start_rank
= Paper_column::get_rank (all_
[breaks_
[start
]]);
483 int end_rank
= Paper_column::get_rank (all_
[breaks_
[end
]]);
484 System
*sys
= pscore_
->root_system ();
485 Interval begin_of_line_extent
= sys
->begin_of_line_pure_height (start_rank
, end_rank
);
486 Interval rest_of_line_extent
= sys
->rest_of_line_pure_height (start_rank
, end_rank
);
487 bool last
= (end
== breaks_
.size () - 1);
489 Grob
*c
= all_
[breaks_
[end
]];
490 out
->last_column_
= c
;
491 out
->break_penalty_
= robust_scm2double (c
->get_property ("line-break-penalty"), 0);
492 out
->page_penalty_
= robust_scm2double (c
->get_property ("page-break-penalty"), 0);
493 out
->turn_penalty_
= robust_scm2double (c
->get_property ("page-turn-penalty"), 0);
494 out
->break_permission_
= c
->get_property ("line-break-permission");
495 out
->page_permission_
= c
->get_property ("page-break-permission");
496 out
->turn_permission_
= c
->get_property ("page-turn-permission");
498 /* turn permission should always be stricter than page permission
499 and page permission should always be stricter than line permission */
500 out
->page_permission_
= min_permission (out
->break_permission_
,
501 out
->page_permission_
);
502 out
->turn_permission_
= min_permission (out
->page_permission_
,
503 out
->turn_permission_
);
505 begin_of_line_extent
= (begin_of_line_extent
.is_empty ()
506 || isnan (begin_of_line_extent
[LEFT
])
507 || isnan (begin_of_line_extent
[RIGHT
]))
508 ? Interval (0, 0) : begin_of_line_extent
;
509 rest_of_line_extent
= (rest_of_line_extent
.is_empty ()
510 || isnan (rest_of_line_extent
[LEFT
])
511 || isnan (rest_of_line_extent
[RIGHT
]))
512 ? Interval (0, 0) : rest_of_line_extent
;
513 out
->shape_
= Line_shape (begin_of_line_extent
, rest_of_line_extent
);
514 out
->padding_
= last
? score_system_padding_
: system_system_padding_
;
515 out
->title_padding_
= score_markup_padding_
;
516 out
->min_distance_
= last
? score_system_min_distance_
: system_system_min_distance_
;
517 out
->title_min_distance_
= score_markup_min_distance_
;
518 out
->space_
= system_system_space_
;
519 out
->title_space_
= system_markup_space_
;
520 out
->inverse_hooke_
= out
->full_height () + system_system_space_
;
522 out
->footnotes_
= sys
->get_footnotes_in_range (start_rank
, end_rank
);
524 out
->refpoint_extent_
= sys
->pure_refpoint_extent (start_rank
, end_rank
);
525 if (out
->refpoint_extent_
.is_empty ())
526 out
->refpoint_extent_
= Interval (0, 0);
530 Constrained_breaking::combine_demerits (Real force
, Real prev_force
)
533 return force
* force
;
535 return force
* force
+ (prev_force
- force
) * (prev_force
- force
);
538 Line_details::Line_details (Prob
*pb
, Output_def
*paper
)
540 SCM spec
= paper
->c_variable ("markup-system-spacing");
541 SCM title_spec
= paper
->c_variable ("markup-markup-spacing");
545 title_min_distance_
= 0;
548 Page_layout_problem::read_spacing_spec (spec
, &space_
, ly_symbol2scm ("basic-distance"));
549 Page_layout_problem::read_spacing_spec (title_spec
, &title_space_
, ly_symbol2scm ("basic-distance"));
550 Page_layout_problem::read_spacing_spec (spec
, &padding_
, ly_symbol2scm ("padding"));
551 Page_layout_problem::read_spacing_spec (title_spec
, &title_padding_
, ly_symbol2scm ("padding"));
552 Page_layout_problem::read_spacing_spec (spec
, &min_distance_
, ly_symbol2scm ("minimum-distance"));
553 Page_layout_problem::read_spacing_spec (title_spec
, &title_min_distance_
, ly_symbol2scm ("minimum-distance"));
555 SCM footnotes
= pb
->get_property ("footnotes");
556 if (scm_is_pair (footnotes
))
557 for (SCM s
= footnotes
; scm_is_pair (s
); s
= scm_cdr (s
))
558 footnotes_
.push_back (unsmob_stencil (scm_car (s
)));
562 Interval stencil_extent
= unsmob_stencil (pb
->get_property ("stencil"))->extent (Y_AXIS
);
563 shape_
= Line_shape (stencil_extent
, stencil_extent
); // pretend it goes all the way across
566 inverse_hooke_
= 1.0;
567 break_permission_
= ly_symbol2scm ("allow");
568 page_permission_
= pb
->get_property ("page-break-permission");
569 turn_permission_
= pb
->get_property ("page-turn-permission");
571 page_penalty_
= robust_scm2double (pb
->get_property ("page-break-penalty"), 0);
572 turn_penalty_
= robust_scm2double (pb
->get_property ("page-turn-penalty"), 0);
573 title_
= to_boolean (pb
->get_property ("is-title"));
574 compressed_lines_count_
= 1;
575 compressed_nontitle_lines_count_
= title_
? 0 : 1;
576 SCM last_scm
= pb
->get_property ("last-markup-line");
577 last_markup_line_
= to_boolean (last_scm
);
578 SCM first_scm
= pb
->get_property ("first-markup-line");
579 first_markup_line_
= to_boolean (first_scm
);
580 tight_spacing_
= to_boolean (pb
->get_property ("tight-spacing"));
581 refpoint_extent_
= Interval (0, 0);
585 Line_details::full_height () const
588 ret
.unite(shape_
.begin_
);
589 ret
.unite(shape_
.rest_
);
594 Line_details::tallness () const
600 Line_details::spring_length (Line_details
const &next_line
) const
602 // space_ measures the spring which goes from the bottom refpoint
603 // of this to the top refpoint of next_line. We want to return
604 // the stretchable space between the bottom of this's extent to
605 // the top of next_line's extent.
606 Real refpoint_dist
= tallness_
+ refpoint_extent_
[DOWN
] - next_line
.refpoint_extent_
[UP
];
607 Real space
= next_line
.title_
? title_space_
: space_
;
608 return max (0.0, space
- refpoint_dist
);
611 Line_shape::Line_shape (Interval begin
, Interval rest
)
618 Line_shape::piggyback (Line_shape mount
, Real padding
) const
620 Real elevation
= max (begin_
[UP
]-mount
.begin_
[DOWN
], rest_
[UP
]-mount
.rest_
[DOWN
]);
621 Interval begin
= Interval (begin_
[DOWN
], elevation
+ mount
.begin_
[UP
] + padding
);
622 Interval rest
= Interval (rest_
[DOWN
], elevation
+ mount
.rest_
[UP
] + padding
);
623 return Line_shape (begin
, rest
);