]> git.donarmstrong.com Git - lilypond.git/blob - lily/simple-spacer.cc
Basic-notation reorg and misc small fixes.
[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--2006 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   force_ = 0.;
63   fits_ = true;
64 }
65
66 Real
67 Simple_spacer::force ()
68 {
69   return force_;
70 }
71
72 bool
73 Simple_spacer::fits ()
74 {
75   return fits_;
76 }
77
78 Real
79 Simple_spacer::rod_force (int l, int r, Real dist)
80 {
81   Real c = range_stiffness (l, r);
82   Real d = range_ideal_len (l, r);
83   Real block_stretch = dist - d;
84   return c * block_stretch;
85 }
86
87 void
88 Simple_spacer::add_rod (int l, int r, Real dist)
89 {
90   if (isinf (dist) || isnan (dist))
91     {
92       programming_error ("ignoring weird minimum distance");
93       return;
94     }
95
96   Real block_force = rod_force (l, r, dist);
97
98   if (isinf (block_force))
99     {
100       Real spring_dist = range_ideal_len (l, r);
101       if (spring_dist < dist)
102         for (int i = l; i < r; i++)
103           springs_[i].ideal_ *= dist / spring_dist;
104
105       return;
106     }
107   force_ = max (force_, block_force);
108   for (int i = l; i < r; i++)
109     springs_[i].block_force_ = max (block_force, springs_[i].block_force_);
110 }
111
112 Real
113 Simple_spacer::range_ideal_len (int l, int r) const
114 {
115   Real d = 0.;
116   for (int i = l; i < r; i++)
117     d += springs_[i].ideal_;
118   return d;
119 }
120
121 Real
122 Simple_spacer::range_stiffness (int l, int r) const
123 {
124   Real den = 0.0;
125   for (int i = l; i < r; i++)
126     den += springs_[i].inverse_hooke_;
127
128   return 1 / den;
129 }
130
131 Real
132 Simple_spacer::configuration_length () const
133 {
134   Real l = 0.;
135   for (vsize i = 0; i < springs_.size (); i++)
136     l += springs_[i].length (force_);
137
138   return l;
139 }
140
141 void
142 Simple_spacer::solve (Real line_len, bool ragged)
143 {
144   Real conf = configuration_length ();
145
146   ragged_ = ragged;
147   line_len_ = line_len;
148   if (ragged)
149     {
150       force_ = 0;
151       fits_ = configuration_length () <= line_len_;
152       /* we need to calculate a force here to prevent a bunch of short lines */
153       if (fits_)
154         force_ = expand_line ();
155     }
156   else if (conf < line_len_)
157     force_ = expand_line ();
158   else if (conf > line_len_)
159     force_ = compress_line ();
160 }
161
162 Real
163 Simple_spacer::expand_line ()
164 {
165   double inv_hooke = 0;
166   double cur_len = configuration_length ();
167
168   fits_ = true;
169   for (vsize i=0; i < springs_.size (); i++)
170     inv_hooke += springs_[i].inverse_hooke_;
171
172   assert (cur_len <= line_len_);
173   return (line_len_ - cur_len) / inv_hooke + force_;
174 }
175
176 Real
177 Simple_spacer::compress_line ()
178 {
179   double inv_hooke = 0;
180   double cur_len = configuration_length ();
181   double cur_force = force_;
182
183   fits_ = true;
184   for (vsize i=0; i < springs_.size (); i++)
185     inv_hooke += springs_[i].inverse_hooke_;
186
187   assert (line_len_ <= cur_len);
188
189   vector<Spring_description> sorted_springs = springs_;
190   sort (sorted_springs.begin (), sorted_springs.end (), greater<Spring_description> ());
191   for (vsize i = 0; i < sorted_springs.size (); i++)
192     {
193       Spring_description sp = sorted_springs[i];
194
195       assert (sp.block_force_ <= cur_force);
196       if (isinf (sp.block_force_))
197         break;
198
199       double block_dist = (cur_force - sp.block_force_) * inv_hooke;
200       if (cur_len - block_dist <= line_len_)
201         return cur_force + (line_len_ - cur_len) / inv_hooke;
202       cur_len -= block_dist;
203       inv_hooke -= sp.inverse_hooke_;
204       cur_force = sp.block_force_;
205     }
206
207   fits_ = false;
208   return cur_force;
209 }
210
211 void
212 Simple_spacer::add_spring (Real ideal, Real inverse_hooke)
213 {
214   Spring_description desc;
215
216   desc.ideal_ = ideal;
217   desc.inverse_hooke_ = inverse_hooke;
218   if (!desc.is_sane ())
219     {
220       programming_error ("insane spring found, setting to unit");
221
222       desc.inverse_hooke_ = 1.0;
223       desc.ideal_ = 1.0;
224     }
225
226   desc.block_force_ = -desc.ideal_ / desc.inverse_hooke_;
227   // block at distance 0
228
229   springs_.push_back (desc);
230 }
231
232 vector<Real>
233 Simple_spacer::spring_positions () const
234 {
235   vector<Real> ret;
236   ret.push_back (0.);
237
238   for (vsize i = 0; i < springs_.size (); i++)
239     ret.push_back (ret.back () + springs_[i].length (ragged_ ? 0.0 : force_));
240   return ret;
241 }
242
243 /****************************************************************/
244
245 Spring_description::Spring_description ()
246 {
247   ideal_ = 0.0;
248   inverse_hooke_ = 0.0;
249   block_force_ = 0.0;
250 }
251
252 bool
253 Spring_description::is_sane () const
254 {
255   return (inverse_hooke_ >= 0)
256     && ideal_ > 0
257     && !isinf (ideal_) && !isnan (ideal_);
258 }
259
260 Real
261 Spring_description::length (Real f) const
262 {
263   return ideal_ + max (f, block_force_) * inverse_hooke_;
264 }
265
266 /****************************************************************/
267
268 /*
269   TODO: should a add penalty for widely varying spring forces (caused
270   by constraints, eg.
271
272
273   .     =====
274   .     |   |
275   .o|o|x ##x
276   .
277
278   The ## forces the notes apart; we shouldn't allow the O's to touch
279   this closely.
280 */
281
282 struct Rod_desc
283 {
284   vsize r_;
285   Real dist_;
286
287   bool operator< (const Rod_desc r)
288   {
289     return r_ < r.r_;
290   }
291
292   Rod_desc () {}
293   Rod_desc (vsize r, Real d)
294   {
295     r_ = r;
296     dist_ = d;
297   }
298 };
299
300 struct Column_desc
301 {
302   vector<Rod_desc> rods_;
303   vector<Rod_desc> end_rods_;   /* use these if they end at the last column of the line */
304   Real ideal_;
305   Real inverse_hooke_;
306   Real end_ideal_;
307   Real end_inverse_hooke_;
308   Interval keep_inside_line_;
309 };
310
311 static int compare_paper_column_rank (Grob *const &a, Grob *const &b);
312
313 static bool
314 is_loose (Grob *g)
315 {
316   return (scm_is_pair (g->get_object ("between-cols")));
317 }
318
319 static Grob*
320 maybe_find_prebroken_piece (Grob *g, Direction d)
321 {
322   Grob *ret = dynamic_cast<Item*> (g)->find_prebroken_piece (d);
323   if (ret)
324     return ret;
325   return g;
326 }
327
328 static Grob*
329 next_spaceable_column (vector<Grob*> const &list, vsize starting)
330 {
331   for (vsize i = starting+1; i < list.size (); i++)
332     if (!is_loose (list[i]))
333       return list[i];
334   return 0;
335 }
336
337 /* this only returns non-NULL if the line-ending column is the next
338    spaceable-or-breakable column */
339 static Grob*
340 next_line_ending_column (vector<Grob*> const &list, vsize starting)
341 {
342   vsize i = starting + 1;
343   for (; i < list.size ()
344          && is_loose (list[i])
345          && !Paper_column::is_breakable (list[i]);
346        i++)
347     ;
348   return dynamic_cast<Item*> (list[i])->find_prebroken_piece (LEFT);
349 }
350
351 static void
352 get_column_spring (Grob *this_col, Grob *next_col, Real *ideal, Real *inv_hooke)
353 {
354   Spring_smob *spring = 0;
355
356   for (SCM s = this_col->get_object ("ideal-distances");
357        !spring && scm_is_pair (s);
358        s = scm_cdr (s))
359     {
360       Spring_smob *sp = unsmob_spring (scm_car (s));
361
362       if (sp->other_ == next_col)
363         spring = sp;
364     }
365
366   if (!spring)
367     programming_error (_f ("No spring between column %d and next one",
368                            Paper_column::get_rank (this_col)));
369
370   *ideal = (spring) ? spring->distance_ : 5.0;
371   *inv_hooke = (spring) ? spring->inverse_strength_ : 1.0;
372 }
373
374 static Column_desc
375 get_column_desc (vector<Grob*> const &cols, vsize col_index, bool line_starter)
376 {
377   Grob *col = cols[col_index];
378   if (line_starter)
379     col = maybe_find_prebroken_piece (col, RIGHT);
380
381   Column_desc desc;
382   Grob *next_col = next_spaceable_column (cols, col_index);
383   if (next_col)
384     get_column_spring (col, next_col, &desc.ideal_, &desc.inverse_hooke_);
385   Grob *end_col = next_line_ending_column (cols, col_index);
386   if (end_col)
387     get_column_spring (col, end_col, &desc.end_ideal_, &desc.end_inverse_hooke_);
388
389   for (SCM s = Spaceable_grob::get_minimum_distances (col);
390        scm_is_pair (s); s = scm_cdr (s))
391     {
392       Grob *other = unsmob_grob (scm_caar (s));
393       vsize j = binary_search (cols, other, &compare_paper_column_rank, col_index);
394       if (j != VPOS)
395         {
396           if (cols[j] == other)
397             desc.rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s))));
398           else /* it must end at the LEFT prebroken_piece */
399             desc.end_rods_.push_back (Rod_desc (j, scm_to_double (scm_cdar (s))));
400         }
401     }
402   if (!line_starter && to_boolean (col->get_property ("keep-inside-line")))
403     desc.keep_inside_line_ = col->extent (col, X_AXIS);
404   return desc;
405 }
406
407 vector<Real>
408 get_line_forces (vector<Grob*> const &icols, vector<vsize> breaks,
409                  Real line_len, Real indent, bool ragged)
410 {
411   vector<Real> force;
412   force.resize (breaks.size () * breaks.size ());
413
414   vector<Column_desc> cols;
415   vsize b = 1;
416   cols.push_back (Column_desc ());
417   for (vsize i = 1; i < icols.size () - 1; i++)
418     {
419       if (b < breaks.size () && breaks[b] == i)
420         {
421           breaks[b] = cols.size ();
422           b++;
423         }
424       if (!is_loose (icols[i]))
425         cols.push_back (get_column_desc (icols, i, false));
426     }
427   breaks.back () = cols.size () - 1;
428
429   for (vsize b = 0; b < breaks.size () - 1; b++)
430     {
431       cols[breaks[b]] = get_column_desc (icols, breaks[b], true);
432       vsize st = breaks[b];
433
434       for (vsize c = b+1; c < breaks.size (); c++)
435         {
436           vsize end = breaks[c];
437           Simple_spacer spacer;
438
439           for (vsize i = breaks[b]; i < end - 1; i++)
440             spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
441           spacer.add_spring (cols[end-1].end_ideal_, cols[end-1].inverse_hooke_);
442
443
444           for (vsize i = breaks[b]; i < end; i++)
445             {
446               for (vsize r = 0; r < cols[i].rods_.size (); r++)
447                 if (cols[i].rods_[r].r_ < end)
448                   spacer.add_rod (i - st, cols[i].rods_[r].r_ - st, cols[i].rods_[r].dist_);
449               for (vsize r = 0; r < cols[i].end_rods_.size (); r++)
450                 if (cols[i].end_rods_[r].r_ == end)
451                   spacer.add_rod (i - st, end - st, cols[i].end_rods_[r].dist_);
452               if (!cols[i].keep_inside_line_.is_empty ())
453                 {
454                   spacer.add_rod (i - st, end - st, cols[i].keep_inside_line_[RIGHT]);
455                   spacer.add_rod (0, i - st, cols[i].keep_inside_line_[LEFT]);
456                 }
457             }
458           spacer.solve ((b == 0) ? line_len - indent : line_len, ragged);
459           force[b * breaks.size () + c] = spacer.force ();
460           if (!spacer.fits ())
461             {
462               force[b * breaks.size () + c] = infinity_f;
463               break;
464             }
465         }
466     }
467   return force;
468 }
469
470 Column_x_positions
471 get_line_configuration (vector<Grob*>const &columns,
472                         Real line_len,
473                         Real indent,
474                         bool ragged)
475 {
476   vector<Column_desc> cols;
477   Simple_spacer spacer;
478   Column_x_positions ret;
479
480   ret.cols_.push_back (dynamic_cast<Item*> (columns[0])->find_prebroken_piece (RIGHT));
481   for (vsize i = 1; i < columns.size () - 1; i++)
482     {
483       if (is_loose (columns[i]))
484         ret.loose_cols_.push_back (columns[i]);
485       else
486         ret.cols_.push_back (columns[i]);
487     }
488   ret.cols_.push_back (dynamic_cast<Item*> (columns.back ())->find_prebroken_piece (LEFT));
489
490   cols.resize (ret.cols_.size () - 1);
491
492   /* since we've already put our line-ending column in the column list, we can ignore
493      the end_XXX_ fields of our column_desc */
494   for (vsize i = 0; i < cols.size (); i++)
495     {
496       cols[i] = get_column_desc (ret.cols_, i, i == 0);
497       spacer.add_spring (cols[i].ideal_, cols[i].inverse_hooke_);
498     }
499   for (vsize i = 0; i < cols.size (); i++)
500     for (vsize r = 0; r < cols[i].rods_.size (); r++)
501       spacer.add_rod (i, cols[i].rods_[r].r_, cols[i].rods_[r].dist_);
502
503   spacer.solve (line_len, ragged);
504   ret.force_ = spacer.force ();
505
506   /*
507     We used to have a penalty for compression, no matter what, but that
508     fucked up wtk1-fugue2 (taking 3 full pages.)
509   */
510   ret.config_ = spacer.spring_positions ();
511   for (vsize i = 0; i < ret.config_.size (); i++)
512     ret.config_[i] += indent;
513
514   ret.satisfies_constraints_ = spacer.fits ();
515
516   /*
517     Check if breaking constraints are met.
518   */
519   for (vsize i = 1; i < ret.cols_.size () - 1; i++)
520     {
521       SCM p = ret.cols_[i]->get_property ("line-break-permission");
522       if (p == ly_symbol2scm ("force"))
523         ret.satisfies_constraints_ = false;
524     }
525
526   return ret;
527 }
528
529 static int
530 compare_paper_column_rank (Grob *const &a,
531                            Grob *const &b)
532 {
533   return Paper_column::get_rank (a) - Paper_column::get_rank (b);
534 }