2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1999--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
7 - add support for different stretch/shrink constants?
9 LilyPond is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
14 LilyPond is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
25 #include "column-x-positions.hh"
26 #include "dimensions.hh"
27 #include "international.hh"
28 #include "libc-extension.hh" // isinf
29 #include "paper-column.hh"
30 #include "simple-spacer.hh"
31 #include "spaceable-grob.hh"
36 A simple spacing constraint solver. The approach:
38 Stretch the line uniformly until none of the constraints (rods)
39 block. It then is very wide.
41 Compress until the next constraint blocks,
43 Mark the springs over the constrained part to be non-active.
45 Repeat with the smaller set of non-active constraints, until all
46 constraints blocked, or until the line is as short as desired.
48 This is much simpler, and much much faster than full scale
49 Constrained QP. On the other hand, a situation like this will not
50 be typeset as dense as possible, because
53 veryveryverylongsyllable2 veryveryverylongsyllable2
54 " "4 veryveryverylongsyllable2 syllable4
57 can be further compressed to
61 veryveryverylongsyllable2 veryveryverylongsyllable2
62 " "4 veryveryverylongsyllable2 syllable4
65 Perhaps this is not a bad thing, because the 1st looks better anyway. */
68 positive force = expanding, negative force = compressing.
71 Simple_spacer::Simple_spacer ()
80 Simple_spacer::force () const
86 Simple_spacer::fits () const
92 Simple_spacer::rod_force (int l, int r, Real dist)
94 Real d = range_ideal_len (l, r);
95 Real c = range_stiffness (l, r, dist > d);
96 Real block_stretch = dist - d;
98 if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
100 return c * block_stretch;
104 Simple_spacer::add_rod (int l, int r, Real dist)
106 if (isinf (dist) || isnan (dist))
108 programming_error ("ignoring weird minimum distance");
112 Real block_force = rod_force (l, r, dist);
114 if (isinf (block_force))
116 Real spring_dist = range_ideal_len (l, r);
117 if (spring_dist < dist)
118 for (int i = l; i < r; i++)
121 springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
123 springs_[i].set_distance (dist / (r - l));
128 force_ = max (force_, block_force);
129 for (int i = l; i < r; i++)
130 springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
134 Simple_spacer::range_ideal_len (int l, int r) const
137 for (int i = l; i < r; i++)
138 d += springs_[i].distance ();
143 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
146 for (int i = l; i < r; i++)
147 den += stretch ? springs_[i].inverse_stretch_strength ()
148 : springs_[i].inverse_compress_strength ();
154 Simple_spacer::configuration_length (Real force) const
157 for (vsize i = 0; i < springs_.size (); i++)
158 l += springs_[i].length (force);
164 Simple_spacer::set_force (Real force)
170 Simple_spacer::solve (Real line_len, bool ragged)
172 Real conf = configuration_length (force_);
175 line_len_ = line_len;
176 if (conf < line_len_)
177 force_ = expand_line ();
178 else if (conf > line_len_)
179 force_ = compress_line ();
181 if (ragged && force_ < 0)
186 Simple_spacer::expand_line ()
188 double inv_hooke = 0;
189 double cur_len = configuration_length (force_);
192 for (vsize i = 0; i < springs_.size (); i++)
193 inv_hooke += springs_[i].inverse_stretch_strength ();
195 if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
196 inv_hooke = 1e-6; /* then report a very large stretching force */
198 if (cur_len > (1 + 1e-6) * line_len_)
199 programming_error ("misuse of expand_line");
200 return (line_len_ - cur_len) / inv_hooke + force_;
204 Simple_spacer::compress_line ()
206 double cur_len = configuration_length (force_);
207 double cur_force = force_;
208 bool compressed = false;
210 /* just because we are in compress_line () doesn't mean that the line
211 will actually be compressed (as in, a negative force) because
212 we start out with a stretched line. Here, we check whether we
213 will be compressed or stretched (so we know which spring constant to use) */
214 if (configuration_length (0.0) > line_len_)
217 cur_len = configuration_length (0.0);
223 if (line_len_ > (1 + 1e-6) * cur_len)
224 programming_error ("misuse of compress_line");
225 vector<Spring> sorted_springs = springs_;
226 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
228 /* inv_hooke is the total flexibility of currently-active springs */
229 double inv_hooke = 0;
230 vsize i = sorted_springs.size ();
231 for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
232 inv_hooke += compressed
233 ? sorted_springs[i - 1].inverse_compress_strength ()
234 : sorted_springs[i - 1].inverse_stretch_strength ();
235 /* i now indexes the first active spring, so */
236 for (; i < sorted_springs.size (); i++)
238 Spring sp = sorted_springs[i];
240 if (isinf (sp.blocking_force ()))
243 double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
244 if (cur_len - block_dist < line_len_)
246 cur_force += (line_len_ - cur_len) / inv_hooke;
252 if (fabs (configuration_length (cur_force) - cur_len) > 1e-6 * cur_len)
253 programming_error (to_string ("mis-predicted force, %.6f ~= %.6f",
254 cur_len, configuration_length(cur_force)));
258 cur_len -= block_dist;
259 inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
260 cur_force = sp.blocking_force ();
268 Simple_spacer::add_spring (Spring const &sp)
270 force_ = max (force_, sp.blocking_force ());
271 springs_.push_back (sp);
275 Simple_spacer::spring_positions () const
280 for (vsize i = 0; i < springs_.size (); i++)
281 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
286 Simple_spacer::force_penalty (bool ragged) const
288 /* If we are ragged-right, we don't want to penalise according to the force,
289 but according to the amount of whitespace that is present after the end
292 return max (0.0, line_len_ - configuration_length (0.0));
294 /* Use a convex compression penalty. */
296 return f - (f < 0 ? f * f * f * f * 2 : 0);
299 /****************************************************************/
301 struct Rod_description
306 bool operator < (const Rod_description r)
317 Rod_description (vsize r, Real d)
324 struct Column_description
326 vector<Rod_description> rods_;
327 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
331 SCM break_permission_;
332 Interval keep_inside_line_;
334 Column_description ()
336 break_permission_ = SCM_EOL;
343 return (scm_is_pair (g->get_object ("between-cols")));
347 maybe_find_prebroken_piece (Grob *g, Direction d)
349 Grob *ret = dynamic_cast<Item *> (g)->find_prebroken_piece (d);
356 next_spaceable_column (vector<Grob *> const &list, vsize starting)
358 for (vsize i = starting + 1; i < list.size (); i++)
359 if (!is_loose (list[i]))
364 static Column_description
365 get_column_description (vector<Grob *> const &cols, vsize col_index, bool line_starter)
367 Grob *col = cols[col_index];
369 col = maybe_find_prebroken_piece (col, RIGHT);
371 Column_description description;
372 Grob *next_col = next_spaceable_column (cols, col_index);
374 description.spring_ = Spaceable_grob::get_spring (col, next_col);
376 if (col_index + 1 < cols.size ())
378 Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
380 description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
383 for (SCM s = Spaceable_grob::get_minimum_distances (col);
384 scm_is_pair (s); s = scm_cdr (s))
386 Grob *other = unsmob<Grob> (scm_caar (s));
387 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
390 if (cols[j] == other)
391 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
392 else /* it must end at the LEFT prebroken_piece */
393 /* see Spanner::set_spacing_rods for more comments on how
394 to deal with situations where we don't know if we're
395 ending yet on the left prebroken piece */
396 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
400 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
401 description.keep_inside_line_ = col->extent (col, X_AXIS);
403 description.break_permission_ = col->get_property ("line-break-permission");
408 get_line_forces (vector<Grob *> const &columns,
409 Real line_len, Real indent, bool ragged)
411 vector<vsize> breaks;
413 vector<Grob *> non_loose;
414 vector<Column_description> cols;
415 SCM force_break = ly_symbol2scm ("force");
417 for (vsize i = 0; i < columns.size (); i++)
418 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
419 non_loose.push_back (columns[i]);
422 breaks.push_back (0);
423 cols.push_back (Column_description ());
424 for (vsize i = 1; i + 1 < non_loose.size (); i++)
426 if (Paper_column::is_breakable (non_loose[i]))
427 breaks.push_back (cols.size ());
429 cols.push_back (get_column_description (non_loose, i, false));
431 breaks.push_back (cols.size ());
432 force.resize (breaks.size () * breaks.size (), infinity_f);
434 for (vsize b = 0; b + 1 < breaks.size (); b++)
436 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
437 vsize st = breaks[b];
439 for (vsize c = b + 1; c < breaks.size (); c++)
441 vsize end = breaks[c];
442 Simple_spacer spacer;
444 for (vsize i = breaks[b]; i < end - 1; i++)
445 spacer.add_spring (cols[i].spring_);
446 spacer.add_spring (cols[end - 1].end_spring_);
448 for (vsize i = breaks[b]; i < end; i++)
450 for (vsize r = 0; r < cols[i].rods_.size (); r++)
451 if (cols[i].rods_[r].r_ < end)
452 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
453 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
454 if (cols[i].end_rods_[r].r_ == end)
455 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
456 if (!cols[i].keep_inside_line_.is_empty ())
458 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
459 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
462 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
463 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
468 force[b * breaks.size () + c] = -200000;
470 force[b * breaks.size () + c] = infinity_f;
473 if (end < cols.size () && scm_is_eq (cols[end].break_permission_, force_break))
481 get_line_configuration (vector<Grob *> const &columns,
486 vector<Column_description> cols;
487 Simple_spacer spacer;
488 Column_x_positions ret;
490 ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
491 for (vsize i = 1; i + 1 < columns.size (); i++)
493 if (is_loose (columns[i]))
494 ret.loose_cols_.push_back (columns[i]);
496 ret.cols_.push_back (columns[i]);
498 ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
500 /* since we've already put our line-ending column in the column list, we can ignore
501 the end_XXX_ fields of our column_description */
502 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
504 cols.push_back (get_column_description (ret.cols_, i, i == 0));
505 spacer.add_spring (cols[i].spring_);
507 for (vsize i = 0; i < cols.size (); i++)
509 for (vsize r = 0; r < cols[i].rods_.size (); r++)
510 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
512 if (!cols[i].keep_inside_line_.is_empty ())
514 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
515 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
519 spacer.solve (line_len, ragged);
520 ret.force_ = spacer.force_penalty (ragged);
522 ret.config_ = spacer.spring_positions ();
523 for (vsize i = 0; i < ret.config_.size (); i++)
524 ret.config_[i] += indent;
526 ret.satisfies_constraints_ = spacer.fits ();
529 Check if breaking constraints are met.
531 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
533 SCM p = ret.cols_[i]->get_property ("line-break-permission");
534 if (scm_is_eq (p, ly_symbol2scm ("force")))
535 ret.satisfies_constraints_ = false;