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"
38 A simple spacing constraint solver. The approach:
40 Stretch the line uniformly until none of the constraints (rods)
41 block. It then is very wide.
43 Compress until the next constraint blocks,
45 Mark the springs over the constrained part to be non-active.
47 Repeat with the smaller set of non-active constraints, until all
48 constraints blocked, or until the line is as short as desired.
50 This is much simpler, and much much faster than full scale
51 Constrained QP. On the other hand, a situation like this will not
52 be typeset as dense as possible, because
55 veryveryverylongsyllable2 veryveryverylongsyllable2
56 " "4 veryveryverylongsyllable2 syllable4
59 can be further compressed to
63 veryveryverylongsyllable2 veryveryverylongsyllable2
64 " "4 veryveryverylongsyllable2 syllable4
67 Perhaps this is not a bad thing, because the 1st looks better anyway. */
70 positive force = expanding, negative force = compressing.
73 Simple_spacer::Simple_spacer ()
82 Simple_spacer::force () const
88 Simple_spacer::fits () const
94 Simple_spacer::rod_force (int l, int r, Real dist)
96 Real d = range_ideal_len (l, r);
97 Real c = range_stiffness (l, r, dist > d);
98 Real block_stretch = dist - d;
100 if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
102 return c * block_stretch;
106 Simple_spacer::add_rod (int l, int r, Real dist)
108 if (isinf (dist) || isnan (dist))
110 programming_error ("ignoring weird minimum distance");
114 Real block_force = rod_force (l, r, dist);
116 if (isinf (block_force))
118 Real spring_dist = range_ideal_len (l, r);
119 if (spring_dist < dist)
120 for (int i = l; i < r; i++)
123 springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
125 springs_[i].set_distance (dist / (r - l));
130 force_ = max (force_, block_force);
131 for (int i = l; i < r; i++)
132 springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
136 Simple_spacer::range_ideal_len (int l, int r) const
139 for (int i = l; i < r; i++)
140 d += springs_[i].distance ();
145 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
148 for (int i = l; i < r; i++)
149 den += stretch ? springs_[i].inverse_stretch_strength ()
150 : springs_[i].inverse_compress_strength ();
156 Simple_spacer::configuration_length (Real force) const
159 for (vsize i = 0; i < springs_.size (); i++)
160 l += springs_[i].length (force);
166 Simple_spacer::set_force (Real force)
172 Simple_spacer::solve (Real line_len, bool ragged)
174 Real conf = configuration_length (force_);
177 line_len_ = line_len;
178 if (conf < line_len_)
179 force_ = expand_line ();
180 else if (conf > line_len_)
181 force_ = compress_line ();
183 if (ragged && force_ < 0)
188 Simple_spacer::expand_line ()
190 double inv_hooke = 0;
191 double cur_len = configuration_length (force_);
194 for (vsize i = 0; i < springs_.size (); i++)
195 inv_hooke += springs_[i].inverse_stretch_strength ();
197 if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
198 inv_hooke = 1e-6; /* then report a very large stretching force */
200 if (cur_len > (1 + 1e-6) * line_len_)
201 programming_error ("misuse of expand_line");
202 return (line_len_ - cur_len) / inv_hooke + force_;
206 Simple_spacer::compress_line ()
208 double cur_len = configuration_length (force_);
209 double cur_force = force_;
210 bool compressed = false;
212 /* just because we are in compress_line () doesn't mean that the line
213 will actually be compressed (as in, a negative force) because
214 we start out with a stretched line. Here, we check whether we
215 will be compressed or stretched (so we know which spring constant to use) */
216 if (configuration_length (0.0) > line_len_)
219 cur_len = configuration_length (0.0);
225 if (line_len_ > (1 + 1e-6) * cur_len)
226 programming_error ("misuse of compress_line");
227 vector<Spring> sorted_springs = springs_;
228 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
230 /* inv_hooke is the total flexibility of currently-active springs */
231 double inv_hooke = 0;
232 vsize i = sorted_springs.size ();
233 for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
234 inv_hooke += compressed
235 ? sorted_springs[i - 1].inverse_compress_strength ()
236 : sorted_springs[i - 1].inverse_stretch_strength ();
237 /* i now indexes the first active spring, so */
238 for (; i < sorted_springs.size (); i++)
240 Spring sp = sorted_springs[i];
242 if (isinf (sp.blocking_force ()))
245 double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
246 if (cur_len - block_dist < line_len_)
248 cur_force += (line_len_ - cur_len) / inv_hooke;
254 if (fabs (configuration_length (cur_force) - cur_len) > 1e-6 * cur_len)
255 programming_error (to_string ("mis-predicted force, %.6f ~= %.6f",
256 cur_len, configuration_length(cur_force)));
260 cur_len -= block_dist;
261 inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
262 cur_force = sp.blocking_force ();
270 Simple_spacer::add_spring (Spring const &sp)
272 force_ = max (force_, sp.blocking_force ());
273 springs_.push_back (sp);
277 Simple_spacer::spring_positions () const
282 for (vsize i = 0; i < springs_.size (); i++)
283 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
288 Simple_spacer::force_penalty (bool ragged) const
290 /* If we are ragged-right, we don't want to penalise according to the force,
291 but according to the amount of whitespace that is present after the end
294 return max (0.0, line_len_ - configuration_length (0.0));
296 /* Use a convex compression penalty. */
298 return f - (f < 0 ? f * f * f * f * 2 : 0);
301 /****************************************************************/
303 struct Rod_description
308 bool operator < (const Rod_description r)
319 Rod_description (vsize r, Real d)
326 struct Column_description
328 vector<Rod_description> rods_;
329 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
333 SCM break_permission_;
334 Interval keep_inside_line_;
336 Column_description ()
338 break_permission_ = SCM_EOL;
345 return (scm_is_pair (g->get_object ("between-cols")));
349 maybe_find_prebroken_piece (Grob *g, Direction d)
351 Grob *ret = dynamic_cast<Item *> (g)->find_prebroken_piece (d);
358 next_spaceable_column (vector<Grob *> const &list, vsize starting)
360 for (vsize i = starting + 1; i < list.size (); i++)
361 if (!is_loose (list[i]))
366 static Column_description
367 get_column_description (vector<Grob *> const &cols, vsize col_index, bool line_starter)
369 Grob *col = cols[col_index];
371 col = maybe_find_prebroken_piece (col, RIGHT);
373 Column_description description;
374 Grob *next_col = next_spaceable_column (cols, col_index);
376 description.spring_ = Spaceable_grob::get_spring (col, next_col);
378 if (col_index + 1 < cols.size ())
380 Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
382 description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
385 for (SCM s = Spaceable_grob::get_minimum_distances (col);
386 scm_is_pair (s); s = scm_cdr (s))
388 Grob *other = unsmob<Grob> (scm_caar (s));
389 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
392 if (cols[j] == other)
393 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
394 else /* it must end at the LEFT prebroken_piece */
395 /* see Spanner::set_spacing_rods for more comments on how
396 to deal with situations where we don't know if we're
397 ending yet on the left prebroken piece */
398 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
402 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
403 description.keep_inside_line_ = col->extent (col, X_AXIS);
405 description.break_permission_ = col->get_property ("line-break-permission");
410 get_line_forces (vector<Grob *> const &columns,
411 Real line_len, Real indent, bool ragged)
413 vector<vsize> breaks;
415 vector<Grob *> non_loose;
416 vector<Column_description> cols;
417 SCM force_break = ly_symbol2scm ("force");
419 for (vsize i = 0; i < columns.size (); i++)
420 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
421 non_loose.push_back (columns[i]);
424 breaks.push_back (0);
425 cols.push_back (Column_description ());
426 for (vsize i = 1; i + 1 < non_loose.size (); i++)
428 if (Paper_column::is_breakable (non_loose[i]))
429 breaks.push_back (cols.size ());
431 cols.push_back (get_column_description (non_loose, i, false));
433 breaks.push_back (cols.size ());
434 force.resize (breaks.size () * breaks.size (), infinity_f);
436 for (vsize b = 0; b + 1 < breaks.size (); b++)
438 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
439 vsize st = breaks[b];
441 for (vsize c = b + 1; c < breaks.size (); c++)
443 vsize end = breaks[c];
444 Simple_spacer spacer;
446 for (vsize i = breaks[b]; i < end - 1; i++)
447 spacer.add_spring (cols[i].spring_);
448 spacer.add_spring (cols[end - 1].end_spring_);
450 for (vsize i = breaks[b]; i < end; i++)
452 for (vsize r = 0; r < cols[i].rods_.size (); r++)
453 if (cols[i].rods_[r].r_ < end)
454 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
455 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
456 if (cols[i].end_rods_[r].r_ == end)
457 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
458 if (!cols[i].keep_inside_line_.is_empty ())
460 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
461 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
464 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
465 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
470 force[b * breaks.size () + c] = -200000;
472 force[b * breaks.size () + c] = infinity_f;
475 if (end < cols.size () && cols[end].break_permission_ == force_break)
483 get_line_configuration (vector<Grob *> const &columns,
488 vector<Column_description> cols;
489 Simple_spacer spacer;
490 Column_x_positions ret;
492 ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
493 for (vsize i = 1; i + 1 < columns.size (); i++)
495 if (is_loose (columns[i]))
496 ret.loose_cols_.push_back (columns[i]);
498 ret.cols_.push_back (columns[i]);
500 ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
502 /* since we've already put our line-ending column in the column list, we can ignore
503 the end_XXX_ fields of our column_description */
504 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
506 cols.push_back (get_column_description (ret.cols_, i, i == 0));
507 spacer.add_spring (cols[i].spring_);
509 for (vsize i = 0; i < cols.size (); i++)
511 for (vsize r = 0; r < cols[i].rods_.size (); r++)
512 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
514 if (!cols[i].keep_inside_line_.is_empty ())
516 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
517 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
521 spacer.solve (line_len, ragged);
522 ret.force_ = spacer.force_penalty (ragged);
524 ret.config_ = spacer.spring_positions ();
525 for (vsize i = 0; i < ret.config_.size (); i++)
526 ret.config_[i] += indent;
528 ret.satisfies_constraints_ = spacer.fits ();
531 Check if breaking constraints are met.
533 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
535 SCM p = ret.cols_[i]->get_property ("line-break-permission");
536 if (scm_is_eq (p, ly_symbol2scm ("force")))
537 ret.satisfies_constraints_ = false;