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 ()
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;
153 fits_ = configuration_length (force_) <= line_len_;
154 /* we need to calculate a force here to prevent a bunch of short lines */
156 force_ = expand_line ();
158 else if (conf < line_len_)
159 force_ = expand_line ();
160 else if (conf > line_len_)
161 force_ = compress_line ();
165 Simple_spacer::expand_line ()
167 double inv_hooke = 0;
168 double cur_len = configuration_length (force_);
171 for (vsize i=0; i < springs_.size (); i++)
172 inv_hooke += springs_[i].inverse_hooke_;
174 assert (cur_len <= line_len_);
175 return (line_len_ - cur_len) / inv_hooke + force_;
179 Simple_spacer::compress_line ()
181 double inv_hooke = 0;
182 double cur_len = configuration_length (force_);
183 double cur_force = force_;
186 for (vsize i=0; i < springs_.size (); i++)
187 inv_hooke += springs_[i].inverse_hooke_;
189 assert (line_len_ <= cur_len);
191 vector<Spring_description> sorted_springs = springs_;
192 sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring_description> ());
193 for (vsize i = 0; i < sorted_springs.size (); i++)
195 Spring_description sp = sorted_springs[i];
197 assert (sp.block_force_ <= cur_force);
198 if (isinf (sp.block_force_))
201 double block_dist = (cur_force - sp.block_force_) * inv_hooke;
202 if (cur_len - block_dist < line_len_)
204 cur_force += (line_len_ - cur_len) / inv_hooke;
210 assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
214 cur_len -= block_dist;
215 inv_hooke -= sp.inverse_hooke_;
216 cur_force = sp.block_force_;
224 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
226 Spring_description description;
228 description.ideal_ = ideal;
229 description.inverse_hooke_ = inverse_hooke;
230 if (!description.is_sane ())
232 programming_error ("insane spring found, setting to unit");
234 description.inverse_hooke_ = 1.0;
235 description.ideal_ = 1.0;
238 description.block_force_ = -description.ideal_ / description.inverse_hooke_;
239 // block at distance 0
241 springs_.push_back (description);
245 Simple_spacer::spring_positions () const
250 for (vsize i = 0; i < springs_.size (); i++)
251 ret.push_back (ret.back () + springs_[i].length (ragged_ ? 0.0 : force_));
255 /****************************************************************/
257 Spring_description::Spring_description ()
260 inverse_hooke_ = 0.0;
265 Spring_description::is_sane () const
267 return (inverse_hooke_ >= 0)
269 && !isinf (ideal_) && !isnan (ideal_)
270 && (inverse_hooke_ == 0.0 || fabs (inverse_hooke_) > 1e-8)
275 Spring_description::length (Real f) const
277 return ideal_ + max (f, block_force_) * inverse_hooke_;
280 /****************************************************************/
283 TODO: should a add penalty for widely varying spring forces (caused
292 The ## forces the notes apart; we shouldn't allow the O's to touch
296 struct Rod_description
301 bool operator< (const Rod_description r)
312 Rod_description (vsize r, Real d)
319 struct Column_description
321 vector<Rod_description> rods_;
322 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
326 Real end_inverse_hooke_;
327 SCM break_permission_;
328 Interval keep_inside_line_;
330 Column_description ()
335 end_inverse_hooke_ = 0;
336 break_permission_ = SCM_EOL;
340 static int compare_paper_column_rank (Grob *const &a, Grob *const &b);
345 return (scm_is_pair (g->get_object ("between-cols")));
349 maybe_find_prebroken_piece (Grob *g, Direction d)
351 Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
358 next_spaceable_column (vector<Grob*> const &list, vsize starting)
360 for (vsize i = starting+1; i < list.size (); i++)
361 if (!is_loose (list[i]))
366 /* this only returns non-NULL if the line-ending column is the next
367 spaceable-or-breakable column */
369 next_line_ending_column (vector<Grob*> const &list, vsize starting)
371 vsize i = starting + 1;
372 for (; i < list.size ()
373 && is_loose (list[i])
374 && !Paper_column::is_breakable (list[i]);
377 return dynamic_cast<Item*> (list[i])->find_prebroken_piece (LEFT);
381 get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
383 Spring_smob *spring = 0;
385 for (SCM s = this_col->get_object ("ideal-distances");
386 !spring && scm_is_pair (s);
389 Spring_smob *sp = unsmob_spring (scm_car (s));
391 if (sp->other_ == next_col)
396 programming_error (_f ("No spring between column %d and next one",
397 Paper_column::get_rank (this_col)));
399 *ideal = (spring) ? spring->distance_ : 5.0;
400 *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
403 static Column_description
404 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
406 Grob *col = cols[col_index];
408 col = maybe_find_prebroken_piece (col, RIGHT);
410 Column_description description;
411 Grob *next_col = next_spaceable_column (cols, col_index);
413 get_column_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
414 Grob *end_col = next_line_ending_column (cols, col_index);
416 get_column_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
418 for (SCM s = Spaceable_grob::get_minimum_distances (col);
419 scm_is_pair (s); s = scm_cdr (s))
421 Grob *other = unsmob_grob (scm_caar (s));
422 vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index);
425 if (cols[j] == other)
426 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
427 else /* it must end at the LEFT prebroken_piece */
428 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
431 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
432 description.keep_inside_line_ = col->extent (col, X_AXIS);
433 description.break_permission_ = col->get_property ("line-break-permission");
438 get_line_forces (vector<Grob*> const &icols, vector<vsize> breaks,
439 Real line_len, Real indent, bool ragged)
442 force.resize (breaks.size () * breaks.size (), infinity_f);
444 vector<Column_description> cols;
446 SCM force_break = ly_symbol2scm ("force");
448 cols.push_back (Column_description ());
449 for (vsize i = 1; i < icols.size () - 1; i++)
451 if (b < breaks.size () && breaks[b] == i)
453 breaks[b] = cols.size ();
456 if (!is_loose (icols[i]))
457 cols.push_back (get_column_description (icols, i, false));
459 breaks.back () = cols.size () - 1;
461 for (vsize b = 0; b < breaks.size () - 1; b++)
463 cols[breaks[b]] = get_column_description (icols, breaks[b], true);
464 vsize st = breaks[b];
466 for (vsize c = b+1; c < breaks.size (); c++)
468 vsize end = breaks[c];
469 Simple_spacer spacer;
471 for (vsize i = breaks[b]; i < end - 1; i++)
472 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
473 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_);
476 for (vsize i = breaks[b]; i < end; i++)
478 for (vsize r = 0; r < cols[i].rods_.size (); r++)
479 if (cols[i].rods_[r].r_ < end)
480 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
481 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
482 if (cols[i].end_rods_[r].r_ == end)
483 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
484 if (!cols[i].keep_inside_line_.is_empty ())
486 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
487 spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
490 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
491 force[b * breaks.size () + c] = spacer.force ();
493 if (cols[end].break_permission_ == force_break)
497 force[b * breaks.size () + c] = infinity_f;
506 get_line_configuration (vector<Grob*> const &columns,
511 vector<Column_description> cols;
512 Simple_spacer spacer;
513 Column_x_positions ret;
515 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
516 for (vsize i = 1; i < columns.size () - 1; i++)
518 if (is_loose (columns[i]))
519 ret.loose_cols_.push_back (columns[i]);
521 ret.cols_.push_back (columns[i]);
523 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
525 /* since we've already put our line-ending column in the column list, we can ignore
526 the end_XXX_ fields of our column_description */
527 for (vsize i = 0; i < ret.cols_.size () - 1; i++)
529 cols.push_back (get_column_description (ret.cols_, i, i == 0));
530 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
532 for (vsize i = 0; i < cols.size (); i++)
534 for (vsize r = 0; r < cols[i].rods_.size (); r++)
535 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
536 if (!cols[i].keep_inside_line_.is_empty ())
538 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
539 spacer.add_rod (0, i, cols[i].keep_inside_line_[LEFT]);
543 spacer.solve (line_len, ragged);
544 ret.force_ = spacer.force ();
547 We used to have a penalty for compression, no matter what, but that
548 fucked up wtk1-fugue2 (taking 3 full pages.)
550 ret.config_ = spacer.spring_positions ();
551 for (vsize i = 0; i < ret.config_.size (); i++)
552 ret.config_[i] += indent;
554 ret.satisfies_constraints_ = spacer.fits ();
557 Check if breaking constraints are met.
559 for (vsize i = 1; i < ret.cols_.size () - 1; i++)
561 SCM p = ret.cols_[i]->get_property ("line-break-permission");
562 if (p == ly_symbol2scm ("force"))
563 ret.satisfies_constraints_ = false;
570 compare_paper_column_rank (Grob *const &a,
573 return Paper_column::get_rank (a) - Paper_column::get_rank (b);