2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
9 - add support for different stretch/shrink constants?
14 #include <libc-extension.hh> // isinf
16 #include "simple-spacer.hh"
17 #include "paper-column.hh"
21 #include "column-x-positions.hh"
22 #include "spaceable-grob.hh"
23 #include "dimensions.hh"
27 A simple spacing constraint solver. The approach:
29 Stretch the line uniformly until none of the constraints (rods)
30 block. It then is very wide.
32 Compress until the next constraint blocks,
34 Mark the springs over the constrained part to be non-active.
36 Repeat with the smaller set of non-active constraints, until all
37 constraints blocked, or until the line is as short as desired.
39 This is much simpler, and much much faster than full scale
40 Constrained QP. On the other hand, a situation like this will not
41 be typeset as dense as possible, because
44 veryveryverylongsyllable2 veryveryverylongsyllable2
45 " "4 veryveryverylongsyllable2 syllable4
48 can be further compressed to
52 veryveryverylongsyllable2 veryveryverylongsyllable2
53 " "4 veryveryverylongsyllable2 syllable4
56 Perhaps this is not a bad thing, because the 1st looks better anyway. */
59 Simple_spacer::Simple_spacer ()
62 Give an extra penalty for compression. Needed to avoid compressing
65 compression_penalty_b_ = false;
69 default_space_f_ = 20 PT;
73 Simple_spacer::add_rod (int l, int r, Real dist)
75 if (isinf (dist) || isnan (dist))
77 programming_error ("Weird minimum distance. Ignoring");
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_f_;
92 if (total_dist < dist)
93 for (int i = l ; i < r; i++)
94 springs_[i].ideal_f_ *= 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_f_ = force_f_ >? block_force;
105 for (int i=l; i < r; i++)
106 springs_[i].block_force_f_ = block_force >?
107 springs_[i].block_force_f_ ;
111 Simple_spacer::range_ideal_len (int l, int r) const
114 for (int i=l; i < r; i++)
115 d += springs_[i].ideal_f_;
120 Simple_spacer::range_stiffness (int l, int r) const
123 for (int i=l; i < r; i++)
125 if (springs_[i].active_b_)
126 den += 1 / springs_[i].hooke_f_;
133 Simple_spacer::active_blocking_force () const
135 Real bf = - infinity_f;
136 for (int i=0; i < springs_.size (); i++)
137 if (springs_[i].active_b_)
139 bf = bf >? springs_[i].block_force_f_;
145 Simple_spacer::active_springs_stiffness () const
148 for (int i=0; i < springs_.size (); i++)
149 if (springs_[i].active_b_)
151 den += 1 / springs_[i].hooke_f_;
157 Simple_spacer::set_active_states ()
159 /* float comparison is safe, since force is only copied. */
160 for (int i=0 ; i <springs_.size (); i++)
161 if (springs_[i].active_b_
162 && springs_[i].block_force_f_ >= force_f_)
164 springs_[i].active_b_ = false;
170 Simple_spacer::configuration_length () const
173 for (int i=0; i < springs_.size (); i++)
174 l += springs_[i].length (force_f_);
180 Simple_spacer::active_b () const
182 return active_count_;
186 Simple_spacer::my_solve_linelen ()
190 force_f_ = active_blocking_force ();
191 Real conf = configuration_length ();
193 if (conf < line_len_f_)
195 force_f_ += (line_len_f_ - conf) * active_springs_stiffness ();
199 set_active_states ();
205 Simple_spacer::my_solve_natural_len ()
209 force_f_ = active_blocking_force () >? 0.0;
211 if (force_f_ < 1e-8) // ugh.,
214 set_active_states ();
219 Simple_spacer::add_columns (Link_array<Grob> cols)
221 for (int i = cols.size (); i--;)
222 if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
224 loose_cols_.push (cols[i]);
229 for (int i=0; i < cols.size () - 1; i++)
231 Spring_smob *spring = 0;
233 for (SCM s = cols[i]->get_grob_property ("ideal-distances");
234 !spring && gh_pair_p (s);
237 Spring_smob *sp = unsmob_spring (ly_car (s));
240 if (sp->other_ == cols[i+1])
244 Spring_description desc;
247 desc.ideal_f_ = spring->distance_f_;
248 desc.hooke_f_ = spring->strength_f_;
252 programming_error (_f("No spring between column %d and next one",
253 Paper_column::rank_i (cols[i])
256 desc.ideal_f_ = default_space_f_;
263 programming_error ("Insane spring found. Setting to unit spring.");
265 cout << "columns " << Paper_column::rank_i (cols[i])
266 << " " << Paper_column::rank_i (cols[i+1]) << endl;
271 if (isinf (desc.hooke_f_))
273 desc.active_b_ = false;
274 springs_.push (desc);
278 desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // block at distance 0
279 springs_.push (desc);
284 if (spring->expand_only_b_)
286 compression_penalty_b_ = true;
291 for (int i=0; i < cols.size () - 1; i++)
293 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
294 gh_pair_p (s); s = ly_cdr (s))
296 Grob * other = unsmob_grob (ly_caar (s));
297 int oi = cols.find_i (other);
300 add_rod (i, oi, gh_scm2double (ly_cdar (s)));
306 TODO: should support natural length on only the last line.
309 my_solve_natural_len ();
317 Simple_spacer::solve (Column_x_positions *positions) const
319 positions->force_f_ = force_f_;
322 positions->force_f_ *= 1.3;
323 if (compression_penalty_b_)
324 positions->force_f_ *= 2; // hmm.
327 positions->config_.push (indent_f_);
328 for (int i=0; i <springs_.size (); i++)
330 positions->config_.push (positions->config_.top () + springs_[i].length (force_f_));
332 positions->cols_ = spaced_cols_;
333 positions->loose_cols_ = loose_cols_;
335 positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b ();
339 Check if breaking constraints are met.
341 bool break_satisfy = true;
342 int sz = positions->cols_.size ();
343 for (int i = sz; i--; )
345 SCM p = positions->cols_[i]->get_grob_property( "penalty");
348 if (gh_scm2double (p) < -9999)
349 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
350 if (gh_scm2double (p) > 9999)
351 break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
356 positions->satisfies_constraints_b_ =
357 positions->satisfies_constraints_b_ && break_satisfy;
360 /****************************************************************/
362 Spring_description::Spring_description ()
367 block_force_f_ = 0.0;
372 Spring_description::sane_b () const
374 return (hooke_f_ > 0) && !isinf (ideal_f_) && !isnan (ideal_f_);
378 Spring_description::length (Real f) const
382 return ideal_f_ + f / hooke_f_ ;