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 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 (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 ));
57 Return whether COL is fixed to its neighbors by some kind of spacing
61 loose_column (Grob *l, Grob *c, Grob *r)
63 SCM rns = c->get_grob_property ("right-neighbors");
64 SCM lns = c->get_grob_property ("left-neighbors");
67 If this column doesn't have a proper neighbor, we should really
68 make it loose, but spacing it correctly is more than we can
71 (this happens in the following situation:
82 the column containing the clef is really loose, and should be
83 attached right to the first column, but that is a lot of work for
84 such a borderline case.)
87 if (!gh_pair_p (lns) || !gh_pair_p (rns))
90 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
91 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
93 if (!l_neighbor || !r_neighbor)
96 l_neighbor = l_neighbor->column_l();
97 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
99 if (l == l_neighbor && r == r_neighbor)
102 if (!l_neighbor || !r_neighbor)
106 Only declare loose if the bounds make a little sense. This means
107 some cases (two isolated, consecutive clef changes) won't be
108 nicely folded, but hey, then don't do that.
110 if ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
111 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor)))
118 If in doubt: we're not loose; the spacing engine should space for
119 it, risking suboptimal spacing.
121 (Otherwise, we might risk core dumps, and other weird stuff.)
128 Remove columns that are not tightly fitting from COLS. In the
129 removed columns, set 'between-cols to the columns where it is in
133 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
135 Link_array<Grob> newcols;
136 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
137 for (int i=0; i < cols->size (); i++)
139 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
141 newcols.push (cols->elem(i));
145 Grob *c = cols->elem(i);
146 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
148 SCM lns = c->get_grob_property ("left-neighbors");
149 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
151 SCM rns = c->get_grob_property ("right-neighbors");
152 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
155 Either object can be non existent, if the score ends
158 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
159 c->set_grob_property ("between-cols", gh_cons (lns,
163 Set distance constraints for loose columns
165 Drul_array<Grob*> next_door;
166 next_door[LEFT] =cols->elem (i - 1);
167 next_door[RIGHT] =cols->elem (i + 1);
169 Drul_array<Real> dists(0,0);
174 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
175 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
177 for (SCM s = lc->get_grob_property ("spacing-wishes");
178 gh_pair_p (s); s = gh_cdr (s))
180 Grob *sp = unsmob_grob (gh_car (s));
181 if (Note_spacing::left_column (sp) != lc
182 || Note_spacing::right_column (sp) != rc)
192 The note spacing should be taken from the musical
196 Real base = note_spacing (me, lc, rc, shortest, &dummy);
197 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
201 dists[d] = dists[d] >? space;
205 Real space, fixed_space;
206 Staff_spacing::get_spacing_params (sp,
207 &space, &fixed_space);
209 dists[d] = dists[d] >? fixed_space;
214 while (flip (&d) != LEFT);
217 r.distance_f_ = dists[LEFT] + dists[RIGHT];
218 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
219 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
233 Set neighboring columns determined by the spacing-wishes grob property.
236 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
238 for (int i=0; i < cols.size(); i++)
240 SCM right_neighbors = SCM_EOL;
241 int min_rank = 100000; // inf.
244 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
245 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
247 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
249 Item * lc = wish->column_l ();
250 Grob * right = Note_spacing::right_column (wish);
255 Item * rc = dynamic_cast<Item*> (right);
257 int right_rank = Paper_column::rank_i (rc);
258 int left_rank = Paper_column::rank_i (lc);
261 update the left column.
263 if (right_rank <= min_rank)
265 if (right_rank < min_rank)
266 right_neighbors =SCM_EOL;
268 min_rank = right_rank;
269 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
273 update the right column of the wish.
276 SCM left_neighs = rc->get_grob_property ("left-neighbors");
277 if (gh_pair_p (left_neighs)
278 && unsmob_grob (gh_car (left_neighs)))
280 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
281 maxrank = Paper_column::rank_i (it->column_l());
284 if (left_rank >= maxrank)
286 if (left_rank > maxrank)
287 left_neighs = SCM_EOL;
289 left_neighs = gh_cons (wish->self_scm (), left_neighs);
290 rc->set_grob_property ("left-neighbors", right_neighbors);
294 if (gh_pair_p (right_neighbors))
296 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
302 Set neighboring columns that have no left/right-neighbor set
303 yet. Only do breakable non-musical columns, and musical columns.
306 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
308 for (int i = 0; i < cols.size (); i++)
310 Item * it = dynamic_cast<Item*>(cols[i]);
311 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
314 // it->breakable || it->musical
317 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
319 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
320 if (!gh_pair_p (ln) && i )
322 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
325 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
326 if (!gh_pair_p (rn) && i < cols.size () - 1)
328 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
334 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
336 Spacing_spanner::set_springs (SCM smob)
338 Grob *me = unsmob_grob (smob);
340 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
342 set_explicit_neighbor_columns (all);
344 Rational global_shortest = find_shortest (all);
345 prune_loose_colunms (me, &all, global_shortest);
346 set_implicit_neighbor_columns (all);
350 for (int i = 1; i < all.size (); i++)
353 if (Item::breakable_b (sc))
355 Link_array<Grob> measure (all.slice (j, i+1));
356 do_measure (global_shortest, me, &measure);
361 return SCM_UNSPECIFIED;
366 We want the shortest note that is also "common" in the piece, so we
367 find the shortest in each measure, and take the most frequently
370 This probably gives weird effects with modern music, where every
371 note has a different duration, but hey, don't write that kind of
376 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
379 ascending in duration
381 Array<Rational> durations;
384 Rational shortest_in_measure;
385 shortest_in_measure.set_infinite (1);
387 for (int i =0 ; i < cols.size (); i++)
389 if (Paper_column::musical_b (cols[i]))
391 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
394 ignore grace notes for shortest notes.
396 if (when && when->grace_part_)
399 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
400 Moment this_shortest = *unsmob_moment (st);
401 assert (this_shortest.to_bool());
402 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
404 else if (!shortest_in_measure.infty_b()
405 && Item::breakable_b (cols[i]))
408 for (; j < durations.size(); j++)
410 if (durations[j] > shortest_in_measure)
412 counts.insert (1, j);
413 durations.insert (shortest_in_measure, j);
416 else if (durations[j] == shortest_in_measure)
423 if (durations.size() == j)
425 durations.push (shortest_in_measure);
429 shortest_in_measure.set_infinite(1);
435 for (int i =durations.size(); i--;)
437 if (counts[i] >= max_count)
440 max_count = counts[i];
443 // printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
447 TODO: 1/8 should be adjustable?
449 Rational d = Rational (1,8);
451 d = d <? durations[max_idx] ;
457 Generate spacing for a single measure. We used to have code that did
458 per-measure spacing. Now we have piecewise spacing. We should fix
459 this to support "spacing-regions": some regions have different notes
460 (different time sigs) than others, and should be spaced differently.
463 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
466 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
467 for (int i= 0; i < cols->size () - 1; i++)
469 Item * l = dynamic_cast<Item*> (cols->elem (i));
470 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
472 Paper_column * lc = dynamic_cast<Paper_column*> (l);
473 Paper_column * rc = dynamic_cast<Paper_column*> (r);
475 if (!Paper_column::musical_b (l))
477 breakable_column_spacing (me, l, r, shortest);
481 The case that the right part is broken as well is rather
482 rare, but it is possible, eg. with a single empty measure,
483 or if one staff finishes a tad earlier than the rest.
486 Item *lb = l->find_prebroken_piece (RIGHT);
487 Item *rb = r->find_prebroken_piece (LEFT);
490 breakable_column_spacing (me, lb,r, shortest);
493 breakable_column_spacing (me, l, rb, shortest);
495 breakable_column_spacing (me, lb, rb, shortest);
501 musical_column_spacing (me, lc, rc, headwid, shortest);
502 if (Item *rb = r->find_prebroken_piece (LEFT))
503 musical_column_spacing (me, lc, rb, headwid, shortest);
509 Generate the space between two musical columns LC and RC, given spacing parameters INCR and SHRTEST.
512 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
514 bool expand_only = false;
515 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
517 Real max_note_space = -infinity_f;
518 Real max_fixed_note_space = -infinity_f;
520 SCM seq = lc->get_grob_property ("right-neighbors");
523 We adjust the space following a note only if the next note
524 happens after the current note (this is set in the grob
525 property SPACING-SEQUENCE.
527 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
529 Grob * wish = unsmob_grob (gh_car (s));
531 Item *wish_rcol = Note_spacing::right_column (wish);
532 if (Note_spacing::left_column (wish) != lc
533 || (wish_rcol != rc && wish_rcol != rc->original_l_))
537 This is probably a waste of time in the case of polyphonic
539 if (Note_spacing::has_interface (wish))
544 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
545 max_note_space = max_note_space >? space;
546 max_fixed_note_space = max_fixed_note_space >? fixed;
551 if (max_note_space < 0)
553 max_note_space = base_note_space;
554 max_fixed_note_space = increment;
557 Spaceable_grob::add_spring (lc, rc, max_note_space, 1 / (max_note_space -max_fixed_note_space), expand_only);
561 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
562 Real * fixed, Real * space,
565 *fixed = l->extent (l, X_AXIS)[RIGHT] - r->extent (r, X_AXIS)[LEFT];
567 if (l->breakable_b (l) && r->breakable_b(r))
569 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
574 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
576 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
580 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
583 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
591 Read hints from L and generate springs.
594 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
596 Real max_fixed = -infinity_f;
597 Real max_space = -infinity_f;
599 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
602 for (SCM s = l->get_grob_property ("spacing-wishes");
603 gh_pair_p (s); s = gh_cdr (s))
605 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
607 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
614 column for the left one settings should be ok due automatic
618 assert (spacing_grob-> column_l () == l);
620 Staff_spacing::get_spacing_params (spacing_grob,
621 &space, &fixed_space);
622 if (space > max_space)
625 max_fixed = fixed_space;
632 if (isinf (max_space))
634 programming_error ("No pref spacing found");
640 if (l->break_status_dir() == RIGHT
641 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
643 /* Start of line: this space is not stretchable */
644 max_fixed = max_space;
648 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
649 works on all architectures.
652 Spaceable_grob::add_spring (l, r, max_space, 1/(max_space - max_fixed), false);
657 Get the measure wide ant for arithmetic spacing.
660 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
662 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
666 Rational ratio = d.main_part_ / shortest;
669 return (0.5 + 0.5 * double (ratio)) * k ;
675 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
676 OSU-CISRC-10/87-TR35, Department of Computer and Information Science,
677 The Ohio State University, 1987.
679 Real log = log_2 (shortest);
681 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
682 *expand_only = false;
684 return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
689 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
690 Moment shortest, bool * expand_only)
692 Moment shortest_playing_len = 0;
693 SCM s = lc->get_grob_property ("shortest-playing-duration");
695 if (unsmob_moment (s))
696 shortest_playing_len = *unsmob_moment (s);
698 if (! shortest_playing_len.to_bool ())
700 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
701 shortest_playing_len = 1;
704 Moment lwhen = Paper_column::when_mom (lc);
705 Moment rwhen = Paper_column::when_mom (rc);
707 Moment delta_t = rwhen - lwhen;
710 if (delta_t.main_part_ && !lwhen.grace_part_)
712 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
713 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
715 else if (delta_t.grace_part_)
718 TODO: figure out how to space grace notes.
720 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
722 Real grace_fact = 1.0;
723 SCM gf = me->get_grob_property ("grace-space-factor");
724 if (gh_number_p (gf))
725 grace_fact = gh_scm2double (gf);
736 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
737 " SPACE = arithmetic_multiplier * ( C + log2 (TIME) ))
738 The space taken by a note is determined by the formula
742 where TIME is the amount of time a note occupies. The value of C is
743 chosen such that the smallest space within a measure is
744 arithmetic_basicspace:
746 C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8))
748 The smallest space is the one following the shortest note in the
749 measure, or the space following a hypothetical 1/8 note. Typically
750 arithmetic_basicspace is set to a value so that the shortest note
751 takes about two noteheads of space (ie, is followed by a notehead of
755 2*quartwidth = arithmetic_multiplier * ( C + log2 (SHORTEST) ))
757 @{ using: C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8)) @}
758 @{ assuming: SHORTEST <= 1/8 @}
760 = arithmetic_multiplier *
761 ( arithmetic_basicspace - log2 (SHORTEST) + log2 (SHORTEST) )
763 = arithmetic_multiplier * arithmetic_basicspace
765 @{ choose: arithmetic_multiplier = 1.0*quartwidth (why?) @}
767 = quartwidth * arithmetic_basicspace
771 arithmetic_basicspace = 2/1 = 2
774 If you want to space your music wider, use something like:
776 arithmetic_basicspace = 4.;
779 "spacing-increment shortest-duration-space");