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_));
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]))
359 static Column_description
360 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
362 Grob *col = cols[col_index];
364 col = maybe_find_prebroken_piece (col, RIGHT);
366 Column_description description;
367 Grob *next_col = next_spaceable_column (cols, col_index);
369 Spaceable_grob::get_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
370 Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
372 Spaceable_grob::get_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
374 for (SCM s = Spaceable_grob::get_minimum_distances (col);
375 scm_is_pair (s); s = scm_cdr (s))
377 Grob *other = unsmob_grob (scm_caar (s));
378 vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
381 if (cols[j] == other)
382 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
383 else /* it must end at the LEFT prebroken_piece */
384 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
388 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
389 description.keep_inside_line_ = col->extent (col, X_AXIS);
391 description.break_permission_ = col->get_property ("line-break-permission");
396 get_line_forces (vector<Grob*> const &columns,
397 Real line_len, Real indent, bool ragged)
399 vector<vsize> breaks;
401 vector<Grob*> non_loose;
402 vector<Column_description> cols;
403 SCM force_break = ly_symbol2scm ("force");
405 for (vsize i = 0; i < columns.size (); i++)
406 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
407 non_loose.push_back (columns[i]);
410 breaks.push_back (0);
411 cols.push_back (Column_description ());
412 for (vsize i = 1; i + 1 < non_loose.size (); i++)
414 if (Paper_column::is_breakable (non_loose[i]))
415 breaks.push_back (cols.size ());
417 cols.push_back (get_column_description (non_loose, i, false));
419 breaks.push_back (cols.size ());
420 force.resize (breaks.size () * breaks.size (), infinity_f);
422 for (vsize b = 0; b + 1 < breaks.size (); b++)
424 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
425 vsize st = breaks[b];
427 for (vsize c = b+1; c < breaks.size (); c++)
429 vsize end = breaks[c];
430 Simple_spacer spacer;
432 for (vsize i = breaks[b]; i < end - 1; i++)
433 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
434 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].end_inverse_hooke_);
437 for (vsize i = breaks[b]; i < end; i++)
439 for (vsize r = 0; r < cols[i].rods_.size (); r++)
440 if (cols[i].rods_[r].r_ < end)
441 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
442 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
443 if (cols[i].end_rods_[r].r_ == end)
444 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
445 if (!cols[i].keep_inside_line_.is_empty ())
447 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
448 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
451 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
453 /* add a (convex) penalty for compression. We do this _only_ in get_line_forces,
454 not get_line_configuration. This is temporary, for backwards compatibility;
455 the old line/page-breaking stuff ignores page breaks when it calculates line
456 breaks, so compression penalties can result in scores (eg. wtk-fugue) blowing
457 up to too many pages. */
458 Real f = spacer.force ();
459 force[b * breaks.size () + c] = f - (f < 0 ? f*f*f*f*4 : 0);
464 force[b * breaks.size () + c] = -200000;
466 force[b * breaks.size () + c] = infinity_f;
469 if (end < cols.size () && cols[end].break_permission_ == force_break)
477 get_line_configuration (vector<Grob*> const &columns,
482 vector<Column_description> cols;
483 Simple_spacer spacer;
484 Column_x_positions ret;
486 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
487 for (vsize i = 1; i + 1 < columns.size (); i++)
489 if (is_loose (columns[i]))
490 ret.loose_cols_.push_back (columns[i]);
492 ret.cols_.push_back (columns[i]);
494 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
496 /* since we've already put our line-ending column in the column list, we can ignore
497 the end_XXX_ fields of our column_description */
498 for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
500 cols.push_back (get_column_description (ret.cols_, i, i == 0));
501 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
503 for (vsize i = 0; i < cols.size (); i++)
505 for (vsize r = 0; r < cols[i].rods_.size (); r++)
506 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
508 if (!cols[i].keep_inside_line_.is_empty ())
510 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
511 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
515 spacer.solve (line_len, ragged);
516 ret.force_ = spacer.force ();
519 We used to have a penalty for compression, no matter what, but that
520 fucked up wtk1-fugue2 (taking 3 full pages.)
522 ret.config_ = spacer.spring_positions ();
523 for (vsize i = 0; i < ret.config_.size (); i++)
524 ret.config_[i] += indent;
526 ret.satisfies_constraints_ = spacer.fits ();
529 Check if breaking constraints are met.
531 for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
533 SCM p = ret.cols_[i]->get_property ("line-break-permission");
534 if (p == ly_symbol2scm ("force"))
535 ret.satisfies_constraints_ = false;