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))));
411 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
412 description.keep_inside_line_ = col->extent (col, X_AXIS);
414 description.break_permission_ = col->get_property ("line-break-permission");
419 get_line_forces (vector<Grob*> const &columns,
420 Real line_len, Real indent, bool ragged)
422 vector<vsize> breaks;
424 vector<Grob*> non_loose;
425 vector<Column_description> cols;
426 SCM force_break = ly_symbol2scm ("force");
428 for (vsize i = 0; i < columns.size (); i++)
429 if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
430 non_loose.push_back (columns[i]);
433 breaks.push_back (0);
434 cols.push_back (Column_description ());
435 for (vsize i = 1; i < non_loose.size () - 1; i++)
437 if (Paper_column::is_breakable (non_loose[i]))
438 breaks.push_back (cols.size ());
440 cols.push_back (get_column_description (non_loose, i, false));
442 breaks.push_back (cols.size ());
443 force.resize (breaks.size () * breaks.size (), infinity_f);
445 for (vsize b = 0; b < breaks.size () - 1; b++)
447 cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
448 vsize st = breaks[b];
450 for (vsize c = b+1; c < breaks.size (); c++)
452 vsize end = breaks[c];
453 Simple_spacer spacer;
455 for (vsize i = breaks[b]; i < end - 1; i++)
456 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
457 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].end_inverse_hooke_);
460 for (vsize i = breaks[b]; i < end; i++)
462 for (vsize r = 0; r < cols[i].rods_.size (); r++)
463 if (cols[i].rods_[r].r_ < end)
464 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
465 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
466 if (cols[i].end_rods_[r].r_ == end)
467 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
468 if (!cols[i].keep_inside_line_.is_empty ())
470 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
471 spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
474 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
476 /* add a (convex) penalty for compression. We do this _only_ in get_line_forces,
477 not get_line_configuration. This is temporary, for backwards compatibility;
478 the old line/page-breaking stuff ignores page breaks when it calculates line
479 breaks, so compression penalties can result in scores (eg. wtk-fugue) blowing
480 up to too many pages. */
481 Real f = spacer.force ();
482 force[b * breaks.size () + c] = f - (f < 0 ? f*f*f*f*4 : 0);
487 force[b * breaks.size () + c] = -200000;
489 force[b * breaks.size () + c] = infinity_f;
492 if (end < cols.size () && cols[end].break_permission_ == force_break)
500 get_line_configuration (vector<Grob*> const &columns,
505 vector<Column_description> cols;
506 Simple_spacer spacer;
507 Column_x_positions ret;
509 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
510 for (vsize i = 1; i < columns.size () - 1; i++)
512 if (is_loose (columns[i]))
513 ret.loose_cols_.push_back (columns[i]);
515 ret.cols_.push_back (columns[i]);
517 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
519 /* since we've already put our line-ending column in the column list, we can ignore
520 the end_XXX_ fields of our column_description */
521 for (vsize i = 0; i < ret.cols_.size () - 1; i++)
523 cols.push_back (get_column_description (ret.cols_, i, i == 0));
524 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
526 for (vsize i = 0; i < cols.size (); i++)
528 for (vsize r = 0; r < cols[i].rods_.size (); r++)
529 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
531 if (!cols[i].keep_inside_line_.is_empty ())
533 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
534 spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
538 spacer.solve (line_len, ragged);
539 ret.force_ = spacer.force ();
542 We used to have a penalty for compression, no matter what, but that
543 fucked up wtk1-fugue2 (taking 3 full pages.)
545 ret.config_ = spacer.spring_positions ();
546 for (vsize i = 0; i < ret.config_.size (); i++)
547 ret.config_[i] += indent;
549 ret.satisfies_constraints_ = spacer.fits ();
552 Check if breaking constraints are met.
554 for (vsize i = 1; i < ret.cols_.size () - 1; i++)
556 SCM p = ret.cols_[i]->get_property ("line-break-permission");
557 if (p == ly_symbol2scm ("force"))
558 ret.satisfies_constraints_ = false;