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 assert (cur_len <= line_len_);
199 return (line_len_ - cur_len) / inv_hooke + force_;
203 Simple_spacer::compress_line ()
205 double cur_len = configuration_length (force_);
206 double cur_force = force_;
207 bool compressed = false;
209 /* just because we are in compress_line () doesn't mean that the line
210 will actually be compressed (as in, a negative force) because
211 we start out with a stretched line. Here, we check whether we
212 will be compressed or stretched (so we know which spring constant to use) */
213 if (configuration_length (0.0) > line_len_)
216 cur_len = configuration_length (0.0);
222 assert (line_len_ <= cur_len);
224 vector<Spring> sorted_springs = springs_;
225 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
227 /* inv_hooke is the total flexibility of currently-active springs */
228 double inv_hooke = 0;
229 vsize i = sorted_springs.size ();
230 for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
231 inv_hooke += compressed
232 ? sorted_springs[i - 1].inverse_compress_strength ()
233 : sorted_springs[i - 1].inverse_stretch_strength ();
234 /* i now indexes the first active spring, so */
235 for (; i < sorted_springs.size (); i++)
237 Spring sp = sorted_springs[i];
239 if (isinf (sp.blocking_force ()))
242 double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
243 if (cur_len - block_dist < line_len_)
245 cur_force += (line_len_ - cur_len) / inv_hooke;
251 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
255 cur_len -= block_dist;
256 inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
257 cur_force = sp.blocking_force ();
265 Simple_spacer::add_spring (Spring const &sp)
267 force_ = max (force_, sp.blocking_force ());
268 springs_.push_back (sp);
272 Simple_spacer::spring_positions () const
277 for (vsize i = 0; i < springs_.size (); i++)
278 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
283 Simple_spacer::force_penalty (bool ragged) const
285 /* If we are ragged-right, we don't want to penalise according to the force,
286 but according to the amount of whitespace that is present after the end
289 return max (0.0, line_len_ - configuration_length (0.0));
291 /* Use a convex compression penalty. */
293 return f - (f < 0 ? f * f * f * f * 2 : 0);
296 /****************************************************************/
298 struct Rod_description
303 bool operator < (const Rod_description r)
314 Rod_description (vsize r, Real d)
321 struct Column_description
323 vector<Rod_description> rods_;
324 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
328 SCM break_permission_;
329 Interval keep_inside_line_;
331 Column_description ()
333 break_permission_ = SCM_EOL;
340 return (scm_is_pair (g->get_object ("between-cols")));
344 maybe_find_prebroken_piece (Grob *g, Direction d)
346 Grob *ret = dynamic_cast<Item *> (g)->find_prebroken_piece (d);
353 next_spaceable_column (vector<Grob *> const &list, vsize starting)
355 for (vsize i = starting + 1; i < list.size (); i++)
356 if (!is_loose (list[i]))
361 static Column_description
362 get_column_description (vector<Grob *> const &cols, vsize col_index, bool line_starter)
364 Grob *col = cols[col_index];
366 col = maybe_find_prebroken_piece (col, RIGHT);
368 Column_description description;
369 Grob *next_col = next_spaceable_column (cols, col_index);
371 description.spring_ = Spaceable_grob::get_spring (col, next_col);
373 if (col_index + 1 < cols.size ())
375 Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
377 description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
380 for (SCM s = Spaceable_grob::get_minimum_distances (col);
381 scm_is_pair (s); s = scm_cdr (s))
383 Grob *other = unsmob<Grob> (scm_caar (s));
384 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
387 if (cols[j] == other)
388 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
389 else /* it must end at the LEFT prebroken_piece */
390 /* see Spanner::set_spacing_rods for more comments on how
391 to deal with situations where we don't know if we're
392 ending yet on the left prebroken piece */
393 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
397 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
398 description.keep_inside_line_ = col->extent (col, X_AXIS);
400 description.break_permission_ = col->get_property ("line-break-permission");
405 get_line_forces (vector<Grob *> const &columns,
406 Real line_len, Real indent, bool ragged)
408 vector<vsize> breaks;
410 vector<Grob *> non_loose;
411 vector<Column_description> cols;
412 SCM force_break = ly_symbol2scm ("force");
414 for (vsize i = 0; i < columns.size (); i++)
415 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
416 non_loose.push_back (columns[i]);
419 breaks.push_back (0);
420 cols.push_back (Column_description ());
421 for (vsize i = 1; i + 1 < non_loose.size (); i++)
423 if (Paper_column::is_breakable (non_loose[i]))
424 breaks.push_back (cols.size ());
426 cols.push_back (get_column_description (non_loose, i, false));
428 breaks.push_back (cols.size ());
429 force.resize (breaks.size () * breaks.size (), infinity_f);
431 for (vsize b = 0; b + 1 < breaks.size (); b++)
433 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
434 vsize st = breaks[b];
436 for (vsize c = b + 1; c < breaks.size (); c++)
438 vsize end = breaks[c];
439 Simple_spacer spacer;
441 for (vsize i = breaks[b]; i < end - 1; i++)
442 spacer.add_spring (cols[i].spring_);
443 spacer.add_spring (cols[end - 1].end_spring_);
445 for (vsize i = breaks[b]; i < end; i++)
447 for (vsize r = 0; r < cols[i].rods_.size (); r++)
448 if (cols[i].rods_[r].r_ < end)
449 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
450 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
451 if (cols[i].end_rods_[r].r_ == end)
452 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
453 if (!cols[i].keep_inside_line_.is_empty ())
455 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
456 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
459 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
460 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
465 force[b * breaks.size () + c] = -200000;
467 force[b * breaks.size () + c] = infinity_f;
470 if (end < cols.size () && cols[end].break_permission_ == force_break)
478 get_line_configuration (vector<Grob *> const &columns,
483 vector<Column_description> cols;
484 Simple_spacer spacer;
485 Column_x_positions ret;
487 ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
488 for (vsize i = 1; i + 1 < columns.size (); i++)
490 if (is_loose (columns[i]))
491 ret.loose_cols_.push_back (columns[i]);
493 ret.cols_.push_back (columns[i]);
495 ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
497 /* since we've already put our line-ending column in the column list, we can ignore
498 the end_XXX_ fields of our column_description */
499 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
501 cols.push_back (get_column_description (ret.cols_, i, i == 0));
502 spacer.add_spring (cols[i].spring_);
504 for (vsize i = 0; i < cols.size (); i++)
506 for (vsize r = 0; r < cols[i].rods_.size (); r++)
507 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
509 if (!cols[i].keep_inside_line_.is_empty ())
511 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
512 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
516 spacer.solve (line_len, ragged);
517 ret.force_ = spacer.force_penalty (ragged);
519 ret.config_ = spacer.spring_positions ();
520 for (vsize i = 0; i < ret.config_.size (); i++)
521 ret.config_[i] += indent;
523 ret.satisfies_constraints_ = spacer.fits ();
526 Check if breaking constraints are met.
528 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
530 SCM p = ret.cols_[i]->get_property ("line-break-permission");
531 if (scm_is_eq (p, ly_symbol2scm ("force")))
532 ret.satisfies_constraints_ = false;