2 spacing-spanner.cc -- implement Spacing_spanner
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
16 #include "output-def.hh"
17 #include "paper-score.hh"
18 #include "paper-column.hh"
21 #include "note-spacing.hh"
24 #include "staff-spacing.hh"
26 #include "paper-column.hh"
27 #include "spaceable-grob.hh"
28 #include "break-align-interface.hh"
29 #include "spacing-interface.hh"
33 TODO: this file/class is too complex. Should figure out how to chop
41 static void standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
42 Real * fixed, Real * space, Moment);
45 static Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
46 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
47 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
48 static Rational find_shortest (Grob *, Link_array<Grob> const &);
49 static void breakable_column_spacing (Grob*, Item* l, Item *r, Moment);
50 static void find_loose_columns () {}
51 static void prune_loose_columns (Grob*,Link_array<Grob> *cols, Rational);
52 static void find_loose_columns (Link_array<Grob> cols);
53 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
54 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
55 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
56 static void musical_column_spacing (Grob*,Item*,Item*, Real, Rational);
57 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
58 static bool has_interface (Grob*);
62 Return whether COL is fixed to its neighbors by some kind of spacing
66 If in doubt, then we're not loose; the spacing engine should space
67 for it, risking suboptimal spacing.
69 (Otherwise, we might risk core dumps, and other weird stuff.)
73 loose_column (Grob *l, Grob *c, Grob *r)
75 SCM rns = c->get_property ("right-neighbors");
76 SCM lns = c->get_property ("left-neighbors");
79 If this column doesn't have a proper neighbor, we should really
80 make it loose, but spacing it correctly is more than we can
83 (this happens in the following situation:
94 the column containing the clef is really loose, and should be
95 attached right to the first column, but that is a lot of work for
96 such a borderline case.)
99 if (!scm_is_pair (lns) || !scm_is_pair (rns))
102 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (ly_car (lns)));
103 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (ly_car (rns)));
105 if (!l_neighbor || !r_neighbor)
108 l_neighbor = l_neighbor->get_column ();
109 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
111 if (l == l_neighbor && r == r_neighbor)
114 if (!l_neighbor || !r_neighbor)
120 Only declare loose if the bounds make a little sense. This means
121 some cases (two isolated, consecutive clef changes) won't be
122 nicely folded, but hey, then don't do that.
124 if (! ((Paper_column::is_musical (l_neighbor) || Item::is_breakable (l_neighbor))
125 && (Paper_column::is_musical (r_neighbor) || Item::is_breakable (r_neighbor))) )
132 A rather hairy check, but we really only want to move around clefs. (anything else?)
134 in any case, we don't want to move bar lines.
136 for (SCM e = c->get_property ("elements"); scm_is_pair (e); e = ly_cdr (e))
138 Grob * g = unsmob_grob (ly_car (e));
139 if (g && Break_align_interface::has_interface (g))
141 for (SCM s = g->get_property ("elements"); scm_is_pair (s);
144 Grob *h = unsmob_grob (ly_car (s));
147 ugh. -- fix staff-bar name?
149 if (h && h->get_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
159 Remove columns that are not tightly fitting from COLS. In the
160 removed columns, set 'between-cols to the columns where it is in
164 Spacing_spanner::prune_loose_columns (Grob*me,Link_array<Grob> *cols, Rational shortest)
166 Link_array<Grob> newcols;
167 Real increment = robust_scm2double (me->get_property ("spacing-increment"), 1.2);
168 for (int i=0; i < cols->size (); i++)
170 if (Item::is_breakable (cols->elem (i)) || Paper_column::is_musical (cols->elem (i)))
172 newcols.push (cols->elem (i));
176 Grob *c = cols->elem (i);
177 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
179 SCM lns = c->get_property ("left-neighbors");
180 lns = scm_is_pair (lns) ? ly_car (lns) : SCM_BOOL_F;
182 SCM rns = c->get_property ("right-neighbors");
183 rns = scm_is_pair (rns) ? ly_car (rns) : SCM_BOOL_F;
186 Either object can be non existent, if the score ends
189 rns = ly_car (unsmob_grob (rns)->get_property ("right-items"));
190 c->set_property ("between-cols", scm_cons (lns,
194 Set distance constraints for loose columns
196 Drul_array<Grob*> next_door;
197 next_door[LEFT] =cols->elem (i - 1);
198 next_door[RIGHT] =cols->elem (i + 1);
200 Drul_array<Real> dists (0,0);
205 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
206 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
208 for (SCM s = lc->get_property ("spacing-wishes");
209 scm_is_pair (s); s = ly_cdr (s))
211 Grob *sp = unsmob_grob (ly_car (s));
212 if (Note_spacing::left_column (sp) != lc
213 || Note_spacing::right_column (sp) != rc)
223 The note spacing should be taken from the musical
227 Real base = note_spacing (me, lc, rc, shortest, &dummy);
228 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
232 dists[d] = dists[d] >? space;
236 Real space, fixed_space;
237 Staff_spacing::get_spacing_params (sp,
238 &space, &fixed_space);
240 dists[d] = dists[d] >? fixed_space;
245 while (flip (&d) != LEFT);
248 r.distance_ = dists[LEFT] + dists[RIGHT];
249 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem (i-1));
250 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
264 Set neighboring columns determined by the spacing-wishes grob property.
267 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
269 for (int i=0; i < cols.size (); i++)
271 SCM right_neighbors = SCM_EOL;
272 int min_rank = 100000; // inf.
275 SCM wishes= cols[i]->get_property ("spacing-wishes");
276 for (SCM s =wishes; scm_is_pair (s); s = ly_cdr (s))
278 Item * wish = dynamic_cast<Item*> (unsmob_grob (ly_car (s)));
280 Item * lc = wish->get_column ();
281 Grob * right = Note_spacing::right_column (wish);
286 Item * rc = dynamic_cast<Item*> (right);
288 int right_rank = Paper_column::get_rank (rc);
289 int left_rank = Paper_column::get_rank (lc);
292 update the left column.
294 if (right_rank <= min_rank)
296 if (right_rank < min_rank)
297 right_neighbors =SCM_EOL;
299 min_rank = right_rank;
300 right_neighbors = scm_cons (wish->self_scm (), right_neighbors);
304 update the right column of the wish.
307 SCM left_neighs = rc->get_property ("left-neighbors");
308 if (scm_is_pair (left_neighs)
309 && unsmob_grob (ly_car (left_neighs)))
311 Item * it = dynamic_cast<Item*> (unsmob_grob (ly_car (left_neighs)));
312 maxrank = Paper_column::get_rank (it->get_column ());
315 if (left_rank >= maxrank)
317 if (left_rank > maxrank)
318 left_neighs = SCM_EOL;
320 left_neighs = scm_cons (wish->self_scm (), left_neighs);
321 rc->set_property ("left-neighbors", right_neighbors);
325 if (scm_is_pair (right_neighbors))
327 cols[i]->set_property ("right-neighbors", right_neighbors);
333 Set neighboring columns that have no left/right-neighbor set
334 yet. Only do breakable non-musical columns, and musical columns.
337 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
339 for (int i = 0; i < cols.size (); i++)
341 Item * it = dynamic_cast<Item*>(cols[i]);
342 if (!Item::is_breakable (it) && !Paper_column::is_musical (it))
345 // it->breakable || it->musical
348 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
350 SCM ln = cols[i] ->get_property ("left-neighbors");
351 if (!scm_is_pair (ln) && i )
353 cols[i]->set_property ("left-neighbors", scm_cons (cols[i-1]->self_scm (), SCM_EOL));
356 SCM rn = cols[i] ->get_property ("right-neighbors");
357 if (!scm_is_pair (rn) && i < cols.size () - 1)
359 cols[i]->set_property ("right-neighbors", scm_cons (cols[i + 1]->self_scm (), SCM_EOL));
365 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
367 Spacing_spanner::set_springs (SCM smob)
369 Grob *me = unsmob_grob (smob);
372 can't use get_system() ? --hwn.
374 Link_array<Grob> all (me->pscore_->system_->columns ());
376 set_explicit_neighbor_columns (all);
378 SCM preset_shortest = me->get_property ("common-shortest-duration");
379 Rational global_shortest;
380 if (unsmob_moment (preset_shortest))
382 global_shortest = unsmob_moment (preset_shortest)->main_part_;
386 global_shortest = find_shortest (me, all);
387 if (verbose_global_b)
388 progress_indication (_f ("Global shortest duration is %s", global_shortest.to_string ()) + "\n");
390 prune_loose_columns (me, &all, global_shortest);
391 set_implicit_neighbor_columns (all);
395 for (int i = 1; i < all.size (); i++)
398 if (Item::is_breakable (sc))
400 Link_array<Grob> measure (all.slice (j, i+1));
401 do_measure (global_shortest, me, &measure);
406 return SCM_UNSPECIFIED;
411 We want the shortest note that is also "common" in the piece, so we
412 find the shortest in each measure, and take the most frequently
415 This probably gives weird effects with modern music, where every
416 note has a different duration, but hey, don't write that kind of
421 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
424 ascending in duration
426 Array<Rational> durations;
429 Rational shortest_in_measure;
430 shortest_in_measure.set_infinite (1);
432 for (int i =0 ; i < cols.size (); i++)
434 if (Paper_column::is_musical (cols[i]))
436 Moment *when = unsmob_moment (cols[i]->get_property ("when"));
439 ignore grace notes for shortest notes.
441 if (when && when->grace_part_)
444 SCM st = cols[i]->get_property ("shortest-starter-duration");
445 Moment this_shortest = *unsmob_moment (st);
446 assert (this_shortest.to_bool ());
447 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
449 else if (!shortest_in_measure.is_infinity ()
450 && Item::is_breakable (cols[i]))
453 for (; j < durations.size (); j++)
455 if (durations[j] > shortest_in_measure)
457 counts.insert (1, j);
458 durations.insert (shortest_in_measure, j);
461 else if (durations[j] == shortest_in_measure)
468 if (durations.size () == j)
470 durations.push (shortest_in_measure);
474 shortest_in_measure.set_infinite (1);
480 for (int i =durations.size (); i--;)
482 if (counts[i] >= max_count)
485 max_count = counts[i];
488 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
491 SCM bsd = me->get_property ("base-shortest-duration");
492 Rational d = Rational (1,8);
493 if (Moment *m = unsmob_moment (bsd))
497 d = d <? durations[max_idx] ;
503 Generate spacing for a single measure. We used to have code that did
504 per-measure spacing. Now we have piecewise spacing. We should fix
505 this to support "spacing-regions": some regions have different notes
506 (different time sigs) than others, and should be spaced differently.
509 Spacing_spanner::do_measure (Rational global_shortest, Grob*me, Link_array<Grob> *cols)
512 Real headwid = robust_scm2double (me->get_property ("spacing-increment"), 1);
513 for (int i= 0; i < cols->size () - 1; i++)
515 Item * l = dynamic_cast<Item*> (cols->elem (i));
516 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
518 Paper_column * lc = dynamic_cast<Paper_column*> (l);
519 Paper_column * rc = dynamic_cast<Paper_column*> (r);
521 if (!Paper_column::is_musical (l))
523 breakable_column_spacing (me, l, r, global_shortest);
527 The case that the right part is broken as well is rather
528 rare, but it is possible, eg. with a single empty measure,
529 or if one staff finishes a tad earlier than the rest.
532 Item *lb = l->find_prebroken_piece (RIGHT);
533 Item *rb = r->find_prebroken_piece (LEFT);
536 breakable_column_spacing (me, lb,r, global_shortest);
539 breakable_column_spacing (me, l, rb, global_shortest);
541 breakable_column_spacing (me, lb, rb, global_shortest);
547 musical_column_spacing (me, lc, rc, headwid, global_shortest);
548 if (Item *rb = r->find_prebroken_piece (LEFT))
549 musical_column_spacing (me, lc, rb, headwid, global_shortest);
555 Generate the space between two musical columns LC and RC, given
556 spacing parameters INCR and SHORTEST.
559 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational global_shortest)
561 bool expand_only = false;
562 Real base_note_space = note_spacing (me, lc, rc, global_shortest, &expand_only);
564 Real compound_note_space = 0.0;
565 Real compound_fixed_note_space = 0.0;
568 SCM seq = lc->get_property ("right-neighbors");
571 We adjust the space following a note only if the next note
572 happens after the current note (this is set in the grob
573 property SPACING-SEQUENCE.
575 for (SCM s = seq; scm_is_pair (s); s = ly_cdr (s))
577 Grob * wish = unsmob_grob (ly_car (s));
579 Item *wish_rcol = Note_spacing::right_column (wish);
580 if (Note_spacing::left_column (wish) != lc
581 || (wish_rcol != rc && wish_rcol != rc->original_))
585 This is probably a waste of time in the case of polyphonic
587 if (Note_spacing::has_interface (wish))
592 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
595 compound_note_space = compound_note_space + space;
596 compound_fixed_note_space = compound_fixed_note_space + fixed;
602 if (Paper_column::when_mom (rc).grace_part_ &&
603 !Paper_column::when_mom (lc).grace_part_)
606 Ugh. 0.8 is arbitrary.
608 compound_note_space *= 0.8;
611 if (compound_note_space < 0 || wish_count == 0)
613 compound_note_space = base_note_space;
614 compound_fixed_note_space = increment;
618 compound_note_space /= wish_count;
619 compound_fixed_note_space /= wish_count;
623 Whatever we do, the fixed space is smaller than the real
626 TODO: this criterion is discontinuous in the derivative.
627 Maybe it should be continuous?
629 compound_fixed_note_space = compound_fixed_note_space <? compound_note_space;
631 bool packed = to_boolean (me->get_paper ()->c_variable ("packed"));
632 Real strength, distance;
635 TODO: make sure that the space doesn't exceed the right margin.
640 In packed mode, pack notes as tight as possible. This makes
641 sense mostly in combination with raggedright mode: the notes
642 are then printed at minimum distance. This is mostly useful
643 for ancient notation, but may also be useful for some flavours
644 of contemporary music. If not in raggedright mode, lily will
645 pack as much bars of music as possible into a line, but the
646 line will then be stretched to fill the whole linewidth.
649 distance = compound_fixed_note_space;
653 strength = 1 / (compound_note_space - compound_fixed_note_space);
654 distance = compound_note_space;
657 Spaceable_grob::add_spring (lc, rc, distance, strength);
662 The one-size-fits all spacing. It doesn't take into account
663 different spacing wishes from one to the next column.
666 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
667 Real * fixed, Real * space,
672 Drul_array<Item*> cols (l,r);
676 if (!Paper_column::is_musical (cols[d]))
679 Tied accidentals over barlines cause problems, so lets see
680 what happens if we do this for non musical columns only.
682 Interval lext = cols[d]->extent (cols [d], X_AXIS);
683 if (!lext.is_empty ())
684 *fixed += -d * lext[-d];
687 while (flip (&d) != LEFT);
690 if (l->is_breakable (l) && r->is_breakable (r))
692 Moment *dt = unsmob_moment (l->get_property ("measure-length"));
697 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
699 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
703 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
705 if (dt == Moment (0,0))
708 In this case, Staff_spacing should handle the job,
709 using dt when it is 0 is silly.
711 *space = *fixed + 0.5;
716 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
723 Read hints from L and generate springs.
726 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
728 Real compound_fixed = 0.0;
729 Real compound_space = 0.0;
732 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
734 if (dt == Moment (0,0))
736 for (SCM s = l->get_property ("spacing-wishes");
737 scm_is_pair (s); s = ly_cdr (s))
739 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (ly_car (s)));
741 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
748 column for the left one settings should be ok due automatic
752 assert (spacing_grob-> get_column () == l);
754 Staff_spacing::get_spacing_params (spacing_grob,
755 &space, &fixed_space);
757 if (Paper_column::when_mom (r).grace_part_)
760 Correct for grace notes.
762 Ugh. The 0.8 is arbitrary.
768 compound_space += space;
769 compound_fixed += fixed_space;
774 if (compound_space <= 0.0 || !wish_count)
776 standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space ,
782 compound_space /= wish_count;
783 compound_fixed /= wish_count;
786 assert (!isinf (compound_space));
787 compound_space = compound_space >? compound_fixed;
791 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
792 works on all architectures.
796 There used to be code that changed spacing depending on
797 raggedright setting. Ugh.
799 Do it more cleanly, or rename the property.
802 Real strength = 1 / (compound_space - compound_fixed);
803 Real distance = compound_space;
804 Spaceable_grob::add_spring (l, r, distance, strength);
809 Get the measure wide ant for arithmetic spacing.
812 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
814 Real k = robust_scm2double (me->get_property ("shortest-duration-space"), 1);
815 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
820 We don't space really short notes using the log of the
821 duration, since it would disproportionally stretches the long
822 notes in a piece. In stead, we use geometric spacing with constant 0.5
825 This should probably be tunable, to use other base numbers.
827 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
828 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
829 mm for 8th. (white space), suggesting that we use
831 (1.2 / 1.5)^{-log2(duration ratio)}
835 Rational ratio = d.main_part_ / shortest;
837 return ((k-1) + double (ratio)) * incr;
842 John S. Gourlay. ``Spacing a Line of Music,'' Technical
843 Report OSU-CISRC-10/87-TR35, Department of Computer and
844 Information Science, The Ohio State University, 1987.
846 Real log = log_2 (shortest);
848 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
849 *expand_only = false;
851 return (log_2 (compdur) + k) * incr;
856 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
857 Moment shortest, bool * expand_only)
859 Moment shortest_playing_len = 0;
860 SCM s = lc->get_property ("shortest-playing-duration");
862 if (unsmob_moment (s))
863 shortest_playing_len = *unsmob_moment (s);
865 if (! shortest_playing_len.to_bool ())
867 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).to_string ());
868 shortest_playing_len = 1;
871 Moment lwhen = Paper_column::when_mom (lc);
872 Moment rwhen = Paper_column::when_mom (rc);
874 Moment delta_t = rwhen - lwhen;
875 if (!Paper_column::is_musical (rc))
878 when toying with mmrests, it is possible to have musical
879 column on the left and non-musical on the right, spanning
883 Moment *dt = unsmob_moment (rc->get_property ("measure-length"));
886 delta_t = delta_t <? *dt;
889 The following is an extra safety measure, such that
890 the length of a mmrest event doesn't cause havoc.
892 shortest_playing_len = shortest_playing_len <? *dt;
898 In normal situations, the next column is at most
899 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
900 with durations, invalidating this assumption. Here we kludge
901 around to get chord tremolos to behave properly.
904 shortest_playing_len = shortest_playing_len >? delta_t;
905 if (delta_t.main_part_ && !lwhen.grace_part_)
907 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
908 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
910 else if (delta_t.grace_part_)
913 TODO: figure out how to space grace notes.
915 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
918 = robust_scm2double (me->get_property ("grace-space-factor"), 1);
929 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
930 "The space taken by a note is dependent on its duration. Doubling a\n"
931 "duration adds spacing-increment to the space. The most common shortest\n"
932 "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
933 "spaced proportonial to their duration.\n"
935 "Typically, the increment is the width of a black note head. In a\n"
936 "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
937 "gets 2 note heads width (i.e. the space following a note is 1 note\n"
938 "head width) A 16th note is followed by 0.5 note head width. The\n"
939 "quarter note is followed by 3 NHW, the half by 4 NHW, etc.\n",
940 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
944 ADD_INTERFACE (Spacing_interface, "spacing-interface",
945 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",