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. */
61 positive force = expanding, negative force = compressing.
65 Simple_spacer::Simple_spacer ()
68 Give an extra penalty for compression. Needed to avoid compressing
74 default_space_ = 20 PT;
78 Simple_spacer::add_rod (int l, int r, Real dist)
80 if (isinf (dist) || isnan (dist))
82 programming_error ("Weird minimum distance. Ignoring");
86 Real c = range_stiffness (l,r);
90 If a spring is fixed, we have to do something here:
91 we let the rod override the spring.
94 for (int i = l ; i < r; i++)
95 total_dist += springs_[i].ideal_;
97 if (total_dist < dist)
98 for (int i = l ; i < r; i++)
99 springs_[i].ideal_ *= dist/total_dist;
104 Real d = range_ideal_len (l,r);
105 Real block_stretch = dist - d;
107 Real block_force = c * block_stretch;
108 force_ = force_ >? block_force;
110 for (int i=l; i < r; i++)
111 springs_[i].block_force_ = block_force >?
112 springs_[i].block_force_ ;
116 Simple_spacer::range_ideal_len (int l, int r) const
119 for (int i=l; i < r; i++)
120 d += springs_[i].ideal_;
125 Simple_spacer::range_stiffness (int l, int r) const
128 for (int i=l; i < r; i++)
130 if (springs_[i].is_active_)
131 den += 1 / springs_[i].hooke_;
138 Simple_spacer::active_blocking_force () const
140 Real bf = - infinity_f;
141 for (int i=0; i < springs_.size (); i++)
142 if (springs_[i].is_active_)
144 bf = bf >? springs_[i].block_force_;
150 Simple_spacer::active_springs_stiffness () const
152 Real stiff = range_stiffness (0, springs_.size ());
156 all springs are inactive. Take the stiffness of the
157 latest spring to block.
160 Real max_block_force = -infinity_f;
162 for (int i=0; i < springs_.size (); i++)
164 if (springs_[i].block_force_ > max_block_force)
167 max_block_force = springs_[i].block_force_;
171 stiff = springs_[max_i].hooke_;
177 Simple_spacer::set_active_states ()
179 /* float comparison is safe, since force is only copied. */
180 for (int i=0 ; i <springs_.size (); i++)
181 if (springs_[i].is_active_
182 && springs_[i].block_force_ >= force_)
184 springs_[i].is_active_ = false;
190 Simple_spacer::configuration_length () const
193 for (int i=0; i < springs_.size (); i++)
194 l += springs_[i].length (force_);
200 Simple_spacer::is_active () const
202 return active_count_;
206 Simple_spacer::my_solve_linelen ()
210 force_ = active_blocking_force ();
211 Real conf = configuration_length ();
213 if (conf < line_len_)
215 force_ += (line_len_ - conf) * active_springs_stiffness ();
219 set_active_states ();
225 Simple_spacer::my_solve_natural_len ()
227 Real line_len_force = 0.0;
231 force_ = active_blocking_force () >? 0.0;
232 Real conf = configuration_length ();
234 if (conf < line_len_)
236 line_len_force = force_
238 * active_springs_stiffness();
241 if (force_ < 1e-8) // ugh.,
244 set_active_states ();
247 force_ = line_len_force;
250 LY_DEFINE(ly_solve_spring_rod_problem, "ly:solve-spring-rod-problem",
251 4, 1, 0, (SCM springs, SCM rods, SCM length, SCM ragged),
252 "Solve a spring and rod problem for @var{count} objects, that "
253 "are connected by @var{count-1} springs, and an arbitrary number of rods "
254 "Springs have the format (ideal, hooke) and rods (idx1, idx2, distance) "
255 "@var{length} is a number, @var{ragged} a boolean "
256 "Return: a list containing the force (positive for stretching, "
257 "negative for compressing and #f for non-satisfied constraints) "
258 "followed by the @var{spring-count}+1 positions of the objects. "
261 int len = scm_ilength (springs);
263 return scm_list_2 (scm_from_double (0.0), scm_from_double (0.0));
265 SCM_ASSERT_TYPE (len >= 0, springs, SCM_ARG1, __FUNCTION__, "list of springs");
266 SCM_ASSERT_TYPE (scm_ilength (rods) >= 0, rods, SCM_ARG2, __FUNCTION__, "list of rods");
267 SCM_ASSERT_TYPE (scm_is_number (length) || length == SCM_BOOL_F,
268 length, SCM_ARG3, __FUNCTION__, "number or #f");
271 bool is_ragged = ragged == SCM_BOOL_T;
272 Simple_spacer spacer;
273 for (SCM s = springs; scm_is_pair (s); s = scm_cdr (s))
275 Real ideal = scm_to_double (scm_caar (s));
276 Real hooke = scm_to_double (scm_cadar (s));
278 spacer.add_spring (ideal, hooke);
281 for (SCM s = rods; scm_is_pair (s); s = scm_cdr (s))
283 SCM entry = scm_car (s);
284 int l = scm_to_int (scm_car (entry));
285 int r = scm_to_int (scm_cadr (entry));
286 entry = scm_cddr (entry);
288 Real distance = scm_to_double (scm_car (entry));
289 spacer.add_rod (l, r, distance);
292 spacer.line_len_ = scm_to_double (length);
295 spacer.my_solve_natural_len ();
297 spacer.my_solve_linelen ();
301 for (int i = 0; i < spacer.springs_.size(); i++)
303 Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_);
304 posns.push (posns.top() + l);
309 SCM force_return = SCM_BOOL_F;
310 if (!isinf (spacer.force_)
311 && spacer.is_active ())
313 force_return = scm_from_double (spacer.force_);
317 && posns.top () > spacer.line_len_)
319 force_return = SCM_BOOL_F;
323 for (int i = posns.size(); i--;)
325 retval = scm_cons (scm_from_double (posns[i]), retval);
328 retval = scm_cons (force_return, retval);
333 /****************************************************************/
335 Spring_description::Spring_description ()
345 Spring_description::is_sane () const
349 && !isinf (ideal_) && !isnan (ideal_);
353 Spring_description::length (Real f) const
357 return ideal_ + f / hooke_ ;
359 /****************************************************************/
364 TODO: should a add penalty for widely varying spring forces (caused
373 The ## forces the notes apart; we shouldn't allow the O's to touch
378 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
381 spacer_->my_solve_natural_len ();
383 spacer_->my_solve_linelen ();
385 positions->force_ = spacer_->force_;
388 We used to have a penalty for compression, no matter what, but that
389 fucked up wtk1-fugue2 (taking 3 full pages.)
391 positions->config_.push (spacer_->indent_);
392 for (int i=0; i < spacer_->springs_.size (); i++)
394 Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
395 positions->config_.push (positions->config_.top () + l);
397 we have l>= 0 here, up to rounding errors
402 For raggedright, we must have a measure of music density: this is
403 to prevent lots of short lines (which all have force = 0).
407 positions->satisfies_constraints_ =
408 positions->config_.top () < spacer_->line_len_ ;
412 positions->cols_ = spaced_cols_;
413 positions->loose_cols_ = loose_cols_;
414 positions->satisfies_constraints_ =
415 positions->satisfies_constraints_ && spacer_->is_active ();
418 Check if breaking constraints are met.
420 bool break_satisfy = true;
421 int sz = positions->cols_.size ();
422 for (int i = sz; i--; )
424 SCM p = positions->cols_[i]->get_property ( "penalty");
425 if (scm_is_number (p))
427 if (scm_to_double (p) < -9999)
428 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
429 if (scm_to_double (p) > 9999)
430 break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
435 positions->satisfies_constraints_ =
436 positions->satisfies_constraints_ && break_satisfy;
440 Simple_spacer::add_spring (Real ideal, Real hooke)
442 Spring_description desc;
446 if (!desc.is_sane ())
448 programming_error ("Insane spring found. Setting to unit spring.");
456 desc.is_active_ = false;
463 desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
467 springs_.push (desc);
471 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
473 Link_array<Grob> cols (icols);
475 for (int i = cols.size (); i--;)
476 if (scm_is_pair (cols[i]->get_property ("between-cols")))
478 loose_cols_.push (cols[i]);
483 for (int i=0; i < cols.size () - 1; i++)
485 Spring_smob *spring = 0;
487 for (SCM s = cols[i]->get_property ("ideal-distances");
488 !spring && scm_is_pair (s);
491 Spring_smob *sp = unsmob_spring (scm_car (s));
494 if (sp->other_ == cols[i+1])
499 programming_error (_f ("No spring between column %d and next one",
500 Paper_column::get_rank (cols[i])
503 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
504 Real hooke = (spring) ? spring->strength_ : 1.0;
506 spacer_->add_spring (ideal, hooke);
509 for (int i=0; i < cols.size () - 1; i++)
511 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
512 scm_is_pair (s); s = scm_cdr (s))
514 Grob * other = unsmob_grob (scm_caar (s));
515 int oi = cols.find_index (other);
518 spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s)));
524 Simple_spacer_wrapper::Simple_spacer_wrapper ()
526 spacer_ = new Simple_spacer ();
529 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
535 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const&)