2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2003 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_ = 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_;
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_ = force_ >? block_force;
105 for (int i=l; i < r; i++)
106 springs_[i].block_force_ = block_force >?
107 springs_[i].block_force_ ;
111 Simple_spacer::range_ideal_len (int l, int r) const
114 for (int i=l; i < r; i++)
115 d += springs_[i].ideal_;
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_;
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_;
145 Simple_spacer::active_springs_stiffness () const
147 return range_stiffness (0, springs_.size ());
151 Simple_spacer::set_active_states ()
153 /* float comparison is safe, since force is only copied. */
154 for (int i=0 ; i <springs_.size (); i++)
155 if (springs_[i].active_b_
156 && springs_[i].block_force_ >= force_)
158 springs_[i].active_b_ = false;
164 Simple_spacer::configuration_length () const
167 for (int i=0; i < springs_.size (); i++)
168 l += springs_[i].length (force_);
174 Simple_spacer::active_b () const
176 return active_count_;
180 Simple_spacer::my_solve_linelen ()
184 force_ = active_blocking_force ();
185 Real conf = configuration_length ();
187 if (conf < line_len_)
189 force_ += (line_len_ - conf) * active_springs_stiffness ();
193 set_active_states ();
199 Simple_spacer::my_solve_natural_len ()
203 force_ = active_blocking_force () >? 0.0;
205 if (force_ < 1e-8) // ugh.,
208 set_active_states ();
213 Simple_spacer::add_columns (Link_array<Grob> const &icols)
215 Link_array<Grob> cols(icols);
217 for (int i = cols.size (); i--;)
218 if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
220 loose_cols_.push (cols[i]);
225 for (int i=0; i < cols.size () - 1; i++)
227 Spring_smob *spring = 0;
229 for (SCM s = cols[i]->get_grob_property ("ideal-distances");
230 !spring && gh_pair_p (s);
233 Spring_smob *sp = unsmob_spring (ly_car (s));
236 if (sp->other_ == cols[i+1])
240 Spring_description desc;
243 desc.ideal_ = spring->distance_;
244 desc.hooke_ = spring->strength_;
248 programming_error (_f("No spring between column %d and next one",
249 Paper_column::get_rank (cols[i])
252 desc.ideal_ = default_space_;
259 programming_error ("Insane spring found. Setting to unit spring.");
265 if (isinf (desc.hooke_))
267 desc.active_b_ = false;
268 springs_.push (desc);
272 desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
273 springs_.push (desc);
278 if (spring->expand_only_b_)
280 compression_penalty_b_ = true;
285 for (int i=0; i < cols.size () - 1; i++)
287 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
288 gh_pair_p (s); s = ly_cdr (s))
290 Grob * other = unsmob_grob (ly_caar (s));
291 int oi = cols.find_index (other);
294 add_rod (i, oi, gh_scm2double (ly_cdar (s)));
304 TODO: should a add penalty for widely varying spring forces (caused
313 The ## forces the notes apart; we shouldn't allow the O's to touch
318 Simple_spacer::solve (Column_x_positions *positions, bool ragged)
321 TODO: should support natural length on only the last line.
323 ragged = ragged || (line_len_ < 0) ;
325 my_solve_natural_len ();
329 positions->force_ = force_;
331 We used to have a penalty for compression, no matter what, but that
332 fucked up wtk1-fugue2 (taking 3 full pages.)
335 positions->config_.push (indent_);
336 for (int i=0; i <springs_.size (); i++)
338 Real l = springs_[i].length ((ragged) ? 0.0 : force_);
339 positions->config_.push (positions->config_.top () + l);
341 we have l>= 0 here, up to rounding errors
346 For raggedright, we must have a measure of music density: this is
347 to prevent lots of short lines (which all have force = 0).
349 if (ragged && line_len_ > 0)
351 Real len = positions->config_.top ();
352 positions->force_ = (line_len_ - len) * active_springs_stiffness ();
356 positions->cols_ = spaced_cols_;
357 positions->loose_cols_ = loose_cols_;
358 positions->satisfies_constraints_b_ = (line_len_ < 0) || active_b ();
361 Check if breaking constraints are met.
363 bool break_satisfy = true;
364 int sz = positions->cols_.size ();
365 for (int i = sz; i--; )
367 SCM p = positions->cols_[i]->get_grob_property( "penalty");
370 if (gh_scm2double (p) < -9999)
371 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
372 if (gh_scm2double (p) > 9999)
373 break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
378 positions->satisfies_constraints_b_ =
379 positions->satisfies_constraints_b_ && break_satisfy;
381 if (ragged && force_ < 0)
382 positions->satisfies_constraints_b_ = false;
385 /****************************************************************/
387 Spring_description::Spring_description ()
397 Spring_description::sane_b () const
399 return (hooke_ > 0) && !isinf (ideal_) && !isnan (ideal_);
403 Spring_description::length (Real f) const
407 return ideal_ + f / hooke_ ;