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>
14 #include "paper-def.hh"
15 #include "paper-score.hh"
16 #include "paper-column.hh"
19 #include "note-spacing.hh"
22 #include "staff-spacing.hh"
24 #include "paper-column.hh"
25 #include "spaceable-grob.hh"
26 #include "break-align-interface.hh"
37 static void standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
38 Real * fixed, Real * space, Moment);
41 static Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
42 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
43 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
44 static Rational find_shortest (Grob *, Link_array<Grob> const &);
45 static void breakable_column_spacing (Grob*, Item* l, Item *r, Moment);
46 static void find_loose_columns () {}
47 static void prune_loose_colunms (Grob*,Link_array<Grob> *cols, Rational);
48 static void find_loose_columns (Link_array<Grob> cols);
49 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
50 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
51 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
52 static void musical_column_spacing (Grob*,Item*,Item*, Real, Rational);
53 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
54 static bool has_interface (Grob*);
58 Return whether COL is fixed to its neighbors by some kind of spacing
62 If in doubt, then we're not loose; the spacing engine should space
63 for it, risking suboptimal spacing.
65 (Otherwise, we might risk core dumps, and other weird stuff.)
69 loose_column (Grob *l, Grob *c, Grob *r)
71 SCM rns = c->get_grob_property ("right-neighbors");
72 SCM lns = c->get_grob_property ("left-neighbors");
75 If this column doesn't have a proper neighbor, we should really
76 make it loose, but spacing it correctly is more than we can
79 (this happens in the following situation:
90 the column containing the clef is really loose, and should be
91 attached right to the first column, but that is a lot of work for
92 such a borderline case.)
95 if (!gh_pair_p (lns) || !gh_pair_p (rns))
98 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
99 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
101 if (!l_neighbor || !r_neighbor)
104 l_neighbor = l_neighbor->column_l();
105 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
107 if (l == l_neighbor && r == r_neighbor)
110 if (!l_neighbor || !r_neighbor)
116 Only declare loose if the bounds make a little sense. This means
117 some cases (two isolated, consecutive clef changes) won't be
118 nicely folded, but hey, then don't do that.
120 if(! ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
121 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor))) )
128 A rather hairy check, but we really only want to move around clefs. (anything else?)
130 in any case, we don't want to move bar lines.
132 for (SCM e = c->get_grob_property ("elements"); gh_pair_p (e); e = gh_cdr (e))
134 Grob * g = unsmob_grob (gh_car (e));
135 if (g && Break_align_interface::has_interface (g))
137 for (SCM s = g->get_grob_property ("elements"); gh_pair_p (s);
140 Grob *h = unsmob_grob (gh_car (s));
143 ugh. -- fix staff-bar name?
145 if (h && h->get_grob_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
155 Remove columns that are not tightly fitting from COLS. In the
156 removed columns, set 'between-cols to the columns where it is in
160 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
162 Link_array<Grob> newcols;
163 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
164 for (int i=0; i < cols->size (); i++)
166 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
168 newcols.push (cols->elem(i));
172 Grob *c = cols->elem(i);
173 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
175 SCM lns = c->get_grob_property ("left-neighbors");
176 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
178 SCM rns = c->get_grob_property ("right-neighbors");
179 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
182 Either object can be non existent, if the score ends
185 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
186 c->set_grob_property ("between-cols", gh_cons (lns,
190 Set distance constraints for loose columns
192 Drul_array<Grob*> next_door;
193 next_door[LEFT] =cols->elem (i - 1);
194 next_door[RIGHT] =cols->elem (i + 1);
196 Drul_array<Real> dists(0,0);
201 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
202 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
204 for (SCM s = lc->get_grob_property ("spacing-wishes");
205 gh_pair_p (s); s = gh_cdr (s))
207 Grob *sp = unsmob_grob (gh_car (s));
208 if (Note_spacing::left_column (sp) != lc
209 || Note_spacing::right_column (sp) != rc)
219 The note spacing should be taken from the musical
223 Real base = note_spacing (me, lc, rc, shortest, &dummy);
224 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
228 dists[d] = dists[d] >? space;
232 Real space, fixed_space;
233 Staff_spacing::get_spacing_params (sp,
234 &space, &fixed_space);
236 dists[d] = dists[d] >? fixed_space;
241 while (flip (&d) != LEFT);
244 r.distance_f_ = dists[LEFT] + dists[RIGHT];
245 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
246 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
260 Set neighboring columns determined by the spacing-wishes grob property.
263 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
265 for (int i=0; i < cols.size(); i++)
267 SCM right_neighbors = SCM_EOL;
268 int min_rank = 100000; // inf.
271 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
272 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
274 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
276 Item * lc = wish->column_l ();
277 Grob * right = Note_spacing::right_column (wish);
282 Item * rc = dynamic_cast<Item*> (right);
284 int right_rank = Paper_column::rank_i (rc);
285 int left_rank = Paper_column::rank_i (lc);
288 update the left column.
290 if (right_rank <= min_rank)
292 if (right_rank < min_rank)
293 right_neighbors =SCM_EOL;
295 min_rank = right_rank;
296 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
300 update the right column of the wish.
303 SCM left_neighs = rc->get_grob_property ("left-neighbors");
304 if (gh_pair_p (left_neighs)
305 && unsmob_grob (gh_car (left_neighs)))
307 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
308 maxrank = Paper_column::rank_i (it->column_l());
311 if (left_rank >= maxrank)
313 if (left_rank > maxrank)
314 left_neighs = SCM_EOL;
316 left_neighs = gh_cons (wish->self_scm (), left_neighs);
317 rc->set_grob_property ("left-neighbors", right_neighbors);
321 if (gh_pair_p (right_neighbors))
323 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
329 Set neighboring columns that have no left/right-neighbor set
330 yet. Only do breakable non-musical columns, and musical columns.
333 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
335 for (int i = 0; i < cols.size (); i++)
337 Item * it = dynamic_cast<Item*>(cols[i]);
338 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
341 // it->breakable || it->musical
344 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
346 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
347 if (!gh_pair_p (ln) && i )
349 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
352 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
353 if (!gh_pair_p (rn) && i < cols.size () - 1)
355 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
361 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
363 Spacing_spanner::set_springs (SCM smob)
365 Grob *me = unsmob_grob (smob);
367 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
369 set_explicit_neighbor_columns (all);
371 Rational global_shortest = find_shortest (me, all);
372 prune_loose_colunms (me, &all, global_shortest);
373 set_implicit_neighbor_columns (all);
377 for (int i = 1; i < all.size (); i++)
380 if (Item::breakable_b (sc))
382 Link_array<Grob> measure (all.slice (j, i+1));
383 do_measure (global_shortest, me, &measure);
388 return SCM_UNSPECIFIED;
393 We want the shortest note that is also "common" in the piece, so we
394 find the shortest in each measure, and take the most frequently
397 This probably gives weird effects with modern music, where every
398 note has a different duration, but hey, don't write that kind of
403 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
406 ascending in duration
408 Array<Rational> durations;
411 Rational shortest_in_measure;
412 shortest_in_measure.set_infinite (1);
414 for (int i =0 ; i < cols.size (); i++)
416 if (Paper_column::musical_b (cols[i]))
418 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
421 ignore grace notes for shortest notes.
423 if (when && when->grace_part_)
426 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
427 Moment this_shortest = *unsmob_moment (st);
428 assert (this_shortest.to_bool());
429 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
431 else if (!shortest_in_measure.infty_b()
432 && Item::breakable_b (cols[i]))
435 for (; j < durations.size(); j++)
437 if (durations[j] > shortest_in_measure)
439 counts.insert (1, j);
440 durations.insert (shortest_in_measure, j);
443 else if (durations[j] == shortest_in_measure)
450 if (durations.size() == j)
452 durations.push (shortest_in_measure);
456 shortest_in_measure.set_infinite(1);
462 for (int i =durations.size(); i--;)
464 if (counts[i] >= max_count)
467 max_count = counts[i];
470 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
473 SCM bsd = me->get_grob_property ("base-shortest-duration");
474 Rational d = Rational (1,8);
475 if (Moment *m = unsmob_moment (bsd))
479 d = d <? durations[max_idx] ;
485 Generate spacing for a single measure. We used to have code that did
486 per-measure spacing. Now we have piecewise spacing. We should fix
487 this to support "spacing-regions": some regions have different notes
488 (different time sigs) than others, and should be spaced differently.
491 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
494 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
495 for (int i= 0; i < cols->size () - 1; i++)
497 Item * l = dynamic_cast<Item*> (cols->elem (i));
498 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
500 Paper_column * lc = dynamic_cast<Paper_column*> (l);
501 Paper_column * rc = dynamic_cast<Paper_column*> (r);
503 if (!Paper_column::musical_b (l))
505 breakable_column_spacing (me, l, r, shortest);
509 The case that the right part is broken as well is rather
510 rare, but it is possible, eg. with a single empty measure,
511 or if one staff finishes a tad earlier than the rest.
514 Item *lb = l->find_prebroken_piece (RIGHT);
515 Item *rb = r->find_prebroken_piece (LEFT);
518 breakable_column_spacing (me, lb,r, shortest);
521 breakable_column_spacing (me, l, rb, shortest);
523 breakable_column_spacing (me, lb, rb, shortest);
529 musical_column_spacing (me, lc, rc, headwid, shortest);
530 if (Item *rb = r->find_prebroken_piece (LEFT))
531 musical_column_spacing (me, lc, rb, headwid, shortest);
537 Generate the space between two musical columns LC and RC, given
538 spacing parameters INCR and SHORTEST.
541 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
543 bool expand_only = false;
544 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
546 Real max_note_space = -infinity_f;
547 Real max_fixed_note_space = -infinity_f;
549 SCM seq = lc->get_grob_property ("right-neighbors");
552 We adjust the space following a note only if the next note
553 happens after the current note (this is set in the grob
554 property SPACING-SEQUENCE.
556 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
558 Grob * wish = unsmob_grob (gh_car (s));
560 Item *wish_rcol = Note_spacing::right_column (wish);
561 if (Note_spacing::left_column (wish) != lc
562 || (wish_rcol != rc && wish_rcol != rc->original_l_))
566 This is probably a waste of time in the case of polyphonic
568 if (Note_spacing::has_interface (wish))
573 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
574 max_note_space = max_note_space >? space;
575 max_fixed_note_space = max_fixed_note_space >? fixed;
579 if (max_note_space < 0)
581 max_note_space = base_note_space;
582 max_fixed_note_space = increment;
585 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
588 Whatever we do, the fixed space is smaller than the real
591 TODO: this criterion is discontinuous in the derivative.
592 Maybe it should be continuous?
594 max_fixed_note_space = max_fixed_note_space <? max_note_space;
596 Real strength = (ragged) ? 1.0 : 1 / (max_note_space - max_fixed_note_space);
597 Real distance = (ragged) ? max_fixed_note_space : max_note_space;
598 // Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
600 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
605 The one-size-fits all spacing. It doesn't take into account
606 different spacing wishes from one to the next column.
609 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
610 Real * fixed, Real * space,
613 *fixed = l->extent (l, X_AXIS)[RIGHT] - r->extent (r, X_AXIS)[LEFT];
615 if (l->breakable_b (l) && r->breakable_b(r))
617 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
622 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
624 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
628 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
631 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
639 Read hints from L and generate springs.
642 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
644 Real max_fixed = -infinity_f;
645 Real max_space = -infinity_f;
647 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
650 for (SCM s = l->get_grob_property ("spacing-wishes");
651 gh_pair_p (s); s = gh_cdr (s))
653 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
655 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
662 column for the left one settings should be ok due automatic
666 assert (spacing_grob-> column_l () == l);
668 Staff_spacing::get_spacing_params (spacing_grob,
669 &space, &fixed_space);
670 if (space > max_space)
673 max_fixed = fixed_space;
680 if (isinf (max_space))
683 One situation where this can happen is when there is a column
684 that only serves as a spanning point for a short staff-symbol.
691 (here no StaffSpacing from Y to X is found.)
693 programming_error ("No StaffSpacing wishes found");
699 if (l->break_status_dir() == RIGHT
700 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
702 /* Start of line: this space is not stretchable */
703 max_fixed = max_space;
707 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
708 works on all architectures.
711 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
712 Real strength = (ragged) ? 1.0 : 1 / (max_space - max_fixed);
713 Real distance = (ragged) ? max_fixed : max_space;
714 Spaceable_grob::add_spring (l, r, distance, strength, false);
719 Get the measure wide ant for arithmetic spacing.
722 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
724 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
725 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
730 We don't space really short notes using the log of the
731 duration, since it would disproportionally stretches the long
732 notes in a piece. In stead, we use geometric spacing with constant 0.5
735 This should probably be tunable, to use other base numbers.
737 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
738 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
739 mm for 8th. (white space), suggesting that we use
741 (1.2 / 1.5)^{-log2(duration ratio)}
745 Rational ratio = d.main_part_ / shortest;
748 return ((k-1) + double (ratio)) * incr;
753 John S. Gourlay. ``Spacing a Line of Music,'' Technical
754 Report OSU-CISRC-10/87-TR35, Department of Computer and
755 Information Science, The Ohio State University, 1987.
757 Real log = log_2 (shortest);
759 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
760 *expand_only = false;
762 return (log_2 (compdur) + k) * incr;
767 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
768 Moment shortest, bool * expand_only)
770 Moment shortest_playing_len = 0;
771 SCM s = lc->get_grob_property ("shortest-playing-duration");
773 if (unsmob_moment (s))
774 shortest_playing_len = *unsmob_moment (s);
776 if (! shortest_playing_len.to_bool ())
778 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
779 shortest_playing_len = 1;
782 Moment lwhen = Paper_column::when_mom (lc);
783 Moment rwhen = Paper_column::when_mom (rc);
785 Moment delta_t = rwhen - lwhen;
789 In normal situations, the next column is at most
790 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
791 with durations, invalidating this assumption. Here we kludge
792 around to get chord tremolos to behave properly.
795 shortest_playing_len = shortest_playing_len >? delta_t;
796 if (delta_t.main_part_ && !lwhen.grace_part_)
798 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
799 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
801 else if (delta_t.grace_part_)
804 TODO: figure out how to space grace notes.
806 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
808 Real grace_fact = 1.0;
809 SCM gf = me->get_grob_property ("grace-space-factor");
810 if (gh_number_p (gf))
811 grace_fact = gh_scm2double (gf);
822 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
824 The space taken by a note is dependent on its duration. Doubling a
825 duration adds spacing-increment to the space. The most common shortest
826 note gets shortest-duration-space. Notes that are even shorter are
827 spaced proportonial to their duration.
829 Typically, the increment is the width of a black note head. In a
830 piece with lots of 8th notes, and some 16th notes, the eighth note
831 gets 2 note heads width (i.e. the space following a note is 1 note
832 head width) A 16th note is followed by 0.5 note head width. The
833 quarter note is followed by 3 NHW, the half by 4 NHW, etc.
835 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space");