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 d = range_ideal_len (l, r);
84 Real c = range_stiffness (l, r, dist > d);
85 Real block_stretch = dist - d;
87 if (isinf (c)) /* take care of the 0*infinity_f case */
89 return c * block_stretch;
93 Simple_spacer::add_rod (int l, int r, Real dist)
95 if (isinf (dist) || isnan (dist))
97 programming_error ("ignoring weird minimum distance");
101 Real block_force = rod_force (l, r, dist);
103 if (isinf (block_force))
105 Real spring_dist = range_ideal_len (l, r);
106 if (spring_dist < dist)
107 for (int i = l; i < r; i++)
108 springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
112 force_ = max (force_, block_force);
113 for (int i = l; i < r; i++)
114 springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
118 Simple_spacer::range_ideal_len (int l, int r) const
121 for (int i = l; i < r; i++)
122 d += springs_[i].distance ();
127 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
130 for (int i = l; i < r; i++)
131 den += stretch ? springs_[i].inverse_stretch_strength ()
132 : springs_[i].inverse_compress_strength ();
138 Simple_spacer::configuration_length (Real force) const
141 for (vsize i = 0; i < springs_.size (); i++)
142 l += springs_[i].length (force);
148 Simple_spacer::solve (Real line_len, bool ragged)
150 Real conf = configuration_length (force_);
153 line_len_ = line_len;
154 if (conf < line_len_)
155 force_ = expand_line ();
156 else if (conf > line_len_)
157 force_ = compress_line ();
159 if (ragged && force_ < 0)
164 Simple_spacer::expand_line ()
166 double inv_hooke = 0;
167 double cur_len = configuration_length (force_);
170 for (vsize i=0; i < springs_.size (); i++)
171 inv_hooke += springs_[i].inverse_stretch_strength ();
173 if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
174 return 0.0; /* anyway, then it makes no difference what the force is */
176 assert (cur_len <= line_len_);
177 return (line_len_ - cur_len) / inv_hooke + force_;
181 Simple_spacer::compress_line ()
183 double inv_hooke = 0;
184 double cur_len = configuration_length (force_);
185 double cur_force = force_;
186 bool compressed = false;
188 /* just because we are in compress_line () doesn't mean that the line
189 will actually be compressed (as in, a negative force) because
190 we start out with a stretched line. Here, we check whether we
191 will be compressed or stretched (so we know which spring constant to use) */
192 if (configuration_length (0.0) > line_len_)
195 cur_len = configuration_length (0.0);
200 for (vsize i=0; i < springs_.size (); i++)
201 inv_hooke += compressed
202 ? springs_[i].inverse_compress_strength ()
203 : springs_[i].inverse_stretch_strength ();
205 assert (line_len_ <= cur_len);
207 vector<Spring> sorted_springs = springs_;
208 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
210 for (vsize i = 0; i < sorted_springs.size (); i++)
212 Spring sp = sorted_springs[i];
214 assert (sp.blocking_force () <= cur_force);
215 if (isinf (sp.blocking_force ()))
218 double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
219 if (cur_len - block_dist < line_len_)
221 cur_force += (line_len_ - cur_len) / inv_hooke;
227 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
231 cur_len -= block_dist;
232 inv_hooke -= sp.inverse_compress_strength ();
233 cur_force = sp.blocking_force ();
241 Simple_spacer::add_spring (Spring const &sp)
243 force_ = max (force_, sp.blocking_force ());
244 springs_.push_back (sp);
248 Simple_spacer::spring_positions () const
253 for (vsize i = 0; i < springs_.size (); i++)
254 ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
259 Simple_spacer::force_penalty (bool ragged) const
261 /* If we are ragged-right, we don't want to penalise according to the force,
262 but according to the amount of whitespace that is present after the end
265 return max (0.0, line_len_ - configuration_length (0.0));
267 /* Use a convex compression penalty. */
269 return f - (f < 0 ? f*f*f*f*2 : 0);
272 /****************************************************************/
274 struct Rod_description
279 bool operator< (const Rod_description r)
290 Rod_description (vsize r, Real d)
297 struct Column_description
299 vector<Rod_description> rods_;
300 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
304 SCM break_permission_;
305 Interval keep_inside_line_;
307 Column_description ()
309 break_permission_ = SCM_EOL;
316 return (scm_is_pair (g->get_object ("between-cols")));
320 maybe_find_prebroken_piece (Grob *g, Direction d)
322 Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
329 next_spaceable_column (vector<Grob*> const &list, vsize starting)
331 for (vsize i = starting+1; i < list.size (); i++)
332 if (!is_loose (list[i]))
337 static Column_description
338 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
340 Grob *col = cols[col_index];
342 col = maybe_find_prebroken_piece (col, RIGHT);
344 Column_description description;
345 Grob *next_col = next_spaceable_column (cols, col_index);
347 description.spring_ = Spaceable_grob::get_spring (col, next_col);
349 Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
351 description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
353 for (SCM s = Spaceable_grob::get_minimum_distances (col);
354 scm_is_pair (s); s = scm_cdr (s))
356 Grob *other = unsmob_grob (scm_caar (s));
357 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
360 if (cols[j] == other)
361 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
362 else /* it must end at the LEFT prebroken_piece */
363 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
367 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
368 description.keep_inside_line_ = col->extent (col, X_AXIS);
370 description.break_permission_ = col->get_property ("line-break-permission");
375 get_line_forces (vector<Grob*> const &columns,
376 Real line_len, Real indent, bool ragged)
378 vector<vsize> breaks;
380 vector<Grob*> non_loose;
381 vector<Column_description> cols;
382 SCM force_break = ly_symbol2scm ("force");
384 for (vsize i = 0; i < columns.size (); i++)
385 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
386 non_loose.push_back (columns[i]);
389 breaks.push_back (0);
390 cols.push_back (Column_description ());
391 for (vsize i = 1; i + 1 < non_loose.size (); i++)
393 if (Paper_column::is_breakable (non_loose[i]))
394 breaks.push_back (cols.size ());
396 cols.push_back (get_column_description (non_loose, i, false));
398 breaks.push_back (cols.size ());
399 force.resize (breaks.size () * breaks.size (), infinity_f);
401 for (vsize b = 0; b + 1 < breaks.size (); b++)
403 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
404 vsize st = breaks[b];
406 for (vsize c = b+1; c < breaks.size (); c++)
408 vsize end = breaks[c];
409 Simple_spacer spacer;
411 for (vsize i = breaks[b]; i < end - 1; i++)
412 spacer.add_spring (cols[i].spring_);
413 spacer.add_spring (cols[end-1].end_spring_);
416 for (vsize i = breaks[b]; i < end; i++)
418 for (vsize r = 0; r < cols[i].rods_.size (); r++)
419 if (cols[i].rods_[r].r_ < end)
420 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
421 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
422 if (cols[i].end_rods_[r].r_ == end)
423 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
424 if (!cols[i].keep_inside_line_.is_empty ())
426 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
427 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
430 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
431 force[b * breaks.size () + c] = spacer.force_penalty (ragged);
436 force[b * breaks.size () + c] = -200000;
438 force[b * breaks.size () + c] = infinity_f;
441 if (end < cols.size () && cols[end].break_permission_ == force_break)
449 get_line_configuration (vector<Grob*> const &columns,
454 vector<Column_description> cols;
455 Simple_spacer spacer;
456 Column_x_positions ret;
458 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
459 for (vsize i = 1; i + 1 < columns.size (); i++)
461 if (is_loose (columns[i]))
462 ret.loose_cols_.push_back (columns[i]);
464 ret.cols_.push_back (columns[i]);
466 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
468 /* since we've already put our line-ending column in the column list, we can ignore
469 the end_XXX_ fields of our column_description */
470 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
472 cols.push_back (get_column_description (ret.cols_, i, i == 0));
473 spacer.add_spring (cols[i].spring_);
475 for (vsize i = 0; i < cols.size (); i++)
477 for (vsize r = 0; r < cols[i].rods_.size (); r++)
478 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
480 if (!cols[i].keep_inside_line_.is_empty ())
482 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
483 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
487 spacer.solve (line_len, ragged);
488 ret.force_ = spacer.force_penalty (ragged);
490 ret.config_ = spacer.spring_positions ();
491 for (vsize i = 0; i < ret.config_.size (); i++)
492 ret.config_[i] += indent;
494 ret.satisfies_constraints_ = spacer.fits ();
497 Check if breaking constraints are met.
499 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
501 SCM p = ret.cols_[i]->get_property ("line-break-permission");
502 if (p == ly_symbol2scm ("force"))
503 ret.satisfies_constraints_ = false;