]> git.donarmstrong.com Git - lilypond.git/blob - lily/constrained-breaking.cc
Doc-es: Update of Input.
[lilypond.git] / lily / constrained-breaking.cc
1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3
4   Copyright (C) 2006--2009 Joe Neeman <joeneeman@gmail.com>
5
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.
10
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.
15
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/>.
18 */
19
20 #include "constrained-breaking.hh"
21
22 #include "international.hh"
23 #include "main.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"
29 #include "system.hh"
30 #include "warn.hh"
31
32 /*
33   We use the following optimal substructure. Let W (A) be our weight function.
34
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
37   the piece)
38
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
42
43   Indices in the code:
44
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].
51
52   The indices "start" and "end" refer to the index in the start_ array of the
53   desired starting and ending columns.
54
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} . . .
58        X         X     a_{3,3,3} . . .
59        .         .         .     .
60        .         .         .       .
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_".
66
67   For finding A_{sys, brk}, let "me" be the (sys_count, brk) cell in our
68   solution array (state_[start][sys * rank + brk]).
69
70   Then A_{sys, brk} = A_{sys - 1, me.prev_} :: me
71 */
72
73 /*
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) */
79 bool
80 Constrained_breaking::calc_subproblem (vsize start, vsize sys, vsize brk)
81 {
82   assert (sys < systems_);
83   assert (start < start_.size ());
84   assert (brk < breaks_.size ());
85
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;)
91     {
92       if (0 == sys && j > 0)
93         continue; /* the first line cannot have its first break after the beginning */
94
95       Line_details const &cur = lines_.at (brk, j + start_col);
96       if (isinf (cur.force_))
97         break;
98
99       Real prev_f = 0;
100       Real prev_dem = 0;
101
102       if (sys > 0)
103         {
104           prev_f = st.at (j, sys-1).details_.force_;
105           prev_dem = st.at (j, sys-1).demerits_;
106         }
107       if (isinf (prev_dem))
108         continue;
109
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_)
113         {
114           found_something = true;
115           n.demerits_ = dem;
116           n.details_ = cur;
117           n.prev_ = j;
118         }
119     }
120   return found_something;
121 }
122
123
124 Column_x_positions
125 Constrained_breaking::space_line (vsize i, vsize j)
126 {
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;
130
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);
136
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
139      ragged spacing. */
140   if (last && i == 0
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")))
144     ragged = true;
145
146   return get_line_configuration (line, line_dims[RIGHT] - line_dims[LEFT], line_dims[LEFT], ragged);
147 }
148
149 void
150 Constrained_breaking::resize (vsize systems)
151 {
152   systems_ = systems;
153
154   if (pscore_ && systems_ > valid_systems_)
155     {
156       for (vsize i = 0; i < state_.size (); i++)
157         state_[i].resize (breaks_.size () - starting_breakpoints_[i], systems_, Constrained_break_node ());
158
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_;
166     }
167 }
168
169 vector<Column_x_positions>
170 Constrained_breaking::solve (vsize start, vsize end, vsize sys_count)
171 {
172   vsize start_brk = starting_breakpoints_[start];
173   vsize end_brk = prepare_solution (start, end, sys_count);
174
175   Matrix<Constrained_break_node> const &st = state_[start];
176   vector<Column_x_positions> ret;
177
178   /* find the first solution that satisfies constraints */
179   for (vsize sys = sys_count-1; sys != VPOS; sys--)
180     {
181       for (vsize brk = end_brk; brk != VPOS; brk--)
182         {
183           if (!isinf (st.at (brk, sys).details_.force_))
184             {
185               if (brk != end_brk)
186                 {
187                   brk = st.at (brk, sys).prev_;
188                   sys--;
189                   warning (_ ("cannot find line breaking that satisfies constraints"));
190                   ret.push_back (space_line (brk, end_brk));
191                 }
192
193               /* build up the good part of the solution */
194               for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
195                 {
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));
199                   brk = prev_brk;
200                 }
201               reverse (ret);
202               return ret;
203             }
204         }
205     }
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));
209   return ret;
210 }
211
212 vector<Column_x_positions>
213 Constrained_breaking::best_solution (vsize start, vsize end)
214 {
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;
219
220   for (vsize i = min_systems; i <= max_systems; i++)
221     {
222       vsize brk = prepare_solution (start, end, i);
223       Real dem = state_[start].at (brk, i-1).demerits_;
224
225       if (dem < best_demerits)
226         {
227           best_demerits = dem;
228           best_so_far = solve (start, end, i);
229         }
230       else
231         {
232           vector<Column_x_positions> cur = solve (start, end, i);
233           bool too_many_lines = true;
234           
235           for (vsize j = 0; j < cur.size (); j++)
236             if (cur[j].force_ < 0)
237               {
238                 too_many_lines = false;
239                 break;
240               }
241           if (too_many_lines)
242             return best_so_far;
243         }
244     }
245   if (best_so_far.size ())
246     return best_so_far;
247   return solve (start, end, max_systems);
248 }
249
250 std::vector<Line_details>
251 Constrained_breaking::line_details (vsize start, vsize end, vsize sys_count)
252 {
253   vsize end_brk = prepare_solution (start, end, sys_count);
254   Matrix<Constrained_break_node> const &st = state_[start];
255   vector<Line_details> ret;
256
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--)
260     {
261       for (vsize brk = end_brk; brk != VPOS; brk--)
262         {
263           if (!isinf (st.at (brk, sys).details_.force_))
264             {
265               if (brk != end_brk)
266                 {
267                   /*
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.
273                   */
274                   Line_details details;
275                   brk = st.at (brk, sys).prev_;
276                   sys--;
277                   fill_line_details (&details, brk, end_brk);
278                   ret.push_back (details);
279                 }
280
281               /* build up the good part of the solution */
282               for (vsize cur_sys = sys; cur_sys != VPOS; cur_sys--)
283                 {
284                   vsize prev_brk = st.at (brk, cur_sys).prev_;
285                   assert (brk != VPOS);
286                   ret.push_back (st.at (brk, cur_sys).details_);
287                   brk = prev_brk;
288                 }
289               reverse (ret);
290               return ret;
291             }
292         }
293     }
294
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);
299   return ret;
300 }
301
302 int
303 Constrained_breaking::min_system_count (vsize start, vsize end)
304 {
305   vsize sys_count;
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];
309
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++)
312     {
313       if (sys_count >= valid_systems_)
314         {
315           resize (sys_count + 3);
316         }
317       if (!isinf (st.at (brk, sys_count).details_.force_))
318         return sys_count + 1;
319     }
320   /* no possible breaks satisfy constraints */
321   return 1;
322 }
323
324 int
325 Constrained_breaking::max_system_count (vsize start, vsize end)
326 {
327   vsize brk = (end >= start_.size ()) ? breaks_.size () - 1 : starting_breakpoints_[end];
328   return brk - starting_breakpoints_[start];
329 }
330
331 vsize
332 Constrained_breaking::prepare_solution (vsize start, vsize end, vsize sys_count)
333 {
334   assert (start < start_.size () && (end == VPOS || end <= start_.size ()));
335   assert (start < end);
336
337   resize (sys_count);
338   if (end == start_.size ())
339     end = VPOS;
340
341   vsize brk;
342   brk = end == VPOS ? breaks_.size () - 1 : starting_breakpoints_[end];
343   brk -= starting_breakpoints_[start];
344   return brk;
345 }
346
347 Constrained_breaking::Constrained_breaking (Paper_score *ps)
348 {
349   valid_systems_ = systems_ = 0;
350   start_.push_back (0);
351   pscore_ = ps;
352   initialize ();
353 }
354
355 Constrained_breaking::Constrained_breaking (Paper_score *ps, vector<vsize> const &start)
356   : start_ (start)
357 {
358   valid_systems_ = systems_ = 0;
359   pscore_ = ps;
360   initialize ();
361 }
362
363 static SCM
364 min_permission (SCM perm1, SCM perm2)
365 {
366   if (perm1 == ly_symbol2scm ("force"))
367     return perm2;
368   if (perm1 == ly_symbol2scm ("allow")
369      && perm2 != ly_symbol2scm ("force"))
370     return perm2;
371   return SCM_EOL;
372 }
373
374 /* find the forces for all possible lines and cache ragged_ and ragged_right_ */
375 void
376 Constrained_breaking::initialize ()
377 {
378   if (!pscore_)
379     return;
380
381   ragged_right_ = to_boolean (pscore_->layout ()->c_variable ("ragged-right"));
382   ragged_last_ = to_boolean (pscore_->layout ()->c_variable ("ragged-last"));
383   /* NOTE: currently, we aren't using the space_ field of a
384      Line_details for anything.  That's because the approximations
385      used for scoring a page configuration don't actually space things
386      properly (for speed reasong) using springs anchored at the staff
387      refpoints.  Rather, the "space" is placed between the extent
388      boxes.  To get a good result, therefore, the "space" value for
389      page breaking needs to be much smaller than the "space" value for
390      page layout.  Currently, we just make it zero always.
391   */
392   between_system_space_ = 0;
393   between_system_padding_ = 0;
394   before_title_padding_ = 0;
395
396   Output_def *l = pscore_->layout ();
397
398   SCM spacing_spec = l->c_variable ("between-system-spacing");
399   SCM title_spec = l->c_variable ("before-title-spacing");
400   SCM page_breaking_spacing_spec = l->c_variable ("page-breaking-between-system-spacing");
401   Page_layout_problem::read_spacing_spec (spacing_spec,
402                                           &between_system_padding_,
403                                           ly_symbol2scm ("padding"));
404   Page_layout_problem::read_spacing_spec (page_breaking_spacing_spec,
405                                           &between_system_padding_,
406                                           ly_symbol2scm ("padding"));
407   Page_layout_problem::read_spacing_spec (title_spec,
408                                           &before_title_padding_,
409                                           ly_symbol2scm ("padding"));
410
411   Interval first_line = line_dimensions_int (pscore_->layout (), 0);
412   Interval other_lines = line_dimensions_int (pscore_->layout (), 1);
413   /* do all the rod/spring problems */
414   breaks_ = pscore_->find_break_indices ();
415   all_ = pscore_->root_system ()->used_columns ();
416   lines_.resize (breaks_.size (), breaks_.size (), Line_details ());
417   vector<Real> forces = get_line_forces (all_,
418                                          other_lines.length (),
419                                          other_lines.length () - first_line.length (),
420                                          ragged_right_);
421   for (vsize i = 0; i + 1 < breaks_.size (); i++)
422     {
423       for (vsize j = i + 1; j < breaks_.size (); j++)
424         {
425           bool last = j == breaks_.size () - 1;
426           bool ragged = ragged_right_ || (last && ragged_last_);
427           Line_details &line = lines_.at (j, i);
428
429           line.force_ = forces[i*breaks_.size () + j];
430           if (ragged && last && !isinf (line.force_))
431             line.force_ = (line.force_ < 0 && j > i + 1) ? infinity_f : 0;
432           if (isinf (line.force_))
433             break;
434
435           fill_line_details (&line, i, j);
436         }
437     }
438
439   /* work out all the starting indices */
440   for (vsize i = 0; i < start_.size (); i++)
441     {
442       vsize j;
443       for (j = 0; j + 1 < breaks_.size () && breaks_[j] < start_[i]; j++)
444         ;
445       starting_breakpoints_.push_back (j);
446       start_[i] = breaks_[j];
447     }
448   state_.resize (start_.size ());
449 }
450
451 /*
452   Fills out all of the information contained in a Line_details,
453   except for information about horizontal spacing.
454 */
455 void
456 Constrained_breaking::fill_line_details (Line_details *const out, vsize start, vsize end)
457 {
458   int start_rank = Paper_column::get_rank (all_[breaks_[start]]);
459   int end_rank = Paper_column::get_rank (all_[breaks_[end]]);
460   System *sys = pscore_->root_system ();
461   Interval extent = sys->pure_height (sys, start_rank, end_rank);
462
463   Grob *c = all_[breaks_[end]];
464   out->last_column_ = c;
465   out->break_penalty_ = robust_scm2double (c->get_property ("line-break-penalty"), 0);
466   out->page_penalty_ = robust_scm2double (c->get_property ("page-break-penalty"), 0);
467   out->turn_penalty_ = robust_scm2double (c->get_property ("page-turn-penalty"), 0);
468   out->break_permission_ = c->get_property ("line-break-permission");
469   out->page_permission_ = c->get_property ("page-break-permission");
470   out->turn_permission_ = c->get_property ("page-turn-permission");
471
472   /* turn permission should always be stricter than page permission
473      and page permission should always be stricter than line permission */
474   out->page_permission_ = min_permission (out->break_permission_,
475                                           out->page_permission_);
476   out->turn_permission_ = min_permission (out->page_permission_,
477                                           out->turn_permission_);
478
479   // TODO: see the hack regarding begin_of_line and
480   // rest_of_line extents in align-interface.  Perhaps we
481   // should do the same thing here so that the effect extends
482   // between systems as well as within systems.  It isn't as
483   // crucial here, however, because the effect is largest when
484   // dealing with large systems.
485   out->extent_ = (extent.is_empty ()
486                   || isnan (extent[LEFT])
487                   || isnan (extent[RIGHT]))
488     ? Interval (0, 0) : extent;
489   out->padding_ = between_system_padding_;
490   out->title_padding_ = before_title_padding_;
491   out->space_ = between_system_space_;
492   out->inverse_hooke_ = extent.length () + between_system_space_;
493 }
494
495 Real
496 Constrained_breaking::combine_demerits (Real force, Real prev_force)
497 {
498   if (ragged_right_)
499     return force * force;
500
501   return force * force + (prev_force - force) * (prev_force - force);
502 }
503
504 Line_details::Line_details (Prob *pb, Output_def *paper)
505 {
506   SCM spec = paper->c_variable ("after-title-spacing");
507   SCM title_spec = paper->c_variable ("between-title-spacing");
508   padding_ = 0;
509   title_padding_ = 0;
510   Page_layout_problem::read_spacing_spec (spec, &padding_, ly_symbol2scm ("padding"));
511   Page_layout_problem::read_spacing_spec (title_spec, &title_padding_, ly_symbol2scm ("padding"));
512
513   last_column_ = 0;
514   force_ = 0;
515   extent_ = unsmob_stencil (pb->get_property ("stencil")) ->extent (Y_AXIS);
516   bottom_padding_ = 0;
517   space_ = robust_scm2double (pb->get_property ("next-space"), 1.0);
518   inverse_hooke_ = 1.0;
519   break_permission_ = ly_symbol2scm ("allow");
520   page_permission_ = pb->get_property ("page-break-permission");
521   turn_permission_ = pb->get_property ("page-turn-permission");
522   break_penalty_ = 0;
523   page_penalty_ = robust_scm2double (pb->get_property ("page-break-penalty"), 0);
524   turn_penalty_ = robust_scm2double (pb->get_property ("page-turn-penalty"), 0);
525   title_ = to_boolean (pb->get_property ("is-title"));
526   compressed_lines_count_ = 1;
527   compressed_nontitle_lines_count_ = title_ ? 0 : 1;
528   SCM last_scm  = pb->get_property ("last-markup-line");
529   last_markup_line_  = to_boolean (last_scm);
530   SCM first_scm = pb->get_property ("first-markup-line");
531   first_markup_line_ = to_boolean (first_scm);
532 }