]> git.donarmstrong.com Git - lilypond.git/blob - lily/simple-spacer.cc
Merge branch 'lilypond/translation' of ssh://git.sv.gnu.org/srv/git/lilypond into...
[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--2009 Han-Wen Nienhuys <hanwen@xs4all.nl>
7
8   TODO:
9   - add support for different stretch/shrink constants?
10 */
11
12 #include <cstdio>
13
14 #include "column-x-positions.hh"
15 #include "dimensions.hh"
16 #include "international.hh"
17 #include "libc-extension.hh"    // isinf
18 #include "paper-column.hh"
19 #include "simple-spacer.hh"
20 #include "spaceable-grob.hh"
21 #include "spring.hh"
22 #include "warn.hh"
23
24 /*
25   A simple spacing constraint solver. The approach:
26
27   Stretch the line uniformly until none of the constraints (rods)
28   block.  It then is very wide.
29
30   Compress until the next constraint blocks,
31
32   Mark the springs over the constrained part to be non-active.
33
34   Repeat with the smaller set of non-active constraints, until all
35   constraints blocked, or until the line is as short as desired.
36
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
40
41   c4                   c4           c4                  c4
42   veryveryverylongsyllable2         veryveryverylongsyllable2
43   " "4                 veryveryverylongsyllable2        syllable4
44
45
46   can be further compressed to
47
48
49   c4    c4                        c4   c4
50   veryveryverylongsyllable2       veryveryverylongsyllable2
51   " "4  veryveryverylongsyllable2      syllable4
52
53
54   Perhaps this is not a bad thing, because the 1st looks better anyway.  */
55
56 /*
57   positive force = expanding, negative force = compressing.
58 */
59
60 Simple_spacer::Simple_spacer ()
61 {
62   line_len_ = 0.0;
63   force_ = 0.0;
64   fits_ = true;
65   ragged_ = true;
66 }
67
68 Real
69 Simple_spacer::force () const
70 {
71   return force_;
72 }
73
74 bool
75 Simple_spacer::fits () const
76 {
77   return fits_;
78 }
79
80 Real
81 Simple_spacer::rod_force (int l, int r, Real dist)
82 {
83   Real d = range_ideal_len (l, r);
84   Real c = range_stiffness (l, r, dist > d);
85   Real block_stretch = dist - d;
86
87   if (isinf (c) && block_stretch == 0) /* take care of the 0*infinity_f case */
88     return 0;
89   return c * block_stretch;
90 }
91
92 void
93 Simple_spacer::add_rod (int l, int r, Real dist)
94 {
95   if (isinf (dist) || isnan (dist))
96     {
97       programming_error ("ignoring weird minimum distance");
98       return;
99     }
100
101   Real block_force = rod_force (l, r, dist);
102
103   if (isinf (block_force))
104     {
105       Real spring_dist = range_ideal_len (l, r);
106       if (spring_dist < dist)
107         for (int i = l; i < r; i++)
108           {
109             if (spring_dist)
110               springs_[i].set_distance (springs_[i].distance () * dist / spring_dist);
111             else
112               springs_[i].set_distance (dist / (r - l));
113           }
114
115       return;
116     }
117   force_ = max (force_, block_force);
118   for (int i = l; i < r; i++)
119     springs_[i].set_blocking_force (max (block_force, springs_[i].blocking_force ()));
120 }
121
122 Real
123 Simple_spacer::range_ideal_len (int l, int r) const
124 {
125   Real d = 0.;
126   for (int i = l; i < r; i++)
127     d += springs_[i].distance ();
128   return d;
129 }
130
131 Real
132 Simple_spacer::range_stiffness (int l, int r, bool stretch) const
133 {
134   Real den = 0.0;
135   for (int i = l; i < r; i++)
136     den += stretch ? springs_[i].inverse_stretch_strength ()
137       : springs_[i].inverse_compress_strength ();
138
139   return 1 / den;
140 }
141
142 Real
143 Simple_spacer::configuration_length (Real force) const
144 {
145   Real l = 0.;
146   for (vsize i = 0; i < springs_.size (); i++)
147     l += springs_[i].length (force);
148
149   return l;
150 }
151
152 void
153 Simple_spacer::solve (Real line_len, bool ragged)
154 {
155   Real conf = configuration_length (force_);
156
157   ragged_ = ragged;
158   line_len_ = line_len;
159   if (conf < line_len_)
160     force_ = expand_line ();
161   else if (conf > line_len_)
162     force_ = compress_line ();
163
164   if (ragged && force_ < 0)
165     fits_ = false;
166 }
167
168 Real
169 Simple_spacer::expand_line ()
170 {
171   double inv_hooke = 0;
172   double cur_len = configuration_length (force_);
173
174   fits_ = true;
175   for (vsize i=0; i < springs_.size (); i++)
176     inv_hooke += springs_[i].inverse_stretch_strength ();
177
178   if (inv_hooke == 0.0) /* avoid division by zero. If springs are infinitely stiff */
179     return 0.0;         /* anyway, then it makes no difference what the force is */
180
181   assert (cur_len <= line_len_);
182   return (line_len_ - cur_len) / inv_hooke + force_;
183 }
184
185 Real
186 Simple_spacer::compress_line ()
187 {
188   double inv_hooke = 0;
189   double cur_len = configuration_length (force_);
190   double cur_force = force_;
191   bool compressed = false;
192
193   /* just because we are in compress_line () doesn't mean that the line
194      will actually be compressed (as in, a negative force) because
195      we start out with a stretched line. Here, we check whether we
196      will be compressed or stretched (so we know which spring constant to use) */
197   if (configuration_length (0.0) > line_len_)
198     {
199       cur_force = 0.0;
200       cur_len = configuration_length (0.0);
201       compressed = true;
202     }
203
204   fits_ = true;
205   for (vsize i=0; i < springs_.size (); i++)
206     inv_hooke += compressed
207       ? springs_[i].inverse_compress_strength ()
208       : springs_[i].inverse_stretch_strength ();
209
210   assert (line_len_ <= cur_len);
211
212   vector<Spring> sorted_springs = springs_;
213   sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring> ());
214
215   for (vsize i = 0; i < sorted_springs.size (); i++)
216     {
217       Spring sp = sorted_springs[i];
218
219       if (sp.blocking_force () > cur_force)
220         continue;
221
222       if (isinf (sp.blocking_force ()))
223         break;
224
225       double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
226       if (cur_len - block_dist < line_len_)
227         {
228           cur_force += (line_len_ - cur_len) / inv_hooke;
229           cur_len = line_len_;
230
231           /*
232             Paranoia check.
233           */
234           assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
235           return cur_force;
236         }
237       
238       cur_len -= block_dist;
239       inv_hooke -= compressed ? sp.inverse_compress_strength () : sp.inverse_stretch_strength ();
240       cur_force = sp.blocking_force ();
241     }
242
243   fits_ = false;
244   return cur_force;
245 }
246
247 void
248 Simple_spacer::add_spring (Spring const &sp)
249 {
250   force_ = max (force_, sp.blocking_force ());
251   springs_.push_back (sp);
252 }
253
254 vector<Real>
255 Simple_spacer::spring_positions () const
256 {
257   vector<Real> ret;
258   ret.push_back (0.);
259
260   for (vsize i = 0; i < springs_.size (); i++)
261     ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
262   return ret;
263 }
264
265 Real
266 Simple_spacer::force_penalty (bool ragged) const
267 {
268   /* If we are ragged-right, we don't want to penalise according to the force,
269      but according to the amount of whitespace that is present after the end
270      of the line. */
271   if (ragged)
272     return max (0.0, line_len_ - configuration_length (0.0));
273
274   /* Use a convex compression penalty. */
275   Real f = force_;
276   return f - (f < 0 ? f*f*f*f*2 : 0);
277 }
278
279 /****************************************************************/
280
281 struct Rod_description
282 {
283   vsize r_;
284   Real dist_;
285
286   bool operator< (const Rod_description r)
287   {
288     return r_ < r.r_;
289   }
290
291   Rod_description ()
292   {
293     r_ = 0;
294     dist_ = 0;
295   }
296
297   Rod_description (vsize r, Real d)
298   {
299     r_ = r;
300     dist_ = d;
301   }
302 };
303
304 struct Column_description
305 {
306   vector<Rod_description> rods_;
307   vector<Rod_description> end_rods_;   /* use these if they end at the last column of the line */
308   Spring spring_;
309   Spring end_spring_;
310
311   SCM break_permission_;
312   Interval keep_inside_line_;
313
314   Column_description ()
315   {
316     break_permission_ = SCM_EOL;
317   }
318 };
319
320 static bool
321 is_loose (Grob *g)
322 {
323   return (scm_is_pair (g->get_object ("between-cols")));
324 }
325
326 static Grob*
327 maybe_find_prebroken_piece (Grob *g, Direction d)
328 {
329   Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
330   if (ret)
331     return ret;
332   return g;
333 }
334
335 static Grob*
336 next_spaceable_column (vector<Grob*> const &list, vsize starting)
337 {
338   for (vsize i = starting+1; i < list.size (); i++)
339     if (!is_loose (list[i]))
340       return list[i];
341   return 0;
342 }
343
344 static Column_description
345 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
346 {
347   Grob *col = cols[col_index];
348   if (line_starter)
349     col = maybe_find_prebroken_piece (col, RIGHT);
350
351   Column_description description;
352   Grob *next_col = next_spaceable_column (cols, col_index);
353   if (next_col)
354     description.spring_ = Spaceable_grob::get_spring (col, next_col);
355
356   Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
357   if (end_col)
358     description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
359
360   for (SCM s = Spaceable_grob::get_minimum_distances (col);
361        scm_is_pair (s); s = scm_cdr (s))
362     {
363       Grob *other = unsmob_grob (scm_caar (s));
364       vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
365       if (j != VPOS)
366         {
367           if (cols[j] == other)
368             description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
369           else /* it must end at the LEFT prebroken_piece */
370             description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
371         }
372     }
373   
374   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
375     description.keep_inside_line_ = col->extent (col, X_AXIS);
376
377   description.break_permission_ = col->get_property ("line-break-permission");
378   return description;
379 }
380
381 vector<Real>
382 get_line_forces (vector<Grob*> const &columns,
383                  Real line_len, Real indent, bool ragged)
384 {
385   vector<vsize> breaks;
386   vector<Real> force;
387   vector<Grob*> non_loose;
388   vector<Column_description> cols;
389   SCM force_break = ly_symbol2scm ("force");
390
391   for (vsize i = 0; i < columns.size (); i++)
392     if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
393       non_loose.push_back (columns[i]);
394
395   breaks.clear ();
396   breaks.push_back (0);
397   cols.push_back (Column_description ());
398   for (vsize i = 1; i + 1 < non_loose.size (); i++)
399     {
400       if (Paper_column::is_breakable (non_loose[i]))
401         breaks.push_back (cols.size ());
402
403       cols.push_back (get_column_description (non_loose, i, false));
404     }
405   breaks.push_back (cols.size ());
406   force.resize (breaks.size () * breaks.size (), infinity_f);
407
408   for (vsize b = 0; b + 1 < breaks.size (); b++)
409     {
410       cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
411       vsize st = breaks[b];
412
413       for (vsize c = b+1; c < breaks.size (); c++)
414         {
415           vsize end = breaks[c];
416           Simple_spacer spacer;
417
418           for (vsize i = breaks[b]; i < end - 1; i++)
419             spacer.add_spring (cols[i].spring_);
420           spacer.add_spring (cols[end-1].end_spring_);
421
422
423           for (vsize i = breaks[b]; i < end; i++)
424             {
425               for (vsize r = 0; r < cols[i].rods_.size (); r++)
426                 if (cols[i].rods_[r].r_ < end)
427                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
428               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
429                 if (cols[i].end_rods_[r].r_ == end)
430                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
431               if (!cols[i].keep_inside_line_.is_empty ())
432                 {
433                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
434                   spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
435                 }
436             }
437           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
438           force[b * breaks.size () + c] = spacer.force_penalty (ragged);
439
440           if (!spacer.fits ())
441             {
442               if (c == b + 1)
443                 force[b * breaks.size () + c] = -200000;
444               else
445                 force[b * breaks.size () + c] = infinity_f;
446               break;
447             }
448           if (end < cols.size () && cols[end].break_permission_ == force_break)
449             break;
450         }
451     }
452   return force;
453 }
454
455 Column_x_positions
456 get_line_configuration (vector<Grob*> const &columns,
457                         Real line_len,
458                         Real indent,
459                         bool ragged)
460 {
461   vector<Column_description> cols;
462   Simple_spacer spacer;
463   Column_x_positions ret;
464
465   ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
466   for (vsize i = 1; i + 1 < columns.size (); i++)
467     {
468       if (is_loose (columns[i]))
469         ret.loose_cols_.push_back (columns[i]);
470       else
471         ret.cols_.push_back (columns[i]);
472     }
473   ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
474
475   /* since we've already put our line-ending column in the column list, we can ignore
476      the end_XXX_ fields of our column_description */
477   for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
478     {
479       cols.push_back (get_column_description (ret.cols_, i, i == 0));
480       spacer.add_spring (cols[i].spring_);
481     }
482   for (vsize i = 0; i < cols.size (); i++)
483     {
484       for (vsize r = 0; r < cols[i].rods_.size (); r++)
485         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
486
487       if (!cols[i].keep_inside_line_.is_empty ())
488         {
489           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
490           spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
491         }
492     }
493
494   spacer.solve (line_len, ragged);
495   ret.force_ = spacer.force_penalty (ragged);
496
497   ret.config_ = spacer.spring_positions ();
498   for (vsize i = 0; i < ret.config_.size (); i++)
499     ret.config_[i] += indent;
500
501   ret.satisfies_constraints_ = spacer.fits ();
502
503   /*
504     Check if breaking constraints are met.
505   */
506   for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
507     {
508       SCM p = ret.cols_[i]->get_property ("line-break-permission");
509       if (p == ly_symbol2scm ("force"))
510         ret.satisfies_constraints_ = false;
511     }
512
513   return ret;
514 }
515