]> git.donarmstrong.com Git - lilypond.git/blob - lily/simple-spacer.cc
Docs: Fix fixed IR compilation (copy @q and @qq from macros.itely)
[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--2007 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       assert (sp.blocking_force () <= cur_force);
220       if (isinf (sp.blocking_force ()))
221         break;
222
223       double block_dist = (cur_force - sp.blocking_force ()) * inv_hooke;
224       if (cur_len - block_dist < line_len_)
225         {
226           cur_force += (line_len_ - cur_len) / inv_hooke;
227           cur_len = line_len_;
228
229           /*
230             Paranoia check.
231           */
232           assert (fabs (configuration_length (cur_force) - cur_len) < 1e-6);
233           return cur_force;
234         }
235       
236       cur_len -= block_dist;
237       inv_hooke -= sp.inverse_compress_strength ();
238       cur_force = sp.blocking_force ();
239     }
240
241   fits_ = false;
242   return cur_force;
243 }
244
245 void
246 Simple_spacer::add_spring (Spring const &sp)
247 {
248   force_ = max (force_, sp.blocking_force ());
249   springs_.push_back (sp);
250 }
251
252 vector<Real>
253 Simple_spacer::spring_positions () const
254 {
255   vector<Real> ret;
256   ret.push_back (0.);
257
258   for (vsize i = 0; i < springs_.size (); i++)
259     ret.push_back (ret.back () + springs_[i].length (ragged_ && force_ > 0 ? 0.0 : force_));
260   return ret;
261 }
262
263 Real
264 Simple_spacer::force_penalty (bool ragged) const
265 {
266   /* If we are ragged-right, we don't want to penalise according to the force,
267      but according to the amount of whitespace that is present after the end
268      of the line. */
269   if (ragged)
270     return max (0.0, line_len_ - configuration_length (0.0));
271
272   /* Use a convex compression penalty. */
273   Real f = force_;
274   return f - (f < 0 ? f*f*f*f*2 : 0);
275 }
276
277 /****************************************************************/
278
279 struct Rod_description
280 {
281   vsize r_;
282   Real dist_;
283
284   bool operator< (const Rod_description r)
285   {
286     return r_ < r.r_;
287   }
288
289   Rod_description ()
290   {
291     r_ = 0;
292     dist_ = 0;
293   }
294
295   Rod_description (vsize r, Real d)
296   {
297     r_ = r;
298     dist_ = d;
299   }
300 };
301
302 struct Column_description
303 {
304   vector<Rod_description> rods_;
305   vector<Rod_description> end_rods_;   /* use these if they end at the last column of the line */
306   Spring spring_;
307   Spring end_spring_;
308
309   SCM break_permission_;
310   Interval keep_inside_line_;
311
312   Column_description ()
313   {
314     break_permission_ = SCM_EOL;
315   }
316 };
317
318 static bool
319 is_loose (Grob *g)
320 {
321   return (scm_is_pair (g->get_object ("between-cols")));
322 }
323
324 static Grob*
325 maybe_find_prebroken_piece (Grob *g, Direction d)
326 {
327   Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
328   if (ret)
329     return ret;
330   return g;
331 }
332
333 static Grob*
334 next_spaceable_column (vector<Grob*> const &list, vsize starting)
335 {
336   for (vsize i = starting+1; i < list.size (); i++)
337     if (!is_loose (list[i]))
338       return list[i];
339   return 0;
340 }
341
342 static Column_description
343 get_column_description (vector<Grob*> const &cols, vsize col_index, bool line_starter)
344 {
345   Grob *col = cols[col_index];
346   if (line_starter)
347     col = maybe_find_prebroken_piece (col, RIGHT);
348
349   Column_description description;
350   Grob *next_col = next_spaceable_column (cols, col_index);
351   if (next_col)
352     description.spring_ = Spaceable_grob::get_spring (col, next_col);
353
354   Grob *end_col = dynamic_cast<Item*> (cols[col_index+1])->find_prebroken_piece (LEFT);
355   if (end_col)
356     description.end_spring_ = Spaceable_grob::get_spring (col, end_col);
357
358   for (SCM s = Spaceable_grob::get_minimum_distances (col);
359        scm_is_pair (s); s = scm_cdr (s))
360     {
361       Grob *other = unsmob_grob (scm_caar (s));
362       vsize j = binary_search (cols, other, Paper_column::less_than, col_index);
363       if (j != VPOS)
364         {
365           if (cols[j] == other)
366             description.rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
367           else /* it must end at the LEFT prebroken_piece */
368             description.end_rods_.push_back (Rod_description (j, scm_to_double (scm_cdar (s))));
369         }
370     }
371   
372   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
373     description.keep_inside_line_ = col->extent (col, X_AXIS);
374
375   description.break_permission_ = col->get_property ("line-break-permission");
376   return description;
377 }
378
379 vector<Real>
380 get_line_forces (vector<Grob*> const &columns,
381                  Real line_len, Real indent, bool ragged)
382 {
383   vector<vsize> breaks;
384   vector<Real> force;
385   vector<Grob*> non_loose;
386   vector<Column_description> cols;
387   SCM force_break = ly_symbol2scm ("force");
388
389   for (vsize i = 0; i < columns.size (); i++)
390     if (!is_loose (columns[i]) || Paper_column::is_breakable (columns[i]))
391       non_loose.push_back (columns[i]);
392
393   breaks.clear ();
394   breaks.push_back (0);
395   cols.push_back (Column_description ());
396   for (vsize i = 1; i + 1 < non_loose.size (); i++)
397     {
398       if (Paper_column::is_breakable (non_loose[i]))
399         breaks.push_back (cols.size ());
400
401       cols.push_back (get_column_description (non_loose, i, false));
402     }
403   breaks.push_back (cols.size ());
404   force.resize (breaks.size () * breaks.size (), infinity_f);
405
406   for (vsize b = 0; b + 1 < breaks.size (); b++)
407     {
408       cols[breaks[b]] = get_column_description (non_loose, breaks[b], true);
409       vsize st = breaks[b];
410
411       for (vsize c = b+1; c < breaks.size (); c++)
412         {
413           vsize end = breaks[c];
414           Simple_spacer spacer;
415
416           for (vsize i = breaks[b]; i < end - 1; i++)
417             spacer.add_spring (cols[i].spring_);
418           spacer.add_spring (cols[end-1].end_spring_);
419
420
421           for (vsize i = breaks[b]; i < end; i++)
422             {
423               for (vsize r = 0; r < cols[i].rods_.size (); r++)
424                 if (cols[i].rods_[r].r_ < end)
425                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
426               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
427                 if (cols[i].end_rods_[r].r_ == end)
428                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
429               if (!cols[i].keep_inside_line_.is_empty ())
430                 {
431                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
432                   spacer.add_rod (0, i - st, -cols[i].keep_inside_line_[LEFT]);
433                 }
434             }
435           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
436           force[b * breaks.size () + c] = spacer.force_penalty (ragged);
437
438           if (!spacer.fits ())
439             {
440               if (c == b + 1)
441                 force[b * breaks.size () + c] = -200000;
442               else
443                 force[b * breaks.size () + c] = infinity_f;
444               break;
445             }
446           if (end < cols.size () && cols[end].break_permission_ == force_break)
447             break;
448         }
449     }
450   return force;
451 }
452
453 Column_x_positions
454 get_line_configuration (vector<Grob*> const &columns,
455                         Real line_len,
456                         Real indent,
457                         bool ragged)
458 {
459   vector<Column_description> cols;
460   Simple_spacer spacer;
461   Column_x_positions ret;
462
463   ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
464   for (vsize i = 1; i + 1 < columns.size (); i++)
465     {
466       if (is_loose (columns[i]))
467         ret.loose_cols_.push_back (columns[i]);
468       else
469         ret.cols_.push_back (columns[i]);
470     }
471   ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
472
473   /* since we've already put our line-ending column in the column list, we can ignore
474      the end_XXX_ fields of our column_description */
475   for (vsize i = 0; i + 1 < ret.cols_.size (); i++)
476     {
477       cols.push_back (get_column_description (ret.cols_, i, i == 0));
478       spacer.add_spring (cols[i].spring_);
479     }
480   for (vsize i = 0; i < cols.size (); i++)
481     {
482       for (vsize r = 0; r < cols[i].rods_.size (); r++)
483         spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
484
485       if (!cols[i].keep_inside_line_.is_empty ())
486         {
487           spacer.add_rod (i, cols.size (), cols[i].keep_inside_line_[RIGHT]);
488           spacer.add_rod (0, i, -cols[i].keep_inside_line_[LEFT]);
489         }
490     }
491
492   spacer.solve (line_len, ragged);
493   ret.force_ = spacer.force_penalty (ragged);
494
495   ret.config_ = spacer.spring_positions ();
496   for (vsize i = 0; i < ret.config_.size (); i++)
497     ret.config_[i] += indent;
498
499   ret.satisfies_constraints_ = spacer.fits ();
500
501   /*
502     Check if breaking constraints are met.
503   */
504   for (vsize i = 1; i + 1 < ret.cols_.size (); i++)
505     {
506       SCM p = ret.cols_[i]->get_property ("line-break-permission");
507       if (p == ly_symbol2scm ("force"))
508         ret.satisfies_constraints_ = false;
509     }
510
511   return ret;
512 }
513