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->column_l();
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_f_ = 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->column_l ();
274 Grob * right = Note_spacing::right_column (wish);
279 Item * rc = dynamic_cast<Item*> (right);
281 int right_rank = Paper_column::rank_i (rc);
282 int left_rank = Paper_column::rank_i (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::rank_i (it->column_l());
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_l_->system_->column_l_arr ()) ;
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.str()));
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_l_))
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 (max_note_space < 0)
591 max_note_space = base_note_space;
592 max_fixed_note_space = increment;
595 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
598 Whatever we do, the fixed space is smaller than the real
601 TODO: this criterion is discontinuous in the derivative.
602 Maybe it should be continuous?
604 max_fixed_note_space = max_fixed_note_space <? max_note_space;
607 This doesn't make sense. For ragged right we want to have the same
608 spacing. Otherwise the option should be called differently.
610 ragged-righted-and-weird-spacing. Whatever.
613 Real strength = (ragged) ? 1.0 : 1 / (max_note_space - max_fixed_note_space);
614 Real distance = (ragged) ? max_fixed_note_space : max_note_space;
618 TODO: make sure that the space doesn't exceed the right margin.
620 Real strength = 1 / (max_note_space - max_fixed_note_space);
621 Real distance = max_note_space;
624 // Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
626 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
631 The one-size-fits all spacing. It doesn't take into account
632 different spacing wishes from one to the next column.
635 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
636 Real * fixed, Real * space,
642 Drul_array<Item*> cols(l,r);
646 if (!Paper_column::musical_b (cols[d]))
649 Tied accidentals over barlines cause problems, so lets see
650 what happens if we do this for non musical columns only.
652 Interval lext = cols[d]->extent (cols [d], X_AXIS);
653 *fixed += -d * lext[-d];
656 while (flip (&d) != LEFT);
658 if (l->breakable_b (l) && r->breakable_b(r))
660 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
665 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
667 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
671 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
674 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
680 Read hints from L and generate springs.
683 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
685 Real max_fixed = -infinity_f;
686 Real max_space = -infinity_f;
688 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
691 for (SCM s = l->get_grob_property ("spacing-wishes");
692 gh_pair_p (s); s = gh_cdr (s))
694 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
696 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
703 column for the left one settings should be ok due automatic
707 assert (spacing_grob-> column_l () == l);
709 Staff_spacing::get_spacing_params (spacing_grob,
710 &space, &fixed_space);
711 if (space > max_space)
714 max_fixed = fixed_space;
721 if (isinf (max_space))
724 One situation where this can happen is when there is a column
725 that only serves as a spanning point for a short staff-symbol.
732 (here no StaffSpacing from Y to X is found.)
734 programming_error ("No StaffSpacing wishes found");
740 if (l->break_status_dir() == RIGHT
741 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
743 /* Start of line: this space is not stretchable */
744 max_fixed = max_space;
748 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
749 works on all architectures.
752 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
753 Real strength = (ragged) ? 1.0 : 1 / (max_space - max_fixed);
754 Real distance = (ragged) ? max_fixed : max_space;
755 Spaceable_grob::add_spring (l, r, distance, strength, false);
760 Get the measure wide ant for arithmetic spacing.
763 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
765 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
766 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
771 We don't space really short notes using the log of the
772 duration, since it would disproportionally stretches the long
773 notes in a piece. In stead, we use geometric spacing with constant 0.5
776 This should probably be tunable, to use other base numbers.
778 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
779 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
780 mm for 8th. (white space), suggesting that we use
782 (1.2 / 1.5)^{-log2(duration ratio)}
786 Rational ratio = d.main_part_ / shortest;
791 return ((k-1) + double (ratio)) * incr;
796 John S. Gourlay. ``Spacing a Line of Music,'' Technical
797 Report OSU-CISRC-10/87-TR35, Department of Computer and
798 Information Science, The Ohio State University, 1987.
800 Real log = log_2 (shortest);
802 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
803 *expand_only = false;
805 return (log_2 (compdur) + k) * incr;
810 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
811 Moment shortest, bool * expand_only)
813 Moment shortest_playing_len = 0;
814 SCM s = lc->get_grob_property ("shortest-playing-duration");
816 if (unsmob_moment (s))
817 shortest_playing_len = *unsmob_moment (s);
819 if (! shortest_playing_len.to_bool ())
821 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
822 shortest_playing_len = 1;
825 Moment lwhen = Paper_column::when_mom (lc);
826 Moment rwhen = Paper_column::when_mom (rc);
828 Moment delta_t = rwhen - lwhen;
832 In normal situations, the next column is at most
833 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
834 with durations, invalidating this assumption. Here we kludge
835 around to get chord tremolos to behave properly.
838 shortest_playing_len = shortest_playing_len >? delta_t;
839 if (delta_t.main_part_ && !lwhen.grace_part_)
841 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
842 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
844 else if (delta_t.grace_part_)
847 TODO: figure out how to space grace notes.
849 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
851 Real grace_fact = 1.0;
852 SCM gf = me->get_grob_property ("grace-space-factor");
853 if (gh_number_p (gf))
854 grace_fact = gh_scm2double (gf);
865 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
867 The space taken by a note is dependent on its duration. Doubling a
868 duration adds spacing-increment to the space. The most common shortest
869 note gets shortest-duration-space. Notes that are even shorter are
870 spaced proportonial to their duration.
872 Typically, the increment is the width of a black note head. In a
873 piece with lots of 8th notes, and some 16th notes, the eighth note
874 gets 2 note heads width (i.e. the space following a note is 1 note
875 head width) A 16th note is followed by 0.5 note head width. The
876 quarter note is followed by 3 NHW, the half by 4 NHW, etc.
878 "grace-space-factor spacing-increment base-shortest-duration shortest-duration-space common-shortest-duration");
882 ADD_INTERFACE (Spacing_interface,"spacing-interface",
883 "Something to do with line breaking and spacing. Kill this one after determining line breaks.",