]> git.donarmstrong.com Git - lilypond.git/blob - lily/simple-spacer.cc
* lily/rest.cc (polyphonic_offset_callback): new function. Do
[lilypond.git] / lily / simple-spacer.cc
1 /*   
2   simple-spacer.cc -- implement Simple_spacer
3   
4   source file of the GNU LilyPond music typesetter
5   
6   (c) 1999--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
7
8   TODO:
9   - add support for different stretch/shrink constants?
10   
11 */
12 #include <stdio.h>
13 #include <math.h>
14 #include <libc-extension.hh>    // isinf
15
16 #include "simple-spacer.hh"
17 #include "paper-column.hh"
18 #include "spring.hh"
19 #include "rod.hh"
20 #include "warn.hh"
21 #include "column-x-positions.hh"
22 #include "spaceable-grob.hh"
23 #include "dimensions.hh"
24
25
26 /*
27    A simple spacing constraint solver. The approach:
28
29    Stretch the line uniformly until none of the constraints (rods)
30    block.  It then is very wide.
31
32       Compress until the next constraint blocks,
33
34       Mark the springs over the constrained part to be non-active.
35       
36    Repeat with the smaller set of non-active constraints, until all
37    constraints blocked, or until the line is as short as desired.
38
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
42
43    c4                   c4           c4                  c4
44    veryveryverylongsyllable2         veryveryverylongsyllable2
45    " "4                 veryveryverylongsyllable2        syllable4
46
47
48    can be further compressed to
49
50
51    c4    c4                        c4   c4
52    veryveryverylongsyllable2       veryveryverylongsyllable2
53    " "4  veryveryverylongsyllable2      syllable4
54
55
56    Perhaps this is not a bad thing, because the 1st looks better anyway.  */
57
58
59 Simple_spacer::Simple_spacer ()
60 {
61   /*
62     Give an extra penalty for compression. Needed to avoid compressing
63     tightly spaced lines.
64   */
65   compression_penalty_b_ = false;
66   active_count_ = 0;
67   force_ = 0.;
68   indent_ =0.0;
69   default_space_ = 20 PT;
70 }
71
72 void
73 Simple_spacer::add_rod (int l, int r, Real dist)
74 {
75   if (isinf (dist) || isnan (dist))
76     {
77       programming_error ("Weird minimum distance. Ignoring");
78       return;
79     }
80
81   Real c = range_stiffness (l,r);
82   if (isinf (c))
83     {
84       /*
85         If a spring is fixed, we have to do something here:
86         we let the rod override the spring. 
87        */
88       Real total_dist = 0.;
89       for (int i = l ; i < r; i++)
90         total_dist += springs_[i].ideal_;
91
92       if (total_dist < dist)
93         for (int i = l ; i < r; i++)
94           springs_[i].ideal_ *= dist/total_dist;
95
96       return;
97     }
98   
99   Real d = range_ideal_len (l,r);
100   Real block_stretch = dist - d;
101   
102   Real block_force = c * block_stretch;
103   force_ = force_ >? block_force;
104
105   for (int i=l; i < r; i++)
106     springs_[i].block_force_ = block_force >?
107       springs_[i].block_force_ ;
108 }
109
110 Real
111 Simple_spacer::range_ideal_len (int l, int r)   const
112 {
113   Real d =0.;
114   for (int i=l; i < r; i++)
115     d += springs_[i].ideal_;
116   return d;
117 }
118
119 Real
120 Simple_spacer::range_stiffness (int l, int r) const
121 {
122   Real den =0.0;
123   for (int i=l; i < r; i++)
124     {
125       if (springs_[i].is_active_)
126         den += 1 / springs_[i].hooke_;
127     }
128
129   return 1 / den;
130 }
131
132 Real
133 Simple_spacer::is_activelocking_force () const
134 {
135   Real bf = - infinity_f; 
136   for (int i=0; i < springs_.size (); i++)
137     if (springs_[i].is_active_)
138       {
139         bf = bf >? springs_[i].block_force_;
140       }
141   return bf;
142 }
143
144 Real
145 Simple_spacer::active_springs_stiffness () const
146 {
147   return range_stiffness (0, springs_.size ());
148 }
149
150 void
151 Simple_spacer::set_active_states ()
152 {
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_)
157       {
158         springs_[i].is_active_ = false;
159         active_count_ --; 
160       }
161 }   
162
163 Real
164 Simple_spacer::configuration_length () const
165 {
166   Real l =0.;
167   for (int i=0; i < springs_.size (); i++)
168     l += springs_[i].length (force_);
169
170   return l;
171 }
172
173 bool
174 Simple_spacer::is_active () const
175 {
176   return active_count_; 
177 }
178
179 void
180 Simple_spacer::my_solve_linelen ()
181 {
182   while (is_active ())
183     {
184       force_ = is_activelocking_force ();
185       Real conf = configuration_length ();
186
187       if (conf < line_len_)
188         {
189           force_ += (line_len_  - conf) * active_springs_stiffness ();
190           break;
191         }
192       else
193         set_active_states ();
194     }
195 }
196
197
198 void
199 Simple_spacer::my_solve_natural_len ()
200 {
201   while (is_active ())
202     {
203       force_ = is_activelocking_force () >? 0.0;
204
205       if (force_ < 1e-8) // ugh.,
206         break;
207       
208       set_active_states ();
209     }
210 }
211
212 void
213 Simple_spacer::add_columns (Link_array<Grob> const &icols)
214 {
215   Link_array<Grob> cols(icols);
216   
217   for (int i =  cols.size (); i--;)
218     if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
219       {
220         loose_cols_.push (cols[i]);
221         cols.del (i);
222       }
223   
224   spaced_cols_ = cols;
225   for (int i=0; i < cols.size () - 1; i++)
226     {
227       Spring_smob *spring = 0;
228
229       for (SCM s = cols[i]->get_grob_property ("ideal-distances");
230            !spring && gh_pair_p (s);
231            s = ly_cdr (s))
232         {
233           Spring_smob *sp = unsmob_spring (ly_car (s));
234           
235           
236           if (sp->other_ == cols[i+1])
237             spring = sp;
238         }
239
240       Spring_description desc;
241       if (spring)
242         {
243           desc.ideal_ = spring->distance_;
244           desc.hooke_ = spring->strength_;
245         }
246       else
247         {
248           programming_error (_f("No spring between column %d and next one",
249                                 Paper_column::get_rank (cols[i])
250                                 ));
251           desc.hooke_ = 1.0;
252           desc.ideal_ = default_space_;
253
254           continue;
255         }
256
257       if (!desc.sane_b ())
258         {
259           programming_error ("Insane spring found. Setting to unit spring.");
260
261           desc.hooke_ = 1.0;
262           desc.ideal_ = 1.0;
263         }
264
265       if (isinf (desc.hooke_))
266         {
267           desc.is_active_ = false;
268           springs_.push (desc);
269         }
270       else
271         {
272           desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
273           springs_.push (desc);
274       
275           active_count_ ++;
276         }
277
278       if (spring->expand_only_b_)
279         {
280           compression_penalty_b_ = true;
281         }
282       
283     }
284   
285   for (int i=0; i < cols.size () - 1; i++)
286     {
287       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
288            gh_pair_p (s); s = ly_cdr (s))
289         {
290           Grob * other = unsmob_grob (ly_caar (s));
291           int oi = cols.find_index (other);
292           if (oi >= 0)
293             {
294               add_rod (i, oi, gh_scm2double (ly_cdar (s)));
295             }
296         }
297     }
298 }
299
300 /*
301   
302   TODO: should a add penalty for widely varying spring forces (caused
303   by constraints, eg.
304
305
306          =====  
307          |   |
308   o|o|  x ##x
309
310
311   The ## forces the notes apart; we shouldn't allow the O's to touch
312   this closely.
313   
314  */
315 void
316 Simple_spacer::solve (Column_x_positions *positions, bool ragged) 
317 {
318   if (ragged)
319     my_solve_natural_len ();
320   else
321     my_solve_linelen ();
322
323   positions->force_ = force_;
324   
325   /*
326     We used to have a penalty for compression, no matter what, but that
327     fucked up wtk1-fugue2 (taking 3 full pages.)
328   */
329   positions->config_.push (indent_);
330   for (int i=0; i <springs_.size (); i++)
331     {
332       Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
333       positions->config_.push (positions->config_.top () + l);
334       /*
335         we have l>= 0 here, up to rounding errors 
336       */
337     }
338
339   /*
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).
342     */
343   if (ragged)
344     {
345       Real len = positions->config_.top ();
346       if (line_len_ - len  >= 0)
347         positions->force_ = ((line_len_ - len) *  active_springs_stiffness ());
348       else
349         {
350           positions->force_ = 0.0;
351           /*
352             Don't go past end-of-line in ragged right.
353            */
354           positions->satisfies_constraints_ = false;
355         }
356     }
357
358
359   positions->cols_ = spaced_cols_;
360   positions->loose_cols_ = loose_cols_;
361   positions->satisfies_constraints_ =
362     positions->satisfies_constraints_ && is_active ();
363
364   /*
365     Check if breaking constraints are met.
366    */
367   bool break_satisfy = true;
368   int sz =  positions->cols_.size ();
369   for (int i = sz; i--; )
370     {
371       SCM p = positions->cols_[i]->get_grob_property( "penalty");
372       if (gh_number_p (p))
373         {
374           if (gh_scm2double (p) < -9999)
375             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
376           if (gh_scm2double (p) > 9999)
377             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
378         }
379       
380     }
381
382   positions->satisfies_constraints_ =
383     positions->satisfies_constraints_ && break_satisfy;
384 }
385
386 /****************************************************************/
387
388 Spring_description::Spring_description ()
389 {
390   ideal_ =0.0;
391   hooke_ =0.0;
392   is_active_ = true;
393   block_force_ = 0.0;
394 }
395
396
397 bool
398 Spring_description::sane_b () const
399 {
400   return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
401 }
402
403 Real
404 Spring_description::length (Real f) const
405 {
406   if (!is_active_)
407     f = block_force_;
408   return ideal_ + f / hooke_ ;
409 }