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].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 = springs_[max_i].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 ()
254 Spring_description::is_sane () const
258 && !isinf (ideal_) && !isnan (ideal_);
262 Spring_description::length (Real f) const
266 return ideal_ + f / 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 hooke)
346 Spring_description desc;
350 if (!desc.is_sane ())
352 programming_error ("insane spring found, setting to unit");
360 desc.is_active_ = false;
367 desc.block_force_ = -desc.hooke_ * desc.ideal_; // block at distance 0
371 springs_.push (desc);
375 compare_paper_column_rank (Grob *const &a,
378 return Paper_column::get_rank (a) - Paper_column::get_rank (b);
382 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
384 Link_array<Grob> cols (icols);
386 for (int i = cols.size (); i--;)
387 if (scm_is_pair (cols[i]->get_property ("between-cols")))
389 loose_cols_.push (cols[i]);
394 for (int i = 0; i < cols.size () - 1; i++)
396 Spring_smob *spring = 0;
398 for (SCM s = cols[i]->get_property ("ideal-distances");
399 !spring && scm_is_pair (s);
402 Spring_smob *sp = unsmob_spring (scm_car (s));
404 if (sp->other_ == cols[i + 1])
409 programming_error (_f ("No spring between column %d and next one",
410 Paper_column::get_rank (cols[i])));
412 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
413 Real hooke = (spring) ? spring->strength_ : 1.0;
415 spacer_->add_spring (ideal, hooke);
418 for (int i = 0; i < cols.size () - 1; i++)
420 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
421 scm_is_pair (s); s = scm_cdr (s))
423 Grob *other = unsmob_grob (scm_caar (s));
424 int oi = binsearch_links (cols, other, &compare_paper_column_rank);
426 && cols[oi] == other)
428 spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s)));
433 && !to_boolean (cols[i]->get_property ("allow-outside-line")))
435 Interval e = cols[i]->extent (cols[i], X_AXIS);
438 spacer_->add_rod (i, cols.size () - 1, e[RIGHT]);
439 spacer_->add_rod (0, i, e[LEFT]);
445 Simple_spacer_wrapper::Simple_spacer_wrapper ()
447 spacer_ = new Simple_spacer ();
450 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
455 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const &)