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_)
138 bf = max (bf, springs_[i].block_force_);
144 Simple_spacer::active_springs_stiffness () const
146 Real stiff = range_stiffness (0, springs_.size ());
150 all springs are inactive. Take the stiffness of the
151 latest spring to block.
154 Real max_block_force = -infinity_f;
156 for (int i = 0; i < springs_.size (); i++)
158 if (springs_[i].block_force_ > max_block_force)
161 max_block_force = springs_[i].block_force_;
165 stiff = 1/springs_[max_i].inverse_hooke_;
171 Simple_spacer::set_active_states ()
173 /* float comparison is safe, since force is only copied. */
174 for (int i = 0; i < springs_.size (); i++)
175 if (springs_[i].is_active_
176 && springs_[i].block_force_ >= force_)
178 springs_[i].is_active_ = false;
184 Simple_spacer::configuration_length () const
187 for (int i = 0; i < springs_.size (); i++)
188 l += springs_[i].length (force_);
194 Simple_spacer::is_active () const
196 return active_count_;
200 Simple_spacer::my_solve_linelen ()
204 force_ = active_blocking_force ();
205 Real conf = configuration_length ();
207 if (conf < line_len_)
209 force_ += (line_len_ - conf) * active_springs_stiffness ();
213 set_active_states ();
218 Simple_spacer::my_solve_natural_len ()
220 Real line_len_force = 0.0;
224 force_ = max (active_blocking_force (), 0.0);
225 Real conf = configuration_length ();
227 if (conf < line_len_)
229 line_len_force = force_
231 * active_springs_stiffness ();
234 if (force_ < 1e-8) // ugh.,
237 set_active_states ();
240 force_ = line_len_force;
243 /****************************************************************/
245 Spring_description::Spring_description ()
248 inverse_hooke_ = 0.0;
254 Spring_description::is_sane () const
256 return (inverse_hooke_ >= 0)
258 && !isinf (ideal_) && !isnan (ideal_);
262 Spring_description::length (Real f) const
266 return ideal_ + f * inverse_hooke_;
268 /****************************************************************/
271 TODO: should a add penalty for widely varying spring forces (caused
280 The ## forces the notes apart; we shouldn't allow the O's to touch
284 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
287 spacer_->my_solve_natural_len ();
289 spacer_->my_solve_linelen ();
291 positions->force_ = spacer_->force_;
294 We used to have a penalty for compression, no matter what, but that
295 fucked up wtk1-fugue2 (taking 3 full pages.)
297 positions->config_.push (spacer_->indent_);
298 for (int i = 0; i < spacer_->springs_.size (); i++)
300 Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
301 positions->config_.push (positions->config_.top () + l);
303 we have l>= 0 here, up to rounding errors
308 For raggedright, we must have a measure of music density: this is
309 to prevent lots of short lines (which all have force = 0).
313 positions->satisfies_constraints_
314 = positions->config_.top () < spacer_->line_len_;
317 positions->satisfies_constraints_ = spacer_->is_active ();
319 positions->cols_ = spaced_cols_;
320 positions->loose_cols_ = loose_cols_;
323 Check if breaking constraints are met.
325 bool break_satisfy = true;
326 int sz = positions->cols_.size ();
327 for (int i = sz; i--;)
329 SCM p = positions->cols_[i]->get_property ("penalty");
330 if (scm_is_number (p))
332 if (scm_to_double (p) < -9999)
333 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
334 if (scm_to_double (p) > 9999)
335 break_satisfy = break_satisfy && ! (i == 0 || i == sz -1);
339 positions->satisfies_constraints_
340 = positions->satisfies_constraints_ && break_satisfy;
344 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
346 Spring_description desc;
349 desc.inverse_hooke_ = inverse_hooke;
350 if (!desc.is_sane ())
352 programming_error ("insane spring found, setting to unit");
354 desc.inverse_hooke_ = 1.0;
360 desc.is_active_ = false;
367 desc.block_force_ = - desc.ideal_ / desc.inverse_hooke_;
368 // block at distance 0
372 springs_.push (desc);
376 compare_paper_column_rank (Grob *const &a,
379 return Paper_column::get_rank (a) - Paper_column::get_rank (b);
383 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
385 Link_array<Grob> cols (icols);
387 for (int i = cols.size (); i--;)
388 if (scm_is_pair (cols[i]->get_property ("between-cols")))
390 loose_cols_.push (cols[i]);
395 for (int i = 0; i < cols.size () - 1; i++)
397 Spring_smob *spring = 0;
399 for (SCM s = cols[i]->get_property ("ideal-distances");
400 !spring && scm_is_pair (s);
403 Spring_smob *sp = unsmob_spring (scm_car (s));
405 if (sp->other_ == cols[i + 1])
410 programming_error (_f ("No spring between column %d and next one",
411 Paper_column::get_rank (cols[i])));
413 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
414 Real inverse_hooke = (spring) ? spring->inverse_strength_ : 1.0;
416 spacer_->add_spring (ideal, inverse_hooke);
419 for (int i = 0; i < cols.size () - 1; i++)
421 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
422 scm_is_pair (s); s = scm_cdr (s))
424 Grob *other = unsmob_grob (scm_caar (s));
425 int oi = binsearch_links (cols, other, &compare_paper_column_rank);
427 && cols[oi] == other)
429 spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s)));
434 && !to_boolean (cols[i]->get_property ("allow-outside-line")))
436 Interval e = cols[i]->extent (cols[i], X_AXIS);
439 spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
440 spacer_->add_rod (0, i, e[LEFT]);
446 Simple_spacer_wrapper::Simple_spacer_wrapper ()
448 spacer_ = new Simple_spacer ();
451 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
456 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)