2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
9 - add support for different stretch/shrink constants?
14 #include "libc-extension.hh" // isinf
15 #include "simple-spacer.hh"
16 #include "paper-column.hh"
19 #include "column-x-positions.hh"
20 #include "spaceable-grob.hh"
21 #include "dimensions.hh"
24 A simple spacing constraint solver. The approach:
26 Stretch the line uniformly until none of the constraints (rods)
27 block. It then is very wide.
29 Compress until the next constraint blocks,
31 Mark the springs over the constrained part to be non-active.
33 Repeat with the smaller set of non-active constraints, until all
34 constraints blocked, or until the line is as short as desired.
36 This is much simpler, and much much faster than full scale
37 Constrained QP. On the other hand, a situation like this will not
38 be typeset as dense as possible, because
41 veryveryverylongsyllable2 veryveryverylongsyllable2
42 " "4 veryveryverylongsyllable2 syllable4
45 can be further compressed to
49 veryveryverylongsyllable2 veryveryverylongsyllable2
50 " "4 veryveryverylongsyllable2 syllable4
53 Perhaps this is not a bad thing, because the 1st looks better anyway. */
56 positive force = expanding, negative force = compressing.
59 Simple_spacer::Simple_spacer ()
62 Give an extra penalty for compression. Needed to avoid compressing
68 default_space_ = 20 PT;
72 Simple_spacer::add_rod (int l, int r, Real dist)
74 if (isinf (dist) || isnan (dist))
76 programming_error ("ignoring weird minimum distance");
80 Real c = range_stiffness (l, r);
84 If a spring is fixed, we have to do something here:
85 we let the rod override the spring.
88 for (int i = l; i < r; i++)
89 total_dist += springs_[i].ideal_;
91 if (total_dist < dist)
92 for (int i = l; i < r; i++)
93 springs_[i].ideal_ *= dist / total_dist;
98 Real d = range_ideal_len (l, r);
99 Real block_stretch = dist - d;
101 Real block_force = c * block_stretch;
102 force_ = max (force_, block_force);
104 for (int i = l; i < r; i++)
105 springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
109 Simple_spacer::range_ideal_len (int l, int r) const
112 for (int i = l; i < r; i++)
113 d += springs_[i].ideal_;
118 Simple_spacer::range_stiffness (int l, int r) const
121 for (int i = l; i < r; i++)
123 if (springs_[i].is_active_)
124 den += 1 * springs_[i].inverse_hooke_;
131 Simple_spacer::active_blocking_force () const
133 Real bf = -infinity_f;
134 for (int i = 0; i < springs_.size (); i++)
135 if (springs_[i].is_active_)
136 bf = max (bf, springs_[i].block_force_);
141 Simple_spacer::active_springs_stiffness () const
143 Real stiff = range_stiffness (0, springs_.size ());
147 all springs are inactive. Take the stiffness of the
148 latest spring to block.
151 Real max_block_force = -infinity_f;
153 for (int i = 0; i < springs_.size (); i++)
155 if (springs_[i].block_force_ > max_block_force)
158 max_block_force = springs_[i].block_force_;
162 stiff = 1/springs_[max_i].inverse_hooke_;
168 Simple_spacer::set_active_states ()
170 /* float comparison is safe, since force is only copied. */
171 for (int i = 0; i < springs_.size (); i++)
172 if (springs_[i].is_active_
173 && springs_[i].block_force_ >= force_)
175 springs_[i].is_active_ = false;
181 Simple_spacer::configuration_length () const
184 for (int i = 0; i < springs_.size (); i++)
185 l += springs_[i].length (force_);
191 Simple_spacer::is_active () const
193 return active_count_;
197 Simple_spacer::my_solve_linelen ()
201 force_ = active_blocking_force ();
202 Real conf = configuration_length ();
204 if (conf < line_len_)
206 force_ += (line_len_ - conf) * active_springs_stiffness ();
210 set_active_states ();
215 Simple_spacer::my_solve_natural_len ()
217 Real line_len_force = 0.0;
221 force_ = max (active_blocking_force (), 0.0);
222 Real conf = configuration_length ();
224 if (conf < line_len_)
226 line_len_force = force_
228 * active_springs_stiffness ();
231 if (force_ < 1e-8) // ugh.,
234 set_active_states ();
237 force_ = line_len_force;
240 /****************************************************************/
242 Spring_description::Spring_description ()
245 inverse_hooke_ = 0.0;
251 Spring_description::is_sane () const
253 return (inverse_hooke_ >= 0)
255 && !isinf (ideal_) && !isnan (ideal_);
259 Spring_description::length (Real f) const
263 return ideal_ + f * inverse_hooke_;
265 /****************************************************************/
268 TODO: should a add penalty for widely varying spring forces (caused
277 The ## forces the notes apart; we shouldn't allow the O's to touch
281 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
284 spacer_->my_solve_natural_len ();
286 spacer_->my_solve_linelen ();
288 positions->force_ = spacer_->force_;
291 We used to have a penalty for compression, no matter what, but that
292 fucked up wtk1-fugue2 (taking 3 full pages.)
294 positions->config_.push (spacer_->indent_);
295 for (int i = 0; i < spacer_->springs_.size (); i++)
297 Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
298 positions->config_.push (positions->config_.top () + l);
300 we have l>= 0 here, up to rounding errors
305 For raggedright, we must have a measure of music density: this is
306 to prevent lots of short lines (which all have force = 0).
310 positions->satisfies_constraints_
311 = positions->config_.top () < spacer_->line_len_;
314 positions->satisfies_constraints_ = spacer_->is_active ();
316 positions->cols_ = spaced_cols_;
317 positions->loose_cols_ = loose_cols_;
320 Check if breaking constraints are met.
322 bool break_satisfy = true;
323 int sz = positions->cols_.size ();
324 for (int i = sz; i--;)
326 SCM p = positions->cols_[i]->get_property ("penalty");
327 if (scm_is_number (p))
329 if (scm_to_double (p) < -9999)
330 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
331 if (scm_to_double (p) > 9999)
332 break_satisfy = break_satisfy && ! (i == 0 || i == sz -1);
336 positions->satisfies_constraints_
337 = positions->satisfies_constraints_ && break_satisfy;
341 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
343 Spring_description desc;
346 desc.inverse_hooke_ = inverse_hooke;
347 if (!desc.is_sane ())
349 programming_error ("insane spring found, setting to unit");
351 desc.inverse_hooke_ = 1.0;
356 desc.is_active_ = false;
362 desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_;
363 // block at distance 0
367 springs_.push (desc);
371 compare_paper_column_rank (Grob *const &a,
374 return Paper_column::get_rank (a) - Paper_column::get_rank (b);
378 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
380 Link_array<Grob> cols (icols);
383 for (int i = 0; i < icols.size (); i++)
384 if (scm_is_pair (icols[i]->get_object ("between-cols")))
385 loose_cols_.push (icols[i]);
387 cols.push (icols[i]);
390 for (int i = 0; i < cols.size () - 1; i++)
392 Spring_smob *spring = 0;
394 for (SCM s = cols[i]->get_object ("ideal-distances");
395 !spring && scm_is_pair (s);
398 Spring_smob *sp = unsmob_spring (scm_car (s));
400 if (sp->other_ == cols[i + 1])
405 programming_error (_f ("No spring between column %d and next one",
406 Paper_column::get_rank (cols[i])));
408 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
409 Real inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0;
411 spacer_->add_spring (ideal, inverse_hooke);
414 for (int i = 0; i < cols.size () - 1; i++)
416 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
417 scm_is_pair (s); s = scm_cdr (s))
419 Grob *other = unsmob_grob (scm_caar (s));
420 int j = binsearch_links (cols, other, &compare_paper_column_rank);
421 if (j >= 0 && cols[j] == other)
422 spacer_->add_rod (i, j, scm_to_double (scm_cdar (s)));
426 && to_boolean (cols[i]->get_property ("keep-inside-line")))
428 Interval e = cols[i]->extent (cols[i], X_AXIS);
431 spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
432 spacer_->add_rod (0, i, e[LEFT]);
438 Simple_spacer_wrapper::Simple_spacer_wrapper ()
440 spacer_ = new Simple_spacer ();
443 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
448 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)