2 spacing-spanner.cc -- implement Spacing_spanner
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
16 #include "output-def.hh"
17 #include "paper-score.hh"
18 #include "paper-column.hh"
20 #include "note-spacing.hh"
23 #include "staff-spacing.hh"
25 #include "paper-column.hh"
26 #include "spaceable-grob.hh"
27 #include "break-align-interface.hh"
28 #include "spacing-interface.hh"
31 TODO: this file/class is too complex. Should figure out how to chop
39 static void standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
40 Real * fixed, Real * space, Moment);
43 static Real default_bar_spacing (Grob*, Grob*, Grob*, Moment);
44 static Real note_spacing (Grob*, Grob*, Grob*, Moment, bool*);
45 static Real get_duration_space (Grob*, Moment dur, Rational shortest, bool*);
46 static Rational find_shortest (Grob *, Link_array<Grob> const &);
47 static void breakable_column_spacing (Grob*, Item* l, Item *r, Moment);
48 static void find_loose_columns () {}
49 static void prune_loose_columns (Grob*, Link_array<Grob> *cols, Rational);
50 static void find_loose_columns (Link_array<Grob> cols);
51 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
52 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
53 static void do_measure (Rational, Grob*me, Link_array<Grob> *cols);
54 static void musical_column_spacing (Grob*, Item*, Item*, Real, Rational);
55 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
56 static bool has_interface (Grob*);
60 Return whether COL is fixed to its neighbors by some kind of spacing
64 If in doubt, then we're not loose; the spacing engine should space
65 for it, risking suboptimal spacing.
67 (Otherwise, we might risk core dumps, and other weird stuff.)
71 loose_column (Grob *l, Grob *c, Grob *r)
73 SCM rns = c->get_property ("right-neighbors");
74 SCM lns = c->get_property ("left-neighbors");
77 If this column doesn't have a proper neighbor, we should really
78 make it loose, but spacing it correctly is more than we can
81 (this happens in the following situation:
92 the column containing the clef is really loose, and should be
93 attached right to the first column, but that is a lot of work for
94 such a borderline case.)
97 if (!scm_is_pair (lns) || !scm_is_pair (rns))
100 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (scm_car (lns)));
101 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (scm_car (rns)));
103 if (!l_neighbor || !r_neighbor)
106 l_neighbor = l_neighbor->get_column ();
107 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
109 if (l == l_neighbor && r == r_neighbor)
112 if (!l_neighbor || !r_neighbor)
118 Only declare loose if the bounds make a little sense. This means
119 some cases (two isolated, consecutive clef changes) won't be
120 nicely folded, but hey, then don't do that.
122 if (! ((Paper_column::is_musical (l_neighbor) || Item::is_breakable (l_neighbor))
123 && (Paper_column::is_musical (r_neighbor) || Item::is_breakable (r_neighbor))) )
130 A rather hairy check, but we really only want to move around clefs. (anything else?)
132 in any case, we don't want to move bar lines.
134 for (SCM e = c->get_property ("elements"); scm_is_pair (e); e = scm_cdr (e))
136 Grob * g = unsmob_grob (scm_car (e));
137 if (g && Break_align_interface::has_interface (g))
139 for (SCM s = g->get_property ("elements"); scm_is_pair (s);
142 Grob *h = unsmob_grob (scm_car (s));
145 ugh. -- fix staff-bar name?
147 if (h && h->get_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
157 Remove columns that are not tightly fitting from COLS. In the
158 removed columns, set 'between-cols to the columns where it is in
162 Spacing_spanner::prune_loose_columns (Grob*me, Link_array<Grob> *cols, Rational shortest)
164 Link_array<Grob> newcols;
165 Real increment = robust_scm2double (me->get_property ("spacing-increment"), 1.2);
166 for (int i = 0; i < cols->size (); i++)
168 if (Item::is_breakable (cols->elem (i)) || Paper_column::is_musical (cols->elem (i)))
170 newcols.push (cols->elem (i));
174 Grob *c = cols->elem (i);
175 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
177 SCM lns = c->get_property ("left-neighbors");
178 lns = scm_is_pair (lns) ? scm_car (lns) : SCM_BOOL_F;
180 SCM rns = c->get_property ("right-neighbors");
181 rns = scm_is_pair (rns) ? scm_car (rns) : SCM_BOOL_F;
184 Either object can be non existent, if the score ends
187 rns = scm_car (unsmob_grob (rns)->get_property ("right-items"));
188 c->set_property ("between-cols", scm_cons (lns,
192 Set distance constraints for loose columns
194 Drul_array<Grob*> next_door;
195 next_door[LEFT] = cols->elem (i - 1);
196 next_door[RIGHT] = cols->elem (i + 1);
198 Drul_array<Real> dists (0, 0);
203 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
204 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
206 for (SCM s = lc->get_property ("spacing-wishes");
207 scm_is_pair (s); s = scm_cdr (s))
209 Grob *sp = unsmob_grob (scm_car (s));
210 if (Note_spacing::left_column (sp) != lc
211 || Note_spacing::right_column (sp) != rc)
221 The note spacing should be taken from the musical
225 Real base = note_spacing (me, lc, rc, shortest, &dummy);
226 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
230 dists[d] = dists[d] >? space;
234 Real space, fixed_space;
235 Staff_spacing::get_spacing_params (sp,
236 &space, &fixed_space);
238 dists[d] = dists[d] >? fixed_space;
243 while (flip (&d) != LEFT);
246 r.distance_ = dists[LEFT] + dists[RIGHT];
247 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem (i-1));
248 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
262 Set neighboring columns determined by the spacing-wishes grob property.
265 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
267 for (int i = 0; i < cols.size (); i++)
269 SCM right_neighbors = SCM_EOL;
270 int min_rank = 100000; // inf.
273 SCM wishes = cols[i]->get_property ("spacing-wishes");
274 for (SCM s = wishes; scm_is_pair (s); s = scm_cdr (s))
276 Item * wish = dynamic_cast<Item*> (unsmob_grob (scm_car (s)));
278 Item * lc = wish->get_column ();
279 Grob * right = Note_spacing::right_column (wish);
284 Item * rc = dynamic_cast<Item*> (right);
286 int right_rank = Paper_column::get_rank (rc);
287 int left_rank = Paper_column::get_rank (lc);
290 update the left column.
292 if (right_rank <= min_rank)
294 if (right_rank < min_rank)
295 right_neighbors = SCM_EOL;
297 min_rank = right_rank;
298 right_neighbors = scm_cons (wish->self_scm (), right_neighbors);
302 update the right column of the wish.
305 SCM left_neighs = rc->get_property ("left-neighbors");
306 if (scm_is_pair (left_neighs)
307 && unsmob_grob (scm_car (left_neighs)))
309 Item * it = dynamic_cast<Item*> (unsmob_grob (scm_car (left_neighs)));
310 maxrank = Paper_column::get_rank (it->get_column ());
313 if (left_rank >= maxrank)
315 if (left_rank > maxrank)
316 left_neighs = SCM_EOL;
318 left_neighs = scm_cons (wish->self_scm (), left_neighs);
319 rc->set_property ("left-neighbors", right_neighbors);
323 if (scm_is_pair (right_neighbors))
325 cols[i]->set_property ("right-neighbors", right_neighbors);
331 Set neighboring columns that have no left/right-neighbor set
332 yet. Only do breakable non-musical columns, and musical columns.
335 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
337 for (int i = 0; i < cols.size (); i++)
339 Item * it = dynamic_cast<Item*>(cols[i]);
340 if (!Item::is_breakable (it) && !Paper_column::is_musical (it))
343 // it->breakable || it->musical
346 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
348 SCM ln = cols[i] ->get_property ("left-neighbors");
349 if (!scm_is_pair (ln) && i )
351 cols[i]->set_property ("left-neighbors", scm_cons (cols[i-1]->self_scm (), SCM_EOL));
354 SCM rn = cols[i] ->get_property ("right-neighbors");
355 if (!scm_is_pair (rn) && i < cols.size () - 1)
357 cols[i]->set_property ("right-neighbors", scm_cons (cols[i + 1]->self_scm (), SCM_EOL));
363 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
365 Spacing_spanner::set_springs (SCM smob)
367 Grob *me = unsmob_grob (smob);
370 can't use get_system() ? --hwn.
372 Link_array<Grob> all (me->pscore_->system_->columns ());
374 set_explicit_neighbor_columns (all);
376 SCM preset_shortest = me->get_property ("common-shortest-duration");
377 Rational global_shortest;
378 if (unsmob_moment (preset_shortest))
380 global_shortest = unsmob_moment (preset_shortest)->main_part_;
384 global_shortest = find_shortest (me, all);
385 if (be_verbose_global)
386 progress_indication (_f ("Global shortest duration is %s", global_shortest.to_string ()) + "\n");
388 prune_loose_columns (me, &all, global_shortest);
389 set_implicit_neighbor_columns (all);
393 for (int i = 1; i < all.size (); i++)
396 if (Item::is_breakable (sc))
398 Link_array<Grob> measure (all.slice (j, i+1));
399 do_measure (global_shortest, me, &measure);
404 return SCM_UNSPECIFIED;
409 We want the shortest note that is also "common" in the piece, so we
410 find the shortest in each measure, and take the most frequently
413 This probably gives weird effects with modern music, where every
414 note has a different duration, but hey, don't write that kind of
419 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
422 ascending in duration
424 Array<Rational> durations;
427 Rational shortest_in_measure;
428 shortest_in_measure.set_infinite (1);
430 for (int i = 0 ; i < cols.size (); i++)
432 if (Paper_column::is_musical (cols[i]))
434 Moment *when = unsmob_moment (cols[i]->get_property ("when"));
437 ignore grace notes for shortest notes.
439 if (when && when->grace_part_)
442 SCM st = cols[i]->get_property ("shortest-starter-duration");
443 Moment this_shortest = *unsmob_moment (st);
444 assert (this_shortest.to_bool ());
445 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
447 else if (!shortest_in_measure.is_infinity ()
448 && Item::is_breakable (cols[i]))
451 for (; j < durations.size (); j++)
453 if (durations[j] > shortest_in_measure)
455 counts.insert (1, j);
456 durations.insert (shortest_in_measure, j);
459 else if (durations[j] == shortest_in_measure)
466 if (durations.size () == j)
468 durations.push (shortest_in_measure);
472 shortest_in_measure.set_infinite (1);
478 for (int i = durations.size (); i--;)
480 if (counts[i] >= max_count)
483 max_count = counts[i];
486 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
489 SCM bsd = me->get_property ("base-shortest-duration");
490 Rational d = Rational (1, 8);
491 if (Moment *m = unsmob_moment (bsd))
495 d = d <? durations[max_idx] ;
501 Generate spacing for a single measure. We used to have code that did
502 per-measure spacing. Now we have piecewise spacing. We should fix
503 this to support "spacing-regions": some regions have different notes
504 (different time sigs) than others, and should be spaced differently.
507 Spacing_spanner::do_measure (Rational global_shortest, Grob*me,
508 Link_array<Grob> *cols)
511 Real headwid = robust_scm2double (me->get_property ("spacing-increment"), 1);
512 for (int i = 0; i < cols->size () - 1; i++)
514 Item * l = dynamic_cast<Item*> (cols->elem (i));
515 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
517 Paper_column * lc = dynamic_cast<Paper_column*> (l);
518 Paper_column * rc = dynamic_cast<Paper_column*> (r);
520 if (!Paper_column::is_musical (l))
522 breakable_column_spacing (me, l, r, global_shortest);
526 The case that the right part is broken as well is rather
527 rare, but it is possible, eg. with a single empty measure,
528 or if one staff finishes a tad earlier than the rest.
531 Item *lb = l->find_prebroken_piece (RIGHT);
532 Item *rb = r->find_prebroken_piece (LEFT);
535 breakable_column_spacing (me, lb, r, global_shortest);
538 breakable_column_spacing (me, l, rb, global_shortest);
540 breakable_column_spacing (me, lb, rb, global_shortest);
544 musical_column_spacing (me, lc, rc, headwid, global_shortest);
545 if (Item *rb = r->find_prebroken_piece (LEFT))
546 musical_column_spacing (me, lc, rb, headwid, global_shortest);
552 Generate the space between two musical columns LC and RC, given
553 spacing parameters INCR and SHORTEST.
556 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational global_shortest)
558 bool expand_only = false;
559 Real base_note_space = note_spacing (me, lc, rc, global_shortest, &expand_only);
561 Real compound_note_space = 0.0;
562 Real compound_fixed_note_space = 0.0;
565 SCM seq = lc->get_property ("right-neighbors");
568 We adjust the space following a note only if the next note
569 happens after the current note (this is set in the grob
570 property SPACING-SEQUENCE.
572 for (SCM s = seq; scm_is_pair (s); s = scm_cdr (s))
574 Grob * wish = unsmob_grob (scm_car (s));
576 Item *wish_rcol = Note_spacing::right_column (wish);
577 if (Note_spacing::left_column (wish) != lc
578 || (wish_rcol != rc && wish_rcol != rc->original_))
582 This is probably a waste of time in the case of polyphonic
584 if (Note_spacing::has_interface (wish))
589 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
592 compound_note_space = compound_note_space + space;
593 compound_fixed_note_space = compound_fixed_note_space + fixed;
599 if (Paper_column::when_mom (rc).grace_part_ &&
600 !Paper_column::when_mom (lc).grace_part_)
603 Ugh. 0.8 is arbitrary.
605 compound_note_space *= 0.8;
608 if (compound_note_space < 0 || wish_count == 0)
610 compound_note_space = base_note_space;
611 compound_fixed_note_space = increment;
615 compound_note_space /= wish_count;
616 compound_fixed_note_space /= wish_count;
620 Whatever we do, the fixed space is smaller than the real
623 TODO: this criterion is discontinuous in the derivative.
624 Maybe it should be continuous?
626 compound_fixed_note_space = compound_fixed_note_space <? compound_note_space;
628 bool packed = to_boolean (me->get_layout ()->c_variable ("packed"));
629 Real strength, distance;
632 TODO: make sure that the space doesn't exceed the right margin.
637 In packed mode, pack notes as tight as possible. This makes
638 sense mostly in combination with raggedright mode: the notes
639 are then printed at minimum distance. This is mostly useful
640 for ancient notation, but may also be useful for some flavours
641 of contemporary music. If not in raggedright mode, lily will
642 pack as much bars of music as possible into a line, but the
643 line will then be stretched to fill the whole linewidth.
646 distance = compound_fixed_note_space;
650 strength = 1 / (compound_note_space - compound_fixed_note_space);
651 distance = compound_note_space;
654 Spaceable_grob::add_spring (lc, rc, distance, strength);
659 The one-size-fits all spacing. It doesn't take into account
660 different spacing wishes from one to the next column.
663 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
664 Real * fixed, Real * space,
669 Drul_array<Item*> cols (l, r);
673 if (!Paper_column::is_musical (cols[d]))
676 Tied accidentals over barlines cause problems, so lets see
677 what happens if we do this for non musical columns only.
679 Interval lext = cols[d]->extent (cols [d], X_AXIS);
680 if (!lext.is_empty ())
681 *fixed += -d * lext[-d];
684 while (flip (&d) != LEFT);
687 if (l->is_breakable (l) && r->is_breakable (r))
689 Moment *dt = unsmob_moment (l->get_property ("measure-length"));
694 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
696 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
700 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
702 if (dt == Moment (0, 0))
705 In this case, Staff_spacing should handle the job,
706 using dt when it is 0 is silly.
708 *space = *fixed + 0.5;
713 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
720 Read hints from L and generate springs.
723 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r, Moment shortest)
725 Real compound_fixed = 0.0;
726 Real compound_space = 0.0;
729 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
731 if (dt == Moment (0, 0))
733 for (SCM s = l->get_property ("spacing-wishes");
734 scm_is_pair (s); s = scm_cdr (s))
736 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (scm_car (s)));
738 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
745 column for the left one settings should be ok due automatic
749 assert (spacing_grob-> get_column () == l);
751 Staff_spacing::get_spacing_params (spacing_grob,
752 &space, &fixed_space);
754 if (Paper_column::when_mom (r).grace_part_)
757 Correct for grace notes.
759 Ugh. The 0.8 is arbitrary.
764 compound_space += space;
765 compound_fixed += fixed_space;
770 if (compound_space <= 0.0 || !wish_count)
772 standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space ,
778 compound_space /= wish_count;
779 compound_fixed /= wish_count;
782 assert (!isinf (compound_space));
783 compound_space = compound_space >? compound_fixed;
787 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
788 works on all architectures.
792 There used to be code that changed spacing depending on
793 raggedright setting. Ugh.
795 Do it more cleanly, or rename the property.
798 Real strength = 1 / (compound_space - compound_fixed);
799 Real distance = compound_space;
800 Spaceable_grob::add_spring (l, r, distance, strength);
805 Get the measure wide ant for arithmetic spacing.
808 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
810 Real k = robust_scm2double (me->get_property ("shortest-duration-space"), 1);
811 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
816 We don't space really short notes using the log of the
817 duration, since it would disproportionally stretches the long
818 notes in a piece. In stead, we use geometric spacing with constant 0.5
821 This should probably be tunable, to use other base numbers.
823 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
824 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
825 mm for 8th. (white space), suggesting that we use
827 (1.2 / 1.5)^{-log2(duration ratio)}
831 Rational ratio = d.main_part_ / shortest;
833 return ((k-1) + double (ratio)) * incr;
838 John S. Gourlay. ``Spacing a Line of Music, '' Technical
839 Report OSU-CISRC-10/87-TR35, Department of Computer and
840 Information Science, The Ohio State University, 1987.
842 Real log = log_2 (shortest);
844 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
845 *expand_only = false;
847 return (log_2 (compdur) + k) * incr;
852 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
853 Moment shortest, bool * expand_only)
855 Moment shortest_playing_len = 0;
856 SCM s = lc->get_property ("shortest-playing-duration");
858 if (unsmob_moment (s))
859 shortest_playing_len = *unsmob_moment (s);
861 if (! shortest_playing_len.to_bool ())
863 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).to_string ());
864 shortest_playing_len = 1;
867 Moment lwhen = Paper_column::when_mom (lc);
868 Moment rwhen = Paper_column::when_mom (rc);
870 Moment delta_t = rwhen - lwhen;
871 if (!Paper_column::is_musical (rc))
874 when toying with mmrests, it is possible to have musical
875 column on the left and non-musical on the right, spanning
879 Moment *dt = unsmob_moment (rc->get_property ("measure-length"));
882 delta_t = delta_t <? *dt;
885 The following is an extra safety measure, such that
886 the length of a mmrest event doesn't cause havoc.
888 shortest_playing_len = shortest_playing_len <? *dt;
894 In normal situations, the next column is at most
895 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
896 with durations, invalidating this assumption. Here we kludge
897 around to get chord tremolos to behave properly.
900 shortest_playing_len = shortest_playing_len >? delta_t;
901 if (delta_t.main_part_ && !lwhen.grace_part_)
903 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
904 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
906 else if (delta_t.grace_part_)
909 TODO: figure out how to space grace notes.
911 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
914 = robust_scm2double (me->get_property ("grace-space-factor"), 1);
925 ADD_INTERFACE (Spacing_spanner, "spacing-spanner-interface",
926 "The space taken by a note is dependent on its duration. Doubling a\n"
927 "duration adds spacing-increment to the space. The most common shortest\n"
928 "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
929 "spaced proportonial to their duration.\n"
931 "Typically, the increment is the width of a black note head. In a\n"
932 "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
933 "gets 2 note heads width (i.e. the space following a note is 1 note\n"
934 "head width) A 16th note is followed by 0.5 note head width. The\n"
935 "quarter note is followed by 3 NHW, the half by 4 NHW, etc.\n",
936 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
940 ADD_INTERFACE (Spacing_interface, "spacing-interface",
941 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",