2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1999--2012 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 return 0.0; /* anyway, then it makes no difference what the force is */
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 Grob *end_col = dynamic_cast<Item *> (cols[col_index + 1])->find_prebroken_piece (LEFT);
375 description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
377 for (SCM s = Spaceable_grob::get_minimum_distances (col);
378 scm_is_pair (s); s = scm_cdr (s))
380 Grob *other = unsmob_grob (scm_caar (s));
381 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
384 if (cols[j] == other)
385 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
386 else /* it must end at the LEFT prebroken_piece */
387 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
391 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
392 description.keep_inside_line_ = col->extent (col, X_AXIS);
394 description.break_permission_ = col->get_property ("line-break-permission");
399 get_line_forces (vector<Grob *> const &columns,
400 Real line_len, Real indent, bool ragged)
402 vector<vsize> breaks;
404 vector<Grob *> non_loose;
405 vector<Column_description> cols;
406 SCM force_break = ly_symbol2scm ("force");
408 for (vsize i = 0; i < columns.size (); i++)
409 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
410 non_loose.push_back (columns[i]);
413 breaks.push_back (0);
414 cols.push_back (Column_description ());
415 for (vsize i = 1; i + 1 < non_loose.size (); i++)
417 if (Paper_column::is_breakable (non_loose[i]))
418 breaks.push_back (cols.size ());
420 cols.push_back (get_column_description (non_loose, i, false));
422 breaks.push_back (cols.size ());
423 force.resize (breaks.size () * breaks.size (), infinity_f);
425 for (vsize b = 0; b + 1 < breaks.size (); b++)
427 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
428 vsize st = breaks[b];
430 for (vsize c = b + 1; c < breaks.size (); c++)
432 vsize end = breaks[c];
433 Simple_spacer spacer;
435 for (vsize i = breaks[b]; i < end - 1; i++)
436 spacer.add_spring (cols[i].spring_);
437 spacer.add_spring (cols[end - 1].end_spring_);
439 for (vsize i = breaks[b]; i < end; i++)
441 for (vsize r = 0; r < cols[i].rods_.size (); r++)
442 if (cols[i].rods_[r].r_ < end)
443 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
444 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
445 if (cols[i].end_rods_[r].r_ == end)
446 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
447 if (!cols[i].keep_inside_line_.is_empty ())
449 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
450 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
453 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
454 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
459 force[b * breaks.size () + c] = -200000;
461 force[b * breaks.size () + c] = infinity_f;
464 if (end < cols.size () && cols[end].break_permission_ == force_break)
472 get_line_configuration (vector<Grob *> const &columns,
477 vector<Column_description> cols;
478 Simple_spacer spacer;
479 Column_x_positions ret;
481 ret.cols_.push_back (dynamic_cast<Item *> (columns[0])->find_prebroken_piece (RIGHT));
482 for (vsize i = 1; i + 1 < columns.size (); i++)
484 if (is_loose (columns[i]))
485 ret.loose_cols_.push_back (columns[i]);
487 ret.cols_.push_back (columns[i]);
489 ret.cols_.push_back (dynamic_cast<Item *> (columns.back ())->find_prebroken_piece (LEFT));
491 /* since we've already put our line-ending column in the column list, we can ignore
492 the end_XXX_ fields of our column_description */
493 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
495 cols.push_back (get_column_description (ret.cols_, i, i == 0));
496 spacer.add_spring (cols[i].spring_);
498 for (vsize i = 0; i < cols.size (); i++)
500 for (vsize r = 0; r < cols[i].rods_.size (); r++)
501 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
503 if (!cols[i].keep_inside_line_.is_empty ())
505 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
506 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
510 spacer.solve (line_len, ragged);
511 ret.force_ = spacer.force_penalty (ragged);
513 ret.config_ = spacer.spring_positions ();
514 for (vsize i = 0; i < ret.config_.size (); i++)
515 ret.config_[i] += indent;
517 ret.satisfies_constraints_ = spacer.fits ();
520 Check if breaking constraints are met.
522 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
524 SCM p = ret.cols_[i]->get_property ("line-break-permission");
525 if (p == ly_symbol2scm ("force"))
526 ret.satisfies_constraints_ = false;
533 #include "ly-smobs.icc"
535 IMPLEMENT_SIMPLE_SMOBS (Simple_spacer);
536 IMPLEMENT_DEFAULT_EQUAL_P (Simple_spacer);
539 Simple_spacer::mark_smob (SCM /* x */)
545 Simple_spacer::print_smob (SCM /* x */, SCM p, scm_print_state *)
547 scm_puts ("#<Simple spacer>", p);