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"
35 ADD_SMOB_INIT (Simple_spacer);
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 assert (cur_len <= line_len_);
201 return (line_len_ - cur_len) / inv_hooke + force_;
205 Simple_spacer::compress_line ()
207 double cur_len = configuration_length (force_);
208 double cur_force = force_;
209 bool compressed = false;
211 /* just because we are in compress_line () doesn't mean that the line
212 will actually be compressed (as in, a negative force) because
213 we start out with a stretched line. Here, we check whether we
214 will be compressed or stretched (so we know which spring constant to use) */
215 if (configuration_length (0.0) > line_len_)
218 cur_len = configuration_length (0.0);
224 assert (line_len_ <= cur_len);
226 vector<Spring> sorted_springs = springs_;
227 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
229 /* inv_hooke is the total flexibility of currently-active springs */
230 double inv_hooke = 0;
231 vsize i = sorted_springs.size ();
232 for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
233 inv_hooke += compressed
234 ? sorted_springs[i - 1].inverse_compress_strength ()
235 : sorted_springs[i - 1].inverse_stretch_strength ();
236 /* i now indexes the first active spring, so */
237 for (; i < sorted_springs.size (); i++)
239 Spring sp = sorted_springs[i];
241 if (isinf (sp.blocking_force ()))
244 double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
245 if (cur_len - block_dist < line_len_)
247 cur_force += (line_len_ - cur_len) / inv_hooke;
253 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
257 cur_len -= block_dist;
258 inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
259 cur_force = sp.blocking_force ();
267 Simple_spacer::add_spring (Spring const &sp)
269 force_ = max (force_, sp.blocking_force ());
270 springs_.push_back (sp);
274 Simple_spacer::spring_positions () const
279 for (vsize i = 0; i < springs_.size (); i++)
280 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
285 Simple_spacer::force_penalty (bool ragged) const
287 /* If we are ragged-right, we don't want to penalise according to the force,
288 but according to the amount of whitespace that is present after the end
291 return max (0.0, line_len_ - configuration_length (0.0));
293 /* Use a convex compression penalty. */
295 return f - (f < 0 ? f * f * f * f * 2 : 0);
298 /****************************************************************/
300 struct Rod_description
305 bool operator < (const Rod_description r)
316 Rod_description (vsize r, Real d)
323 struct Column_description
325 vector<Rod_description> rods_;
326 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
330 SCM break_permission_;
331 Interval keep_inside_line_;
333 Column_description ()
335 break_permission_ = SCM_EOL;
342 return (scm_is_pair (g->get_object ("between-cols")));
346 maybe_find_prebroken_piece (Grob *g, Direction d)
348 Grob *ret = dynamic_cast<Item *> (g)->find_prebroken_piece (d);
355 next_spaceable_column (vector<Grob *> const &list, vsize starting)
357 for (vsize i = starting + 1; i < list.size (); i++)
358 if (!is_loose (list[i]))
363 static Column_description
364 get_column_description (vector<Grob *> const &cols, vsize col_index, bool line_starter)
366 Grob *col = cols[col_index];
368 col = maybe_find_prebroken_piece (col, RIGHT);
370 Column_description description;
371 Grob *next_col = next_spaceable_column (cols, col_index);
373 description.spring_ = Spaceable_grob::get_spring (col, next_col);
375 if (col_index + 1 < cols.size ())
377 Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
379 description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
382 for (SCM s = Spaceable_grob::get_minimum_distances (col);
383 scm_is_pair (s); s = scm_cdr (s))
385 Grob *other = Grob::unsmob (scm_caar (s));
386 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
389 if (cols[j] == other)
390 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
391 else /* it must end at the LEFT prebroken_piece */
392 /* see Spanner::set_spacing_rods for more comments on how
393 to deal with situations where we don't know if we're
394 ending yet on the left prebroken piece */
395 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
399 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
400 description.keep_inside_line_ = col->extent (col, X_AXIS);
402 description.break_permission_ = col->get_property ("line-break-permission");
407 get_line_forces (vector<Grob *> const &columns,
408 Real line_len, Real indent, bool ragged)
410 vector<vsize> breaks;
412 vector<Grob *> non_loose;
413 vector<Column_description> cols;
414 SCM force_break = ly_symbol2scm ("force");
416 for (vsize i = 0; i < columns.size (); i++)
417 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
418 non_loose.push_back (columns[i]);
421 breaks.push_back (0);
422 cols.push_back (Column_description ());
423 for (vsize i = 1; i + 1 < non_loose.size (); i++)
425 if (Paper_column::is_breakable (non_loose[i]))
426 breaks.push_back (cols.size ());
428 cols.push_back (get_column_description (non_loose, i, false));
430 breaks.push_back (cols.size ());
431 force.resize (breaks.size () * breaks.size (), infinity_f);
433 for (vsize b = 0; b + 1 < breaks.size (); b++)
435 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
436 vsize st = breaks[b];
438 for (vsize c = b + 1; c < breaks.size (); c++)
440 vsize end = breaks[c];
441 Simple_spacer spacer;
443 for (vsize i = breaks[b]; i < end - 1; i++)
444 spacer.add_spring (cols[i].spring_);
445 spacer.add_spring (cols[end - 1].end_spring_);
447 for (vsize i = breaks[b]; i < end; i++)
449 for (vsize r = 0; r < cols[i].rods_.size (); r++)
450 if (cols[i].rods_[r].r_ < end)
451 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
452 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
453 if (cols[i].end_rods_[r].r_ == end)
454 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
455 if (!cols[i].keep_inside_line_.is_empty ())
457 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
458 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
461 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
462 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
467 force[b * breaks.size () + c] = -200000;
469 force[b * breaks.size () + c] = infinity_f;
472 if (end < cols.size () && cols[end].break_permission_ == force_break)
480 get_line_configuration (vector<Grob *> const &columns,
485 vector<Column_description> cols;
486 Simple_spacer spacer;
487 Column_x_positions ret;
489 ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
490 for (vsize i = 1; i + 1 < columns.size (); i++)
492 if (is_loose (columns[i]))
493 ret.loose_cols_.push_back (columns[i]);
495 ret.cols_.push_back (columns[i]);
497 ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
499 /* since we've already put our line-ending column in the column list, we can ignore
500 the end_XXX_ fields of our column_description */
501 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
503 cols.push_back (get_column_description (ret.cols_, i, i == 0));
504 spacer.add_spring (cols[i].spring_);
506 for (vsize i = 0; i < cols.size (); i++)
508 for (vsize r = 0; r < cols[i].rods_.size (); r++)
509 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
511 if (!cols[i].keep_inside_line_.is_empty ())
513 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
514 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
518 spacer.solve (line_len, ragged);
519 ret.force_ = spacer.force_penalty (ragged);
521 ret.config_ = spacer.spring_positions ();
522 for (vsize i = 0; i < ret.config_.size (); i++)
523 ret.config_[i] += indent;
525 ret.satisfies_constraints_ = spacer.fits ();
528 Check if breaking constraints are met.
530 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
532 SCM p = ret.cols_[i]->get_property ("line-break-permission");
533 if (scm_is_eq (p, ly_symbol2scm ("force")))
534 ret.satisfies_constraints_ = false;