2 spacing-spanner.cc -- implement Spacing_spanner
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2003 Han-Wen Nienhuys <hanwen@cs.uu.nl>
16 #include "paper-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"
34 static void standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
35 Real * fixed, Real * space, Moment);
38 static Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
39 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
40 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
41 static Rational find_shortest (Grob *, Link_array<Grob> const &);
42 static void breakable_column_spacing (Grob*, Item* l, Item *r, Moment);
43 static void find_loose_columns () {}
44 static void prune_loose_columns (Grob*,Link_array<Grob> *cols, Rational);
45 static void find_loose_columns (Link_array<Grob> cols);
46 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
47 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
48 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
49 static void musical_column_spacing (Grob*,Item*,Item*, Real, Rational);
50 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
51 static bool has_interface (Grob*);
55 Return whether COL is fixed to its neighbors by some kind of spacing
59 If in doubt, then we're not loose; the spacing engine should space
60 for it, risking suboptimal spacing.
62 (Otherwise, we might risk core dumps, and other weird stuff.)
66 loose_column (Grob *l, Grob *c, Grob *r)
68 SCM rns = c->get_grob_property ("right-neighbors");
69 SCM lns = c->get_grob_property ("left-neighbors");
72 If this column doesn't have a proper neighbor, we should really
73 make it loose, but spacing it correctly is more than we can
76 (this happens in the following situation:
87 the column containing the clef is really loose, and should be
88 attached right to the first column, but that is a lot of work for
89 such a borderline case.)
92 if (!gh_pair_p (lns) || !gh_pair_p (rns))
95 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
96 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
98 if (!l_neighbor || !r_neighbor)
101 l_neighbor = l_neighbor->get_column ();
102 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
104 if (l == l_neighbor && r == r_neighbor)
107 if (!l_neighbor || !r_neighbor)
113 Only declare loose if the bounds make a little sense. This means
114 some cases (two isolated, consecutive clef changes) won't be
115 nicely folded, but hey, then don't do that.
117 if(! ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
118 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor))) )
125 A rather hairy check, but we really only want to move around clefs. (anything else?)
127 in any case, we don't want to move bar lines.
129 for (SCM e = c->get_grob_property ("elements"); gh_pair_p (e); e = gh_cdr (e))
131 Grob * g = unsmob_grob (gh_car (e));
132 if (g && Break_align_interface::has_interface (g))
134 for (SCM s = g->get_grob_property ("elements"); gh_pair_p (s);
137 Grob *h = unsmob_grob (gh_car (s));
140 ugh. -- fix staff-bar name?
142 if (h && h->get_grob_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
152 Remove columns that are not tightly fitting from COLS. In the
153 removed columns, set 'between-cols to the columns where it is in
157 Spacing_spanner::prune_loose_columns (Grob*me,Link_array<Grob> *cols, Rational shortest)
159 Link_array<Grob> newcols;
160 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
161 for (int i=0; i < cols->size (); i++)
163 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
165 newcols.push (cols->elem(i));
169 Grob *c = cols->elem(i);
170 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
172 SCM lns = c->get_grob_property ("left-neighbors");
173 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
175 SCM rns = c->get_grob_property ("right-neighbors");
176 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
179 Either object can be non existent, if the score ends
182 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
183 c->set_grob_property ("between-cols", gh_cons (lns,
187 Set distance constraints for loose columns
189 Drul_array<Grob*> next_door;
190 next_door[LEFT] =cols->elem (i - 1);
191 next_door[RIGHT] =cols->elem (i + 1);
193 Drul_array<Real> dists(0,0);
198 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
199 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
201 for (SCM s = lc->get_grob_property ("spacing-wishes");
202 gh_pair_p (s); s = gh_cdr (s))
204 Grob *sp = unsmob_grob (gh_car (s));
205 if (Note_spacing::left_column (sp) != lc
206 || Note_spacing::right_column (sp) != rc)
216 The note spacing should be taken from the musical
220 Real base = note_spacing (me, lc, rc, shortest, &dummy);
221 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
225 dists[d] = dists[d] >? space;
229 Real space, fixed_space;
230 Staff_spacing::get_spacing_params (sp,
231 &space, &fixed_space);
233 dists[d] = dists[d] >? fixed_space;
238 while (flip (&d) != LEFT);
241 r.distance_ = dists[LEFT] + dists[RIGHT];
242 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
243 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
257 Set neighboring columns determined by the spacing-wishes grob property.
260 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
262 for (int i=0; i < cols.size(); i++)
264 SCM right_neighbors = SCM_EOL;
265 int min_rank = 100000; // inf.
268 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
269 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
271 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
273 Item * lc = wish->get_column ();
274 Grob * right = Note_spacing::right_column (wish);
279 Item * rc = dynamic_cast<Item*> (right);
281 int right_rank = Paper_column::get_rank (rc);
282 int left_rank = Paper_column::get_rank (lc);
285 update the left column.
287 if (right_rank <= min_rank)
289 if (right_rank < min_rank)
290 right_neighbors =SCM_EOL;
292 min_rank = right_rank;
293 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
297 update the right column of the wish.
300 SCM left_neighs = rc->get_grob_property ("left-neighbors");
301 if (gh_pair_p (left_neighs)
302 && unsmob_grob (gh_car (left_neighs)))
304 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
305 maxrank = Paper_column::get_rank (it->get_column ());
308 if (left_rank >= maxrank)
310 if (left_rank > maxrank)
311 left_neighs = SCM_EOL;
313 left_neighs = gh_cons (wish->self_scm (), left_neighs);
314 rc->set_grob_property ("left-neighbors", right_neighbors);
318 if (gh_pair_p (right_neighbors))
320 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
326 Set neighboring columns that have no left/right-neighbor set
327 yet. Only do breakable non-musical columns, and musical columns.
330 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
332 for (int i = 0; i < cols.size (); i++)
334 Item * it = dynamic_cast<Item*>(cols[i]);
335 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
338 // it->breakable || it->musical
341 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
343 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
344 if (!gh_pair_p (ln) && i )
346 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
349 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
350 if (!gh_pair_p (rn) && i < cols.size () - 1)
352 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
358 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
360 Spacing_spanner::set_springs (SCM smob)
362 Grob *me = unsmob_grob (smob);
364 Link_array<Grob> all (me->pscore_->system_->columns ()) ;
366 set_explicit_neighbor_columns (all);
368 SCM preset_shortest = me->get_grob_property ("common-shortest-duration");
369 Rational global_shortest;
370 if (unsmob_moment (preset_shortest))
372 global_shortest = unsmob_moment (preset_shortest)->main_part_;
376 global_shortest = find_shortest (me, all);
377 if (verbose_global_b)
379 progress_indication (_f("Global shortest duration is %s\n", global_shortest.to_string ()));
382 prune_loose_columns (me, &all, global_shortest);
383 set_implicit_neighbor_columns (all);
387 for (int i = 1; i < all.size (); i++)
390 if (Item::breakable_b (sc))
392 Link_array<Grob> measure (all.slice (j, i+1));
393 do_measure (global_shortest, me, &measure);
398 return SCM_UNSPECIFIED;
403 We want the shortest note that is also "common" in the piece, so we
404 find the shortest in each measure, and take the most frequently
407 This probably gives weird effects with modern music, where every
408 note has a different duration, but hey, don't write that kind of
413 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
416 ascending in duration
418 Array<Rational> durations;
421 Rational shortest_in_measure;
422 shortest_in_measure.set_infinite (1);
424 for (int i =0 ; i < cols.size (); i++)
426 if (Paper_column::musical_b (cols[i]))
428 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
431 ignore grace notes for shortest notes.
433 if (when && when->grace_part_)
436 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
437 Moment this_shortest = *unsmob_moment (st);
438 assert (this_shortest.to_bool());
439 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
441 else if (!shortest_in_measure.infty_b()
442 && Item::breakable_b (cols[i]))
445 for (; j < durations.size(); j++)
447 if (durations[j] > shortest_in_measure)
449 counts.insert (1, j);
450 durations.insert (shortest_in_measure, j);
453 else if (durations[j] == shortest_in_measure)
460 if (durations.size() == j)
462 durations.push (shortest_in_measure);
466 shortest_in_measure.set_infinite(1);
472 for (int i =durations.size(); i--;)
474 if (counts[i] >= max_count)
477 max_count = counts[i];
480 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
483 SCM bsd = me->get_grob_property ("base-shortest-duration");
484 Rational d = Rational (1,8);
485 if (Moment *m = unsmob_moment (bsd))
489 d = d <? durations[max_idx] ;
495 Generate spacing for a single measure. We used to have code that did
496 per-measure spacing. Now we have piecewise spacing. We should fix
497 this to support "spacing-regions": some regions have different notes
498 (different time sigs) than others, and should be spaced differently.
501 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
504 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
505 for (int i= 0; i < cols->size () - 1; i++)
507 Item * l = dynamic_cast<Item*> (cols->elem (i));
508 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
510 Paper_column * lc = dynamic_cast<Paper_column*> (l);
511 Paper_column * rc = dynamic_cast<Paper_column*> (r);
513 if (!Paper_column::musical_b (l))
515 breakable_column_spacing (me, l, r, shortest);
519 The case that the right part is broken as well is rather
520 rare, but it is possible, eg. with a single empty measure,
521 or if one staff finishes a tad earlier than the rest.
524 Item *lb = l->find_prebroken_piece (RIGHT);
525 Item *rb = r->find_prebroken_piece (LEFT);
528 breakable_column_spacing (me, lb,r, shortest);
531 breakable_column_spacing (me, l, rb, shortest);
533 breakable_column_spacing (me, lb, rb, shortest);
539 musical_column_spacing (me, lc, rc, headwid, shortest);
540 if (Item *rb = r->find_prebroken_piece (LEFT))
541 musical_column_spacing (me, lc, rb, headwid, shortest);
547 Generate the space between two musical columns LC and RC, given
548 spacing parameters INCR and SHORTEST.
551 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
553 bool expand_only = false;
554 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
556 Real compound_note_space = 0.0;
557 Real compound_fixed_note_space = 0.0;
560 SCM seq = lc->get_grob_property ("right-neighbors");
563 We adjust the space following a note only if the next note
564 happens after the current note (this is set in the grob
565 property SPACING-SEQUENCE.
567 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
569 Grob * wish = unsmob_grob (gh_car (s));
571 Item *wish_rcol = Note_spacing::right_column (wish);
572 if (Note_spacing::left_column (wish) != lc
573 || (wish_rcol != rc && wish_rcol != rc->original_))
577 This is probably a waste of time in the case of polyphonic
579 if (Note_spacing::has_interface (wish))
584 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
587 compound_note_space = compound_note_space + space;
588 compound_fixed_note_space = compound_fixed_note_space + fixed;
594 if (Paper_column::when_mom (rc).grace_part_ &&
595 !Paper_column::when_mom (lc).grace_part_)
598 Ugh. 0.8 is arbitrary.
600 compound_note_space *= 0.8;
603 if (compound_note_space < 0 || wish_count == 0)
605 compound_note_space = base_note_space;
606 compound_fixed_note_space = increment;
610 compound_note_space /= wish_count;
611 compound_fixed_note_space /= wish_count;
615 Whatever we do, the fixed space is smaller than the real
618 TODO: this criterion is discontinuous in the derivative.
619 Maybe it should be continuous?
621 compound_fixed_note_space = compound_fixed_note_space <? compound_note_space;
623 bool packed = to_boolean (me->get_paper ()->get_scmvar ("packed"));
624 Real strength, distance;
627 TODO: make sure that the space doesn't exceed the right margin.
632 In packed mode, pack notes as tight as possible. This makes
633 sense mostly in combination with raggedright mode: the notes
634 are then printed at minimum distance. This is mostly useful
635 for ancient notation, but may also be useful for some flavours
636 of contemporary music. If not in raggedright mode, lily will
637 pack as much bars of music as possible into a line, but the
638 line will then be stretched to fill the whole linewidth.
641 distance = compound_fixed_note_space;
645 strength = 1 / (compound_note_space - compound_fixed_note_space);
646 distance = compound_note_space;
649 // Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
651 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
656 The one-size-fits all spacing. It doesn't take into account
657 different spacing wishes from one to the next column.
660 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
661 Real * fixed, Real * space,
667 Drul_array<Item*> cols(l,r);
671 if (!Paper_column::musical_b (cols[d]))
674 Tied accidentals over barlines cause problems, so lets see
675 what happens if we do this for non musical columns only.
677 Interval lext = cols[d]->extent (cols [d], X_AXIS);
678 *fixed += -d * lext[-d];
681 while (flip (&d) != LEFT);
683 if (l->breakable_b (l) && r->breakable_b(r))
685 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
690 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
692 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
696 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
699 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
705 Read hints from L and generate springs.
708 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
710 Real max_fixed = -infinity_f;
711 Real max_space = -infinity_f;
713 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
716 for (SCM s = l->get_grob_property ("spacing-wishes");
717 gh_pair_p (s); s = gh_cdr (s))
719 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
721 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
728 column for the left one settings should be ok due automatic
732 assert (spacing_grob-> get_column () == l);
734 Staff_spacing::get_spacing_params (spacing_grob,
735 &space, &fixed_space);
737 if (Paper_column::when_mom (r).grace_part_)
740 Correct for grace notes.
742 Ugh. The 0.8 is arbitrary.
746 if (space > max_space)
749 max_fixed = fixed_space;
756 if (isinf (max_space))
759 One situation where this can happen is when there is a column
760 that only serves as a spanning point for a short staff-symbol.
767 (here no StaffSpacing from Y to X is found.)
769 warning ("No spacing wishes found. Does your score have a staff?");
775 if (l->break_status_dir() == RIGHT
776 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
778 /* Start of line: this space is not stretchable */
779 max_fixed = max_space;
783 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
784 works on all architectures.
788 There used to be code that changed spacing depending on
789 raggedright setting. Ugh.
791 Do it more cleanly, or rename the property.
794 Real strength = 1 / (max_space - max_fixed);
795 Real distance = max_space;
796 Spaceable_grob::add_spring (l, r, distance, strength, false);
801 Get the measure wide ant for arithmetic spacing.
804 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
806 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
807 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
812 We don't space really short notes using the log of the
813 duration, since it would disproportionally stretches the long
814 notes in a piece. In stead, we use geometric spacing with constant 0.5
817 This should probably be tunable, to use other base numbers.
819 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
820 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
821 mm for 8th. (white space), suggesting that we use
823 (1.2 / 1.5)^{-log2(duration ratio)}
827 Rational ratio = d.main_part_ / shortest;
832 return ((k-1) + double (ratio)) * incr;
837 John S. Gourlay. ``Spacing a Line of Music,'' Technical
838 Report OSU-CISRC-10/87-TR35, Department of Computer and
839 Information Science, The Ohio State University, 1987.
841 Real log = log_2 (shortest);
843 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
844 *expand_only = false;
846 return (log_2 (compdur) + k) * incr;
851 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
852 Moment shortest, bool * expand_only)
854 Moment shortest_playing_len = 0;
855 SCM s = lc->get_grob_property ("shortest-playing-duration");
857 if (unsmob_moment (s))
858 shortest_playing_len = *unsmob_moment (s);
860 if (! shortest_playing_len.to_bool ())
862 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).to_string ());
863 shortest_playing_len = 1;
866 Moment lwhen = Paper_column::when_mom (lc);
867 Moment rwhen = Paper_column::when_mom (rc);
869 Moment delta_t = rwhen - lwhen;
870 if (!Paper_column::musical_b (rc ))
873 when toying with mmrests, it is possible to have musical
874 column on the left and non-musical on the right, spanning
878 Moment *dt = unsmob_moment (rc->get_grob_property ("measure-length"));
880 delta_t = delta_t <? *dt;
885 In normal situations, the next column is at most
886 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
887 with durations, invalidating this assumption. Here we kludge
888 around to get chord tremolos to behave properly.
891 shortest_playing_len = shortest_playing_len >? delta_t;
892 if (delta_t.main_part_ && !lwhen.grace_part_)
894 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
895 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
897 else if (delta_t.grace_part_)
900 TODO: figure out how to space grace notes.
902 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
904 Real grace_fact = 1.0;
905 SCM gf = me->get_grob_property ("grace-space-factor");
906 if (gh_number_p (gf))
907 grace_fact = gh_scm2double (gf);
918 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
919 "The space taken by a note is dependent on its duration. Doubling a\n"
920 "duration adds spacing-increment to the space. The most common shortest\n"
921 "note gets shortest-duration-space. Notes that are even shorter are\n"
922 "spaced proportonial to their duration.\n"
924 "Typically, the increment is the width of a black note head. In a\n"
925 "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
926 "gets 2 note heads width (i.e. the space following a note is 1 note\n"
927 "head width) A 16th note is followed by 0.5 note head width. The\n"
928 "quarter note is followed by 3 NHW, the half by 4 NHW, etc.\n",
929 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
933 ADD_INTERFACE (Spacing_interface,"spacing-interface",
934 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",