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
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
].is_active_
)
126 den
+= 1 / springs_
[i
].hooke_
;
133 Simple_spacer::is_activelocking_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 return range_stiffness (0, springs_
.size ());
151 Simple_spacer::set_active_states ()
153 /* float comparison is safe, since force is only copied. */
154 for (int i
=0 ; i
<springs_
.size (); i
++)
155 if (springs_
[i
].is_active_
156 && springs_
[i
].block_force_
>= force_
)
158 springs_
[i
].is_active_
= false;
164 Simple_spacer::configuration_length () const
167 for (int i
=0; i
< springs_
.size (); i
++)
168 l
+= springs_
[i
].length (force_
);
174 Simple_spacer::is_active () const
176 return active_count_
;
180 Simple_spacer::my_solve_linelen ()
184 force_
= is_activelocking_force ();
185 Real conf
= configuration_length ();
187 if (conf
< line_len_
)
189 force_
+= (line_len_
- conf
) * active_springs_stiffness ();
193 set_active_states ();
199 Simple_spacer::my_solve_natural_len ()
203 force_
= is_activelocking_force () >? 0.0;
205 if (force_
< 1e-8) // ugh.,
208 set_active_states ();
213 Simple_spacer::add_columns (Link_array
<Grob
> const &icols
)
215 Link_array
<Grob
> cols (icols
);
217 for (int i
= cols
.size (); i
--;)
218 if (ly_c_pair_p (cols
[i
]->get_property ("between-cols")))
220 loose_cols_
.push (cols
[i
]);
225 for (int i
=0; i
< cols
.size () - 1; i
++)
227 Spring_smob
*spring
= 0;
229 for (SCM s
= cols
[i
]->get_property ("ideal-distances");
230 !spring
&& ly_c_pair_p (s
);
233 Spring_smob
*sp
= unsmob_spring (ly_car (s
));
236 if (sp
->other_
== cols
[i
+1])
240 Spring_description desc
;
243 desc
.ideal_
= spring
->distance_
;
244 desc
.hooke_
= spring
->strength_
;
248 programming_error (_f ("No spring between column %d and next one",
249 Paper_column::get_rank (cols
[i
])
252 desc
.ideal_
= default_space_
;
257 if (!desc
.is_sane ())
259 programming_error ("Insane spring found. Setting to unit spring.");
265 if (isinf (desc
.hooke_
))
267 desc
.is_active_
= false;
268 springs_
.push (desc
);
272 desc
.block_force_
= - desc
.hooke_
* desc
.ideal_
; // block at distance 0
273 springs_
.push (desc
);
278 if (spring
->expand_only_b_
)
280 compression_penalty_b_
= true;
285 for (int i
=0; i
< cols
.size () - 1; i
++)
287 for (SCM s
= Spaceable_grob::get_minimum_distances (cols
[i
]);
288 ly_c_pair_p (s
); s
= ly_cdr (s
))
290 Grob
* other
= unsmob_grob (ly_caar (s
));
291 int oi
= cols
.find_index (other
);
294 add_rod (i
, oi
, ly_scm2double (ly_cdar (s
)));
302 TODO: should a add penalty for widely varying spring forces (caused
311 The ## forces the notes apart; we shouldn't allow the O's to touch
316 Simple_spacer::solve (Column_x_positions
*positions
, bool ragged
)
319 my_solve_natural_len ();
323 positions
->force_
= force_
;
326 We used to have a penalty for compression, no matter what, but that
327 fucked up wtk1-fugue2 (taking 3 full pages.)
329 positions
->config_
.push (indent_
);
330 for (int i
=0; i
<springs_
.size (); i
++)
332 Real l
= springs_
[i
].length ((ragged
) ? 0.0 : force_
);
333 positions
->config_
.push (positions
->config_
.top () + l
);
335 we have l>= 0 here, up to rounding errors
340 For raggedright, we must have a measure of music density: this is
341 to prevent lots of short lines (which all have force = 0).
345 Real len
= positions
->config_
.top ();
346 if (line_len_
- len
>= 0)
347 positions
->force_
= ((line_len_
- len
) * active_springs_stiffness ());
350 positions
->force_
= 0.0;
352 Don't go past end-of-line in ragged right.
354 positions
->satisfies_constraints_
= false;
359 positions
->cols_
= spaced_cols_
;
360 positions
->loose_cols_
= loose_cols_
;
361 positions
->satisfies_constraints_
=
362 positions
->satisfies_constraints_
&& is_active ();
365 Check if breaking constraints are met.
367 bool break_satisfy
= true;
368 int sz
= positions
->cols_
.size ();
369 for (int i
= sz
; i
--; )
371 SCM p
= positions
->cols_
[i
]->get_property ( "penalty");
372 if (ly_c_number_p (p
))
374 if (ly_scm2double (p
) < -9999)
375 break_satisfy
= break_satisfy
&& (i
== 0 || i
== sz
-1);
376 if (ly_scm2double (p
) > 9999)
377 break_satisfy
= break_satisfy
&& !(i
== 0 || i
== sz
-1);
382 positions
->satisfies_constraints_
=
383 positions
->satisfies_constraints_
&& break_satisfy
;
386 /****************************************************************/
388 Spring_description::Spring_description ()
398 Spring_description::is_sane () const
400 return (hooke_
> 0) && !isinf (ideal_
) && !isnan (ideal_
);
404 Spring_description::length (Real f
) const
408 return ideal_
+ f
/ hooke_
;