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 (scm_car (lns)));
103 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (scm_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 = scm_cdr (e))
138 Grob * g = unsmob_grob (scm_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 (scm_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) ? scm_car (lns) : SCM_BOOL_F;
182 SCM rns = c->get_property ("right-neighbors");
183 rns = scm_is_pair (rns) ? scm_car (rns) : SCM_BOOL_F;
186 Either object can be non existent, if the score ends
189 rns = scm_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 = scm_cdr (s))
211 Grob *sp = unsmob_grob (scm_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 = scm_cdr (s))
278 Item * wish = dynamic_cast<Item*> (unsmob_grob (scm_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 (scm_car (left_neighs)))
311 Item * it = dynamic_cast<Item*> (unsmob_grob (scm_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,
510 Link_array<Grob> *cols)
513 Real headwid = robust_scm2double (me->get_property ("spacing-increment"), 1);
514 for (int i= 0; i < cols->size () - 1; i++)
516 Item * l = dynamic_cast<Item*> (cols->elem (i));
517 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
519 Paper_column * lc = dynamic_cast<Paper_column*> (l);
520 Paper_column * rc = dynamic_cast<Paper_column*> (r);
522 if (!Paper_column::is_musical (l))
524 breakable_column_spacing (me, l, r, global_shortest);
528 The case that the right part is broken as well is rather
529 rare, but it is possible, eg. with a single empty measure,
530 or if one staff finishes a tad earlier than the rest.
533 Item *lb = l->find_prebroken_piece (RIGHT);
534 Item *rb = r->find_prebroken_piece (LEFT);
537 breakable_column_spacing (me, lb,r, global_shortest);
540 breakable_column_spacing (me, l, rb, global_shortest);
542 breakable_column_spacing (me, lb, rb, global_shortest);
546 musical_column_spacing (me, lc, rc, headwid, global_shortest);
547 if (Item *rb = r->find_prebroken_piece (LEFT))
548 musical_column_spacing (me, lc, rb, headwid, global_shortest);
554 Generate the space between two musical columns LC and RC, given
555 spacing parameters INCR and SHORTEST.
558 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational global_shortest)
560 bool expand_only = false;
561 Real base_note_space = note_spacing (me, lc, rc, global_shortest, &expand_only);
563 Real compound_note_space = 0.0;
564 Real compound_fixed_note_space = 0.0;
567 SCM seq = lc->get_property ("right-neighbors");
570 We adjust the space following a note only if the next note
571 happens after the current note (this is set in the grob
572 property SPACING-SEQUENCE.
574 for (SCM s = seq; scm_is_pair (s); s = scm_cdr (s))
576 Grob * wish = unsmob_grob (scm_car (s));
578 Item *wish_rcol = Note_spacing::right_column (wish);
579 if (Note_spacing::left_column (wish) != lc
580 || (wish_rcol != rc && wish_rcol != rc->original_))
584 This is probably a waste of time in the case of polyphonic
586 if (Note_spacing::has_interface (wish))
591 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
594 compound_note_space = compound_note_space + space;
595 compound_fixed_note_space = compound_fixed_note_space + fixed;
601 if (Paper_column::when_mom (rc).grace_part_ &&
602 !Paper_column::when_mom (lc).grace_part_)
605 Ugh. 0.8 is arbitrary.
607 compound_note_space *= 0.8;
610 if (compound_note_space < 0 || wish_count == 0)
612 compound_note_space = base_note_space;
613 compound_fixed_note_space = increment;
617 compound_note_space /= wish_count;
618 compound_fixed_note_space /= wish_count;
622 Whatever we do, the fixed space is smaller than the real
625 TODO: this criterion is discontinuous in the derivative.
626 Maybe it should be continuous?
628 compound_fixed_note_space = compound_fixed_note_space <? compound_note_space;
630 bool packed = to_boolean (me->get_layout ()->c_variable ("packed"));
631 Real strength, distance;
634 TODO: make sure that the space doesn't exceed the right margin.
639 In packed mode, pack notes as tight as possible. This makes
640 sense mostly in combination with raggedright mode: the notes
641 are then printed at minimum distance. This is mostly useful
642 for ancient notation, but may also be useful for some flavours
643 of contemporary music. If not in raggedright mode, lily will
644 pack as much bars of music as possible into a line, but the
645 line will then be stretched to fill the whole linewidth.
648 distance = compound_fixed_note_space;
652 strength = 1 / (compound_note_space - compound_fixed_note_space);
653 distance = compound_note_space;
656 Spaceable_grob::add_spring (lc, rc, distance, strength);
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 scm_is_pair (s); s = scm_cdr (s))
738 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (scm_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);
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.",