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_;
324 We used to have a penalty for compression, no matter what, but that
325 fucked up wtk1-fugue2 (taking 3 full pages.)
327 maybe this should be tunable?
329 if (compression_penalty_b_)
330 positions->force_f_ *= 2; // hmm.
333 positions->config_.push (indent_f_);
334 for (int i=0; i <springs_.size (); i++)
336 positions->config_.push (positions->config_.top () + springs_[i].length (force_f_));
338 positions->cols_ = spaced_cols_;
339 positions->loose_cols_ = loose_cols_;
341 positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b ();
345 Check if breaking constraints are met.
347 bool break_satisfy = true;
348 int sz = positions->cols_.size ();
349 for (int i = sz; i--; )
351 SCM p = positions->cols_[i]->get_grob_property( "penalty");
354 if (gh_scm2double (p) < -9999)
355 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
356 if (gh_scm2double (p) > 9999)
357 break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
362 positions->satisfies_constraints_b_ =
363 positions->satisfies_constraints_b_ && break_satisfy;
366 /****************************************************************/
368 Spring_description::Spring_description ()
373 block_force_f_ = 0.0;
378 Spring_description::sane_b () const
380 return (hooke_f_ > 0) && !isinf (ideal_f_) && !isnan (ideal_f_);
384 Spring_description::length (Real f) const
388 return ideal_f_ + f / hooke_f_ ;