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?
15 #include "libc-extension.hh" // isinf
16 #include "simple-spacer.hh"
17 #include "paper-column.hh"
20 #include "column-x-positions.hh"
21 #include "spaceable-grob.hh"
22 #include "dimensions.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 ()
63 Give an extra penalty for compression. Needed to avoid compressing
69 default_space_ = 20 PT;
73 Simple_spacer::add_rod (int l, int r, Real dist)
75 if (isinf (dist) || isnan (dist))
77 programming_error ("ignoring weird minimum distance");
81 Real c = range_stiffness (l, r);
85 If a spring is fixed, we have to do something here:
86 we let the rod override the spring.
89 for (int i = l; i < r; i++)
90 total_dist += springs_[i].ideal_;
92 if (total_dist < dist)
93 for (int i = l; i < r; i++)
94 springs_[i].ideal_ *= dist / total_dist;
99 Real d = range_ideal_len (l, r);
100 Real block_stretch = dist - d;
102 Real block_force = c * block_stretch;
103 force_ = max (force_, block_force);
105 for (int i = l; i < r; i++)
106 springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
110 Simple_spacer::range_ideal_len (int l, int r) const
113 for (int i = l; i < r; i++)
114 d += springs_[i].ideal_;
119 Simple_spacer::range_stiffness (int l, int r) const
122 for (int i = l; i < r; i++)
124 if (springs_[i].is_active_)
125 den += 1 * springs_[i].inverse_hooke_;
132 Simple_spacer::active_blocking_force () const
134 Real bf = -infinity_f;
135 for (int i = 0; i < springs_.size (); i++)
136 if (springs_[i].is_active_)
137 bf = max (bf, springs_[i].block_force_);
142 Simple_spacer::active_springs_stiffness () const
144 Real stiff = range_stiffness (0, springs_.size ());
148 all springs are inactive. Take the stiffness of the
149 latest spring to block.
152 Real max_block_force = -infinity_f;
154 for (int i = 0; i < springs_.size (); i++)
156 if (springs_[i].block_force_ > max_block_force)
159 max_block_force = springs_[i].block_force_;
163 stiff = 1/springs_[max_i].inverse_hooke_;
169 Simple_spacer::set_active_states ()
171 /* float comparison is safe, since force is only copied. */
172 for (int i = 0; i < springs_.size (); i++)
173 if (springs_[i].is_active_
174 && springs_[i].block_force_ >= force_)
176 springs_[i].is_active_ = false;
182 Simple_spacer::configuration_length () const
185 for (int i = 0; i < springs_.size (); i++)
186 l += springs_[i].length (force_);
192 Simple_spacer::is_active () const
194 return active_count_;
198 Simple_spacer::my_solve_linelen ()
202 force_ = active_blocking_force ();
203 Real conf = configuration_length ();
205 if (conf < line_len_)
207 force_ += (line_len_ - conf) * active_springs_stiffness ();
211 set_active_states ();
216 Simple_spacer::my_solve_natural_len ()
218 Real line_len_force = 0.0;
222 force_ = max (active_blocking_force (), 0.0);
223 Real conf = configuration_length ();
225 if (conf < line_len_)
227 line_len_force = force_
229 * active_springs_stiffness ();
232 if (force_ < 1e-8) // ugh.,
235 set_active_states ();
238 force_ = line_len_force;
241 /****************************************************************/
243 Spring_description::Spring_description ()
246 inverse_hooke_ = 0.0;
252 Spring_description::is_sane () const
254 return (inverse_hooke_ >= 0)
256 && !isinf (ideal_) && !isnan (ideal_);
260 Spring_description::length (Real f) const
264 return ideal_ + f * inverse_hooke_;
266 /****************************************************************/
269 TODO: should a add penalty for widely varying spring forces (caused
278 The ## forces the notes apart; we shouldn't allow the O's to touch
282 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
285 spacer_->my_solve_natural_len ();
287 spacer_->my_solve_linelen ();
289 positions->force_ = spacer_->force_;
292 We used to have a penalty for compression, no matter what, but that
293 fucked up wtk1-fugue2 (taking 3 full pages.)
295 positions->config_.push (spacer_->indent_);
296 for (int i = 0; i < spacer_->springs_.size (); i++)
298 Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
299 positions->config_.push (positions->config_.top () + l);
301 we have l>= 0 here, up to rounding errors
306 For raggedright, we must have a measure of music density: this is
307 to prevent lots of short lines (which all have force = 0).
311 positions->satisfies_constraints_
312 = positions->config_.top () < spacer_->line_len_;
315 positions->satisfies_constraints_ = spacer_->is_active ();
317 positions->cols_ = spaced_cols_;
318 positions->loose_cols_ = loose_cols_;
321 Check if breaking constraints are met.
323 bool break_satisfy = true;
324 int sz = positions->cols_.size ();
325 for (int i = sz; i--;)
327 SCM p = positions->cols_[i]->get_property ("penalty");
328 if (scm_is_number (p))
330 if (scm_to_double (p) < -9999)
331 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
332 if (scm_to_double (p) > 9999)
333 break_satisfy = break_satisfy && ! (i == 0 || i == sz -1);
337 positions->satisfies_constraints_
338 = positions->satisfies_constraints_ && break_satisfy;
342 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
344 Spring_description desc;
347 desc.inverse_hooke_ = inverse_hooke;
348 if (!desc.is_sane ())
350 programming_error ("insane spring found, setting to unit");
352 desc.inverse_hooke_ = 1.0;
357 desc.is_active_ = false;
363 desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_;
364 // block at distance 0
368 springs_.push (desc);
372 compare_paper_column_rank (Grob *const &a,
375 return Paper_column::get_rank (a) - Paper_column::get_rank (b);
379 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
381 Link_array<Grob> cols (icols);
384 for (int i = 0; i < icols.size (); i++)
385 if (scm_is_pair (icols[i]->get_object ("between-cols")))
386 loose_cols_.push (icols[i]);
388 cols.push (icols[i]);
391 for (int i = 0; i < cols.size () - 1; i++)
393 Spring_smob *spring = 0;
395 for (SCM s = cols[i]->get_object ("ideal-distances");
396 !spring && scm_is_pair (s);
399 Spring_smob *sp = unsmob_spring (scm_car (s));
401 if (sp->other_ == cols[i + 1])
406 programming_error (_f ("No spring between column %d and next one",
407 Paper_column::get_rank (cols[i])));
409 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
410 Real inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0;
412 spacer_->add_spring (ideal, inverse_hooke);
415 for (int i = 0; i < cols.size () - 1; i++)
417 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
418 scm_is_pair (s); s = scm_cdr (s))
420 Grob *other = unsmob_grob (scm_caar (s));
421 int j = binsearch_links (cols, other, &compare_paper_column_rank);
422 if (j >= 0 && cols[j] == other)
423 spacer_->add_rod (i, j, scm_to_double (scm_cdar (s)));
427 && to_boolean (cols[i]->get_property ("keep-inside-line")))
429 Interval e = cols[i]->extent (cols[i], X_AXIS);
432 spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
433 spacer_->add_rod (0, i, e[LEFT]);
439 Simple_spacer_wrapper::Simple_spacer_wrapper ()
441 spacer_ = new Simple_spacer ();
444 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
449 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)