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"
27 #include "spacing-interface.hh"
35 static void standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
36 Real * fixed, Real * space, Moment);
39 static Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
40 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
41 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
42 static Rational find_shortest (Grob *, Link_array<Grob> const &);
43 static void breakable_column_spacing (Grob*, Item* l, Item *r, Moment);
44 static void find_loose_columns () {}
45 static void prune_loose_colunms (Grob*,Link_array<Grob> *cols, Rational);
46 static void find_loose_columns (Link_array<Grob> cols);
47 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
48 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
49 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
50 static void musical_column_spacing (Grob*,Item*,Item*, Real, Rational);
51 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
52 static bool has_interface (Grob*);
56 Return whether COL is fixed to its neighbors by some kind of spacing
60 If in doubt, then we're not loose; the spacing engine should space
61 for it, risking suboptimal spacing.
63 (Otherwise, we might risk core dumps, and other weird stuff.)
67 loose_column (Grob *l, Grob *c, Grob *r)
69 SCM rns = c->get_grob_property ("right-neighbors");
70 SCM lns = c->get_grob_property ("left-neighbors");
73 If this column doesn't have a proper neighbor, we should really
74 make it loose, but spacing it correctly is more than we can
77 (this happens in the following situation:
88 the column containing the clef is really loose, and should be
89 attached right to the first column, but that is a lot of work for
90 such a borderline case.)
93 if (!gh_pair_p (lns) || !gh_pair_p (rns))
96 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
97 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
99 if (!l_neighbor || !r_neighbor)
102 l_neighbor = l_neighbor->column_l();
103 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
105 if (l == l_neighbor && r == r_neighbor)
108 if (!l_neighbor || !r_neighbor)
114 Only declare loose if the bounds make a little sense. This means
115 some cases (two isolated, consecutive clef changes) won't be
116 nicely folded, but hey, then don't do that.
118 if(! ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
119 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor))) )
126 A rather hairy check, but we really only want to move around clefs. (anything else?)
128 in any case, we don't want to move bar lines.
130 for (SCM e = c->get_grob_property ("elements"); gh_pair_p (e); e = gh_cdr (e))
132 Grob * g = unsmob_grob (gh_car (e));
133 if (g && Break_align_interface::has_interface (g))
135 for (SCM s = g->get_grob_property ("elements"); gh_pair_p (s);
138 Grob *h = unsmob_grob (gh_car (s));
141 ugh. -- fix staff-bar name?
143 if (h && h->get_grob_property ("break-align-symbol") == ly_symbol2scm ("staff-bar"))
153 Remove columns that are not tightly fitting from COLS. In the
154 removed columns, set 'between-cols to the columns where it is in
158 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
160 Link_array<Grob> newcols;
161 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
162 for (int i=0; i < cols->size (); i++)
164 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
166 newcols.push (cols->elem(i));
170 Grob *c = cols->elem(i);
171 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
173 SCM lns = c->get_grob_property ("left-neighbors");
174 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
176 SCM rns = c->get_grob_property ("right-neighbors");
177 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
180 Either object can be non existent, if the score ends
183 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
184 c->set_grob_property ("between-cols", gh_cons (lns,
188 Set distance constraints for loose columns
190 Drul_array<Grob*> next_door;
191 next_door[LEFT] =cols->elem (i - 1);
192 next_door[RIGHT] =cols->elem (i + 1);
194 Drul_array<Real> dists(0,0);
199 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
200 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
202 for (SCM s = lc->get_grob_property ("spacing-wishes");
203 gh_pair_p (s); s = gh_cdr (s))
205 Grob *sp = unsmob_grob (gh_car (s));
206 if (Note_spacing::left_column (sp) != lc
207 || Note_spacing::right_column (sp) != rc)
217 The note spacing should be taken from the musical
221 Real base = note_spacing (me, lc, rc, shortest, &dummy);
222 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
226 dists[d] = dists[d] >? space;
230 Real space, fixed_space;
231 Staff_spacing::get_spacing_params (sp,
232 &space, &fixed_space);
234 dists[d] = dists[d] >? fixed_space;
239 while (flip (&d) != LEFT);
242 r.distance_f_ = dists[LEFT] + dists[RIGHT];
243 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
244 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
258 Set neighboring columns determined by the spacing-wishes grob property.
261 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
263 for (int i=0; i < cols.size(); i++)
265 SCM right_neighbors = SCM_EOL;
266 int min_rank = 100000; // inf.
269 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
270 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
272 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
274 Item * lc = wish->column_l ();
275 Grob * right = Note_spacing::right_column (wish);
280 Item * rc = dynamic_cast<Item*> (right);
282 int right_rank = Paper_column::rank_i (rc);
283 int left_rank = Paper_column::rank_i (lc);
286 update the left column.
288 if (right_rank <= min_rank)
290 if (right_rank < min_rank)
291 right_neighbors =SCM_EOL;
293 min_rank = right_rank;
294 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
298 update the right column of the wish.
301 SCM left_neighs = rc->get_grob_property ("left-neighbors");
302 if (gh_pair_p (left_neighs)
303 && unsmob_grob (gh_car (left_neighs)))
305 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
306 maxrank = Paper_column::rank_i (it->column_l());
309 if (left_rank >= maxrank)
311 if (left_rank > maxrank)
312 left_neighs = SCM_EOL;
314 left_neighs = gh_cons (wish->self_scm (), left_neighs);
315 rc->set_grob_property ("left-neighbors", right_neighbors);
319 if (gh_pair_p (right_neighbors))
321 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
327 Set neighboring columns that have no left/right-neighbor set
328 yet. Only do breakable non-musical columns, and musical columns.
331 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
333 for (int i = 0; i < cols.size (); i++)
335 Item * it = dynamic_cast<Item*>(cols[i]);
336 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
339 // it->breakable || it->musical
342 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
344 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
345 if (!gh_pair_p (ln) && i )
347 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
350 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
351 if (!gh_pair_p (rn) && i < cols.size () - 1)
353 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
359 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
361 Spacing_spanner::set_springs (SCM smob)
363 Grob *me = unsmob_grob (smob);
365 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
367 set_explicit_neighbor_columns (all);
369 Rational global_shortest = find_shortest (me, all);
370 prune_loose_colunms (me, &all, global_shortest);
371 set_implicit_neighbor_columns (all);
375 for (int i = 1; i < all.size (); i++)
378 if (Item::breakable_b (sc))
380 Link_array<Grob> measure (all.slice (j, i+1));
381 do_measure (global_shortest, me, &measure);
386 return SCM_UNSPECIFIED;
391 We want the shortest note that is also "common" in the piece, so we
392 find the shortest in each measure, and take the most frequently
395 This probably gives weird effects with modern music, where every
396 note has a different duration, but hey, don't write that kind of
401 Spacing_spanner::find_shortest (Grob *me, Link_array<Grob> const &cols)
404 ascending in duration
406 Array<Rational> durations;
409 Rational shortest_in_measure;
410 shortest_in_measure.set_infinite (1);
412 for (int i =0 ; i < cols.size (); i++)
414 if (Paper_column::musical_b (cols[i]))
416 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
419 ignore grace notes for shortest notes.
421 if (when && when->grace_part_)
424 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
425 Moment this_shortest = *unsmob_moment (st);
426 assert (this_shortest.to_bool());
427 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
429 else if (!shortest_in_measure.infty_b()
430 && Item::breakable_b (cols[i]))
433 for (; j < durations.size(); j++)
435 if (durations[j] > shortest_in_measure)
437 counts.insert (1, j);
438 durations.insert (shortest_in_measure, j);
441 else if (durations[j] == shortest_in_measure)
448 if (durations.size() == j)
450 durations.push (shortest_in_measure);
454 shortest_in_measure.set_infinite(1);
460 for (int i =durations.size(); i--;)
462 if (counts[i] >= max_count)
465 max_count = counts[i];
468 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
471 SCM bsd = me->get_grob_property ("base-shortest-duration");
472 Rational d = Rational (1,8);
473 if (Moment *m = unsmob_moment (bsd))
477 d = d <? durations[max_idx] ;
483 Generate spacing for a single measure. We used to have code that did
484 per-measure spacing. Now we have piecewise spacing. We should fix
485 this to support "spacing-regions": some regions have different notes
486 (different time sigs) than others, and should be spaced differently.
489 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
492 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
493 for (int i= 0; i < cols->size () - 1; i++)
495 Item * l = dynamic_cast<Item*> (cols->elem (i));
496 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
498 Paper_column * lc = dynamic_cast<Paper_column*> (l);
499 Paper_column * rc = dynamic_cast<Paper_column*> (r);
501 if (!Paper_column::musical_b (l))
503 breakable_column_spacing (me, l, r, shortest);
507 The case that the right part is broken as well is rather
508 rare, but it is possible, eg. with a single empty measure,
509 or if one staff finishes a tad earlier than the rest.
512 Item *lb = l->find_prebroken_piece (RIGHT);
513 Item *rb = r->find_prebroken_piece (LEFT);
516 breakable_column_spacing (me, lb,r, shortest);
519 breakable_column_spacing (me, l, rb, shortest);
521 breakable_column_spacing (me, lb, rb, shortest);
527 musical_column_spacing (me, lc, rc, headwid, shortest);
528 if (Item *rb = r->find_prebroken_piece (LEFT))
529 musical_column_spacing (me, lc, rb, headwid, shortest);
535 Generate the space between two musical columns LC and RC, given
536 spacing parameters INCR and SHORTEST.
539 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
541 bool expand_only = false;
542 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
544 Real max_note_space = -infinity_f;
545 Real max_fixed_note_space = -infinity_f;
547 SCM seq = lc->get_grob_property ("right-neighbors");
550 We adjust the space following a note only if the next note
551 happens after the current note (this is set in the grob
552 property SPACING-SEQUENCE.
554 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
556 Grob * wish = unsmob_grob (gh_car (s));
558 Item *wish_rcol = Note_spacing::right_column (wish);
559 if (Note_spacing::left_column (wish) != lc
560 || (wish_rcol != rc && wish_rcol != rc->original_l_))
564 This is probably a waste of time in the case of polyphonic
566 if (Note_spacing::has_interface (wish))
571 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
572 max_note_space = max_note_space >? space;
573 max_fixed_note_space = max_fixed_note_space >? fixed;
577 if (max_note_space < 0)
579 max_note_space = base_note_space;
580 max_fixed_note_space = increment;
583 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
586 Whatever we do, the fixed space is smaller than the real
589 TODO: this criterion is discontinuous in the derivative.
590 Maybe it should be continuous?
592 max_fixed_note_space = max_fixed_note_space <? max_note_space;
594 Real strength = (ragged) ? 1.0 : 1 / (max_note_space - max_fixed_note_space);
595 Real distance = (ragged) ? max_fixed_note_space : max_note_space;
596 // Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
598 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
603 The one-size-fits all spacing. It doesn't take into account
604 different spacing wishes from one to the next column.
607 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
608 Real * fixed, Real * space,
613 Drul_array<Item*> cols(l,r);
617 Interval lext = cols[d]->extent (cols [d], X_AXIS);
619 *fixed += -d * lext[-d];
621 while (flip (&d) != LEFT);
623 if (l->breakable_b (l) && r->breakable_b(r))
625 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
630 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
632 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
636 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
639 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
647 Read hints from L and generate springs.
650 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
652 Real max_fixed = -infinity_f;
653 Real max_space = -infinity_f;
655 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
658 for (SCM s = l->get_grob_property ("spacing-wishes");
659 gh_pair_p (s); s = gh_cdr (s))
661 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
663 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
670 column for the left one settings should be ok due automatic
674 assert (spacing_grob-> column_l () == l);
676 Staff_spacing::get_spacing_params (spacing_grob,
677 &space, &fixed_space);
678 if (space > max_space)
681 max_fixed = fixed_space;
688 if (isinf (max_space))
691 One situation where this can happen is when there is a column
692 that only serves as a spanning point for a short staff-symbol.
699 (here no StaffSpacing from Y to X is found.)
701 programming_error ("No StaffSpacing wishes found");
707 if (l->break_status_dir() == RIGHT
708 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
710 /* Start of line: this space is not stretchable */
711 max_fixed = max_space;
715 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
716 works on all architectures.
719 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
720 Real strength = (ragged) ? 1.0 : 1 / (max_space - max_fixed);
721 Real distance = (ragged) ? max_fixed : max_space;
722 Spaceable_grob::add_spring (l, r, distance, strength, false);
727 Get the measure wide ant for arithmetic spacing.
730 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
732 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
733 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
738 We don't space really short notes using the log of the
739 duration, since it would disproportionally stretches the long
740 notes in a piece. In stead, we use geometric spacing with constant 0.5
743 This should probably be tunable, to use other base numbers.
745 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
746 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
747 mm for 8th. (white space), suggesting that we use
749 (1.2 / 1.5)^{-log2(duration ratio)}
753 Rational ratio = d.main_part_ / shortest;
756 return ((k-1) + double (ratio)) * incr;
761 John S. Gourlay. ``Spacing a Line of Music,'' Technical
762 Report OSU-CISRC-10/87-TR35, Department of Computer and
763 Information Science, The Ohio State University, 1987.
765 Real log = log_2 (shortest);
767 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
768 *expand_only = false;
770 return (log_2 (compdur) + k) * incr;
775 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
776 Moment shortest, bool * expand_only)
778 Moment shortest_playing_len = 0;
779 SCM s = lc->get_grob_property ("shortest-playing-duration");
781 if (unsmob_moment (s))
782 shortest_playing_len = *unsmob_moment (s);
784 if (! shortest_playing_len.to_bool ())
786 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
787 shortest_playing_len = 1;
790 Moment lwhen = Paper_column::when_mom (lc);
791 Moment rwhen = Paper_column::when_mom (rc);
793 Moment delta_t = rwhen - lwhen;
797 In normal situations, the next column is at most
798 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
799 with durations, invalidating this assumption. Here we kludge
800 around to get chord tremolos to behave properly.
803 shortest_playing_len = shortest_playing_len >? delta_t;
804 if (delta_t.main_part_ && !lwhen.grace_part_)
806 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
807 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
809 else if (delta_t.grace_part_)
812 TODO: figure out how to space grace notes.
814 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
816 Real grace_fact = 1.0;
817 SCM gf = me->get_grob_property ("grace-space-factor");
818 if (gh_number_p (gf))
819 grace_fact = gh_scm2double (gf);
830 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
832 The space taken by a note is dependent on its duration. Doubling a
833 duration adds spacing-increment to the space. The most common shortest
834 note gets shortest-duration-space. Notes that are even shorter are
835 spaced proportonial to their duration.
837 Typically, the increment is the width of a black note head. In a
838 piece with lots of 8th notes, and some 16th notes, the eighth note
839 gets 2 note heads width (i.e. the space following a note is 1 note
840 head width) A 16th note is followed by 0.5 note head width. The
841 quarter note is followed by 3 NHW, the half by 4 NHW, etc.
843 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space");
847 ADD_INTERFACE (Spacing_interface,"spacing-interface",
848 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",