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;
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_));
250 /****************************************************************/
252 Spring_description::Spring_description ()
255 inverse_hooke_ = 0.0;
260 Spring_description::is_sane () const
262 return (inverse_hooke_ >= 0)
264 && !isinf (ideal_) && !isnan (ideal_)
265 && (inverse_hooke_ == 0.0 || fabs (inverse_hooke_) > 1e-8)
270 Spring_description::length (Real f) const
272 return ideal_ + max (f, block_force_) * inverse_hooke_;
275 /****************************************************************/
278 TODO: should a add penalty for widely varying spring forces (caused
287 The ## forces the notes apart; we shouldn't allow the O's to touch
291 struct Rod_description
296 bool operator< (const Rod_description r)
307 Rod_description (vsize r, Real d)
314 struct Column_description
316 vector<Rod_description> rods_;
317 vector<Rod_description> end_rods_; /* use these if they end at the last column of the line */
321 Real end_inverse_hooke_;
322 SCM break_permission_;
323 Interval keep_inside_line_;
325 Column_description ()
330 end_inverse_hooke_ = 0;
331 break_permission_ = SCM_EOL;
338 return (scm_is_pair (g->get_object ("between-cols")));
342 maybe_find_prebroken_piece (Grob *g, Direction d)
344 Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
351 next_spaceable_column (vector<Grob*> const &list, vsize starting)
353 for (vsize i = starting+1; i < list.size (); i++)
354 if (!is_loose (list[i]))
360 get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
362 Spring_smob *spring = 0;
364 for (SCM s = this_col->get_object ("ideal-distances");
365 !spring && scm_is_pair (s);
368 Spring_smob *sp = unsmob_spring (scm_car (s));
370 if (sp->other_ == next_col)
375 programming_error (_f ("No spring between column %d and next one",
376 Paper_column::get_rank (this_col)));
378 *ideal = (spring) ? spring->distance_ : 5.0;
379 *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
382 static Column_description
383 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
385 Grob *col = cols[col_index];
387 col = maybe_find_prebroken_piece (col, RIGHT);
389 Column_description description;
390 Grob *next_col = next_spaceable_column (cols, col_index);
392 get_column_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
393 Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
395 get_column_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
397 for (SCM s = Spaceable_grob::get_minimum_distances (col);
398 scm_is_pair (s); s = scm_cdr (s))
400 Grob *other = unsmob_grob (scm_caar (s));
401 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
404 if (cols[j] == other)
405 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
406 else /* it must end at the LEFT prebroken_piece */
407 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
410 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
411 description.keep_inside_line_ = col->extent (col, X_AXIS);
412 description.break_permission_ = col->get_property ("line-break-permission");
417 get_line_forces (vector<Grob*> const &columns,
418 Real line_len, Real indent, bool ragged)
420 vector<vsize> breaks;
422 vector<Grob*> non_loose;
423 vector<Column_description> cols;
424 SCM force_break = ly_symbol2scm ("force");
426 for (vsize i = 0; i < columns.size (); i++)
427 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
428 non_loose.push_back (columns[i]);
431 breaks.push_back (0);
432 cols.push_back (Column_description ());
433 for (vsize i = 1; i < non_loose.size () - 1; i++)
435 if (Paper_column::is_breakable (non_loose[i]))
436 breaks.push_back (cols.size ());
438 cols.push_back (get_column_description (non_loose, i, false));
440 breaks.push_back (cols.size ());
441 force.resize (breaks.size () * breaks.size (), infinity_f);
443 for (vsize b = 0; b < breaks.size () - 1; b++)
445 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
446 vsize st = breaks[b];
448 for (vsize c = b+1; c < breaks.size (); c++)
450 vsize end = breaks[c];
451 Simple_spacer spacer;
453 for (vsize i = breaks[b]; i < end - 1; i++)
454 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
455 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].end_inverse_hooke_);
458 for (vsize i = breaks[b]; i < end; i++)
460 for (vsize r = 0; r < cols[i].rods_.size (); r++)
461 if (cols[i].rods_[r].r_ < end)
462 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
463 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
464 if (cols[i].end_rods_[r].r_ == end)
465 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
466 if (!cols[i].keep_inside_line_.is_empty ())
468 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
469 spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
472 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
474 /* add a (convex) penalty for compression. We do this _only_ in get_line_forces,
475 not get_line_configuration. This is temporary, for backwards compatibility;
476 the old line/page-breaking stuff ignores page breaks when it calculates line
477 breaks, so compression penalties can result in scores (eg. wtk-fugue) blowing
478 up to too many pages. */
479 Real f = spacer.force ();
480 force[b * breaks.size () + c] = f - (f < 0 ? f*f*f*f*4 : 0);
482 if (end < cols.size () && cols[end].break_permission_ == force_break)
487 force[b * breaks.size () + c] = -200000;
489 force[b * breaks.size () + c] = infinity_f;
498 get_line_configuration (vector<Grob*> const &columns,
503 vector<Column_description> cols;
504 Simple_spacer spacer;
505 Column_x_positions ret;
507 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
508 for (vsize i = 1; i < columns.size () - 1; i++)
510 if (is_loose (columns[i]))
511 ret.loose_cols_.push_back (columns[i]);
513 ret.cols_.push_back (columns[i]);
515 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
517 /* since we've already put our line-ending column in the column list, we can ignore
518 the end_XXX_ fields of our column_description */
519 for (vsize i = 0; i < ret.cols_.size () - 1; i++)
521 cols.push_back (get_column_description (ret.cols_, i, i == 0));
522 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
524 for (vsize i = 0; i < cols.size (); i++)
526 for (vsize r = 0; r < cols[i].rods_.size (); r++)
527 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
529 if (!cols[i].keep_inside_line_.is_empty ())
531 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
532 spacer.add_rod (0, i, cols[i].keep_inside_line_[LEFT]);
536 spacer.solve (line_len, ragged);
537 ret.force_ = spacer.force ();
540 We used to have a penalty for compression, no matter what, but that
541 fucked up wtk1-fugue2 (taking 3 full pages.)
543 ret.config_ = spacer.spring_positions ();
544 for (vsize i = 0; i < ret.config_.size (); i++)
545 ret.config_[i] += indent;
547 ret.satisfies_constraints_ = spacer.fits ();
550 Check if breaking constraints are met.
552 for (vsize i = 1; i < ret.cols_.size () - 1; i++)
554 SCM p = ret.cols_[i]->get_property ("line-break-permission");
555 if (p == ly_symbol2scm ("force"))
556 ret.satisfies_constraints_ = false;