2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2002 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
65 compression_penalty_b_
= false;
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 ("Weird minimum distance. Ignoring");
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
].active_b_
)
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
].active_b_
)
139 bf
= bf
>? springs_
[i
].block_force_
;
145 Simple_spacer::active_springs_stiffness () const
148 for (int i
=0; i
< springs_
.size (); i
++)
149 if (springs_
[i
].active_b_
)
151 den
+= 1 / springs_
[i
].hooke_
;
157 Simple_spacer::set_active_states ()
159 /* float comparison is safe, since force is only copied. */
160 for (int i
=0 ; i
<springs_
.size (); i
++)
161 if (springs_
[i
].active_b_
162 && springs_
[i
].block_force_
>= force_
)
164 springs_
[i
].active_b_
= false;
170 Simple_spacer::configuration_length () const
173 for (int i
=0; i
< springs_
.size (); i
++)
174 l
+= springs_
[i
].length (force_
);
180 Simple_spacer::active_b () const
182 return active_count_
;
186 Simple_spacer::my_solve_linelen ()
190 force_
= active_blocking_force ();
191 Real conf
= configuration_length ();
193 if (conf
< line_len_
)
195 force_
+= (line_len_
- conf
) * active_springs_stiffness ();
199 set_active_states ();
205 Simple_spacer::my_solve_natural_len ()
209 force_
= active_blocking_force () >? 0.0;
211 if (force_
< 1e-8) // ugh.,
214 set_active_states ();
219 Simple_spacer::add_columns (Link_array
<Grob
> const &icols
)
221 Link_array
<Grob
> cols(icols
);
223 for (int i
= cols
.size (); i
--;)
224 if (gh_pair_p (cols
[i
]->get_grob_property ("between-cols")))
226 loose_cols_
.push (cols
[i
]);
231 for (int i
=0; i
< cols
.size () - 1; i
++)
233 Spring_smob
*spring
= 0;
235 for (SCM s
= cols
[i
]->get_grob_property ("ideal-distances");
236 !spring
&& gh_pair_p (s
);
239 Spring_smob
*sp
= unsmob_spring (ly_car (s
));
242 if (sp
->other_
== cols
[i
+1])
246 Spring_description desc
;
249 desc
.ideal_
= spring
->distance_
;
250 desc
.hooke_
= spring
->strength_
;
254 programming_error (_f("No spring between column %d and next one",
255 Paper_column::get_rank (cols
[i
])
258 desc
.ideal_
= default_space_
;
265 programming_error ("Insane spring found. Setting to unit spring.");
271 if (isinf (desc
.hooke_
))
273 desc
.active_b_
= false;
274 springs_
.push (desc
);
278 desc
.block_force_
= - desc
.hooke_
* desc
.ideal_
; // block at distance 0
279 springs_
.push (desc
);
284 if (spring
->expand_only_b_
)
286 compression_penalty_b_
= true;
291 for (int i
=0; i
< cols
.size () - 1; i
++)
293 for (SCM s
= Spaceable_grob::get_minimum_distances (cols
[i
]);
294 gh_pair_p (s
); s
= ly_cdr (s
))
296 Grob
* other
= unsmob_grob (ly_caar (s
));
297 int oi
= cols
.find_index (other
);
300 add_rod (i
, oi
, gh_scm2double (ly_cdar (s
)));
306 TODO: should support natural length on only the last line.
309 my_solve_natural_len ();
316 TODO: should a add penalty for widely varying spring forces (caused
325 The ## forces the notes apart; we shouldn't allow the O's to touch
330 Simple_spacer::solve (Column_x_positions
*positions
, bool ragged
) const
332 positions
->force_
= force_
;
337 We used to have a penalty for compression, no matter what, but that
338 fucked up wtk1-fugue2 (taking 3 full pages.)
340 maybe this should be tunable?
342 if (compression_penalty_b_
)
343 ; // positions->force_ *= 2; // hmm.
346 positions
->config_
.push (indent_
);
347 for (int i
=0; i
<springs_
.size (); i
++)
349 Real l
= springs_
[i
].length ((ragged
) ? 0.0 : force_
);
350 positions
->config_
.push (positions
->config_
.top () + l
);
352 we have l>= 0 here, up to rounding errors
355 positions
->cols_
= spaced_cols_
;
356 positions
->loose_cols_
= loose_cols_
;
358 positions
->satisfies_constraints_b_
= (line_len_
< 0) || active_b ();
362 Check if breaking constraints are met.
364 bool break_satisfy
= true;
365 int sz
= positions
->cols_
.size ();
366 for (int i
= sz
; i
--; )
368 SCM p
= positions
->cols_
[i
]->get_grob_property( "penalty");
371 if (gh_scm2double (p
) < -9999)
372 break_satisfy
= break_satisfy
&& (i
== 0 || i
== sz
-1);
373 if (gh_scm2double (p
) > 9999)
374 break_satisfy
= break_satisfy
&& !(i
== 0 || i
== sz
-1);
379 positions
->satisfies_constraints_b_
=
380 positions
->satisfies_constraints_b_
&& break_satisfy
;
382 if (ragged
&& force_
< 0)
383 positions
->satisfies_constraints_b_
= false;
386 /****************************************************************/
388 Spring_description::Spring_description ()
398 Spring_description::sane_b () const
400 return (hooke_
> 0) && !isinf (ideal_
) && !isnan (ideal_
);
404 Spring_description::length (Real f
) const
408 return ideal_
+ f
/ hooke_
;