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-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 (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 ));
58 Return whether COL is fixed to its neighbors by some kind of spacing
62 loose_column (Grob *l, Grob *c, Grob *r)
64 SCM rns = c->get_grob_property ("right-neighbors");
65 SCM lns = c->get_grob_property ("left-neighbors");
68 If this column doesn't have a proper neighbor, we should really
69 make it loose, but spacing it correctly is more than we can
72 (this happens in the following situation:
83 the column containing the clef is really loose, and should be
84 attached right to the first column, but that is a lot of work for
85 such a borderline case.)
88 if (!gh_pair_p (lns) || !gh_pair_p (rns))
91 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
92 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
94 if (!l_neighbor || !r_neighbor)
97 l_neighbor = l_neighbor->column_l();
98 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
100 if (l == l_neighbor && r == r_neighbor)
103 if (!l_neighbor || !r_neighbor)
107 Only declare loose if the bounds make a little sense. This means
108 some cases (two isolated, consecutive clef changes) won't be
109 nicely folded, but hey, then don't do that.
111 if ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
112 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor)))
119 If in doubt: we're not loose; the spacing engine should space for
120 it, risking suboptimal spacing.
122 (Otherwise, we might risk core dumps, and other weird stuff.)
129 Remove columns that are not tightly fitting from COLS. In the
130 removed columns, set 'between-cols to the columns where it is in
134 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
136 Link_array<Grob> newcols;
137 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
138 for (int i=0; i < cols->size (); i++)
140 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
142 newcols.push (cols->elem(i));
146 Grob *c = cols->elem(i);
147 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
149 SCM lns = c->get_grob_property ("left-neighbors");
150 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
152 SCM rns = c->get_grob_property ("right-neighbors");
153 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
156 Either object can be non existent, if the score ends
159 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
160 c->set_grob_property ("between-cols", gh_cons (lns,
164 Set distance constraints for loose columns
166 Drul_array<Grob*> next_door;
167 next_door[LEFT] =cols->elem (i - 1);
168 next_door[RIGHT] =cols->elem (i + 1);
170 Drul_array<Real> dists(0,0);
175 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
176 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
178 for (SCM s = lc->get_grob_property ("spacing-wishes");
179 gh_pair_p (s); s = gh_cdr (s))
181 Grob *sp = unsmob_grob (gh_car (s));
182 if (Note_spacing::left_column (sp) != lc
183 || Note_spacing::right_column (sp) != rc)
193 The note spacing should be taken from the musical
197 Real base = note_spacing (me, lc, rc, shortest, &dummy);
198 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
202 dists[d] = dists[d] >? space;
206 Real space, fixed_space;
207 Staff_spacing::get_spacing_params (sp,
208 &space, &fixed_space);
210 dists[d] = dists[d] >? fixed_space;
215 while (flip (&d) != LEFT);
218 r.distance_f_ = dists[LEFT] + dists[RIGHT];
219 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
220 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
234 Set neighboring columns determined by the spacing-wishes grob property.
237 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
239 for (int i=0; i < cols.size(); i++)
241 SCM right_neighbors = SCM_EOL;
242 int min_rank = 100000; // inf.
245 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
246 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
248 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
250 Item * lc = wish->column_l ();
251 Grob * right = Note_spacing::right_column (wish);
256 Item * rc = dynamic_cast<Item*> (right);
258 int right_rank = Paper_column::rank_i (rc);
259 int left_rank = Paper_column::rank_i (lc);
262 update the left column.
264 if (right_rank <= min_rank)
266 if (right_rank < min_rank)
267 right_neighbors =SCM_EOL;
269 min_rank = right_rank;
270 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
274 update the right column of the wish.
277 SCM left_neighs = rc->get_grob_property ("left-neighbors");
278 if (gh_pair_p (left_neighs)
279 && unsmob_grob (gh_car (left_neighs)))
281 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
282 maxrank = Paper_column::rank_i (it->column_l());
285 if (left_rank >= maxrank)
287 if (left_rank > maxrank)
288 left_neighs = SCM_EOL;
290 left_neighs = gh_cons (wish->self_scm (), left_neighs);
291 rc->set_grob_property ("left-neighbors", right_neighbors);
295 if (gh_pair_p (right_neighbors))
297 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
303 Set neighboring columns that have no left/right-neighbor set
304 yet. Only do breakable non-musical columns, and musical columns.
307 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
309 for (int i = 0; i < cols.size (); i++)
311 Item * it = dynamic_cast<Item*>(cols[i]);
312 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
315 // it->breakable || it->musical
318 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
320 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
321 if (!gh_pair_p (ln) && i )
323 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
326 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
327 if (!gh_pair_p (rn) && i < cols.size () - 1)
329 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
335 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
337 Spacing_spanner::set_springs (SCM smob)
339 Grob *me = unsmob_grob (smob);
341 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
343 set_explicit_neighbor_columns (all);
345 Rational global_shortest = find_shortest (all);
346 prune_loose_colunms (me, &all, global_shortest);
347 set_implicit_neighbor_columns (all);
351 for (int i = 1; i < all.size (); i++)
354 if (Item::breakable_b (sc))
356 Link_array<Grob> measure (all.slice (j, i+1));
357 do_measure (global_shortest, me, &measure);
362 return SCM_UNSPECIFIED;
367 We want the shortest note that is also "common" in the piece, so we
368 find the shortest in each measure, and take the most frequently
371 This probably gives weird effects with modern music, where every
372 note has a different duration, but hey, don't write that kind of
377 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
380 ascending in duration
382 Array<Rational> durations;
385 Rational shortest_in_measure;
386 shortest_in_measure.set_infinite (1);
388 for (int i =0 ; i < cols.size (); i++)
390 if (Paper_column::musical_b (cols[i]))
392 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
395 ignore grace notes for shortest notes.
397 if (when && when->grace_part_)
400 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
401 Moment this_shortest = *unsmob_moment (st);
402 assert (this_shortest.to_bool());
403 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
405 else if (!shortest_in_measure.infty_b()
406 && Item::breakable_b (cols[i]))
409 for (; j < durations.size(); j++)
411 if (durations[j] > shortest_in_measure)
413 counts.insert (1, j);
414 durations.insert (shortest_in_measure, j);
417 else if (durations[j] == shortest_in_measure)
424 if (durations.size() == j)
426 durations.push (shortest_in_measure);
430 shortest_in_measure.set_infinite(1);
436 for (int i =durations.size(); i--;)
438 if (counts[i] >= max_count)
441 max_count = counts[i];
444 // printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
448 TODO: 1/8 should be adjustable?
450 Rational d = Rational (1,8);
452 d = d <? durations[max_idx] ;
458 Generate spacing for a single measure. We used to have code that did
459 per-measure spacing. Now we have piecewise spacing. We should fix
460 this to support "spacing-regions": some regions have different notes
461 (different time sigs) than others, and should be spaced differently.
464 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
467 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
468 for (int i= 0; i < cols->size () - 1; i++)
470 Item * l = dynamic_cast<Item*> (cols->elem (i));
471 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
473 Paper_column * lc = dynamic_cast<Paper_column*> (l);
474 Paper_column * rc = dynamic_cast<Paper_column*> (r);
476 if (!Paper_column::musical_b (l))
478 breakable_column_spacing (me, l, r, shortest);
482 The case that the right part is broken as well is rather
483 rare, but it is possible, eg. with a single empty measure,
484 or if one staff finishes a tad earlier than the rest.
487 Item *lb = l->find_prebroken_piece (RIGHT);
488 Item *rb = r->find_prebroken_piece (LEFT);
491 breakable_column_spacing (me, lb,r, shortest);
494 breakable_column_spacing (me, l, rb, shortest);
496 breakable_column_spacing (me, lb, rb, shortest);
502 musical_column_spacing (me, lc, rc, headwid, shortest);
503 if (Item *rb = r->find_prebroken_piece (LEFT))
504 musical_column_spacing (me, lc, rb, headwid, shortest);
510 Generate the space between two musical columns LC and RC, given spacing parameters INCR and SHRTEST.
513 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
515 bool expand_only = false;
516 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
518 Real max_note_space = -infinity_f;
519 Real max_fixed_note_space = -infinity_f;
521 SCM seq = lc->get_grob_property ("right-neighbors");
524 We adjust the space following a note only if the next note
525 happens after the current note (this is set in the grob
526 property SPACING-SEQUENCE.
528 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
530 Grob * wish = unsmob_grob (gh_car (s));
532 Item *wish_rcol = Note_spacing::right_column (wish);
533 if (Note_spacing::left_column (wish) != lc
534 || (wish_rcol != rc && wish_rcol != rc->original_l_))
538 This is probably a waste of time in the case of polyphonic
540 if (Note_spacing::has_interface (wish))
545 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
546 max_note_space = max_note_space >? space;
547 max_fixed_note_space = max_fixed_note_space >? fixed;
552 if (max_note_space < 0)
554 max_note_space = base_note_space;
555 max_fixed_note_space = increment;
558 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
559 Real strength = (ragged) ? 1.0 : 1 / (max_note_space - max_fixed_note_space);
560 Real distance = (ragged) ? max_fixed_note_space : max_note_space;
561 Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
565 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
566 Real * fixed, Real * space,
569 *fixed = l->extent (l, X_AXIS)[RIGHT] - r->extent (r, X_AXIS)[LEFT];
571 if (l->breakable_b (l) && r->breakable_b(r))
573 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
578 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
580 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
584 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
587 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
595 Read hints from L and generate springs.
598 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
600 Real max_fixed = -infinity_f;
601 Real max_space = -infinity_f;
603 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
606 for (SCM s = l->get_grob_property ("spacing-wishes");
607 gh_pair_p (s); s = gh_cdr (s))
609 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
611 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
618 column for the left one settings should be ok due automatic
622 assert (spacing_grob-> column_l () == l);
624 Staff_spacing::get_spacing_params (spacing_grob,
625 &space, &fixed_space);
626 if (space > max_space)
629 max_fixed = fixed_space;
636 if (isinf (max_space))
638 programming_error ("No pref spacing found");
644 if (l->break_status_dir() == RIGHT
645 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
647 /* Start of line: this space is not stretchable */
648 max_fixed = max_space;
652 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
653 works on all architectures.
656 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
657 Real strength = (ragged) ? 1.0 : 1 / (max_space - max_fixed);
658 Real distance = (ragged) ? max_fixed : max_space;
659 Spaceable_grob::add_spring (l, r, distance, strength, false);
664 Get the measure wide ant for arithmetic spacing.
667 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
669 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
673 Rational ratio = d.main_part_ / shortest;
676 return (0.5 + 0.5 * double (ratio)) * k ;
682 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
683 OSU-CISRC-10/87-TR35, Department of Computer and Information Science,
684 The Ohio State University, 1987.
686 Real log = log_2 (shortest);
688 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
689 *expand_only = false;
691 return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
696 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
697 Moment shortest, bool * expand_only)
699 Moment shortest_playing_len = 0;
700 SCM s = lc->get_grob_property ("shortest-playing-duration");
702 if (unsmob_moment (s))
703 shortest_playing_len = *unsmob_moment (s);
705 if (! shortest_playing_len.to_bool ())
707 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
708 shortest_playing_len = 1;
711 Moment lwhen = Paper_column::when_mom (lc);
712 Moment rwhen = Paper_column::when_mom (rc);
714 Moment delta_t = rwhen - lwhen;
717 if (delta_t.main_part_ && !lwhen.grace_part_)
719 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
720 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
722 else if (delta_t.grace_part_)
725 TODO: figure out how to space grace notes.
727 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
729 Real grace_fact = 1.0;
730 SCM gf = me->get_grob_property ("grace-space-factor");
731 if (gh_number_p (gf))
732 grace_fact = gh_scm2double (gf);
743 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
744 " SPACE = arithmetic_multiplier * ( C + log2 (TIME) ))
745 The space taken by a note is determined by the formula
749 where TIME is the amount of time a note occupies. The value of C is
750 chosen such that the smallest space within a measure is
751 arithmetic_basicspace:
753 C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8))
755 The smallest space is the one following the shortest note in the
756 measure, or the space following a hypothetical 1/8 note. Typically
757 arithmetic_basicspace is set to a value so that the shortest note
758 takes about two noteheads of space (ie, is followed by a notehead of
762 2*quartwidth = arithmetic_multiplier * ( C + log2 (SHORTEST) ))
764 @{ using: C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8)) @}
765 @{ assuming: SHORTEST <= 1/8 @}
767 = arithmetic_multiplier *
768 ( arithmetic_basicspace - log2 (SHORTEST) + log2 (SHORTEST) )
770 = arithmetic_multiplier * arithmetic_basicspace
772 @{ choose: arithmetic_multiplier = 1.0*quartwidth (why?) @}
774 = quartwidth * arithmetic_basicspace
778 arithmetic_basicspace = 2/1 = 2
781 If you want to space your music wider, use something like:
783 arithmetic_basicspace = 4.;
786 "spacing-increment shortest-duration-space");