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"
30 Don't be confused by right-items: each spacing wish can also contain
31 a number of items, with which a spacing constraint may be kept. It's
32 a little baroque, but it might come in handy later on?
38 static void standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
39 Real * fixed, Real * space, Moment);
42 static Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
43 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
44 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
45 static Rational find_shortest (Grob *, Link_array<Grob> const &);
46 static void breakable_column_spacing (Grob*, Item* l, Item *r, Moment);
47 static void find_loose_columns () {}
48 static void prune_loose_colunms (Grob*,Link_array<Grob> *cols, Rational);
49 static void find_loose_columns (Link_array<Grob> cols);
50 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
51 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
52 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
53 static void musical_column_spacing (Grob*,Item*,Item*, Real, Rational);
54 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
55 static bool has_interface (Grob*);
59 Return whether COL is fixed to its neighbors by some kind of spacing
63 loose_column (Grob *l, Grob *c, Grob *r)
65 SCM rns = c->get_grob_property ("right-neighbors");
66 SCM lns = c->get_grob_property ("left-neighbors");
69 If this column doesn't have a proper neighbor, we should really
70 make it loose, but spacing it correctly is more than we can
73 (this happens in the following situation:
84 the column containing the clef is really loose, and should be
85 attached right to the first column, but that is a lot of work for
86 such a borderline case.)
89 if (!gh_pair_p (lns) || !gh_pair_p (rns))
92 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
93 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
95 if (!l_neighbor || !r_neighbor)
98 l_neighbor = l_neighbor->column_l();
99 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
101 if (l == l_neighbor && r == r_neighbor)
104 if (!l_neighbor || !r_neighbor)
108 Only declare loose if the bounds make a little sense. This means
109 some cases (two isolated, consecutive clef changes) won't be
110 nicely folded, but hey, then don't do that.
112 if ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
113 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor)))
120 If in doubt: we're not loose; the spacing engine should space for
121 it, risking suboptimal spacing.
123 (Otherwise, we might risk core dumps, and other weird stuff.)
130 Remove columns that are not tightly fitting from COLS. In the
131 removed columns, set 'between-cols to the columns where it is in
135 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
137 Link_array<Grob> newcols;
138 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
139 for (int i=0; i < cols->size (); i++)
141 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
143 newcols.push (cols->elem(i));
147 Grob *c = cols->elem(i);
148 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
150 SCM lns = c->get_grob_property ("left-neighbors");
151 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
153 SCM rns = c->get_grob_property ("right-neighbors");
154 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
157 Either object can be non existent, if the score ends
160 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
161 c->set_grob_property ("between-cols", gh_cons (lns,
165 Set distance constraints for loose columns
167 Drul_array<Grob*> next_door;
168 next_door[LEFT] =cols->elem (i - 1);
169 next_door[RIGHT] =cols->elem (i + 1);
171 Drul_array<Real> dists(0,0);
176 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
177 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
179 for (SCM s = lc->get_grob_property ("spacing-wishes");
180 gh_pair_p (s); s = gh_cdr (s))
182 Grob *sp = unsmob_grob (gh_car (s));
183 if (Note_spacing::left_column (sp) != lc
184 || Note_spacing::right_column (sp) != rc)
194 The note spacing should be taken from the musical
198 Real base = note_spacing (me, lc, rc, shortest, &dummy);
199 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
203 dists[d] = dists[d] >? space;
207 Real space, fixed_space;
208 Staff_spacing::get_spacing_params (sp,
209 &space, &fixed_space);
211 dists[d] = dists[d] >? fixed_space;
216 while (flip (&d) != LEFT);
219 r.distance_f_ = dists[LEFT] + dists[RIGHT];
220 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
221 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
235 Set neighboring columns determined by the spacing-wishes grob property.
238 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
240 for (int i=0; i < cols.size(); i++)
242 SCM right_neighbors = SCM_EOL;
243 int min_rank = 100000; // inf.
246 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
247 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
249 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
251 Item * lc = wish->column_l ();
252 Grob * right = Note_spacing::right_column (wish);
257 Item * rc = dynamic_cast<Item*> (right);
259 int right_rank = Paper_column::rank_i (rc);
260 int left_rank = Paper_column::rank_i (lc);
263 update the left column.
265 if (right_rank <= min_rank)
267 if (right_rank < min_rank)
268 right_neighbors =SCM_EOL;
270 min_rank = right_rank;
271 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
275 update the right column of the wish.
278 SCM left_neighs = rc->get_grob_property ("left-neighbors");
279 if (gh_pair_p (left_neighs)
280 && unsmob_grob (gh_car (left_neighs)))
282 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
283 maxrank = Paper_column::rank_i (it->column_l());
286 if (left_rank >= maxrank)
288 if (left_rank > maxrank)
289 left_neighs = SCM_EOL;
291 left_neighs = gh_cons (wish->self_scm (), left_neighs);
292 rc->set_grob_property ("left-neighbors", right_neighbors);
296 if (gh_pair_p (right_neighbors))
298 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
304 Set neighboring columns that have no left/right-neighbor set
305 yet. Only do breakable non-musical columns, and musical columns.
308 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
310 for (int i = 0; i < cols.size (); i++)
312 Item * it = dynamic_cast<Item*>(cols[i]);
313 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
316 // it->breakable || it->musical
319 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
321 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
322 if (!gh_pair_p (ln) && i )
324 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
327 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
328 if (!gh_pair_p (rn) && i < cols.size () - 1)
330 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
336 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
338 Spacing_spanner::set_springs (SCM smob)
340 Grob *me = unsmob_grob (smob);
342 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
344 set_explicit_neighbor_columns (all);
346 Rational global_shortest = find_shortest (me, all);
347 prune_loose_colunms (me, &all, global_shortest);
348 set_implicit_neighbor_columns (all);
352 for (int i = 1; i < all.size (); i++)
355 if (Item::breakable_b (sc))
357 Link_array<Grob> measure (all.slice (j, i+1));
358 do_measure (global_shortest, me, &measure);
363 return SCM_UNSPECIFIED;
368 We want the shortest note that is also "common" in the piece, so we
369 find the shortest in each measure, and take the most frequently
372 This probably gives weird effects with modern music, where every
373 note has a different duration, but hey, don't write that kind of
378 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
381 ascending in duration
383 Array<Rational> durations;
386 Rational shortest_in_measure;
387 shortest_in_measure.set_infinite (1);
389 for (int i =0 ; i < cols.size (); i++)
391 if (Paper_column::musical_b (cols[i]))
393 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
396 ignore grace notes for shortest notes.
398 if (when && when->grace_part_)
401 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
402 Moment this_shortest = *unsmob_moment (st);
403 assert (this_shortest.to_bool());
404 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
406 else if (!shortest_in_measure.infty_b()
407 && Item::breakable_b (cols[i]))
410 for (; j < durations.size(); j++)
412 if (durations[j] > shortest_in_measure)
414 counts.insert (1, j);
415 durations.insert (shortest_in_measure, j);
418 else if (durations[j] == shortest_in_measure)
425 if (durations.size() == j)
427 durations.push (shortest_in_measure);
431 shortest_in_measure.set_infinite(1);
437 for (int i =durations.size(); i--;)
439 if (counts[i] >= max_count)
442 max_count = counts[i];
445 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
448 SCM bsd = me->get_grob_property ("base-shortest-duration");
449 Rational d = Rational (1,8);
450 if (Moment *m = unsmob_moment (bsd))
454 d = d <? durations[max_idx] ;
460 Generate spacing for a single measure. We used to have code that did
461 per-measure spacing. Now we have piecewise spacing. We should fix
462 this to support "spacing-regions": some regions have different notes
463 (different time sigs) than others, and should be spaced differently.
466 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
469 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
470 for (int i= 0; i < cols->size () - 1; i++)
472 Item * l = dynamic_cast<Item*> (cols->elem (i));
473 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
475 Paper_column * lc = dynamic_cast<Paper_column*> (l);
476 Paper_column * rc = dynamic_cast<Paper_column*> (r);
478 if (!Paper_column::musical_b (l))
480 breakable_column_spacing (me, l, r, shortest);
484 The case that the right part is broken as well is rather
485 rare, but it is possible, eg. with a single empty measure,
486 or if one staff finishes a tad earlier than the rest.
489 Item *lb = l->find_prebroken_piece (RIGHT);
490 Item *rb = r->find_prebroken_piece (LEFT);
493 breakable_column_spacing (me, lb,r, shortest);
496 breakable_column_spacing (me, l, rb, shortest);
498 breakable_column_spacing (me, lb, rb, shortest);
504 musical_column_spacing (me, lc, rc, headwid, shortest);
505 if (Item *rb = r->find_prebroken_piece (LEFT))
506 musical_column_spacing (me, lc, rb, headwid, shortest);
512 Generate the space between two musical columns LC and RC, given
513 spacing parameters INCR and SHORTEST.
516 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
518 bool expand_only = false;
519 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
521 Real max_note_space = -infinity_f;
522 Real max_fixed_note_space = -infinity_f;
524 SCM seq = lc->get_grob_property ("right-neighbors");
527 We adjust the space following a note only if the next note
528 happens after the current note (this is set in the grob
529 property SPACING-SEQUENCE.
531 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
533 Grob * wish = unsmob_grob (gh_car (s));
535 Item *wish_rcol = Note_spacing::right_column (wish);
536 if (Note_spacing::left_column (wish) != lc
537 || (wish_rcol != rc && wish_rcol != rc->original_l_))
541 This is probably a waste of time in the case of polyphonic
543 if (Note_spacing::has_interface (wish))
548 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
549 max_note_space = max_note_space >? space;
550 max_fixed_note_space = max_fixed_note_space >? fixed;
554 if (max_note_space < 0)
556 max_note_space = base_note_space;
557 max_fixed_note_space = increment;
560 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
563 Whatever we do, the fixed space is smaller than the real
566 TODO: this criterion is discontinuous in the derivative.
567 Maybe it should be continuous?
569 max_fixed_note_space = max_fixed_note_space <? max_note_space;
571 Real strength = (ragged) ? 1.0 : 1 / (max_note_space - max_fixed_note_space);
572 Real distance = (ragged) ? max_fixed_note_space : max_note_space;
573 // Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
575 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
580 The one-size-fits all spacing. It doesn't take into account
581 different spacing wishes from one to the next column.
584 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
585 Real * fixed, Real * space,
588 *fixed = l->extent (l, X_AXIS)[RIGHT] - r->extent (r, X_AXIS)[LEFT];
590 if (l->breakable_b (l) && r->breakable_b(r))
592 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
597 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
599 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
603 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
606 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
614 Read hints from L and generate springs.
617 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
619 Real max_fixed = -infinity_f;
620 Real max_space = -infinity_f;
622 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
625 for (SCM s = l->get_grob_property ("spacing-wishes");
626 gh_pair_p (s); s = gh_cdr (s))
628 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
630 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
637 column for the left one settings should be ok due automatic
641 assert (spacing_grob-> column_l () == l);
643 Staff_spacing::get_spacing_params (spacing_grob,
644 &space, &fixed_space);
645 if (space > max_space)
648 max_fixed = fixed_space;
655 if (isinf (max_space))
658 One situation where this can happen is when there is a column
659 that only serves as a spanning point for a short staff-symbol.
666 (here no StaffSpacing from Y to X is found.)
668 programming_error ("No StaffSpacing wishes found");
674 if (l->break_status_dir() == RIGHT
675 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
677 /* Start of line: this space is not stretchable */
678 max_fixed = max_space;
682 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
683 works on all architectures.
686 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
687 Real strength = (ragged) ? 1.0 : 1 / (max_space - max_fixed);
688 Real distance = (ragged) ? max_fixed : max_space;
689 Spaceable_grob::add_spring (l, r, distance, strength, false);
694 Get the measure wide ant for arithmetic spacing.
697 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
699 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
700 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
705 We don't space really short notes using the log of the
706 duration, since it would disproportionally stretches the long
707 notes in a piece. In stead, we use geometric spacing with constant 0.5
710 This should probably be tunable, to use other base numbers.
712 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
713 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
714 mm for 8th. (white space), suggesting that we use
716 (1.2 / 1.5)^{-log2(duration ratio)}
720 Rational ratio = d.main_part_ / shortest;
723 return ((k-1) + double (ratio)) * incr;
728 John S. Gourlay. ``Spacing a Line of Music,'' Technical
729 Report OSU-CISRC-10/87-TR35, Department of Computer and
730 Information Science, The Ohio State University, 1987.
732 Real log = log_2 (shortest);
734 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
735 *expand_only = false;
737 return (log_2 (compdur) + k) * incr;
742 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
743 Moment shortest, bool * expand_only)
745 Moment shortest_playing_len = 0;
746 SCM s = lc->get_grob_property ("shortest-playing-duration");
748 if (unsmob_moment (s))
749 shortest_playing_len = *unsmob_moment (s);
751 if (! shortest_playing_len.to_bool ())
753 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
754 shortest_playing_len = 1;
757 Moment lwhen = Paper_column::when_mom (lc);
758 Moment rwhen = Paper_column::when_mom (rc);
760 Moment delta_t = rwhen - lwhen;
764 In normal situations, the next column is at most
765 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
766 with durations, invalidating this assumption. Here we kludge
767 around to get chord tremolos to behave properly.
770 shortest_playing_len = shortest_playing_len >? delta_t;
771 if (delta_t.main_part_ && !lwhen.grace_part_)
773 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
774 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
776 else if (delta_t.grace_part_)
779 TODO: figure out how to space grace notes.
781 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
783 Real grace_fact = 1.0;
784 SCM gf = me->get_grob_property ("grace-space-factor");
785 if (gh_number_p (gf))
786 grace_fact = gh_scm2double (gf);
797 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
799 The space taken by a note is dependent on its duration. Doubling a
800 duration adds spacing-increment to the space. The most common shortest
801 note gets shortest-duration-space. Notes that are even shorter are
802 spaced proportonial to their duration.
804 Typically, the increment is the width of a black note head. In a
805 piece with lots of 8th notes, and some 16th notes, the eighth note
806 gets 2 note heads width (i.e. the space following a note is 1 note
807 head width) A 16th note is followed by 0.5 note head width. The
808 quarter note is followed by 3 NHW, the half by 4 NHW, etc.
810 "grace-space-factor spacing-increment shortest-duration-space");