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>
13 #include "line-of-score.hh"
14 #include "paper-score.hh"
15 #include "paper-column.hh"
18 #include "note-spacing.hh"
21 #include "staff-spacing.hh"
23 #include "paper-column.hh"
24 #include "spaceable-grob.hh"
29 Don't be confused by right-items: each spacing wish can also contain
30 a number of items, with which a spacing constraint may be kept. It's
31 a little baroque, but it might come in handy later on?
37 static Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
38 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
39 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
40 static Rational find_shortest (Link_array<Grob> const &);
41 static void breakable_column_spacing (Item* l, Item *r);
42 static void find_loose_columns () {}
43 static void prune_loose_colunms (Grob*,Link_array<Grob> *cols, Rational);
44 static void find_loose_columns (Link_array<Grob> cols);
45 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
46 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
47 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
48 static void musical_column_spacing (Grob*,Item*,Item*, Real, Rational);
49 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
53 Return whether COL is fixed to its neighbors by some kind of spacing
57 loose_column (Grob *l, Grob *c, Grob *r)
59 SCM rns = c->get_grob_property ("right-neighbors");
60 SCM lns = c->get_grob_property ("left-neighbors");
63 If this column doesn't have a proper neighbor, we should really
64 make it loose, but spacing it correctly is more than we can
67 (this happens in the following situation:
78 the column containing the clef is really loose, and should be
79 attached right to the first column, but that is a lot of work for
80 such a borderline case.)
83 if (!gh_pair_p (lns) || !gh_pair_p (rns))
86 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
87 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
89 if (!l_neighbor || !r_neighbor)
92 l_neighbor = l_neighbor->column_l();
93 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
95 if (l == l_neighbor && r == r_neighbor)
98 if (!l_neighbor || !r_neighbor)
102 Only declare loose if the bounds make a little sense. This means
103 some cases (two isolated, consecutive clef changes) won't be
104 nicely folded, but hey, then don't do that.
106 if ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
107 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor)))
114 If in doubt: we're not loose; the spacing engine should space for
115 it, risking suboptimal spacing.
117 (Otherwise, we might risk core dumps, and other weird stuff.)
124 Remove columns that are not tightly fitting from COLS. In the
125 removed columns, set 'between-cols to the columns where it is in
129 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
131 Link_array<Grob> newcols;
132 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
133 for (int i=0; i < cols->size (); i++)
135 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
137 newcols.push (cols->elem(i));
141 Grob *c = cols->elem(i);
142 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
144 SCM lns = c->get_grob_property ("left-neighbors");
145 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
147 SCM rns = c->get_grob_property ("right-neighbors");
148 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
151 Either object can be non existent, if the score ends
154 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
155 c->set_grob_property ("between-cols", gh_cons (lns,
159 Set distance constraints for loose columns
161 Drul_array<Grob*> next_door;
162 next_door[LEFT] =cols->elem (i - 1);
163 next_door[RIGHT] =cols->elem (i + 1);
165 Drul_array<Real> dists(0,0);
170 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
171 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
173 for (SCM s = lc->get_grob_property ("spacing-wishes");
174 gh_pair_p (s); s = gh_cdr (s))
176 Grob *sp = unsmob_grob (gh_car (s));
177 if (Note_spacing::left_column (sp) != lc
178 || Note_spacing::right_column (sp) != rc)
188 The note spacing should be taken from the musical
192 Real base = note_spacing (me, lc, rc, shortest, &dummy);
193 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
197 dists[d] = dists[d] >? space;
201 Real space, fixed_space;
202 Staff_spacing::get_spacing_params (sp,
203 &space, &fixed_space);
205 dists[d] = dists[d] >? fixed_space;
210 while (flip (&d) != LEFT);
213 r.distance_f_ = dists[LEFT] + dists[RIGHT];
214 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
215 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
229 Set neighboring columns determined by the spacing-wishes grob property.
232 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
234 for (int i=0; i < cols.size(); i++)
236 SCM right_neighbors = SCM_EOL;
237 int min_rank = 100000; // inf.
240 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
241 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
243 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
245 Item * lc = wish->column_l ();
246 Grob * right = Note_spacing::right_column (wish);
251 Item * rc = dynamic_cast<Item*> (right);
253 int right_rank = Paper_column::rank_i (rc);
254 int left_rank = Paper_column::rank_i (lc);
257 update the left column.
259 if (right_rank <= min_rank)
261 if (right_rank < min_rank)
262 right_neighbors =SCM_EOL;
264 min_rank = right_rank;
265 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
269 update the right column of the wish.
272 SCM left_neighs = rc->get_grob_property ("left-neighbors");
273 if (gh_pair_p (left_neighs)
274 && unsmob_grob (gh_car (left_neighs)))
276 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
277 maxrank = Paper_column::rank_i (it->column_l());
280 if (left_rank >= maxrank)
282 if (left_rank > maxrank)
283 left_neighs = SCM_EOL;
285 left_neighs = gh_cons (wish->self_scm (), left_neighs);
286 rc->set_grob_property ("left-neighbors", right_neighbors);
290 if (gh_pair_p (right_neighbors))
292 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
298 Set neighboring columns that have no left/right-neighbor set
299 yet. Only do breakable non-musical columns, and musical columns.
302 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
304 for (int i = 0; i < cols.size (); i++)
306 Item * it = dynamic_cast<Item*>(cols[i]);
307 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
310 // it->breakable || it->musical
313 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
315 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
316 if (!gh_pair_p (ln) && i )
318 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
321 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
322 if (!gh_pair_p (rn) && i < cols.size () - 1)
324 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
330 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
332 Spacing_spanner::set_springs (SCM smob)
334 Grob *me = unsmob_grob (smob);
336 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
338 set_explicit_neighbor_columns (all);
340 Rational global_shortest = find_shortest (all);
341 prune_loose_colunms (me, &all, global_shortest);
342 set_implicit_neighbor_columns (all);
346 for (int i = 1; i < all.size (); i++)
349 if (Item::breakable_b (sc))
351 Link_array<Grob> measure (all.slice (j, i+1));
352 do_measure (global_shortest, me, &measure);
357 return SCM_UNSPECIFIED;
362 We want the shortest note that is also "common" in the piece, so we
363 find the shortest in each measure, and take the most frequently
366 This probably gives weird effects with modern music, where every
367 note has a different duration, but hey, don't write that kind of
372 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
375 ascending in duration
377 Array<Rational> durations;
380 Rational shortest_in_measure;
381 shortest_in_measure.set_infinite (1);
383 for (int i =0 ; i < cols.size (); i++)
385 if (Paper_column::musical_b (cols[i]))
387 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
390 ignore grace notes for shortest notes.
392 if (when && when->grace_part_)
395 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
396 Moment this_shortest = *unsmob_moment (st);
397 assert (this_shortest.to_bool());
398 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
400 else if (!shortest_in_measure.infty_b()
401 && Item::breakable_b (cols[i]))
404 for (; j < durations.size(); j++)
406 if (durations[j] > shortest_in_measure)
408 counts.insert (1, j);
409 durations.insert (shortest_in_measure, j);
412 else if (durations[j] == shortest_in_measure)
419 if (durations.size() == j)
421 durations.push (shortest_in_measure);
425 shortest_in_measure.set_infinite(1);
431 for (int i =durations.size(); i--;)
433 if (counts[i] >= max_count)
436 max_count = counts[i];
439 // printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
443 TODO: 1/8 should be adjustable?
445 Rational d = Rational (1,8);
447 d = d <? durations[max_idx] ;
453 Generate spacing for a single measure. We used to have code that did
454 per-measure spacing. Now we have piecewise spacing. We should fix
455 this to support "spacing-regions": some regions have different notes
456 (different time sigs) than others, and should be spaced differently.
459 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
462 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
463 for (int i= 0; i < cols->size () - 1; i++)
465 Item * l = dynamic_cast<Item*> (cols->elem (i));
466 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
468 Paper_column * lc = dynamic_cast<Paper_column*> (l);
469 Paper_column * rc = dynamic_cast<Paper_column*> (r);
471 if (!Paper_column::musical_b (l))
473 breakable_column_spacing (l, r);
477 The case that the right part is broken as well is rather
478 rare, but it is possible, eg. with a single empty measure,
479 or if one staff finishes a tad earlier than the rest.
482 Item *lb = l->find_prebroken_piece (RIGHT);
483 Item *rb = r->find_prebroken_piece (LEFT);
486 breakable_column_spacing (lb,r);
489 breakable_column_spacing (l, rb);
491 breakable_column_spacing (lb, rb);
497 musical_column_spacing (me, lc, rc, headwid, shortest);
498 if (Item *rb = r->find_prebroken_piece (LEFT))
499 musical_column_spacing (me, lc, rb, headwid, shortest);
505 Generate the space between two musical columns LC and RC, given spacing parameters INCR and SHRTEST.
508 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
510 bool expand_only = false;
511 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
513 Real max_note_space = -infinity_f;
514 Real max_fixed_note_space = -infinity_f;
516 SCM seq = lc->get_grob_property ("right-neighbors");
519 We adjust the space following a note only if the next note
520 happens after the current note (this is set in the grob
521 property SPACING-SEQUENCE.
523 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
525 Grob * wish = unsmob_grob (gh_car (s));
527 Item *wish_rcol = Note_spacing::right_column (wish);
528 if (Note_spacing::left_column (wish) != lc
529 || (wish_rcol != rc && wish_rcol != rc->original_l_))
533 This is probably a waste of time in the case of polyphonic
535 if (Note_spacing::has_interface (wish))
540 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
541 max_note_space = max_note_space >? space;
542 max_fixed_note_space = max_fixed_note_space >? fixed;
547 if (max_note_space < 0)
549 max_note_space = base_note_space;
550 max_fixed_note_space = increment;
553 Spaceable_grob::add_spring (lc, rc, max_note_space, 1 / (max_note_space -max_fixed_note_space), expand_only);
558 Read hints from L and generate springs.
561 Spacing_spanner::breakable_column_spacing (Item* l, Item *r)
563 Real max_fixed = -infinity_f;
564 Real max_space = -infinity_f;
566 for (SCM s = l->get_grob_property ("spacing-wishes");
567 gh_pair_p (s); s = gh_cdr (s))
569 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
571 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
578 column for the left one settings should be ok due automatic
582 assert (spacing_grob-> column_l () == l);
584 Staff_spacing::get_spacing_params (spacing_grob,
585 &space, &fixed_space);
586 if (space > max_space)
589 max_fixed = fixed_space;
593 if (isinf (max_space))
595 programming_error ("No pref spacing found");
601 if (l->break_status_dir() == RIGHT
602 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
604 /* Start of line: this space is not stretchable */
605 max_fixed = max_space;
609 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
610 works on all architectures.
613 Spaceable_grob::add_spring (l, r, max_space, 1/(max_space - max_fixed), false);
618 Get the measure wide ant for arithmetic spacing.
621 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
623 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
627 Rational ratio = d.main_part_ / shortest;
630 return (0.5 + 0.5 * double (ratio)) * k ;
636 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
637 OSU-CISRC-10/87-TR35, Department of Computer and Information Science,
638 The Ohio State University, 1987.
640 Real log = log_2 (shortest);
642 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
643 *expand_only = false;
645 return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
650 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
651 Moment shortest, bool * expand_only)
653 Moment shortest_playing_len = 0;
654 SCM s = lc->get_grob_property ("shortest-playing-duration");
656 if (unsmob_moment (s))
657 shortest_playing_len = *unsmob_moment (s);
659 if (! shortest_playing_len.to_bool ())
661 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
662 shortest_playing_len = 1;
665 Moment delta_t = Paper_column::when_mom (rc) - Paper_column::when_mom (lc);
668 if (delta_t.main_part_)
670 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
671 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
673 else if (delta_t.grace_part_)
676 TODO: figure out how to space grace notes.
678 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
680 Real grace_fact = 1.0;
681 SCM gf = me->get_grob_property ("grace-space-factor");
682 if (gh_number_p (gf))
683 grace_fact = gh_scm2double (gf);
694 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
695 " SPACE = arithmetic_multiplier * ( C + log2 (TIME) ))
696 The space taken by a note is determined by the formula
700 where TIME is the amount of time a note occupies. The value of C is
701 chosen such that the smallest space within a measure is
702 arithmetic_basicspace:
704 C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8))
706 The smallest space is the one following the shortest note in the
707 measure, or the space following a hypothetical 1/8 note. Typically
708 arithmetic_basicspace is set to a value so that the shortest note
709 takes about two noteheads of space (ie, is followed by a notehead of
713 2*quartwidth = arithmetic_multiplier * ( C + log2 (SHORTEST) ))
715 @{ using: C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8)) @}
716 @{ assuming: SHORTEST <= 1/8 @}
718 = arithmetic_multiplier *
719 ( arithmetic_basicspace - log2 (SHORTEST) + log2 (SHORTEST) )
721 = arithmetic_multiplier * arithmetic_basicspace
723 @{ choose: arithmetic_multiplier = 1.0*quartwidth (why?) @}
725 = quartwidth * arithmetic_basicspace
729 arithmetic_basicspace = 2/1 = 2
732 If you want to space your music wider, use something like:
734 arithmetic_basicspace = 4.;
737 "spacing-increment shortest-duration-space");