2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
9 - add support for different stretch/shrink constants?
14 #include "column-x-positions.hh"
15 #include "dimensions.hh"
16 #include "international.hh"
17 #include "libc-extension.hh" // isinf
18 #include "paper-column.hh"
19 #include "simple-spacer.hh"
20 #include "spaceable-grob.hh"
25 A simple spacing constraint solver. The approach:
27 Stretch the line uniformly until none of the constraints (rods)
28 block. It then is very wide.
30 Compress until the next constraint blocks,
32 Mark the springs over the constrained part to be non-active.
34 Repeat with the smaller set of non-active constraints, until all
35 constraints blocked, or until the line is as short as desired.
37 This is much simpler, and much much faster than full scale
38 Constrained QP. On the other hand, a situation like this will not
39 be typeset as dense as possible, because
42 veryveryverylongsyllable2 veryveryverylongsyllable2
43 " "4 veryveryverylongsyllable2 syllable4
46 can be further compressed to
50 veryveryverylongsyllable2 veryveryverylongsyllable2
51 " "4 veryveryverylongsyllable2 syllable4
54 Perhaps this is not a bad thing, because the 1st looks better anyway. */
57 positive force = expanding, negative force = compressing.
60 Simple_spacer::Simple_spacer ()
69 Simple_spacer::force () const
75 Simple_spacer::fits () const
81 Simple_spacer::rod_force (int l, int r, Real dist)
83 Real c = range_stiffness (l, r);
84 Real d = range_ideal_len (l, r);
85 Real block_stretch = dist - d;
86 return c * block_stretch;
90 Simple_spacer::add_rod (int l, int r, Real dist)
92 if (isinf (dist) || isnan (dist))
94 programming_error ("ignoring weird minimum distance");
98 Real block_force = rod_force (l, r, dist);
100 if (isinf (block_force))
102 Real spring_dist = range_ideal_len (l, r);
103 if (spring_dist < dist)
104 for (int i = l; i < r; i++)
105 springs_[i].ideal_ *= dist / spring_dist;
109 force_ = max (force_, block_force);
110 for (int i = l; i < r; i++)
111 springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
115 Simple_spacer::range_ideal_len (int l, int r) const
118 for (int i = l; i < r; i++)
119 d += springs_[i].ideal_;
124 Simple_spacer::range_stiffness (int l, int r) const
127 for (int i = l; i < r; i++)
128 den += springs_[i].inverse_hooke_;
134 Simple_spacer::configuration_length (Real force) const
137 for (vsize i = 0; i < springs_.size (); i++)
138 l += springs_[i].length (force);
144 Simple_spacer::solve (Real line_len, bool ragged)
146 Real conf = configuration_length (force_);
147 double inv_hooke = 0;
148 for (vsize i=0; i < springs_.size (); i++)
149 inv_hooke += springs_[i].inverse_hooke_;
152 line_len_ = line_len;
153 if ((inv_hooke > 0) && (conf < line_len_))
154 force_ = expand_line ();
155 else if (conf > line_len_)
156 force_ = compress_line ();
158 if (ragged && force_ < 0)
163 Simple_spacer::expand_line ()
165 double inv_hooke = 0;
166 double cur_len = configuration_length (force_);
169 for (vsize i=0; i < springs_.size (); i++)
170 inv_hooke += springs_[i].inverse_hooke_;
172 assert (cur_len <= line_len_);
173 return (line_len_ - cur_len) / inv_hooke + force_;
177 Simple_spacer::compress_line ()
179 double inv_hooke = 0;
180 double cur_len = configuration_length (force_);
181 double cur_force = force_;
184 for (vsize i=0; i < springs_.size (); i++)
185 inv_hooke += springs_[i].inverse_hooke_;
187 assert (line_len_ <= cur_len);
189 vector<Spring_description> sorted_springs = springs_;
190 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring_description> ());
191 for (vsize i = 0; i < sorted_springs.size (); i++)
193 Spring_description sp = sorted_springs[i];
195 assert (sp.block_force_ <= cur_force);
196 if (isinf (sp.block_force_))
199 double block_dist = (cur_force - sp.block_force_) * inv_hooke;
200 if (cur_len - block_dist < line_len_)
202 cur_force += (line_len_ - cur_len) / inv_hooke;
208 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
212 cur_len -= block_dist;
213 inv_hooke -= sp.inverse_hooke_;
214 cur_force = sp.block_force_;
222 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
224 Spring_description description;
226 description.ideal_ = ideal;
227 description.inverse_hooke_ = inverse_hooke;
228 if (!description.is_sane ())
230 programming_error ("insane spring found, setting to unit");
232 description.inverse_hooke_ = 1.0;
233 description.ideal_ = 1.0;
236 description.block_force_ = -description.ideal_ / description.inverse_hooke_;
237 // block at distance 0
239 springs_.push_back (description);
243 Simple_spacer::spring_positions () const
248 for (vsize i = 0; i < springs_.size (); i++)
249 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
254 Simple_spacer::force_penalty (bool ragged) const
256 /* If we are ragged-right, we don't want to penalise according to the force,
257 but according to the amount of whitespace that is present after the end
260 return max (0.0, line_len_ - configuration_length (0.0));
262 /* Use a convex compression penalty. */
264 return f - (f < 0 ? f*f*f*f*4 : 0);
267 /****************************************************************/
269 Spring_description::Spring_description ()
272 inverse_hooke_ = 0.0;
277 Spring_description::is_sane () const
279 return (inverse_hooke_ >= 0)
281 && !isinf (ideal_) && !isnan (ideal_)
282 && (inverse_hooke_ == 0.0 || fabs (inverse_hooke_) > 1e-8)
287 Spring_description::length (Real f) const
289 return ideal_ + max (f, block_force_) * inverse_hooke_;
292 /****************************************************************/
295 TODO: should a add penalty for widely varying spring forces (caused
304 The ## forces the notes apart; we shouldn't allow the O's to touch
308 struct Rod_description
313 bool operator< (const Rod_description r)
324 Rod_description (vsize r, Real d)
331 struct Column_description
333 vector<Rod_description> rods_;
334 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
338 Real end_inverse_hooke_;
339 SCM break_permission_;
340 Interval keep_inside_line_;
342 Column_description ()
347 end_inverse_hooke_ = 0;
348 break_permission_ = SCM_EOL;
355 return (scm_is_pair (g->get_object ("between-cols")));
359 maybe_find_prebroken_piece (Grob *g, Direction d)
361 Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
368 next_spaceable_column (vector<Grob*> const &list, vsize starting)
370 for (vsize i = starting+1; i < list.size (); i++)
371 if (!is_loose (list[i]))
376 static Column_description
377 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
379 Grob *col = cols[col_index];
381 col = maybe_find_prebroken_piece (col, RIGHT);
383 Column_description description;
384 Grob *next_col = next_spaceable_column (cols, col_index);
386 Spaceable_grob::get_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
387 Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
389 Spaceable_grob::get_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
391 for (SCM s = Spaceable_grob::get_minimum_distances (col);
392 scm_is_pair (s); s = scm_cdr (s))
394 Grob *other = unsmob_grob (scm_caar (s));
395 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
398 if (cols[j] == other)
399 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
400 else /* it must end at the LEFT prebroken_piece */
401 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
405 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
406 description.keep_inside_line_ = col->extent (col, X_AXIS);
408 description.break_permission_ = col->get_property ("line-break-permission");
413 get_line_forces (vector<Grob*> const &columns,
414 Real line_len, Real indent, bool ragged)
416 vector<vsize> breaks;
418 vector<Grob*> non_loose;
419 vector<Column_description> cols;
420 SCM force_break = ly_symbol2scm ("force");
422 for (vsize i = 0; i < columns.size (); i++)
423 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
424 non_loose.push_back (columns[i]);
427 breaks.push_back (0);
428 cols.push_back (Column_description ());
429 for (vsize i = 1; i + 1 < non_loose.size (); i++)
431 if (Paper_column::is_breakable (non_loose[i]))
432 breaks.push_back (cols.size ());
434 cols.push_back (get_column_description (non_loose, i, false));
436 breaks.push_back (cols.size ());
437 force.resize (breaks.size () * breaks.size (), infinity_f);
439 for (vsize b = 0; b + 1 < breaks.size (); b++)
441 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
442 vsize st = breaks[b];
444 for (vsize c = b+1; c < breaks.size (); c++)
446 vsize end = breaks[c];
447 Simple_spacer spacer;
449 for (vsize i = breaks[b]; i < end - 1; i++)
450 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
451 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].end_inverse_hooke_);
454 for (vsize i = breaks[b]; i < end; i++)
456 for (vsize r = 0; r < cols[i].rods_.size (); r++)
457 if (cols[i].rods_[r].r_ < end)
458 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
459 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
460 if (cols[i].end_rods_[r].r_ == end)
461 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
462 if (!cols[i].keep_inside_line_.is_empty ())
464 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
465 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
468 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
469 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
474 force[b * breaks.size () + c] = -200000;
476 force[b * breaks.size () + c] = infinity_f;
479 if (end < cols.size () && cols[end].break_permission_ == force_break)
487 get_line_configuration (vector<Grob*> const &columns,
492 vector<Column_description> cols;
493 Simple_spacer spacer;
494 Column_x_positions ret;
496 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
497 for (vsize i = 1; i + 1 < columns.size (); i++)
499 if (is_loose (columns[i]))
500 ret.loose_cols_.push_back (columns[i]);
502 ret.cols_.push_back (columns[i]);
504 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
506 /* since we've already put our line-ending column in the column list, we can ignore
507 the end_XXX_ fields of our column_description */
508 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
510 cols.push_back (get_column_description (ret.cols_, i, i == 0));
511 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
513 for (vsize i = 0; i < cols.size (); i++)
515 for (vsize r = 0; r < cols[i].rods_.size (); r++)
516 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
518 if (!cols[i].keep_inside_line_.is_empty ())
520 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
521 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
525 spacer.solve (line_len, ragged);
526 ret.force_ = spacer.force_penalty (ragged);
528 ret.config_ = spacer.spring_positions ();
529 for (vsize i = 0; i < ret.config_.size (); i++)
530 ret.config_[i] += indent;
532 ret.satisfies_constraints_ = spacer.fits ();
535 Check if breaking constraints are met.
537 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
539 SCM p = ret.cols_[i]->get_property ("line-break-permission");
540 if (p == ly_symbol2scm ("force"))
541 ret.satisfies_constraints_ = false;