2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1999--2014 Han-Wen Nienhuys <hanwen@xs4all.nl>
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.
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.
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/>.
20 #include "spacing-spanner.hh"
25 #include "spacing-options.hh"
26 #include "international.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"
43 Spacing_spanner::get_columns (Grob *me_grob)
45 Spanner *me = dynamic_cast<Spanner *> (me_grob);
46 vector<Grob *> all (get_root_system (me)->used_columns ());
47 vsize start = binary_search (all, (Grob *)me->get_bound (LEFT),
48 &Paper_column::less_than);
49 vsize end = binary_search (all, (Grob *) me->get_bound (RIGHT),
50 &Paper_column::less_than);
52 all = vector<Grob *> (all.begin () + start,
53 all.begin () + end + 1);
57 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
59 Spacing_spanner::set_springs (SCM smob)
61 Spanner *me = Spanner::unsmob (smob);
64 can't use get_system () ? --hwn.
66 Spacing_options options;
67 options.init_from_grob (me);
68 vector<Grob *> cols = Spacing_spanner::get_columns (me);
69 set_explicit_neighbor_columns (cols);
71 prune_loose_columns (me, &cols, &options);
72 set_implicit_neighbor_columns (cols);
73 generate_springs (me, cols, &options);
75 return SCM_UNSPECIFIED;
79 We want the shortest note that is also "common" in the piece, so we
80 find the shortest in each measure, and take the most frequently
83 This probably gives weird effects with modern music, where every
84 note has a different duration, but hey, don't write that kind of
88 MAKE_SCHEME_CALLBACK (Spacing_spanner, calc_common_shortest_duration, 1);
90 Spacing_spanner::calc_common_shortest_duration (SCM grob)
92 Spanner *me = Spanner::unsmob (grob);
94 vector<Grob *> cols (get_columns (me));
99 vector<Rational> durations;
102 Rational shortest_in_measure;
103 shortest_in_measure.set_infinite (1);
105 for (vsize i = 0; i < cols.size (); i++)
107 if (Paper_column::is_musical (cols[i]))
109 Moment *when = Moment::unsmob (cols[i]->get_property ("when"));
112 ignore grace notes for shortest notes.
114 if (when && when->grace_part_)
117 SCM st = cols[i]->get_property ("shortest-starter-duration");
118 Moment this_shortest = *Moment::unsmob (st);
119 assert (this_shortest.to_bool ());
120 shortest_in_measure = min (shortest_in_measure, this_shortest.main_part_);
122 else if (!shortest_in_measure.is_infinity ()
123 && Paper_column::is_breakable (cols[i]))
126 for (; j < durations.size (); j++)
128 if (durations[j] > shortest_in_measure)
130 counts.insert (counts.begin () + j, 1);
131 durations.insert (durations.begin () + j, shortest_in_measure);
134 else if (durations[j] == shortest_in_measure)
141 if (durations.size () == j)
143 durations.push_back (shortest_in_measure);
144 counts.push_back (1);
147 shortest_in_measure.set_infinite (1);
151 vsize max_idx = VPOS;
153 for (vsize i = durations.size (); i--;)
155 if (counts[i] >= max_count)
158 max_count = counts[i];
162 SCM bsd = me->get_property ("base-shortest-duration");
163 Rational d = Rational (1, 8);
164 if (Moment *m = Moment::unsmob (bsd))
168 d = min (d, durations[max_idx]);
170 return Moment (d).smobbed_copy ();
174 Spacing_spanner::generate_pair_spacing (Grob *me,
175 Paper_column *left_col, Paper_column *right_col,
176 Paper_column *after_right_col,
177 Spacing_options const *options)
179 if (Paper_column::is_musical (left_col))
181 if (!Paper_column::is_musical (right_col)
182 && (options->float_nonmusical_columns_ || to_boolean (right_col->get_property ("maybe-loose")))
184 && Paper_column::is_musical (after_right_col))
187 TODO: should generate rods to prevent collisions.
189 musical_column_spacing (me, left_col, after_right_col, options);
190 right_col->set_object ("between-cols", scm_cons (left_col->self_scm (),
191 after_right_col->self_scm ()));
194 musical_column_spacing (me, left_col, right_col, options);
196 if (Item *rb = right_col->find_prebroken_piece (LEFT))
197 musical_column_spacing (me, left_col, rb, options);
202 The case that the right part is broken as well is rather
203 rare, but it is possible, eg. with a single empty measure,
204 or if one staff finishes a tad earlier than the rest.
206 Item *lb = left_col->find_prebroken_piece (RIGHT);
207 Item *rb = right_col->find_prebroken_piece (LEFT);
209 if (left_col && right_col)
210 breakable_column_spacing (me, left_col, right_col, options);
213 breakable_column_spacing (me, lb, right_col, options);
216 breakable_column_spacing (me, left_col, rb, options);
219 breakable_column_spacing (me, lb, rb, options);
224 set_column_rods (vector<Grob *> const &cols, Real padding)
226 /* distances[i] will be the distance betwen cols[i-1] and cols[i], and
227 overhangs[j] the amount by which cols[0 thru j] extend beyond cols[j]
228 when each column is placed as far to the left as possible. */
229 vector<Real> distances (cols.size ());
230 vector<Real> overhangs (cols.size ());
232 for (vsize i = 0; i < cols.size (); i++)
234 Item *r = dynamic_cast<Item *> (cols[i]);
235 Item *rb = r->find_prebroken_piece (LEFT);
237 if (Separation_item::is_empty (r) && (!rb || Separation_item::is_empty (rb)))
240 Skyline_pair *skys = Skyline_pair::unsmob (r->get_property ("horizontal-skylines"));
241 overhangs[i] = skys ? (*skys)[RIGHT].max_height () : 0.0;
243 if (0 == i) continue;
245 /* min rather than max because stickout will be negative if the right-hand column
246 sticks out a lot to the left */
247 Real stickout = min (skys ? (*skys)[LEFT].max_height () : 0.0,
248 Separation_item::conditional_skyline (r, cols[i - 1]).max_height ());
250 Real prev_distances = 0.0;
252 /* This is an inner loop and hence it is potentially quadratic. However, we only continue
253 as long as there is a rod to insert. Therefore, this loop will usually only execute
254 a constant number of times per iteration of the outer loop. */
255 for (vsize j = i; j--;)
257 if (overhangs[j] + padding <= prev_distances + distances[i] + stickout)
258 break; // cols[0 thru j] cannot reach cols[i]
260 Item *l = dynamic_cast<Item *> (cols[j]);
261 Item *lb = l->find_prebroken_piece (RIGHT);
263 Real dist = Separation_item::set_distance (l, r, padding);
264 distances[i] = max (distances[i], dist - prev_distances);
268 dist = Separation_item::set_distance (lb, r, padding);
269 // The left-broken version might reach more columns to the
270 // right than the unbroken version, by extending farther and/or
271 // nesting more closely;
272 if (j == i - 1) // check this, the first time we see each lb.
273 overhangs[j] = max (overhangs[j],
274 lb->extent (lb, X_AXIS)[RIGHT]
275 + distances[i] - dist);
278 Separation_item::set_distance (l, rb, padding);
280 Separation_item::set_distance (lb, rb, padding);
282 prev_distances += distances[j];
284 overhangs[i] = max (overhangs[i],
285 overhangs[i - 1] - distances[i]);
290 Spacing_spanner::generate_springs (Grob *me,
291 vector<Grob *> const &cols,
292 Spacing_options const *options)
294 Paper_column *prev = dynamic_cast<Paper_column *> (cols[0]);
295 for (vsize i = 1; i < cols.size (); i++)
297 Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
298 Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i + 1]) : 0;
300 generate_pair_spacing (me, prev, col, next, options);
305 Real padding = robust_scm2double (prev->get_property ("padding"), 0.1);
306 set_column_rods (cols, padding);
310 Generate the space between two musical columns LEFT_COL and RIGHT_COL.
313 Spacing_spanner::musical_column_spacing (Grob *me,
316 Spacing_options const *options)
318 Spring spring = note_spacing (me, left_col, right_col, options);
320 if (options->stretch_uniformly_)
322 spring.set_min_distance (0.0);
323 spring.set_default_strength ();
327 vector<Spring> springs;
328 extract_grob_set (left_col, "spacing-wishes", wishes);
330 for (vsize i = 0; i < wishes.size (); i++)
332 Grob *wish = wishes[i];
333 if (Spacing_interface::left_column (wish) != left_col)
335 /* This shouldn't really happen, but the ancient music
336 stuff really messes up the spacing code, grrr
341 extract_grob_set (wish, "right-items", right_items);
342 bool found_matching_column = false;
343 for (vsize j = 0; j < right_items.size (); j++)
345 Item *it = dynamic_cast<Item *> (right_items[j]);
346 if (it && (right_col == it->get_column ()
347 || right_col->original () == it->get_column ()))
348 found_matching_column = true;
352 This is probably a waste of time in the case of polyphonic
354 if (found_matching_column && Note_spacing::has_interface (wish))
356 Real inc = options->increment_;
357 Grob *gsp = Grob::unsmob (left_col->get_object ("grace-spacing"));
358 if (gsp && Paper_column::when_mom (left_col).grace_part_)
360 Spacing_options grace_opts;
361 grace_opts.init_from_grob (gsp);
362 inc = grace_opts.increment_;
364 springs.push_back (Note_spacing::get_spacing (wish, right_col, spring, inc));
368 if (springs.empty ())
370 if (Paper_column::is_musical (right_col))
373 Min distance should be 0.0. If there are no spacing
374 wishes, we're probably dealing with polyphonic spacing
377 spring.set_min_distance (0.0);
381 spring = merge_springs (springs);
384 if (Paper_column::when_mom (right_col).grace_part_
385 && !Paper_column::when_mom (left_col).grace_part_)
388 Ugh. 0.8 is arbitrary.
394 TODO: make sure that the space doesn't exceed the right margin.
396 if (options->packed_)
399 In packed mode, pack notes as tight as possible. This makes
400 sense mostly in combination with ragged-right mode: the notes
401 are then printed at minimum distance. This is mostly useful
402 for ancient notation, but may also be useful for some flavours
403 of contemporary music. If not in ragged-right mode, lily will
404 pack as many bars of music as possible into a line, but the
405 line will then be stretched to fill the whole linewidth.
407 Note that we don't actually pack things as tightly as possible:
408 we don't allow the next column to begin before this one ends.
410 /* FIXME: the else clause below is the "right" thing to do,
411 but we can't do it because of all the empty columns that the
412 ligature-engravers leave lying around. In that case, the extent of
413 the column is incorrect because it includes note-heads that aren't
414 there. We get around this by only including the column extent if
415 the left-hand column is "genuine". This is a dirty hack and it
416 should be fixed in the ligature-engravers. --jneem
418 if (Paper_column::is_extraneous_column_from_ligature (left_col))
419 spring.set_distance (spring.min_distance ());
421 spring.set_distance (max (left_col->extent (left_col, X_AXIS)[RIGHT],
422 spring.min_distance ()));
424 spring.set_inverse_stretch_strength (1.0);
427 Spaceable_grob::add_spring (left_col, right_col, spring);
431 Check if COL fills the whole measure.
434 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
436 System *sys = get_root_system (me);
437 Item *next = sys->column (col->get_column ()->get_rank () + 1);
441 if (Paper_column::is_musical (next)
442 || Paper_column::is_musical (left)
443 || !Paper_column::is_musical (col)
444 || !Paper_column::is_used (next))
448 = Paper_column::when_mom (next) - Paper_column::when_mom (col);
450 Moment *len = Moment::unsmob (left->get_property ("measure-length"));
455 Don't check for exact measure length, since ending measures are
456 often shortened due to pickups.
458 if (dt.main_part_ > len->main_part_ / Rational (2)
459 && (next->is_broken ()
460 || next->break_status_dir ()))
467 Read hints from L and generate springs.
470 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
471 Spacing_options const *options)
473 vector<Spring> springs;
476 Real full_measure_space = 0.0;
477 if (Paper_column::is_musical (r)
478 && l->break_status_dir () == CENTER
479 && fills_measure (me, l, r))
480 full_measure_space = robust_scm2double (l->get_property ("full-measure-extra-space"), 1.0);
482 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
484 if (dt == Moment (0, 0))
486 extract_grob_set (l, "spacing-wishes", wishes);
488 for (vsize i = 0; i < wishes.size (); i++)
490 Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
492 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
496 column for the left one settings should be ok due automatic
499 assert (spacing_grob->get_column () == l);
501 springs.push_back (Staff_spacing::get_spacing (spacing_grob, r,
502 full_measure_space));
506 if (springs.empty ())
507 spring = standard_breakable_column_spacing (me, l, r, options);
509 spring = merge_springs (springs);
511 if (Paper_column::when_mom (r).grace_part_)
514 Correct for grace notes.
516 Ugh. The 0.8 is arbitrary.
521 if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
523 spring.set_min_distance (0.0);
524 spring.set_default_strength ();
527 Spaceable_grob::add_spring (l, r, spring);
530 ADD_INTERFACE (Spacing_spanner,
531 "The space taken by a note is dependent on its duration."
532 " Doubling a duration adds @code{spacing-increment} to the"
533 " space. The most common shortest note gets"
534 " @code{shortest-duration-space}. Notes that are even shorter"
535 " are spaced proportonial to their duration.\n"
537 "Typically, the increment is the width of a black note head."
538 " In a piece with lots of 8th notes, and some 16th notes, the"
539 " eighth note gets a 2@tie{}note heads width (i.e., the space"
540 " following a note is a 1@tie{}note head width). A 16th note"
541 " is followed by 0.5 note head width. The quarter note is"
542 " followed by 3@tie{}NHW, the half by 4@tie{}NHW, etc.",
545 "average-spacing-wishes "
546 "base-shortest-duration "
547 "common-shortest-duration "
549 "shortest-duration-space "
551 "strict-grace-spacing "
552 "strict-note-spacing "
553 "uniform-stretching "