2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2004 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
68 default_space_ = 20 PT;
72 Simple_spacer::add_rod (int l, int r, Real dist)
74 if (isinf (dist) || isnan (dist))
76 programming_error ("Weird minimum distance. Ignoring");
80 Real c = range_stiffness (l,r);
84 If a spring is fixed, we have to do something here:
85 we let the rod override the spring.
88 for (int i = l ; i < r; i++)
89 total_dist += springs_[i].ideal_;
91 if (total_dist < dist)
92 for (int i = l ; i < r; i++)
93 springs_[i].ideal_ *= dist/total_dist;
98 Real d = range_ideal_len (l,r);
99 Real block_stretch = dist - d;
101 Real block_force = c * block_stretch;
102 force_ = force_ >? block_force;
104 for (int i=l; i < r; i++)
105 springs_[i].block_force_ = block_force >?
106 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 = 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 ();
219 Simple_spacer::my_solve_natural_len ()
223 force_ = active_blocking_force () >? 0.0;
225 if (force_ < 1e-8) // ugh.,
228 set_active_states ();
232 LY_DEFINE(ly_solve_spring_rod_problem, "ly:solve-spring-rod-problem",
233 4, 1, 0, (SCM springs, SCM rods, SCM length, SCM ragged),
234 "Solve a spring and rod problem for @var{count} objects, that "
235 "are connected by @var{count-1} springs, and an arbitrary number of rods "
236 "Springs have the format (ideal, hooke) and rods (idx1, idx2, distance) "
237 "@var{length} is a number, @var{ragged} a boolean "
238 "Return: a list containing the force (#f for non-satisfied constraints) "
239 "followed by the @var{spring-count}+1 positions of the objects. "
242 int len = scm_ilength (springs);
244 return scm_list_2 (scm_from_double (0.0), scm_from_double (0.0));
246 SCM_ASSERT_TYPE (len >= 0, springs, SCM_ARG1, __FUNCTION__, "list of springs");
247 SCM_ASSERT_TYPE (scm_ilength (rods) >= 0, rods, SCM_ARG2, __FUNCTION__, "list of rods");
248 SCM_ASSERT_TYPE (scm_is_number (length) || length == SCM_BOOL_F,
249 length, SCM_ARG3, __FUNCTION__, "number or #f");
252 bool is_ragged = ragged == SCM_BOOL_T;
253 Simple_spacer spacer;
254 for (SCM s = springs; ly_c_pair_p (s); s = ly_cdr (s))
256 Real ideal = scm_to_double (ly_caar (s));
257 Real hooke = scm_to_double (ly_cadar (s));
259 spacer.add_spring (ideal, hooke);
262 for (SCM s = rods; ly_c_pair_p (s); s = ly_cdr (s))
264 SCM entry = ly_car (s);
265 int l = scm_to_int (ly_car (entry));
266 int r = scm_to_int (ly_cadr (entry));
267 entry = ly_cddr (entry);
269 Real distance = scm_to_double (ly_car (entry));
270 spacer.add_rod (l, r, distance);
273 spacer.line_len_ = scm_to_double (length);
276 spacer.my_solve_natural_len ();
278 spacer.my_solve_linelen ();
282 for (int i = 0; i < spacer.springs_.size(); i++)
284 Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_);
285 posns.push (posns.top() + l);
288 SCM force_return = SCM_BOOL_F;
291 Real len = posns.top ();
292 if (spacer.line_len_ - len >= 0)
293 force_return = scm_from_double ((spacer.line_len_ - len)
294 * spacer.active_springs_stiffness ());
296 else if (not isinf (spacer.force_)
297 && spacer.is_active ())
299 force_return = scm_from_double (spacer.force_);
303 for (int i = posns.size(); i--;)
305 retval = scm_cons (scm_from_double (posns[i]), retval);
308 retval = scm_cons (force_return, retval);
313 /****************************************************************/
315 Spring_description::Spring_description ()
325 Spring_description::is_sane () const
329 && !isinf (ideal_) && !isnan (ideal_);
333 Spring_description::length (Real f) const
337 return ideal_ + f / hooke_ ;
339 /****************************************************************/
344 TODO: should a add penalty for widely varying spring forces (caused
353 The ## forces the notes apart; we shouldn't allow the O's to touch
358 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
361 spacer_->my_solve_natural_len ();
363 spacer_->my_solve_linelen ();
365 positions->force_ = spacer_->force_;
368 We used to have a penalty for compression, no matter what, but that
369 fucked up wtk1-fugue2 (taking 3 full pages.)
371 positions->config_.push (spacer_->indent_);
372 for (int i=0; i < spacer_->springs_.size (); i++)
374 Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
375 positions->config_.push (positions->config_.top () + l);
377 we have l>= 0 here, up to rounding errors
382 For raggedright, we must have a measure of music density: this is
383 to prevent lots of short lines (which all have force = 0).
387 Real len = positions->config_.top ();
388 if (spacer_->line_len_ - len >= 0)
389 positions->force_ = ((spacer_->line_len_ - len)
390 * spacer_->active_springs_stiffness ());
393 positions->force_ = 0.0;
395 Don't go past end-of-line in ragged right.
397 positions->satisfies_constraints_ = false;
402 positions->cols_ = spaced_cols_;
403 positions->loose_cols_ = loose_cols_;
404 positions->satisfies_constraints_ =
405 positions->satisfies_constraints_ && spacer_->is_active ();
408 Check if breaking constraints are met.
410 bool break_satisfy = true;
411 int sz = positions->cols_.size ();
412 for (int i = sz; i--; )
414 SCM p = positions->cols_[i]->get_property ( "penalty");
415 if (scm_is_number (p))
417 if (scm_to_double (p) < -9999)
418 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
419 if (scm_to_double (p) > 9999)
420 break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
425 positions->satisfies_constraints_ =
426 positions->satisfies_constraints_ && break_satisfy;
430 Simple_spacer::add_spring (Real ideal, Real hooke)
432 Spring_description desc;
436 if (!desc.is_sane ())
438 programming_error ("Insane spring found. Setting to unit spring.");
446 desc.is_active_ = false;
453 desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
457 springs_.push (desc);
461 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
463 Link_array<Grob> cols (icols);
465 for (int i = cols.size (); i--;)
466 if (ly_c_pair_p (cols[i]->get_property ("between-cols")))
468 loose_cols_.push (cols[i]);
473 for (int i=0; i < cols.size () - 1; i++)
475 Spring_smob *spring = 0;
477 for (SCM s = cols[i]->get_property ("ideal-distances");
478 !spring && ly_c_pair_p (s);
481 Spring_smob *sp = unsmob_spring (ly_car (s));
484 if (sp->other_ == cols[i+1])
489 programming_error (_f ("No spring between column %d and next one",
490 Paper_column::get_rank (cols[i])
493 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
494 Real hooke = (spring) ? spring->strength_ : 1.0;
496 spacer_->add_spring (ideal, hooke);
499 for (int i=0; i < cols.size () - 1; i++)
501 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
502 ly_c_pair_p (s); s = ly_cdr (s))
504 Grob * other = unsmob_grob (ly_caar (s));
505 int oi = cols.find_index (other);
508 spacer_->add_rod (i, oi, scm_to_double (ly_cdar (s)));
514 Simple_spacer_wrapper::Simple_spacer_wrapper ()
516 spacer_ = new Simple_spacer ();
519 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
525 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const&)