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_);
149 line_len_ = line_len;
150 if (conf < line_len_)
151 force_ = expand_line ();
152 else if (conf > line_len_)
153 force_ = compress_line ();
155 if (ragged && force_ < 0)
160 Simple_spacer::expand_line ()
162 double inv_hooke = 0;
163 double cur_len = configuration_length (force_);
166 for (vsize i=0; i < springs_.size (); i++)
167 inv_hooke += springs_[i].inverse_hooke_;
169 assert (cur_len <= line_len_);
170 return (line_len_ - cur_len) / inv_hooke + force_;
174 Simple_spacer::compress_line ()
176 double inv_hooke = 0;
177 double cur_len = configuration_length (force_);
178 double cur_force = force_;
181 for (vsize i=0; i < springs_.size (); i++)
182 inv_hooke += springs_[i].inverse_hooke_;
184 assert (line_len_ <= cur_len);
186 vector<Spring_description> sorted_springs = springs_;
187 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring_description> ());
188 for (vsize i = 0; i < sorted_springs.size (); i++)
190 Spring_description sp = sorted_springs[i];
192 assert (sp.block_force_ <= cur_force);
193 if (isinf (sp.block_force_))
196 double block_dist = (cur_force - sp.block_force_) * inv_hooke;
197 if (cur_len - block_dist < line_len_)
199 cur_force += (line_len_ - cur_len) / inv_hooke;
205 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
209 cur_len -= block_dist;
210 inv_hooke -= sp.inverse_hooke_;
211 cur_force = sp.block_force_;
219 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
221 Spring_description description;
223 description.ideal_ = ideal;
224 description.inverse_hooke_ = inverse_hooke;
225 if (!description.is_sane ())
227 programming_error ("insane spring found, setting to unit");
229 description.inverse_hooke_ = 1.0;
230 description.ideal_ = 1.0;
233 description.block_force_ = -description.ideal_ / description.inverse_hooke_;
234 // block at distance 0
236 springs_.push_back (description);
240 Simple_spacer::spring_positions () const
245 for (vsize i = 0; i < springs_.size (); i++)
246 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
251 Simple_spacer::force_penalty (bool ragged) const
253 /* If we are ragged-right, we don't want to penalise according to the force,
254 but according to the amount of whitespace that is present after the end
257 return max (0.0, line_len_ - configuration_length (0.0));
259 /* Use a convex compression penalty. */
261 return f - (f < 0 ? f*f*f*f*4 : 0);
264 /****************************************************************/
266 Spring_description::Spring_description ()
269 inverse_hooke_ = 0.0;
274 Spring_description::is_sane () const
276 return (inverse_hooke_ >= 0)
278 && !isinf (ideal_) && !isnan (ideal_)
279 && (inverse_hooke_ == 0.0 || fabs (inverse_hooke_) > 1e-8)
284 Spring_description::length (Real f) const
286 return ideal_ + max (f, block_force_) * inverse_hooke_;
289 /****************************************************************/
292 TODO: should a add penalty for widely varying spring forces (caused
301 The ## forces the notes apart; we shouldn't allow the O's to touch
305 struct Rod_description
310 bool operator< (const Rod_description r)
321 Rod_description (vsize r, Real d)
328 struct Column_description
330 vector<Rod_description> rods_;
331 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
335 Real end_inverse_hooke_;
336 SCM break_permission_;
337 Interval keep_inside_line_;
339 Column_description ()
344 end_inverse_hooke_ = 0;
345 break_permission_ = SCM_EOL;
352 return (scm_is_pair (g->get_object ("between-cols")));
356 maybe_find_prebroken_piece (Grob *g, Direction d)
358 Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
365 next_spaceable_column (vector<Grob*> const &list, vsize starting)
367 for (vsize i = starting+1; i < list.size (); i++)
368 if (!is_loose (list[i]))
373 static Column_description
374 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
376 Grob *col = cols[col_index];
378 col = maybe_find_prebroken_piece (col, RIGHT);
380 Column_description description;
381 Grob *next_col = next_spaceable_column (cols, col_index);
383 Spaceable_grob::get_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
384 Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
386 Spaceable_grob::get_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
388 for (SCM s = Spaceable_grob::get_minimum_distances (col);
389 scm_is_pair (s); s = scm_cdr (s))
391 Grob *other = unsmob_grob (scm_caar (s));
392 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
395 if (cols[j] == other)
396 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
397 else /* it must end at the LEFT prebroken_piece */
398 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
402 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
403 description.keep_inside_line_ = col->extent (col, X_AXIS);
405 description.break_permission_ = col->get_property ("line-break-permission");
410 get_line_forces (vector<Grob*> const &columns,
411 Real line_len, Real indent, bool ragged)
413 vector<vsize> breaks;
415 vector<Grob*> non_loose;
416 vector<Column_description> cols;
417 SCM force_break = ly_symbol2scm ("force");
419 for (vsize i = 0; i < columns.size (); i++)
420 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
421 non_loose.push_back (columns[i]);
424 breaks.push_back (0);
425 cols.push_back (Column_description ());
426 for (vsize i = 1; i + 1 < non_loose.size (); i++)
428 if (Paper_column::is_breakable (non_loose[i]))
429 breaks.push_back (cols.size ());
431 cols.push_back (get_column_description (non_loose, i, false));
433 breaks.push_back (cols.size ());
434 force.resize (breaks.size () * breaks.size (), infinity_f);
436 for (vsize b = 0; b + 1 < breaks.size (); b++)
438 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
439 vsize st = breaks[b];
441 for (vsize c = b+1; c < breaks.size (); c++)
443 vsize end = breaks[c];
444 Simple_spacer spacer;
446 for (vsize i = breaks[b]; i < end - 1; i++)
447 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
448 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].end_inverse_hooke_);
451 for (vsize i = breaks[b]; i < end; i++)
453 for (vsize r = 0; r < cols[i].rods_.size (); r++)
454 if (cols[i].rods_[r].r_ < end)
455 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
456 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
457 if (cols[i].end_rods_[r].r_ == end)
458 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
459 if (!cols[i].keep_inside_line_.is_empty ())
461 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
462 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
465 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
466 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
471 force[b * breaks.size () + c] = -200000;
473 force[b * breaks.size () + c] = infinity_f;
476 if (end < cols.size () && cols[end].break_permission_ == force_break)
484 get_line_configuration (vector<Grob*> const &columns,
489 vector<Column_description> cols;
490 Simple_spacer spacer;
491 Column_x_positions ret;
493 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
494 for (vsize i = 1; i + 1 < columns.size (); i++)
496 if (is_loose (columns[i]))
497 ret.loose_cols_.push_back (columns[i]);
499 ret.cols_.push_back (columns[i]);
501 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
503 /* since we've already put our line-ending column in the column list, we can ignore
504 the end_XXX_ fields of our column_description */
505 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
507 cols.push_back (get_column_description (ret.cols_, i, i == 0));
508 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
510 for (vsize i = 0; i < cols.size (); i++)
512 for (vsize r = 0; r < cols[i].rods_.size (); r++)
513 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
515 if (!cols[i].keep_inside_line_.is_empty ())
517 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
518 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
522 spacer.solve (line_len, ragged);
523 ret.force_ = spacer.force_penalty (ragged);
525 ret.config_ = spacer.spring_positions ();
526 for (vsize i = 0; i < ret.config_.size (); i++)
527 ret.config_[i] += indent;
529 ret.satisfies_constraints_ = spacer.fits ();
532 Check if breaking constraints are met.
534 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
536 SCM p = ret.cols_[i]->get_property ("line-break-permission");
537 if (p == ly_symbol2scm ("force"))
538 ret.satisfies_constraints_ = false;