2 constrained-breaking.cc -- implement a line breaker that
3 support limits on the number of systems
5 source file of the GNU LilyPond music typesetter
7 (c) 2006--2009 Joe Neeman <joeneeman@gmail.com>
10 #include "constrained-breaking.hh"
12 #include "international.hh"
14 #include "output-def.hh"
15 #include "page-layout-problem.hh"
16 #include "paper-column.hh"
17 #include "paper-score.hh"
18 #include "simple-spacer.hh"
23 We use the following optimal substructure. Let W (A) be our weight function.
25 Let A_{k, n} = (a_{k, n, 1}, ... a_{k, n, k}) be the optimal set of line breaks
26 for k systems and n potential breakpoints. a_{k, n, k} = n (it is the end of
29 Then A_{k+1, m} is contructed from
30 min_ {k < j < m} ( W (A_{k, j} :: m) )
31 where by A::m we denote appending m to the list A
35 The above algorithm makes it easy to end at a point before the end of the
36 score (just find A_{k, m} for some m < breaks_.size () - 1). However, we must
37 add information for starting at a point after the beginning. One constructor
38 allows the specification of a list of starting columns, start_. We then have
39 start_.size () different solution arrays. state_[i] is the array for the
40 solution starting at column number start_[i].
42 The indices "start" and "end" refer to the index in the start_ array of the
43 desired starting and ending columns.
45 each solution array looks like
46 a_{1,1,1} a_{2,1,2} a_{3,1,3} . . .
47 X a_{2,2,2} a_{3,2,3} . . .
51 where the X's mark invalid solutions (can't have more systems than
52 breakpoints). Note that each value is of the form a_{x, n, x}. This is because
53 a breakpoint of the form a_{x, n, x-1} will also be called a_{x-1, m, x-1} for
54 some m < n. Each cell in the array stores the value of its m (ie. the
55 ending breakpoint of the previous line) as "prev_".
57 For finding A_{sys, brk}, let "me" be the (sys_count, brk) cell in our
58 solution array (state_[start][sys * rank + brk]).
60 Then A_{sys, brk} = A_{sys - 1, me.prev_} :: me
64 start and sys here are indexed from 0.
65 brk is indexed from starting_breakpoints_[start]
66 (for brk, starting_breakpoints_[start] is the beginning
67 of the piece; the smallest value we should ever see here is
68 starting_breakpoints_[start] + 1) */
70 Constrained_breaking::calc_subproblem (vsize start
, vsize sys
, vsize brk
)
72 assert (sys
< systems_
);
73 assert (start
< start_
.size ());
74 assert (brk
< breaks_
.size ());
76 bool found_something
= false;
77 vsize start_col
= starting_breakpoints_
[start
];
78 Matrix
<Constrained_break_node
> &st
= state_
[start
];
79 vsize max_index
= brk
- start_col
;
80 for (vsize j
=max_index
; j
-- > sys
;)
82 if (0 == sys
&& j
> 0)
83 continue; /* the first line cannot have its first break after the beginning */
85 Line_details
const &cur
= lines_
.at (brk
, j
+ start_col
);
86 if (isinf (cur
.force_
))
94 prev_f
= st
.at (j
, sys
-1).details_
.force_
;
95 prev_dem
= st
.at (j
, sys
-1).demerits_
;
100 Real dem
= combine_demerits (cur
.force_
, prev_f
) + prev_dem
+ cur
.break_penalty_
;
101 Constrained_break_node
&n
= st
.at (max_index
, sys
);
102 if (dem
< n
.demerits_
)
104 found_something
= true;
110 return found_something
;
115 Constrained_breaking::space_line (vsize i
, vsize j
)
117 bool ragged_right
= to_boolean (pscore_
->layout ()->c_variable ("ragged-right"));
118 bool ragged_last
= to_boolean (pscore_
->layout ()->c_variable ("ragged-last"));
119 Column_x_positions col
;
121 vector
<Grob
*> line (all_
.begin () + breaks_
[i
],
122 all_
.begin () + breaks_
[j
] + 1);
123 Interval line_dims
= line_dimensions_int (pscore_
->layout (), i
);
124 bool last
= j
== breaks_
.size () - 1;
125 bool ragged
= ragged_right
|| (last
&& ragged_last
);
127 /* As a special case, if there is only one line in the score and ragged-right
128 hasn't been specifically forbidden and the line is stretched, use
131 && lines_
.at (i
, j
).force_
>= 0
132 && !scm_is_bool (pscore_
->layout ()->c_variable ("ragged-right"))
133 && !scm_is_bool (pscore_
->layout ()->c_variable ("ragged-last")))
136 return get_line_configuration (line
, line_dims
[RIGHT
] - line_dims
[LEFT
], line_dims
[LEFT
], ragged
);
140 Constrained_breaking::resize (vsize systems
)
144 if (pscore_
&& systems_
> valid_systems_
)
146 for (vsize i
= 0; i
< state_
.size (); i
++)
147 state_
[i
].resize (breaks_
.size () - starting_breakpoints_
[i
], systems_
, Constrained_break_node ());
149 /* fill out the matrices */
150 for (vsize i
= 0; i
< state_
.size (); i
++)
151 for (vsize j
= valid_systems_
; j
< systems_
; j
++)
152 for (vsize k
= starting_breakpoints_
[i
] + j
+ 1; k
< breaks_
.size (); k
++)
153 if (!calc_subproblem (i
, j
, k
))
154 break; /* if we couldn't break this, it is too cramped already */
155 valid_systems_
= systems_
;
159 vector
<Column_x_positions
>
160 Constrained_breaking::solve (vsize start
, vsize end
, vsize sys_count
)
162 vsize start_brk
= starting_breakpoints_
[start
];
163 vsize end_brk
= prepare_solution (start
, end
, sys_count
);
165 Matrix
<Constrained_break_node
> const &st
= state_
[start
];
166 vector
<Column_x_positions
> ret
;
168 /* find the first solution that satisfies constraints */
169 for (vsize sys
= sys_count
-1; sys
!= VPOS
; sys
--)
171 for (vsize brk
= end_brk
; brk
!= VPOS
; brk
--)
173 if (!isinf (st
.at (brk
, sys
).details_
.force_
))
177 brk
= st
.at (brk
, sys
).prev_
;
179 warning (_ ("cannot find line breaking that satisfies constraints"));
180 ret
.push_back (space_line (brk
, end_brk
));
183 /* build up the good part of the solution */
184 for (vsize cur_sys
= sys
; cur_sys
!= VPOS
; cur_sys
--)
186 vsize prev_brk
= st
.at (brk
, cur_sys
).prev_
;
187 assert (brk
!= VPOS
);
188 ret
.push_back (space_line (prev_brk
+ start_brk
, brk
+ start_brk
));
196 /* if we get to here, just put everything on one line */
197 warning (_ ("cannot find line breaking that satisfies constraints"));
198 ret
.push_back (space_line (0, end_brk
));
202 vector
<Column_x_positions
>
203 Constrained_breaking::best_solution (vsize start
, vsize end
)
205 vsize min_systems
= min_system_count (start
, end
);
206 vsize max_systems
= max_system_count (start
, end
);
207 Real best_demerits
= infinity_f
;
208 vector
<Column_x_positions
> best_so_far
;
210 for (vsize i
= min_systems
; i
<= max_systems
; i
++)
212 vsize brk
= prepare_solution (start
, end
, i
);
213 Real dem
= state_
[start
].at (brk
, i
-1).demerits_
;
215 if (dem
< best_demerits
)
218 best_so_far
= solve (start
, end
, i
);
222 vector
<Column_x_positions
> cur
= solve (start
, end
, i
);
223 bool too_many_lines
= true;
225 for (vsize j
= 0; j
< cur
.size (); j
++)
226 if (cur
[j
].force_
< 0)
228 too_many_lines
= false;
235 if (best_so_far
.size ())
237 return solve (start
, end
, max_systems
);
240 std::vector
<Line_details
>
241 Constrained_breaking::line_details (vsize start
, vsize end
, vsize sys_count
)
243 vsize end_brk
= prepare_solution (start
, end
, sys_count
);
244 Matrix
<Constrained_break_node
> const &st
= state_
[start
];
245 vector
<Line_details
> ret
;
247 /* This loop structure is C&Ped from solve(). */
248 /* find the first solution that satisfies constraints */
249 for (vsize sys
= sys_count
-1; sys
!= VPOS
; sys
--)
251 for (vsize brk
= end_brk
; brk
!= VPOS
; brk
--)
253 if (!isinf (st
.at (brk
, sys
).details_
.force_
))
258 During initialize(), we only fill out a
259 Line_details for lines that are valid (ie. not too
260 long), otherwise line breaking becomes O(n^3).
261 In case sys_count is such that no valid solution
262 is found, we need to fill in the Line_details.
264 Line_details details
;
265 brk
= st
.at (brk
, sys
).prev_
;
267 fill_line_details (&details
, brk
, end_brk
);
268 ret
.push_back (details
);
271 /* build up the good part of the solution */
272 for (vsize cur_sys
= sys
; cur_sys
!= VPOS
; cur_sys
--)
274 vsize prev_brk
= st
.at (brk
, cur_sys
).prev_
;
275 assert (brk
!= VPOS
);
276 ret
.push_back (st
.at (brk
, cur_sys
).details_
);
285 /* if we get to here, just put everything on one line */
286 Line_details details
;
287 fill_line_details (&details
, 0, end_brk
);
288 ret
.push_back (details
);
293 Constrained_breaking::min_system_count (vsize start
, vsize end
)
296 vsize brk
= prepare_solution (start
, end
, 1);
297 vsize rank
= breaks_
.size () - starting_breakpoints_
[start
];
298 Matrix
<Constrained_break_node
> const &st
= state_
[start
];
300 /* sys_count < rank : rank is the # of breakpoints, we can't have more systems */
301 for (sys_count
= 0; sys_count
< rank
; sys_count
++)
303 if (sys_count
>= valid_systems_
)
305 resize (sys_count
+ 3);
307 if (!isinf (st
.at (brk
, sys_count
).details_
.force_
))
308 return sys_count
+ 1;
310 /* no possible breaks satisfy constraints */
315 Constrained_breaking::max_system_count (vsize start
, vsize end
)
317 vsize brk
= (end
>= start_
.size ()) ? breaks_
.size () - 1 : starting_breakpoints_
[end
];
318 return brk
- starting_breakpoints_
[start
];
322 Constrained_breaking::prepare_solution (vsize start
, vsize end
, vsize sys_count
)
324 assert (start
< start_
.size () && (end
== VPOS
|| end
<= start_
.size ()));
325 assert (start
< end
);
328 if (end
== start_
.size ())
332 brk
= end
== VPOS
? breaks_
.size () - 1 : starting_breakpoints_
[end
];
333 brk
-= starting_breakpoints_
[start
];
337 Constrained_breaking::Constrained_breaking (Paper_score
*ps
)
339 valid_systems_
= systems_
= 0;
340 start_
.push_back (0);
345 Constrained_breaking::Constrained_breaking (Paper_score
*ps
, vector
<vsize
> const &start
)
348 valid_systems_
= systems_
= 0;
354 min_permission (SCM perm1
, SCM perm2
)
356 if (perm1
== ly_symbol2scm ("force"))
358 if (perm1
== ly_symbol2scm ("allow")
359 && perm2
!= ly_symbol2scm ("force"))
364 /* find the forces for all possible lines and cache ragged_ and ragged_right_ */
366 Constrained_breaking::initialize ()
371 ragged_right_
= to_boolean (pscore_
->layout ()->c_variable ("ragged-right"));
372 ragged_last_
= to_boolean (pscore_
->layout ()->c_variable ("ragged-last"));
373 /* NOTE: currently, we aren't using the space_ field of a
374 Line_details for anything. That's because the approximations
375 used for scoring a page configuration don't actually space things
376 properly (for speed reasong) using springs anchored at the staff
377 refpoints. Rather, the "space" is placed between the extent
378 boxes. To get a good result, therefore, the "space" value for
379 page breaking needs to be much smaller than the "space" value for
380 page layout. Currently, we just make it zero always.
382 between_system_space_
= 0;
383 between_system_padding_
= 0;
385 Output_def
*l
= pscore_
->layout ();
387 SCM spacing_spec
= l
->c_variable ("between-system-spacing");
388 SCM page_breaking_spacing_spec
= l
->c_variable ("page-breaking-between-system-spacing");
389 Page_layout_problem::read_spacing_spec (spacing_spec
,
390 &between_system_padding_
,
391 ly_symbol2scm ("padding"));
392 Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec
,
393 &between_system_padding_
,
394 ly_symbol2scm ("padding"));
396 Interval first_line
= line_dimensions_int (pscore_
->layout (), 0);
397 Interval other_lines
= line_dimensions_int (pscore_
->layout (), 1);
398 /* do all the rod/spring problems */
399 breaks_
= pscore_
->find_break_indices ();
400 all_
= pscore_
->root_system ()->used_columns ();
401 lines_
.resize (breaks_
.size (), breaks_
.size (), Line_details ());
402 vector
<Real
> forces
= get_line_forces (all_
,
403 other_lines
.length (),
404 other_lines
.length () - first_line
.length (),
406 for (vsize i
= 0; i
+ 1 < breaks_
.size (); i
++)
408 for (vsize j
= i
+ 1; j
< breaks_
.size (); j
++)
410 bool last
= j
== breaks_
.size () - 1;
411 bool ragged
= ragged_right_
|| (last
&& ragged_last_
);
412 Line_details
&line
= lines_
.at (j
, i
);
414 line
.force_
= forces
[i
*breaks_
.size () + j
];
415 if (ragged
&& last
&& !isinf (line
.force_
))
416 line
.force_
= (line
.force_
< 0 && j
> i
+ 1) ? infinity_f
: 0;
417 if (isinf (line
.force_
))
420 fill_line_details (&line
, i
, j
);
424 /* work out all the starting indices */
425 for (vsize i
= 0; i
< start_
.size (); i
++)
428 for (j
= 0; j
+ 1 < breaks_
.size () && breaks_
[j
] < start_
[i
]; j
++)
430 starting_breakpoints_
.push_back (j
);
431 start_
[i
] = breaks_
[j
];
433 state_
.resize (start_
.size ());
437 Fills out all of the information contained in a Line_details,
438 except for information about horizontal spacing.
441 Constrained_breaking::fill_line_details (Line_details
*const out
, vsize start
, vsize end
)
443 int start_rank
= Paper_column::get_rank (all_
[breaks_
[start
]]);
444 int end_rank
= Paper_column::get_rank (all_
[breaks_
[end
]]);
445 System
*sys
= pscore_
->root_system ();
446 Interval extent
= sys
->pure_height (sys
, start_rank
, end_rank
);
448 Grob
*c
= all_
[breaks_
[end
]];
449 out
->last_column_
= c
;
450 out
->break_penalty_
= robust_scm2double (c
->get_property ("line-break-penalty"), 0);
451 out
->page_penalty_
= robust_scm2double (c
->get_property ("page-break-penalty"), 0);
452 out
->turn_penalty_
= robust_scm2double (c
->get_property ("page-turn-penalty"), 0);
453 out
->break_permission_
= c
->get_property ("line-break-permission");
454 out
->page_permission_
= c
->get_property ("page-break-permission");
455 out
->turn_permission_
= c
->get_property ("page-turn-permission");
457 /* turn permission should always be stricter than page permission
458 and page permission should always be stricter than line permission */
459 out
->page_permission_
= min_permission (out
->break_permission_
,
460 out
->page_permission_
);
461 out
->turn_permission_
= min_permission (out
->page_permission_
,
462 out
->turn_permission_
);
464 // TODO: see the hack regarding begin_of_line and
465 // rest_of_line extents in align-interface. Perhaps we
466 // should do the same thing here so that the effect extends
467 // between systems as well as within systems. It isn't as
468 // crucial here, however, because the effect is largest when
469 // dealing with large systems.
470 out
->extent_
= (extent
.is_empty ()
471 || isnan (extent
[LEFT
])
472 || isnan (extent
[RIGHT
]))
473 ? Interval (0, 0) : extent
;
474 out
->padding_
= between_system_padding_
;
475 out
->space_
= between_system_space_
;
476 out
->inverse_hooke_
= extent
.length () + between_system_space_
;
480 Constrained_breaking::combine_demerits (Real force
, Real prev_force
)
483 return force
* force
;
485 return force
* force
+ (prev_force
- force
) * (prev_force
- force
);