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;
335 static int compare_paper_column_rank (Grob *const &a, Grob *const &b);
340 return (scm_is_pair (g->get_object ("between-cols")));
344 maybe_find_prebroken_piece (Grob *g, Direction d)
346 Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
353 next_spaceable_column (vector<Grob*> const &list, vsize starting)
355 for (vsize i = starting+1; i < list.size (); i++)
356 if (!is_loose (list[i]))
361 /* this only returns non-NULL if the line-ending column is the next
362 spaceable-or-breakable column */
364 next_line_ending_column (vector<Grob*> const &list, vsize starting)
366 vsize i = starting + 1;
367 for (; i < list.size ()
368 && is_loose (list[i])
369 && !Paper_column::is_breakable (list[i]);
372 return dynamic_cast<Item*> (list[i])->find_prebroken_piece (LEFT);
376 get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
378 Spring_smob *spring = 0;
380 for (SCM s = this_col->get_object ("ideal-distances");
381 !spring && scm_is_pair (s);
384 Spring_smob *sp = unsmob_spring (scm_car (s));
386 if (sp->other_ == next_col)
391 programming_error (_f ("No spring between column %d and next one",
392 Paper_column::get_rank (this_col)));
394 *ideal = (spring) ? spring->distance_ : 5.0;
395 *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
398 static Column_description
399 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
401 Grob *col = cols[col_index];
403 col = maybe_find_prebroken_piece (col, RIGHT);
405 Column_description description;
406 Grob *next_col = next_spaceable_column (cols, col_index);
408 get_column_spring (col, next_col, &description.ideal_, &description.inverse_hooke_);
409 Grob *end_col = next_line_ending_column (cols, col_index);
411 get_column_spring (col, end_col, &description.end_ideal_, &description.end_inverse_hooke_);
413 for (SCM s = Spaceable_grob::get_minimum_distances (col);
414 scm_is_pair (s); s = scm_cdr (s))
416 Grob *other = unsmob_grob (scm_caar (s));
417 vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index);
420 if (cols[j] == other)
421 description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
422 else /* it must end at the LEFT prebroken_piece */
423 description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
426 if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
427 description.keep_inside_line_ = col->extent (col, X_AXIS);
428 description.break_permission_ = col->get_property ("line-break-permission");
433 get_line_forces (vector<Grob*> const &icols, vector<vsize> breaks,
434 Real line_len, Real indent, bool ragged)
437 force.resize (breaks.size () * breaks.size (), infinity_f);
439 vector<Column_description> cols;
441 SCM force_break = ly_symbol2scm ("force");
443 cols.push_back (Column_description ());
444 for (vsize i = 1; i < icols.size () - 1; i++)
446 if (b < breaks.size () && breaks[b] == i)
448 breaks[b] = cols.size ();
451 if (!is_loose (icols[i]))
452 cols.push_back (get_column_description (icols, i, false));
454 breaks.back () = cols.size ();
456 for (vsize b = 0; b < breaks.size () - 1; b++)
458 cols[breaks[b]] = get_column_description (icols, breaks[b], true);
459 vsize st = breaks[b];
461 for (vsize c = b+1; c < breaks.size (); c++)
463 vsize end = breaks[c];
464 Simple_spacer spacer;
466 for (vsize i = breaks[b]; i < end - 1; i++)
467 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
468 spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_);
471 for (vsize i = breaks[b]; i < end; i++)
473 for (vsize r = 0; r < cols[i].rods_.size (); r++)
474 if (cols[i].rods_[r].r_ < end)
475 spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
476 for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
477 if (cols[i].end_rods_[r].r_ == end)
478 spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
479 if (!cols[i].keep_inside_line_.is_empty ())
481 spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
482 spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
485 spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
487 /* add a (convex) penalty for compression. We do this _only_ in get_line_forces,
488 not get_line_configuration. This is temporary, for backwards compatibility;
489 the old line/page-breaking stuff ignores page breaks when it calculates line
490 breaks, so compression penalties can result in scores (eg. wtk-fugue) blowing
491 up to too many pages. */
492 Real f = spacer.force ();
493 force[b * breaks.size () + c] = f - (f < 0 ? f*f*6 : 0);
495 if (end < cols.size () && cols[end].break_permission_ == force_break)
499 force[b * breaks.size () + c] = infinity_f;
508 get_line_configuration (vector<Grob*> const &columns,
513 vector<Column_description> cols;
514 Simple_spacer spacer;
515 Column_x_positions ret;
517 ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
518 for (vsize i = 1; i < columns.size () - 1; i++)
520 if (is_loose (columns[i]))
521 ret.loose_cols_.push_back (columns[i]);
523 ret.cols_.push_back (columns[i]);
525 ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
527 /* since we've already put our line-ending column in the column list, we can ignore
528 the end_XXX_ fields of our column_description */
529 for (vsize i = 0; i < ret.cols_.size () - 1; i++)
531 cols.push_back (get_column_description (ret.cols_, i, i == 0));
532 spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
534 for (vsize i = 0; i < cols.size (); i++)
536 for (vsize r = 0; r < cols[i].rods_.size (); r++)
537 spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
538 if (!cols[i].keep_inside_line_.is_empty ())
540 spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
541 spacer.add_rod (0, i, cols[i].keep_inside_line_[LEFT]);
545 spacer.solve (line_len, ragged);
546 ret.force_ = spacer.force ();
549 We used to have a penalty for compression, no matter what, but that
550 fucked up wtk1-fugue2 (taking 3 full pages.)
552 ret.config_ = spacer.spring_positions ();
553 for (vsize i = 0; i < ret.config_.size (); i++)
554 ret.config_[i] += indent;
556 ret.satisfies_constraints_ = spacer.fits ();
559 Check if breaking constraints are met.
561 for (vsize i = 1; i < ret.cols_.size () - 1; i++)
563 SCM p = ret.cols_[i]->get_property ("line-break-permission");
564 if (p == ly_symbol2scm ("force"))
565 ret.satisfies_constraints_ = false;
572 compare_paper_column_rank (Grob *const &a,
575 return Paper_column::get_rank (a) - Paper_column::get_rank (b);