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_
= 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
].is_active_
)
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
].is_active_
)
139 bf
= bf
>? springs_
[i
].block_force_
;
145 Simple_spacer::active_springs_stiffness () const
147 Real stiff
= range_stiffness (0, springs_
.size ());
151 all springs are inactive. Take the stiffness of the
152 latest spring to block.
155 Real max_block_force
= -infinity_f
;
157 for (int i
= 0; i
< springs_
.size (); i
++)
159 if (springs_
[i
].block_force_
> max_block_force
)
162 max_block_force
= springs_
[i
].block_force_
;
166 stiff
= springs_
[max_i
].hooke_
;
172 Simple_spacer::set_active_states ()
174 /* float comparison is safe, since force is only copied. */
175 for (int i
= 0; i
< springs_
.size (); i
++)
176 if (springs_
[i
].is_active_
177 && springs_
[i
].block_force_
>= force_
)
179 springs_
[i
].is_active_
= false;
185 Simple_spacer::configuration_length () const
188 for (int i
= 0; i
< springs_
.size (); i
++)
189 l
+= springs_
[i
].length (force_
);
195 Simple_spacer::is_active () const
197 return active_count_
;
201 Simple_spacer::my_solve_linelen ()
205 force_
= active_blocking_force ();
206 Real conf
= configuration_length ();
208 if (conf
< line_len_
)
210 force_
+= (line_len_
- conf
) * active_springs_stiffness ();
214 set_active_states ();
219 Simple_spacer::my_solve_natural_len ()
221 Real line_len_force
= 0.0;
225 force_
= active_blocking_force () >? 0.0;
226 Real conf
= configuration_length ();
228 if (conf
< line_len_
)
230 line_len_force
= force_
232 * active_springs_stiffness ();
235 if (force_
< 1e-8) // ugh.,
238 set_active_states ();
241 force_
= line_len_force
;
244 /****************************************************************/
246 Spring_description::Spring_description ()
255 Spring_description::is_sane () const
259 && !isinf (ideal_
) && !isnan (ideal_
);
263 Spring_description::length (Real f
) const
267 return ideal_
+ f
/ hooke_
;
269 /****************************************************************/
272 TODO: should a add penalty for widely varying spring forces (caused
281 The ## forces the notes apart; we shouldn't allow the O's to touch
285 Simple_spacer_wrapper::solve (Column_x_positions
*positions
, bool ragged
)
288 spacer_
->my_solve_natural_len ();
290 spacer_
->my_solve_linelen ();
292 positions
->force_
= spacer_
->force_
;
295 We used to have a penalty for compression, no matter what, but that
296 fucked up wtk1-fugue2 (taking 3 full pages.)
298 positions
->config_
.push (spacer_
->indent_
);
299 for (int i
= 0; i
< spacer_
->springs_
.size (); i
++)
301 Real l
= spacer_
->springs_
[i
].length ((ragged
) ? 0.0 : spacer_
->force_
);
302 positions
->config_
.push (positions
->config_
.top () + l
);
304 we have l>= 0 here, up to rounding errors
309 For raggedright, we must have a measure of music density: this is
310 to prevent lots of short lines (which all have force = 0).
314 positions
->satisfies_constraints_
315 = positions
->config_
.top () < spacer_
->line_len_
;
318 positions
->satisfies_constraints_
= spacer_
->is_active ();
320 positions
->cols_
= spaced_cols_
;
321 positions
->loose_cols_
= loose_cols_
;
324 Check if breaking constraints are met.
326 bool break_satisfy
= true;
327 int sz
= positions
->cols_
.size ();
328 for (int i
= sz
; i
--;)
330 SCM p
= positions
->cols_
[i
]->get_property ("penalty");
331 if (scm_is_number (p
))
333 if (scm_to_double (p
) < -9999)
334 break_satisfy
= break_satisfy
&& (i
== 0 || i
== sz
-1);
335 if (scm_to_double (p
) > 9999)
336 break_satisfy
= break_satisfy
&& ! (i
== 0 || i
== sz
-1);
340 positions
->satisfies_constraints_
341 = positions
->satisfies_constraints_
&& break_satisfy
;
345 Simple_spacer::add_spring (Real ideal
, Real hooke
)
347 Spring_description desc
;
351 if (!desc
.is_sane ())
353 programming_error ("insane spring found, setting to unit");
361 desc
.is_active_
= false;
368 desc
.block_force_
= -desc
.hooke_
* desc
.ideal_
; // block at distance 0
372 springs_
.push (desc
);
376 compare_paper_column_rank (Grob
*const &a
,
379 return Paper_column::get_rank (a
) - Paper_column::get_rank (b
);
383 Simple_spacer_wrapper::add_columns (Link_array
<Grob
> const &icols
)
385 Link_array
<Grob
> cols (icols
);
387 for (int i
= cols
.size (); i
--;)
388 if (scm_is_pair (cols
[i
]->get_property ("between-cols")))
390 loose_cols_
.push (cols
[i
]);
395 for (int i
= 0; i
< cols
.size () - 1; i
++)
397 Spring_smob
*spring
= 0;
399 for (SCM s
= cols
[i
]->get_property ("ideal-distances");
400 !spring
&& scm_is_pair (s
);
403 Spring_smob
*sp
= unsmob_spring (scm_car (s
));
405 if (sp
->other_
== cols
[i
+ 1])
410 programming_error (_f ("No spring between column %d and next one",
411 Paper_column::get_rank (cols
[i
])));
413 Real ideal
= (spring
) ? spring
->distance_
: spacer_
->default_space_
;
414 Real hooke
= (spring
) ? spring
->strength_
: 1.0;
416 spacer_
->add_spring (ideal
, hooke
);
419 for (int i
= 0; i
< cols
.size () - 1; i
++)
421 for (SCM s
= Spaceable_grob::get_minimum_distances (cols
[i
]);
422 scm_is_pair (s
); s
= scm_cdr (s
))
424 Grob
*other
= unsmob_grob (scm_caar (s
));
425 int oi
= binsearch_links (cols
, other
, &compare_paper_column_rank
);
427 && cols
[oi
] == other
)
429 spacer_
->add_rod (i
, oi
, scm_to_double (scm_cdar (s
)));
434 && !to_boolean (cols
[i
]->get_property ("allow-outside-line")))
436 Interval e
= cols
[i
]->extent (cols
[i
], X_AXIS
);
439 spacer_
->add_rod (i
, cols
.size () - 1, e
[RIGHT
]);
440 spacer_
->add_rod (0, i
, e
[LEFT
]);
446 Simple_spacer_wrapper::Simple_spacer_wrapper ()
448 spacer_
= new Simple_spacer ();
451 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
456 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper
const &)