2 spacing-spanner.cc -- implement Spacing_spanner
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2002 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_colunms (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_colunms (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.string ()));
382 prune_loose_colunms (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 max_note_space = -infinity_f;
557 Real max_fixed_note_space = -infinity_f;
559 SCM seq = lc->get_grob_property ("right-neighbors");
562 We adjust the space following a note only if the next note
563 happens after the current note (this is set in the grob
564 property SPACING-SEQUENCE.
566 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
568 Grob * wish = unsmob_grob (gh_car (s));
570 Item *wish_rcol = Note_spacing::right_column (wish);
571 if (Note_spacing::left_column (wish) != lc
572 || (wish_rcol != rc && wish_rcol != rc->original_))
576 This is probably a waste of time in the case of polyphonic
578 if (Note_spacing::has_interface (wish))
583 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
584 max_note_space = max_note_space >? space;
585 max_fixed_note_space = max_fixed_note_space >? fixed;
589 if (Paper_column::when_mom (rc).grace_part_ &&
590 !Paper_column::when_mom (lc).grace_part_)
593 Ugh. 0.8 is arbitrary.
595 max_note_space *= 0.8;
598 if (max_note_space < 0)
600 max_note_space = base_note_space;
601 max_fixed_note_space = increment;
604 bool ragged = to_boolean (me->get_paper ()->get_scmvar ("raggedright"));
607 Whatever we do, the fixed space is smaller than the real
610 TODO: this criterion is discontinuous in the derivative.
611 Maybe it should be continuous?
613 max_fixed_note_space = max_fixed_note_space <? max_note_space;
618 This doesn't make sense. For ragged right we want to have the same
619 spacing. Otherwise the option should be called differently.
621 ragged-righted-and-weird-spacing. Whatever.
624 Real strength = (ragged) ? 1.0 : 1 / (max_note_space - max_fixed_note_space);
625 Real distance = (ragged) ? max_fixed_note_space : max_note_space;
629 TODO: make sure that the space doesn't exceed the right margin.
631 Real strength = 1 / (max_note_space - max_fixed_note_space);
632 Real distance = max_note_space;
635 // Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
637 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
642 The one-size-fits all spacing. It doesn't take into account
643 different spacing wishes from one to the next column.
646 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
647 Real * fixed, Real * space,
653 Drul_array<Item*> cols(l,r);
657 if (!Paper_column::musical_b (cols[d]))
660 Tied accidentals over barlines cause problems, so lets see
661 what happens if we do this for non musical columns only.
663 Interval lext = cols[d]->extent (cols [d], X_AXIS);
664 *fixed += -d * lext[-d];
667 while (flip (&d) != LEFT);
669 if (l->breakable_b (l) && r->breakable_b(r))
671 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
676 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
678 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
682 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
685 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
691 Read hints from L and generate springs.
694 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
696 Real max_fixed = -infinity_f;
697 Real max_space = -infinity_f;
699 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
702 for (SCM s = l->get_grob_property ("spacing-wishes");
703 gh_pair_p (s); s = gh_cdr (s))
705 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
707 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
714 column for the left one settings should be ok due automatic
718 assert (spacing_grob-> get_column () == l);
720 Staff_spacing::get_spacing_params (spacing_grob,
721 &space, &fixed_space);
723 if (Paper_column::when_mom (r).grace_part_)
726 Correct for grace notes.
728 Ugh. The 0.8 is arbitrary.
732 if (space > max_space)
735 max_fixed = fixed_space;
742 if (isinf (max_space))
745 One situation where this can happen is when there is a column
746 that only serves as a spanning point for a short staff-symbol.
753 (here no StaffSpacing from Y to X is found.)
755 programming_error ("No StaffSpacing wishes found");
761 if (l->break_status_dir() == RIGHT
762 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
764 /* Start of line: this space is not stretchable */
765 max_fixed = max_space;
769 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
770 works on all architectures.
774 There used to be code that changed spacing depending on
775 raggedright setting. Ugh.
777 Do it more cleanly, or rename the property.
780 Real strength = 1 / (max_space - max_fixed);
781 Real distance = max_space;
782 Spaceable_grob::add_spring (l, r, distance, strength, false);
787 Get the measure wide ant for arithmetic spacing.
790 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
792 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
793 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
798 We don't space really short notes using the log of the
799 duration, since it would disproportionally stretches the long
800 notes in a piece. In stead, we use geometric spacing with constant 0.5
803 This should probably be tunable, to use other base numbers.
805 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
806 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
807 mm for 8th. (white space), suggesting that we use
809 (1.2 / 1.5)^{-log2(duration ratio)}
813 Rational ratio = d.main_part_ / shortest;
818 return ((k-1) + double (ratio)) * incr;
823 John S. Gourlay. ``Spacing a Line of Music,'' Technical
824 Report OSU-CISRC-10/87-TR35, Department of Computer and
825 Information Science, The Ohio State University, 1987.
827 Real log = log_2 (shortest);
829 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
830 *expand_only = false;
832 return (log_2 (compdur) + k) * incr;
837 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
838 Moment shortest, bool * expand_only)
840 Moment shortest_playing_len = 0;
841 SCM s = lc->get_grob_property ("shortest-playing-duration");
843 if (unsmob_moment (s))
844 shortest_playing_len = *unsmob_moment (s);
846 if (! shortest_playing_len.to_bool ())
848 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).string ());
849 shortest_playing_len = 1;
852 Moment lwhen = Paper_column::when_mom (lc);
853 Moment rwhen = Paper_column::when_mom (rc);
855 Moment delta_t = rwhen - lwhen;
859 In normal situations, the next column is at most
860 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
861 with durations, invalidating this assumption. Here we kludge
862 around to get chord tremolos to behave properly.
865 shortest_playing_len = shortest_playing_len >? delta_t;
866 if (delta_t.main_part_ && !lwhen.grace_part_)
868 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
869 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
871 else if (delta_t.grace_part_)
874 TODO: figure out how to space grace notes.
876 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
878 Real grace_fact = 1.0;
879 SCM gf = me->get_grob_property ("grace-space-factor");
880 if (gh_number_p (gf))
881 grace_fact = gh_scm2double (gf);
892 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
893 "The space taken by a note is dependent on its duration. Doubling a\n"
894 "duration adds spacing-increment to the space. The most common shortest\n"
895 "note gets shortest-duration-space. Notes that are even shorter are\n"
896 "spaced proportonial to their duration.\n"
898 "Typically, the increment is the width of a black note head. In a\n"
899 "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
900 "gets 2 note heads width (i.e. the space following a note is 1 note\n"
901 "head width) A 16th note is followed by 0.5 note head width. The\n"
902 "quarter note is followed by 3 NHW, the half by 4 NHW, etc.\n",
903 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
907 ADD_INTERFACE (Spacing_interface,"spacing-interface",
908 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",