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 (!ly_c_pair_p (lns) || !ly_c_pair_p (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"); ly_c_pair_p (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"); ly_c_pair_p (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 = ly_c_pair_p (lns) ? ly_car (lns) : SCM_BOOL_F;
182 SCM rns = c->get_property ("right-neighbors");
183 rns = ly_c_pair_p (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 ly_c_pair_p (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; ly_c_pair_p (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 (ly_c_pair_p (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 (ly_c_pair_p (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 (!ly_c_pair_p (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 (!ly_c_pair_p (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);
371 Link_array<Grob> all (me->pscore_->system_->columns ());
373 set_explicit_neighbor_columns (all);
375 SCM preset_shortest = me->get_property ("common-shortest-duration");
376 Rational global_shortest;
377 if (unsmob_moment (preset_shortest))
379 global_shortest = unsmob_moment (preset_shortest)->main_part_;
383 global_shortest = find_shortest (me, all);
384 if (verbose_global_b)
385 progress_indication (_f ("Global shortest duration is %s", global_shortest.to_string ()) + "\n");
387 prune_loose_columns (me, &all, global_shortest);
388 set_implicit_neighbor_columns (all);
392 for (int i = 1; i < all.size (); i++)
395 if (Item::is_breakable (sc))
397 Link_array<Grob> measure (all.slice (j, i+1));
398 do_measure (global_shortest, me, &measure);
403 return SCM_UNSPECIFIED;
408 We want the shortest note that is also "common" in the piece, so we
409 find the shortest in each measure, and take the most frequently
412 This probably gives weird effects with modern music, where every
413 note has a different duration, but hey, don't write that kind of
418 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
421 ascending in duration
423 Array<Rational> durations;
426 Rational shortest_in_measure;
427 shortest_in_measure.set_infinite (1);
429 for (int i =0 ; i < cols.size (); i++)
431 if (Paper_column::is_musical (cols[i]))
433 Moment *when = unsmob_moment (cols[i]->get_property ("when"));
436 ignore grace notes for shortest notes.
438 if (when && when->grace_part_)
441 SCM st = cols[i]->get_property ("shortest-starter-duration");
442 Moment this_shortest = *unsmob_moment (st);
443 assert (this_shortest.to_bool ());
444 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
446 else if (!shortest_in_measure.is_infinity ()
447 && Item::is_breakable (cols[i]))
450 for (; j < durations.size (); j++)
452 if (durations[j] > shortest_in_measure)
454 counts.insert (1, j);
455 durations.insert (shortest_in_measure, j);
458 else if (durations[j] == shortest_in_measure)
465 if (durations.size () == j)
467 durations.push (shortest_in_measure);
471 shortest_in_measure.set_infinite (1);
477 for (int i =durations.size (); i--;)
479 if (counts[i] >= max_count)
482 max_count = counts[i];
485 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
488 SCM bsd = me->get_property ("base-shortest-duration");
489 Rational d = Rational (1,8);
490 if (Moment *m = unsmob_moment (bsd))
494 d = d <? durations[max_idx] ;
500 Generate spacing for a single measure. We used to have code that did
501 per-measure spacing. Now we have piecewise spacing. We should fix
502 this to support "spacing-regions": some regions have different notes
503 (different time sigs) than others, and should be spaced differently.
506 Spacing_spanner::do_measure (Rational global_shortest, Grob*me, Link_array<Grob> *cols)
509 Real headwid = robust_scm2double (me->get_property ("spacing-increment"), 1);
510 for (int i= 0; i < cols->size () - 1; i++)
512 Item * l = dynamic_cast<Item*> (cols->elem (i));
513 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
515 Paper_column * lc = dynamic_cast<Paper_column*> (l);
516 Paper_column * rc = dynamic_cast<Paper_column*> (r);
518 if (!Paper_column::is_musical (l))
520 breakable_column_spacing (me, l, r, global_shortest);
524 The case that the right part is broken as well is rather
525 rare, but it is possible, eg. with a single empty measure,
526 or if one staff finishes a tad earlier than the rest.
529 Item *lb = l->find_prebroken_piece (RIGHT);
530 Item *rb = r->find_prebroken_piece (LEFT);
533 breakable_column_spacing (me, lb,r, global_shortest);
536 breakable_column_spacing (me, l, rb, global_shortest);
538 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; ly_c_pair_p (s); s = ly_cdr (s))
574 Grob * wish = unsmob_grob (ly_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_paper ()->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, expand_only);
656 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
661 The one-size-fits all spacing. It doesn't take into account
662 different spacing wishes from one to the next column.
665 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
666 Real * fixed, Real * space,
671 Drul_array<Item*> cols (l,r);
675 if (!Paper_column::is_musical (cols[d]))
678 Tied accidentals over barlines cause problems, so lets see
679 what happens if we do this for non musical columns only.
681 Interval lext = cols[d]->extent (cols [d], X_AXIS);
682 if (!lext.is_empty ())
683 *fixed += -d * lext[-d];
686 while (flip (&d) != LEFT);
689 if (l->is_breakable (l) && r->is_breakable (r))
691 Moment *dt = unsmob_moment (l->get_property ("measure-length"));
696 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
698 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
702 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
704 if (dt == Moment (0,0))
707 In this case, Staff_spacing should handle the job,
708 using dt when it is 0 is silly.
710 *space = *fixed + 0.5;
715 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
722 Read hints from L and generate springs.
725 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
727 Real compound_fixed = 0.0;
728 Real compound_space = 0.0;
731 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
733 if (dt == Moment (0,0))
735 for (SCM s = l->get_property ("spacing-wishes");
736 ly_c_pair_p (s); s = ly_cdr (s))
738 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (ly_car (s)));
740 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
747 column for the left one settings should be ok due automatic
751 assert (spacing_grob-> get_column () == l);
753 Staff_spacing::get_spacing_params (spacing_grob,
754 &space, &fixed_space);
756 if (Paper_column::when_mom (r).grace_part_)
759 Correct for grace notes.
761 Ugh. The 0.8 is arbitrary.
767 compound_space += space;
768 compound_fixed += fixed_space;
773 if (compound_space <= 0.0 || !wish_count)
775 standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space ,
781 compound_space /= wish_count;
782 compound_fixed /= wish_count;
785 assert (!isinf (compound_space));
786 compound_space = compound_space >? compound_fixed;
790 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
791 works on all architectures.
795 There used to be code that changed spacing depending on
796 raggedright setting. Ugh.
798 Do it more cleanly, or rename the property.
801 Real strength = 1 / (compound_space - compound_fixed);
802 Real distance = compound_space;
803 Spaceable_grob::add_spring (l, r, distance, strength, false);
808 Get the measure wide ant for arithmetic spacing.
811 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
813 Real k = robust_scm2double (me->get_property ("shortest-duration-space"), 1);
814 Real incr = robust_scm2double (me->get_property ("spacing-increment"), 1);
819 We don't space really short notes using the log of the
820 duration, since it would disproportionally stretches the long
821 notes in a piece. In stead, we use geometric spacing with constant 0.5
824 This should probably be tunable, to use other base numbers.
826 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
827 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
828 mm for 8th. (white space), suggesting that we use
830 (1.2 / 1.5)^{-log2(duration ratio)}
834 Rational ratio = d.main_part_ / shortest;
836 return ((k-1) + double (ratio)) * incr;
841 John S. Gourlay. ``Spacing a Line of Music,'' Technical
842 Report OSU-CISRC-10/87-TR35, Department of Computer and
843 Information Science, The Ohio State University, 1987.
845 Real log = log_2 (shortest);
847 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
848 *expand_only = false;
850 return (log_2 (compdur) + k) * incr;
855 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
856 Moment shortest, bool * expand_only)
858 Moment shortest_playing_len = 0;
859 SCM s = lc->get_property ("shortest-playing-duration");
861 if (unsmob_moment (s))
862 shortest_playing_len = *unsmob_moment (s);
864 if (! shortest_playing_len.to_bool ())
866 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).to_string ());
867 shortest_playing_len = 1;
870 Moment lwhen = Paper_column::when_mom (lc);
871 Moment rwhen = Paper_column::when_mom (rc);
873 Moment delta_t = rwhen - lwhen;
874 if (!Paper_column::is_musical (rc))
877 when toying with mmrests, it is possible to have musical
878 column on the left and non-musical on the right, spanning
882 Moment *dt = unsmob_moment (rc->get_property ("measure-length"));
885 delta_t = delta_t <? *dt;
888 The following is an extra safety measure, such that
889 the length of a mmrest event doesn't cause havoc.
891 shortest_playing_len = shortest_playing_len <? *dt;
897 In normal situations, the next column is at most
898 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
899 with durations, invalidating this assumption. Here we kludge
900 around to get chord tremolos to behave properly.
903 shortest_playing_len = shortest_playing_len >? delta_t;
904 if (delta_t.main_part_ && !lwhen.grace_part_)
906 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
907 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
909 else if (delta_t.grace_part_)
912 TODO: figure out how to space grace notes.
914 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
917 = robust_scm2double (me->get_property ("grace-space-factor"), 1);
928 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
929 "The space taken by a note is dependent on its duration. Doubling a\n"
930 "duration adds spacing-increment to the space. The most common shortest\n"
931 "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
932 "spaced proportonial to their duration.\n"
934 "Typically, the increment is the width of a black note head. In a\n"
935 "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
936 "gets 2 note heads width (i.e. the space following a note is 1 note\n"
937 "head width) A 16th note is followed by 0.5 note head width. The\n"
938 "quarter note is followed by 3 NHW, the half by 4 NHW, etc.\n",
939 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
943 ADD_INTERFACE (Spacing_interface,"spacing-interface",
944 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",