]> git.donarmstrong.com Git - lilypond.git/blob - lily/spacing-spanner.cc
Revert "Issue 4550 (2/2) Avoid "using namespace std;" in included files"
[lilypond.git] / lily / spacing-spanner.cc
1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3
4   Copyright (C) 1999--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
5
6   LilyPond is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   LilyPond is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "spacing-spanner.hh"
21
22 #include <math.h>
23 #include <cstdio>
24
25 #include "spacing-options.hh"
26 #include "international.hh"
27 #include "main.hh"
28 #include "moment.hh"
29 #include "note-spacing.hh"
30 #include "output-def.hh"
31 #include "paper-column.hh"
32 #include "paper-score.hh"
33 #include "pointer-group-interface.hh"
34 #include "separation-item.hh"
35 #include "skyline-pair.hh"
36 #include "spaceable-grob.hh"
37 #include "spacing-interface.hh"
38 #include "staff-spacing.hh"
39 #include "system.hh"
40 #include "warn.hh"
41
42 using std::vector;
43
44 vector<Grob *>
45 Spacing_spanner::get_columns (Grob *me_grob)
46 {
47   Spanner *me = dynamic_cast<Spanner *> (me_grob);
48   vector<Grob *> all (get_root_system (me)->used_columns ());
49   vsize start = binary_search (all, (Grob *)me->get_bound (LEFT),
50                                &Paper_column::less_than);
51   vsize end = binary_search (all, (Grob *) me->get_bound (RIGHT),
52                              &Paper_column::less_than);
53
54   all = vector<Grob *> (all.begin () + start,
55                         all.begin () + end + 1);
56   return all;
57 }
58
59 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
60 SCM
61 Spacing_spanner::set_springs (SCM smob)
62 {
63   Spanner *me = unsmob<Spanner> (smob);
64
65   /*
66     can't use get_system () ? --hwn.
67   */
68   Spacing_options options;
69   options.init_from_grob (me);
70   vector<Grob *> cols = Spacing_spanner::get_columns (me);
71   set_explicit_neighbor_columns (cols);
72
73   prune_loose_columns (me, &cols, &options);
74   set_implicit_neighbor_columns (cols);
75   generate_springs (me, cols, &options);
76
77   return SCM_UNSPECIFIED;
78 }
79
80 /*
81   We want the shortest note that is also "common" in the piece, so we
82   find the shortest in each measure, and take the most frequently
83   found duration.
84
85   This probably gives weird effects with modern music, where every
86   note has a different duration, but hey, don't write that kind of
87   stuff, then.
88 */
89
90 MAKE_SCHEME_CALLBACK (Spacing_spanner, calc_common_shortest_duration, 1);
91 SCM
92 Spacing_spanner::calc_common_shortest_duration (SCM grob)
93 {
94   Spanner *me = unsmob<Spanner> (grob);
95
96   vector<Grob *> cols (get_columns (me));
97
98   /*
99     ascending in duration
100   */
101   vector<Rational> durations;
102   vector<int> counts;
103
104   Rational shortest_in_measure;
105   shortest_in_measure.set_infinite (1);
106
107   for (vsize i = 0; i < cols.size (); i++)
108     {
109       if (Paper_column::is_musical (cols[i]))
110         {
111           Moment *when = unsmob<Moment> (cols[i]->get_property ("when"));
112
113           /*
114             ignore grace notes for shortest notes.
115           */
116           if (when && when->grace_part_)
117             continue;
118
119           SCM st = cols[i]->get_property ("shortest-starter-duration");
120           Moment this_shortest = *unsmob<Moment> (st);
121           assert (this_shortest.to_bool ());
122           shortest_in_measure = min (shortest_in_measure, this_shortest.main_part_);
123         }
124       else if (!shortest_in_measure.is_infinity ()
125                && Paper_column::is_breakable (cols[i]))
126         {
127           vsize j = 0;
128           for (; j < durations.size (); j++)
129             {
130               if (durations[j] > shortest_in_measure)
131                 {
132                   counts.insert (counts.begin () + j, 1);
133                   durations.insert (durations.begin () + j, shortest_in_measure);
134                   break;
135                 }
136               else if (durations[j] == shortest_in_measure)
137                 {
138                   counts[j]++;
139                   break;
140                 }
141             }
142
143           if (durations.size () == j)
144             {
145               durations.push_back (shortest_in_measure);
146               counts.push_back (1);
147             }
148
149           shortest_in_measure.set_infinite (1);
150         }
151     }
152
153   vsize max_idx = VPOS;
154   int max_count = 0;
155   for (vsize i = durations.size (); i--;)
156     {
157       if (counts[i] >= max_count)
158         {
159           max_idx = i;
160           max_count = counts[i];
161         }
162     }
163
164   SCM bsd = me->get_property ("base-shortest-duration");
165   Rational d = Rational (1, 8);
166   if (Moment *m = unsmob<Moment> (bsd))
167     d = m->main_part_;
168
169   if (max_idx != VPOS)
170     d = min (d, durations[max_idx]);
171
172   return Moment (d).smobbed_copy ();
173 }
174
175 void
176 Spacing_spanner::generate_pair_spacing (Grob *me,
177                                         Paper_column *left_col, Paper_column *right_col,
178                                         Paper_column *after_right_col,
179                                         Spacing_options const *options)
180 {
181   if (Paper_column::is_musical (left_col))
182     {
183       if (!Paper_column::is_musical (right_col)
184           && (options->float_nonmusical_columns_ || to_boolean (right_col->get_property ("maybe-loose")))
185           && after_right_col
186           && Paper_column::is_musical (after_right_col))
187         {
188           /*
189             TODO: should generate rods to prevent collisions.
190           */
191           musical_column_spacing (me, left_col, after_right_col, options);
192           right_col->set_object ("between-cols", scm_cons (left_col->self_scm (),
193                                                            after_right_col->self_scm ()));
194         }
195       else
196         musical_column_spacing (me, left_col, right_col, options);
197
198       if (Item *rb = right_col->find_prebroken_piece (LEFT))
199         musical_column_spacing (me, left_col, rb, options);
200     }
201   else
202     {
203       /*
204         The case that the right part is broken as well is rather
205         rare, but it is possible, eg. with a single empty measure,
206         or if one staff finishes a tad earlier than the rest.
207       */
208       Item *lb = left_col->find_prebroken_piece (RIGHT);
209       Item *rb = right_col->find_prebroken_piece (LEFT);
210
211       if (left_col && right_col)
212         breakable_column_spacing (me, left_col, right_col, options);
213
214       if (lb && right_col)
215         breakable_column_spacing (me, lb, right_col, options);
216
217       if (left_col && rb)
218         breakable_column_spacing (me, left_col, rb, options);
219
220       if (lb && rb)
221         breakable_column_spacing (me, lb, rb, options);
222     }
223 }
224
225 static void
226 set_column_rods (vector<Grob *> const &cols, Real padding)
227 {
228   /* distances[i] will be the distance betwen cols[i-1] and cols[i], and
229      overhangs[j] the amount by which cols[0 thru j] extend beyond cols[j]
230      when each column is placed as far to the left as possible. */
231   vector<Real> distances (cols.size ());
232   vector<Real> overhangs (cols.size ());
233
234   for (vsize i = 0; i < cols.size (); i++)
235     {
236       Item *r = dynamic_cast<Item *> (cols[i]);
237       Item *rb = r->find_prebroken_piece (LEFT);
238
239       if (Separation_item::is_empty (r) && (!rb || Separation_item::is_empty (rb)))
240         continue;
241
242       Skyline_pair *skys = unsmob<Skyline_pair> (r->get_property ("horizontal-skylines"));
243       overhangs[i] = skys ? (*skys)[RIGHT].max_height () : 0.0;
244
245       if (0 == i) continue;
246
247       /* min rather than max because stickout will be negative if the right-hand column
248          sticks out a lot to the left */
249       Real stickout = min (skys ? (*skys)[LEFT].max_height () : 0.0,
250                            Separation_item::conditional_skyline (r, cols[i - 1]).max_height ());
251
252       Real prev_distances = 0.0;
253
254       /* This is an inner loop and hence it is potentially quadratic. However, we only continue
255          as long as there is a rod to insert. Therefore, this loop will usually only execute
256          a constant number of times per iteration of the outer loop. */
257       for (vsize j = i; j--;)
258         {
259           if (overhangs[j] + padding <= prev_distances + distances[i] + stickout)
260             break; // cols[0 thru j] cannot reach cols[i]
261
262           Item *l = dynamic_cast<Item *> (cols[j]);
263           Item *lb = l->find_prebroken_piece (RIGHT);
264
265           Real dist = Separation_item::set_distance (l, r, padding);
266           distances[i] = max (distances[i], dist - prev_distances);
267
268           if (lb)
269             {
270               dist = Separation_item::set_distance (lb, r, padding);
271               // The left-broken version might reach more columns to the
272               // right than the unbroken version, by extending farther and/or
273               // nesting more closely;
274               if (j == i - 1) // check this, the first time we see each lb.
275                 overhangs[j] = max (overhangs[j],
276                                     lb->extent (lb, X_AXIS)[RIGHT]
277                                     + distances[i] - dist);
278             }
279           if (rb)
280             Separation_item::set_distance (l, rb, padding);
281           if (lb && rb)
282             Separation_item::set_distance (lb, rb, padding);
283
284           prev_distances += distances[j];
285         }
286       overhangs[i] = max (overhangs[i],
287                           overhangs[i - 1] - distances[i]);
288     }
289 }
290
291 void
292 Spacing_spanner::generate_springs (Grob *me,
293                                    vector<Grob *> const &cols,
294                                    Spacing_options const *options)
295 {
296   Paper_column *prev = dynamic_cast<Paper_column *> (cols[0]);
297   for (vsize i = 1; i < cols.size (); i++)
298     {
299       Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
300       Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i + 1]) : 0;
301
302       generate_pair_spacing (me, prev, col, next, options);
303
304       prev = col;
305     }
306
307   Real padding = robust_scm2double (prev->get_property ("padding"), 0.1);
308   set_column_rods (cols, padding);
309 }
310
311 /*
312   Generate the space between two musical columns LEFT_COL and RIGHT_COL.
313 */
314 void
315 Spacing_spanner::musical_column_spacing (Grob *me,
316                                          Item *left_col,
317                                          Item *right_col,
318                                          Spacing_options const *options)
319 {
320   Spring spring = note_spacing (me, left_col, right_col, options);
321
322   if (options->stretch_uniformly_)
323     {
324       spring.set_min_distance (0.0);
325       spring.set_default_strength ();
326     }
327   else
328     {
329       vector<Spring> springs;
330       extract_grob_set (left_col, "spacing-wishes", wishes);
331
332       for (vsize i = 0; i < wishes.size (); i++)
333         {
334           Grob *wish = wishes[i];
335           if (Spacing_interface::left_column (wish) != left_col)
336             {
337               /* This shouldn't really happen, but the ancient music
338                  stuff really messes up the spacing code, grrr
339               */
340               continue;
341             }
342
343           extract_grob_set (wish, "right-items", right_items);
344           bool found_matching_column = false;
345           for (vsize j = 0; j < right_items.size (); j++)
346             {
347               Item *it = dynamic_cast<Item *> (right_items[j]);
348               if (it && (right_col == it->get_column ()
349                          || right_col->original () == it->get_column ()))
350                 found_matching_column = true;
351             }
352
353           /*
354             This is probably a waste of time in the case of polyphonic
355             music.  */
356           if (found_matching_column && has_interface<Note_spacing> (wish))
357             {
358               Real inc = options->increment_;
359               Grob *gsp = unsmob<Grob> (left_col->get_object ("grace-spacing"));
360               if (gsp && Paper_column::when_mom (left_col).grace_part_)
361                 {
362                   Spacing_options grace_opts;
363                   grace_opts.init_from_grob (gsp);
364                   inc = grace_opts.increment_;
365                 }
366               springs.push_back (Note_spacing::get_spacing (wish, right_col, spring, inc));
367             }
368         }
369
370       if (springs.empty ())
371         {
372           if (Paper_column::is_musical (right_col))
373             {
374               /*
375                 Min distance should be 0.0. If there are no spacing
376                 wishes, we're probably dealing with polyphonic spacing
377                 of hemiolas.
378               */
379               spring.set_min_distance (0.0);
380             }
381         }
382       else
383         spring = merge_springs (springs);
384     }
385
386   if (Paper_column::when_mom (right_col).grace_part_
387       && !Paper_column::when_mom (left_col).grace_part_)
388     {
389       /*
390         Ugh. 0.8 is arbitrary.
391       */
392       spring *= 0.8;
393     }
394
395   /*
396     TODO: make sure that the space doesn't exceed the right margin.
397   */
398   if (options->packed_)
399     {
400       /*
401         In packed mode, pack notes as tight as possible.  This makes
402         sense mostly in combination with ragged-right mode: the notes
403         are then printed at minimum distance.  This is mostly useful
404         for ancient notation, but may also be useful for some flavours
405         of contemporary music.  If not in ragged-right mode, lily will
406         pack as many bars of music as possible into a line, but the
407         line will then be stretched to fill the whole linewidth.
408
409         Note that we don't actually pack things as tightly as possible:
410         we don't allow the next column to begin before this one ends.
411       */
412       /* FIXME: the else clause below is the "right" thing to do,
413          but we can't do it because of all the empty columns that the
414          ligature-engravers leave lying around. In that case, the extent of
415          the column is incorrect because it includes note-heads that aren't
416          there. We get around this by only including the column extent if
417          the left-hand column is "genuine". This is a dirty hack and it
418          should be fixed in the ligature-engravers. --jneem
419       */
420       if (Paper_column::is_extraneous_column_from_ligature (left_col))
421         spring.set_distance (spring.min_distance ());
422       else
423         spring.set_distance (max (left_col->extent (left_col, X_AXIS)[RIGHT],
424                                   spring.min_distance ()));
425
426       spring.set_inverse_stretch_strength (1.0);
427     }
428
429   Spaceable_grob::add_spring (left_col, right_col, spring);
430 }
431
432 /*
433   Check if COL fills the whole measure.
434  */
435 bool
436 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
437 {
438   System *sys = get_root_system (me);
439   Item *next = sys->column (col->get_column ()->get_rank () + 1);
440   if (!next)
441     return false;
442
443   if (Paper_column::is_musical (next)
444       || Paper_column::is_musical (left)
445       || !Paper_column::is_musical (col)
446       || !Paper_column::is_used (next))
447     return false;
448
449   Moment dt
450     = Paper_column::when_mom (next) - Paper_column::when_mom (col);
451
452   Moment *len = unsmob<Moment> (left->get_property ("measure-length"));
453   if (!len)
454     return false;
455
456   /*
457     Don't check for exact measure length, since ending measures are
458     often shortened due to pickups.
459    */
460   if (dt.main_part_ > len->main_part_ / Rational (2)
461       && (next->is_broken ()
462           || next->break_status_dir ()))
463     return true;
464
465   return false;
466 }
467
468 /*
469   Read hints from L and generate springs.
470 */
471 void
472 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
473                                            Spacing_options const *options)
474 {
475   vector<Spring> springs;
476   Spring spring;
477
478   Real full_measure_space = 0.0;
479   if (Paper_column::is_musical (r)
480       && l->break_status_dir () == CENTER
481       && fills_measure (me, l, r))
482     full_measure_space = robust_scm2double (l->get_property ("full-measure-extra-space"), 1.0);
483
484   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
485
486   if (dt == Moment (0, 0))
487     {
488       extract_grob_set (l, "spacing-wishes", wishes);
489
490       for (vsize i = 0; i < wishes.size (); i++)
491         {
492           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
493
494           if (!spacing_grob || !has_interface<Staff_spacing> (spacing_grob))
495             continue;
496
497           /*
498             column for the left one settings should be ok due automatic
499             pointer munging.
500           */
501           assert (spacing_grob->get_column () == l);
502
503           springs.push_back (Staff_spacing::get_spacing (spacing_grob, r,
504                                                          full_measure_space));
505         }
506     }
507
508   if (springs.empty ())
509     spring = standard_breakable_column_spacing (me, l, r, options);
510   else
511     spring = merge_springs (springs);
512
513   if (Paper_column::when_mom (r).grace_part_)
514     {
515       /*
516         Correct for grace notes.
517
518         Ugh. The 0.8 is arbitrary.
519       */
520       spring *= 0.8;
521     }
522
523   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
524     {
525       spring.set_min_distance (0.0);
526       spring.set_default_strength ();
527     }
528
529   Spaceable_grob::add_spring (l, r, spring);
530 }
531
532 ADD_INTERFACE (Spacing_spanner,
533                "The space taken by a note is dependent on its duration."
534                "  Doubling a duration adds @code{spacing-increment} to the"
535                " space.  The most common shortest note gets"
536                " @code{shortest-duration-space}.  Notes that are even shorter"
537                " are spaced proportonial to their duration.\n"
538                "\n"
539                "Typically, the increment is the width of a black note head."
540                "  In a piece with lots of 8th notes, and some 16th notes, the"
541                " eighth note gets a 2@tie{}note heads width (i.e., the space"
542                " following a note is a 1@tie{}note head width).  A 16th note"
543                " is followed by 0.5 note head width.  The quarter note is"
544                " followed by 3@tie{}NHW, the half by 4@tie{}NHW, etc.",
545
546                /* properties */
547                "average-spacing-wishes "
548                "base-shortest-duration "
549                "common-shortest-duration "
550                "packed-spacing "
551                "shortest-duration-space "
552                "spacing-increment "
553                "strict-grace-spacing "
554                "strict-note-spacing "
555                "uniform-stretching "
556               );
557