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?
13 #include "simple-spacer.hh"
18 #include <libc-extension.hh> // isinf
20 #include "paper-column.hh"
23 #include "column-x-positions.hh"
24 #include "spaceable-grob.hh"
25 #include "dimensions.hh"
28 A simple spacing constraint solver. The approach:
30 Stretch the line uniformly until none of the constraints (rods)
31 block. It then is very wide.
33 Compress until the next constraint blocks,
35 Mark the springs over the constrained part to be non-active.
37 Repeat with the smaller set of non-active constraints, until all
38 constraints blocked, or until the line is as short as desired.
40 This is much simpler, and much much faster than full scale
41 Constrained QP. On the other hand, a situation like this will not
42 be typeset as dense as possible, because
45 veryveryverylongsyllable2 veryveryverylongsyllable2
46 " "4 veryveryverylongsyllable2 syllable4
49 can be further compressed to
53 veryveryverylongsyllable2 veryveryverylongsyllable2
54 " "4 veryveryverylongsyllable2 syllable4
57 Perhaps this is not a bad thing, because the 1st looks better anyway. */
62 positive force = expanding, negative force = compressing.
66 Simple_spacer::Simple_spacer ()
69 Give an extra penalty for compression. Needed to avoid compressing
75 default_space_ = 20 PT;
79 Simple_spacer::add_rod (int l, int r, Real dist)
81 if (isinf (dist) || isnan (dist))
83 programming_error ("Weird minimum distance. Ignoring");
87 Real c = range_stiffness (l,r);
91 If a spring is fixed, we have to do something here:
92 we let the rod override the spring.
95 for (int i = l ; i < r; i++)
96 total_dist += springs_[i].ideal_;
98 if (total_dist < dist)
99 for (int i = l ; i < r; i++)
100 springs_[i].ideal_ *= dist/total_dist;
105 Real d = range_ideal_len (l,r);
106 Real block_stretch = dist - d;
108 Real block_force = c * block_stretch;
109 force_ = force_ >? block_force;
111 for (int i = l; i < r; i++)
112 springs_[i].block_force_ = block_force >?
113 springs_[i].block_force_ ;
117 Simple_spacer::range_ideal_len (int l, int r) const
120 for (int i = l; i < r; i++)
121 d += springs_[i].ideal_;
126 Simple_spacer::range_stiffness (int l, int r) const
129 for (int i = l; i < r; i++)
131 if (springs_[i].is_active_)
132 den += 1 / springs_[i].hooke_;
139 Simple_spacer::active_blocking_force () const
141 Real bf = - infinity_f;
142 for (int i = 0; i < springs_.size (); i++)
143 if (springs_[i].is_active_)
145 bf = bf >? springs_[i].block_force_;
151 Simple_spacer::active_springs_stiffness () const
153 Real stiff = range_stiffness (0, springs_.size ());
157 all springs are inactive. Take the stiffness of the
158 latest spring to block.
161 Real max_block_force = -infinity_f;
163 for (int i = 0; i < springs_.size (); i++)
165 if (springs_[i].block_force_ > max_block_force)
168 max_block_force = springs_[i].block_force_;
172 stiff = springs_[max_i].hooke_;
178 Simple_spacer::set_active_states ()
180 /* float comparison is safe, since force is only copied. */
181 for (int i = 0 ; i <springs_.size (); i++)
182 if (springs_[i].is_active_
183 && springs_[i].block_force_ >= force_)
185 springs_[i].is_active_ = false;
191 Simple_spacer::configuration_length () const
194 for (int i = 0; i < springs_.size (); i++)
195 l += springs_[i].length (force_);
201 Simple_spacer::is_active () const
203 return active_count_;
207 Simple_spacer::my_solve_linelen ()
211 force_ = active_blocking_force ();
212 Real conf = configuration_length ();
214 if (conf < line_len_)
216 force_ += (line_len_ - conf) * active_springs_stiffness ();
220 set_active_states ();
226 Simple_spacer::my_solve_natural_len ()
228 Real line_len_force = 0.0;
232 force_ = active_blocking_force () >? 0.0;
233 Real conf = configuration_length ();
235 if (conf < line_len_)
237 line_len_force = force_
239 * active_springs_stiffness();
242 if (force_ < 1e-8) // ugh.,
245 set_active_states ();
248 force_ = line_len_force;
251 LY_DEFINE(ly_solve_spring_rod_problem, "ly:solve-spring-rod-problem",
252 4, 1, 0, (SCM springs, SCM rods, SCM length, SCM ragged),
253 "Solve a spring and rod problem for @var{count} objects, that "
254 "are connected by @var{count-1} springs, and an arbitrary number of rods "
255 "Springs have the format (ideal, hooke) and rods (idx1, idx2, distance) "
256 "@var{length} is a number, @var{ragged} a boolean "
257 "Return: a list containing the force (positive for stretching, "
258 "negative for compressing and #f for non-satisfied constraints) "
259 "followed by the @var{spring-count}+1 positions of the objects. "
262 int len = scm_ilength (springs);
264 return scm_list_2 (scm_from_double (0.0), scm_from_double (0.0));
266 SCM_ASSERT_TYPE (len >= 0, springs, SCM_ARG1, __FUNCTION__, "list of springs");
267 SCM_ASSERT_TYPE (scm_ilength (rods) >= 0, rods, SCM_ARG2, __FUNCTION__, "list of rods");
268 SCM_ASSERT_TYPE (scm_is_number (length) || length == SCM_BOOL_F,
269 length, SCM_ARG3, __FUNCTION__, "number or #f");
272 bool is_ragged = ragged == SCM_BOOL_T;
273 Simple_spacer spacer;
274 for (SCM s = springs; scm_is_pair (s); s = scm_cdr (s))
276 Real ideal = scm_to_double (scm_caar (s));
277 Real hooke = scm_to_double (scm_cadar (s));
279 spacer.add_spring (ideal, hooke);
282 for (SCM s = rods; scm_is_pair (s); s = scm_cdr (s))
284 SCM entry = scm_car (s);
285 int l = scm_to_int (scm_car (entry));
286 int r = scm_to_int (scm_cadr (entry));
287 entry = scm_cddr (entry);
289 Real distance = scm_to_double (scm_car (entry));
290 spacer.add_rod (l, r, distance);
293 spacer.line_len_ = scm_to_double (length);
296 spacer.my_solve_natural_len ();
298 spacer.my_solve_linelen ();
302 for (int i = 0; i < spacer.springs_.size(); i++)
304 Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_);
305 posns.push (posns.top() + l);
310 SCM force_return = SCM_BOOL_F;
311 if (!isinf (spacer.force_)
312 && (spacer.is_active () || is_ragged))
314 force_return = scm_from_double (spacer.force_);
318 && posns.top () > spacer.line_len_)
320 force_return = SCM_BOOL_F;
323 SCM retval = SCM_EOL;
324 for (int i = posns.size(); i--;)
326 retval = scm_cons (scm_from_double (posns[i]), retval);
329 retval = scm_cons (force_return, retval);
334 /****************************************************************/
336 Spring_description::Spring_description ()
346 Spring_description::is_sane () const
350 && !isinf (ideal_) && !isnan (ideal_);
354 Spring_description::length (Real f) const
358 return ideal_ + f / hooke_ ;
360 /****************************************************************/
365 TODO: should a add penalty for widely varying spring forces (caused
374 The ## forces the notes apart; we shouldn't allow the O's to touch
379 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
382 spacer_->my_solve_natural_len ();
384 spacer_->my_solve_linelen ();
386 positions->force_ = spacer_->force_;
389 We used to have a penalty for compression, no matter what, but that
390 fucked up wtk1-fugue2 (taking 3 full pages.)
392 positions->config_.push (spacer_->indent_);
393 for (int i = 0; i < spacer_->springs_.size (); i++)
395 Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
396 positions->config_.push (positions->config_.top () + l);
398 we have l>= 0 here, up to rounding errors
403 For raggedright, we must have a measure of music density: this is
404 to prevent lots of short lines (which all have force = 0).
408 positions->satisfies_constraints_ =
409 positions->config_.top () < spacer_->line_len_ ;
412 positions->satisfies_constraints_ = spacer_->is_active ();
414 positions->cols_ = spaced_cols_;
415 positions->loose_cols_ = loose_cols_;
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 compare_paper_column_rank (Grob *const &a,
474 return Paper_column::get_rank (a) - Paper_column::get_rank (b);
478 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
480 Link_array<Grob> cols (icols);
482 for (int i = cols.size (); i--;)
483 if (scm_is_pair (cols[i]->get_property ("between-cols")))
485 loose_cols_.push (cols[i]);
490 for (int i = 0; i < cols.size () - 1; i++)
492 Spring_smob *spring = 0;
494 for (SCM s = cols[i]->get_property ("ideal-distances");
495 !spring && scm_is_pair (s);
498 Spring_smob *sp = unsmob_spring (scm_car (s));
501 if (sp->other_ == cols[i+1])
506 programming_error (_f ("No spring between column %d and next one",
507 Paper_column::get_rank (cols[i])
510 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
511 Real hooke = (spring) ? spring->strength_ : 1.0;
513 spacer_->add_spring (ideal, hooke);
516 for (int i = 0; i < cols.size () - 1; i++)
518 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
519 scm_is_pair (s); s = scm_cdr (s))
521 Grob * other = unsmob_grob (scm_caar (s));
522 int oi = binsearch_links (cols, other, &compare_paper_column_rank);
525 spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s)));
530 && !to_boolean (cols[i]->get_property ("allow-outside-line")))
532 Interval e = cols[i]->extent (cols[i], X_AXIS);
535 spacer_->add_rod (i, cols.size()-1, e[RIGHT]);
536 spacer_->add_rod (0, i, e[LEFT]);
542 Simple_spacer_wrapper::Simple_spacer_wrapper ()
544 spacer_ = new Simple_spacer ();
547 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
553 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const&)