2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1999--2011 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::solve (Real line_len, bool ragged)
166 Real conf = configuration_length (force_);
169 line_len_ = line_len;
170 if (conf < line_len_)
171 force_ = expand_line ();
172 else if (conf > line_len_)
173 force_ = compress_line ();
175 if (ragged && force_ < 0)
180 Simple_spacer::expand_line ()
182 double inv_hooke = 0;
183 double cur_len = configuration_length (force_);
186 for (vsize i = 0; i < springs_.size (); i++)
187 inv_hooke += springs_[i].inverse_stretch_strength ();
189 if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
190 return 0.0; /* anyway, then it makes no difference what the force is */
192 assert (cur_len <= line_len_);
193 return (line_len_ - cur_len) / inv_hooke + force_;
197 Simple_spacer::compress_line ()
199 double cur_len = configuration_length (force_);
200 double cur_force = force_;
201 bool compressed = false;
203 /* just because we are in compress_line () doesn't mean that the line
204 will actually be compressed (as in, a negative force) because
205 we start out with a stretched line. Here, we check whether we
206 will be compressed or stretched (so we know which spring constant to use) */
207 if (configuration_length (0.0) > line_len_)
210 cur_len = configuration_length (0.0);
216 assert (line_len_ <= cur_len);
218 vector<Spring> sorted_springs = springs_;
219 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
221 /* inv_hooke is the total flexibility of currently-active springs */
222 double inv_hooke = 0;
223 vsize i = sorted_springs.size ();
224 for (; i && sorted_springs[i - 1].blocking_force () < cur_force; i--)
225 inv_hooke += compressed
226 ? sorted_springs[i - 1].inverse_compress_strength ()
227 : sorted_springs[i - 1].inverse_stretch_strength ();
228 /* i now indexes the first active spring, so */
229 for (; i < sorted_springs.size (); i++)
231 Spring sp = sorted_springs[i];
233 if (isinf (sp.blocking_force ()))
236 double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
237 if (cur_len - block_dist < line_len_)
239 cur_force += (line_len_ - cur_len) / inv_hooke;
245 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
249 cur_len -= block_dist;
250 inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
251 cur_force = sp.blocking_force ();
259 Simple_spacer::add_spring (Spring const &sp)
261 force_ = max (force_, sp.blocking_force ());
262 springs_.push_back (sp);
266 Simple_spacer::spring_positions () const
271 for (vsize i = 0; i < springs_.size (); i++)
272 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
277 Simple_spacer::force_penalty (bool ragged) const
279 /* If we are ragged-right, we don't want to penalise according to the force,
280 but according to the amount of whitespace that is present after the end
283 return max (0.0, line_len_ - configuration_length (0.0));
285 /* Use a convex compression penalty. */
287 return f - (f < 0 ? f * f * f * f * 2 : 0);
290 /****************************************************************/
292 struct Rod_description
297 bool operator < (const Rod_description r)
308 Rod_description (vsize r, Real d)
315 struct Column_description
317 vector<Rod_description> rods_;
318 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
322 SCM break_permission_;
323 Interval keep_inside_line_;
325 Column_description ()
327 break_permission_ = SCM_EOL;
334 return (scm_is_pair (g->get_object ("between-cols")));
338 maybe_find_prebroken_piece (Grob *g, Direction d)
340 Grob *ret = dynamic_cast<Item *> (g)->find_prebroken_piece (d);
347 next_spaceable_column (vector<Grob *> const &list, vsize starting)
349 for (vsize i = starting + 1; i < list.size (); i++)
350 if (!is_loose (list[i]))
355 static Column_description
356 get_column_description (vector<Grob *> const &cols, vsize col_index, bool line_starter)
358 Grob *col = cols[col_index];
360 col = maybe_find_prebroken_piece (col, RIGHT);
362 Column_description description;
363 Grob *next_col = next_spaceable_column (cols, col_index);
365 description.spring_ = Spaceable_grob::get_spring (col, next_col);
367 Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
369 description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
371 for (SCM s = Spaceable_grob::get_minimum_distances (col);
372 scm_is_pair (s); s = scm_cdr (s))
374 Grob *other = unsmob_grob (scm_caar (s));
375 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
378 if (cols[j] == other)
379 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
380 else /* it must end at the LEFT prebroken_piece */
381 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
385 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
386 description.keep_inside_line_ = col->extent (col, X_AXIS);
388 description.break_permission_ = col->get_property ("line-break-permission");
393 get_line_forces (vector<Grob *> const &columns,
394 Real line_len, Real indent, bool ragged)
396 vector<vsize> breaks;
398 vector<Grob *> non_loose;
399 vector<Column_description> cols;
400 SCM force_break = ly_symbol2scm ("force");
402 for (vsize i = 0; i < columns.size (); i++)
403 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
404 non_loose.push_back (columns[i]);
407 breaks.push_back (0);
408 cols.push_back (Column_description ());
409 for (vsize i = 1; i + 1 < non_loose.size (); i++)
411 if (Paper_column::is_breakable (non_loose[i]))
412 breaks.push_back (cols.size ());
414 cols.push_back (get_column_description (non_loose, i, false));
416 breaks.push_back (cols.size ());
417 force.resize (breaks.size () * breaks.size (), infinity_f);
419 for (vsize b = 0; b + 1 < breaks.size (); b++)
421 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
422 vsize st = breaks[b];
424 for (vsize c = b + 1; c < breaks.size (); c++)
426 vsize end = breaks[c];
427 Simple_spacer spacer;
429 for (vsize i = breaks[b]; i < end - 1; i++)
430 spacer.add_spring (cols[i].spring_);
431 spacer.add_spring (cols[end - 1].end_spring_);
433 for (vsize i = breaks[b]; i < end; i++)
435 for (vsize r = 0; r < cols[i].rods_.size (); r++)
436 if (cols[i].rods_[r].r_ < end)
437 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
438 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
439 if (cols[i].end_rods_[r].r_ == end)
440 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
441 if (!cols[i].keep_inside_line_.is_empty ())
443 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
444 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
447 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
448 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
453 force[b * breaks.size () + c] = -200000;
455 force[b * breaks.size () + c] = infinity_f;
458 if (end < cols.size () && cols[end].break_permission_ == force_break)
466 get_line_configuration (vector<Grob *> const &columns,
471 vector<Column_description> cols;
472 Simple_spacer spacer;
473 Column_x_positions ret;
475 ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
476 for (vsize i = 1; i + 1 < columns.size (); i++)
478 if (is_loose (columns[i]))
479 ret.loose_cols_.push_back (columns[i]);
481 ret.cols_.push_back (columns[i]);
483 ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
485 /* since we've already put our line-ending column in the column list, we can ignore
486 the end_XXX_ fields of our column_description */
487 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
489 cols.push_back (get_column_description (ret.cols_, i, i == 0));
490 spacer.add_spring (cols[i].spring_);
492 for (vsize i = 0; i < cols.size (); i++)
494 for (vsize r = 0; r < cols[i].rods_.size (); r++)
495 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
497 if (!cols[i].keep_inside_line_.is_empty ())
499 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
500 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
504 spacer.solve (line_len, ragged);
505 ret.force_ = spacer.force_penalty (ragged);
507 ret.config_ = spacer.spring_positions ();
508 for (vsize i = 0; i < ret.config_.size (); i++)
509 ret.config_[i] += indent;
511 ret.satisfies_constraints_ = spacer.fits ();
514 Check if breaking constraints are met.
516 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
518 SCM p = ret.cols_[i]->get_property ("line-break-permission");
519 if (p == ly_symbol2scm ("force"))
520 ret.satisfies_constraints_ = false;
527 #include "ly-smobs.icc"
529 IMPLEMENT_SIMPLE_SMOBS (Simple_spacer);
530 IMPLEMENT_DEFAULT_EQUAL_P (Simple_spacer);
533 Simple_spacer::mark_smob (SCM /* x */)
539 Simple_spacer::print_smob (SCM /* x */, SCM p, scm_print_state *)
541 scm_puts ("#<Simple spacer>", p);