2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2006 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 ()
67 Simple_spacer::force ()
73 Simple_spacer::fits ()
79 Simple_spacer::rod_force (int l, int r, Real dist)
81 Real c = range_stiffness (l, r);
82 Real d = range_ideal_len (l, r);
83 Real block_stretch = dist - d;
84 return c * block_stretch;
88 Simple_spacer::add_rod (int l, int r, Real dist)
90 if (isinf (dist) || isnan (dist))
92 programming_error ("ignoring weird minimum distance");
96 Real block_force = rod_force (l, r, dist);
98 if (isinf (block_force))
100 Real spring_dist = range_ideal_len (l, r);
101 if (spring_dist < dist)
102 for (int i = l; i < r; i++)
103 springs_[i].ideal_ *= dist / spring_dist;
107 force_ = max (force_, block_force);
108 for (int i = l; i < r; i++)
109 springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
113 Simple_spacer::range_ideal_len (int l, int r) const
116 for (int i = l; i < r; i++)
117 d += springs_[i].ideal_;
122 Simple_spacer::range_stiffness (int l, int r) const
125 for (int i = l; i < r; i++)
126 den += springs_[i].inverse_hooke_;
132 Simple_spacer::configuration_length () const
135 for (vsize i = 0; i < springs_.size (); i++)
136 l += springs_[i].length (force_);
142 Simple_spacer::solve (Real line_len, bool ragged)
144 Real conf = configuration_length ();
147 line_len_ = line_len;
151 fits_ = configuration_length () <= line_len_;
152 /* we need to calculate a force here to prevent a bunch of short lines */
154 force_ = expand_line ();
156 else if (conf < line_len_)
157 force_ = expand_line ();
158 else if (conf > line_len_)
159 force_ = compress_line ();
163 Simple_spacer::expand_line ()
165 double inv_hooke = 0;
166 double cur_len = configuration_length ();
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 ();
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_)
201 return cur_force + (line_len_ - cur_len) / inv_hooke;
202 cur_len -= block_dist;
203 inv_hooke -= sp.inverse_hooke_;
204 cur_force = sp.block_force_;
212 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
214 Spring_description description;
216 description.ideal_ = ideal;
217 description.inverse_hooke_ = inverse_hooke;
218 if (!description.is_sane ())
220 programming_error ("insane spring found, setting to unit");
222 description.inverse_hooke_ = 1.0;
223 description.ideal_ = 1.0;
226 description.block_force_ = -description.ideal_ / description.inverse_hooke_;
227 // block at distance 0
229 springs_.push_back (description);
233 Simple_spacer::spring_positions () const
238 for (vsize i = 0; i < springs_.size (); i++)
239 ret.push_back (ret.back () + springs_[i].length (ragged_ ? 0.0 : force_));
243 /****************************************************************/
245 Spring_description::Spring_description ()
248 inverse_hooke_ = 0.0;
253 Spring_description::is_sane () const
255 return (inverse_hooke_ >= 0)
257 && !isinf (ideal_) && !isnan (ideal_);
261 Spring_description::length (Real f) const
263 return ideal_ + max (f, block_force_) * inverse_hooke_;
266 /****************************************************************/
269 TODO: should a add penalty for widely varying spring forces (caused
278 The ## forces the notes apart; we shouldn't allow the O's to touch
282 struct Rod_description
287 bool operator< (const Rod_description r)
298 Rod_description (vsize r, Real d)
305 struct Column_description
307 vector<Rod_description> rods_;
308 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
312 Real end_inverse_hooke_;
313 SCM break_permission_;
314 Interval keep_inside_line_;
316 Column_description ()
321 end_inverse_hooke_ = 0;
322 break_permission_ = SCM_EOL;
326 static int compare_paper_column_rank (Grob *const &a, Grob *const &b);
331 return (scm_is_pair (g->get_object ("between-cols")));
335 maybe_find_prebroken_piece (Grob *g, Direction d)
337 Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
344 next_spaceable_column (vector<Grob*> const &list, vsize starting)
346 for (vsize i = starting+1; i < list.size (); i++)
347 if (!is_loose (list[i]))
352 /* this only returns non-NULL if the line-ending column is the next
353 spaceable-or-breakable column */
355 next_line_ending_column (vector<Grob*> const &list, vsize starting)
357 vsize i = starting + 1;
358 for (; i < list.size ()
359 && is_loose (list[i])
360 && !Paper_column::is_breakable (list[i]);
363 return dynamic_cast<Item*> (list[i])->find_prebroken_piece (LEFT);
367 get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
369 Spring_smob *spring = 0;
371 for (SCM s = this_col->get_object ("ideal-distances");
372 !spring && scm_is_pair (s);
375 Spring_smob *sp = unsmob_spring (scm_car (s));
377 if (sp->other_ == next_col)
382 programming_error (_f ("No spring between column %d and next one",
383 Paper_column::get_rank (this_col)));
385 *ideal = (spring) ? spring->distance_ : 5.0;
386 *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
389 static Column_description
390 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
392 Grob *col = cols[col_index];
394 col = maybe_find_prebroken_piece (col, RIGHT);
396 Column_description description;
397 Grob *next_col = next_spaceable_column (cols, col_index);
399 get_column_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
400 Grob *end_col = next_line_ending_column (cols, col_index);
402 get_column_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
404 for (SCM s = Spaceable_grob::get_minimum_distances (col);
405 scm_is_pair (s); s = scm_cdr (s))
407 Grob *other = unsmob_grob (scm_caar (s));
408 vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index);
411 if (cols[j] == other)
412 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
413 else /* it must end at the LEFT prebroken_piece */
414 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
417 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
418 description.keep_inside_line_ = col->extent (col, X_AXIS);
419 description.break_permission_ = col->get_property ("line-break-permission");
424 get_line_forces (vector<Grob*> const &icols, vector<vsize> breaks,
425 Real line_len, Real indent, bool ragged)
428 force.resize (breaks.size () * breaks.size (), infinity_f);
430 vector<Column_description> cols;
432 SCM force_break = ly_symbol2scm ("force");
434 cols.push_back (Column_description ());
435 for (vsize i = 1; i < icols.size () - 1; i++)
437 if (b < breaks.size () && breaks[b] == i)
439 breaks[b] = cols.size ();
442 if (!is_loose (icols[i]))
443 cols.push_back (get_column_description (icols, i, false));
445 breaks.back () = cols.size () - 1;
447 for (vsize b = 0; b < breaks.size () - 1; b++)
449 cols[breaks[b]] = get_column_description (icols, breaks[b], true);
450 vsize st = breaks[b];
452 for (vsize c = b+1; c < breaks.size (); c++)
454 vsize end = breaks[c];
455 Simple_spacer spacer;
457 for (vsize i = breaks[b]; i < end - 1; i++)
458 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
459 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_);
462 for (vsize i = breaks[b]; i < end; i++)
464 for (vsize r = 0; r < cols[i].rods_.size (); r++)
465 if (cols[i].rods_[r].r_ < end)
466 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
467 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
468 if (cols[i].end_rods_[r].r_ == end)
469 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
470 if (!cols[i].keep_inside_line_.is_empty ())
472 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
473 spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
476 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
477 force[b * breaks.size () + c] = spacer.force ();
479 if (cols[end].break_permission_ == force_break)
483 force[b * breaks.size () + c] = infinity_f;
492 get_line_configuration (vector<Grob*>const &columns,
497 vector<Column_description> cols;
498 Simple_spacer spacer;
499 Column_x_positions ret;
501 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
502 for (vsize i = 1; i < columns.size () - 1; i++)
504 if (is_loose (columns[i]))
505 ret.loose_cols_.push_back (columns[i]);
507 ret.cols_.push_back (columns[i]);
509 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
511 cols.resize (ret.cols_.size () - 1);
513 /* since we've already put our line-ending column in the column list, we can ignore
514 the end_XXX_ fields of our column_description */
515 for (vsize i = 0; i < cols.size (); i++)
517 cols[i] = get_column_description (ret.cols_, i, i == 0);
518 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
520 for (vsize i = 0; i < cols.size (); i++)
522 for (vsize r = 0; r < cols[i].rods_.size (); r++)
523 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
524 if (!cols[i].keep_inside_line_.is_empty ())
526 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
527 spacer.add_rod (0, i, cols[i].keep_inside_line_[LEFT]);
531 spacer.solve (line_len, ragged);
532 ret.force_ = spacer.force ();
535 We used to have a penalty for compression, no matter what, but that
536 fucked up wtk1-fugue2 (taking 3 full pages.)
538 ret.config_ = spacer.spring_positions ();
539 for (vsize i = 0; i < ret.config_.size (); i++)
540 ret.config_[i] += indent;
542 ret.satisfies_constraints_ = spacer.fits ();
545 Check if breaking constraints are met.
547 for (vsize i = 1; i < ret.cols_.size () - 1; i++)
549 SCM p = ret.cols_[i]->get_property ("line-break-permission");
550 if (p == ly_symbol2scm ("force"))
551 ret.satisfies_constraints_ = false;
558 compare_paper_column_rank (Grob *const &a,
561 return Paper_column::get_rank (a) - Paper_column::get_rank (b);