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 ("duration %d/%d, count %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;
551 if (max_note_space < 0)
553 max_note_space = base_note_space;
554 max_fixed_note_space = increment;
557 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
558 Real strength = (ragged) ? 1.0 : 1 / (max_note_space - max_fixed_note_space);
559 Real distance = (ragged) ? max_fixed_note_space : max_note_space;
560 Spaceable_grob::add_spring (lc, rc, distance, strength, expand_only);
564 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
565 Real * fixed, Real * space,
568 *fixed = l->extent (l, X_AXIS)[RIGHT] - r->extent (r, X_AXIS)[LEFT];
570 if (l->breakable_b (l) && r->breakable_b(r))
572 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
577 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
579 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
583 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
586 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
594 Read hints from L and generate springs.
597 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
599 Real max_fixed = -infinity_f;
600 Real max_space = -infinity_f;
602 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
605 for (SCM s = l->get_grob_property ("spacing-wishes");
606 gh_pair_p (s); s = gh_cdr (s))
608 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
610 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
617 column for the left one settings should be ok due automatic
621 assert (spacing_grob-> column_l () == l);
623 Staff_spacing::get_spacing_params (spacing_grob,
624 &space, &fixed_space);
625 if (space > max_space)
628 max_fixed = fixed_space;
635 if (isinf (max_space))
637 programming_error ("No pref spacing found");
643 if (l->break_status_dir() == RIGHT
644 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
646 /* Start of line: this space is not stretchable */
647 max_fixed = max_space;
651 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
652 works on all architectures.
655 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
656 Real strength = (ragged) ? 1.0 : 1 / (max_space - max_fixed);
657 Real distance = (ragged) ? max_fixed : max_space;
658 Spaceable_grob::add_spring (l, r, distance, strength, false);
663 Get the measure wide ant for arithmetic spacing.
666 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
668 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
669 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
674 We don't space really short notes using the log of the
675 duration, since it would disproportionally stretches the long
676 notes in a piece. In stead, we use geometric spacing with constant 0.5
679 This should probably be tunable, to use other base numbers.
681 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
682 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
683 mm for 8th. (white space), suggesting that we use
685 (1.2 / 1.5)^{-log2(duration ratio)}
689 Rational ratio = d.main_part_ / shortest;
692 return ((k-1) + double (ratio)) * incr;
697 John S. Gourlay. ``Spacing a Line of Music,'' Technical
698 Report OSU-CISRC-10/87-TR35, Department of Computer and
699 Information Science, The Ohio State University, 1987.
701 Real log = log_2 (shortest);
703 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
704 *expand_only = false;
706 return (log_2 (compdur) + k) * incr;
711 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
712 Moment shortest, bool * expand_only)
714 Moment shortest_playing_len = 0;
715 SCM s = lc->get_grob_property ("shortest-playing-duration");
717 if (unsmob_moment (s))
718 shortest_playing_len = *unsmob_moment (s);
720 if (! shortest_playing_len.to_bool ())
722 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
723 shortest_playing_len = 1;
726 Moment lwhen = Paper_column::when_mom (lc);
727 Moment rwhen = Paper_column::when_mom (rc);
729 Moment delta_t = rwhen - lwhen;
732 if (delta_t.main_part_ && !lwhen.grace_part_)
734 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
735 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
737 else if (delta_t.grace_part_)
740 TODO: figure out how to space grace notes.
742 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
744 Real grace_fact = 1.0;
745 SCM gf = me->get_grob_property ("grace-space-factor");
746 if (gh_number_p (gf))
747 grace_fact = gh_scm2double (gf);
758 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
760 The space taken by a note is dependent on its duration. Doubling a
761 duration adds spacing-increment to the space. The most common shortest
762 note gets shortest-duration-space. Notes that are even shorter are
763 spaced proportonial to their duration.
765 Typically, the increment is the width of a black note head. In a
766 piece with lots of 8th notes, and some 16th notes, the eighth note
767 gets 2 note heads width (i.e. the space following a note is 1 note
768 head width) A 16th note is followed by 0.5 note head width. The
769 quarter note is followed by 3 NHW, the half by 4 NHW, etc.
771 "spacing-increment shortest-duration-space");