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>
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 ));
55 static bool has_interface (Grob*);
59 Return whether COL is fixed to its neighbors by some kind of spacing
63 loose_column (Grob *l, Grob *c, Grob *r)
65 SCM rns = c->get_grob_property ("right-neighbors");
66 SCM lns = c->get_grob_property ("left-neighbors");
69 If this column doesn't have a proper neighbor, we should really
70 make it loose, but spacing it correctly is more than we can
73 (this happens in the following situation:
84 the column containing the clef is really loose, and should be
85 attached right to the first column, but that is a lot of work for
86 such a borderline case.)
89 if (!gh_pair_p (lns) || !gh_pair_p (rns))
92 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
93 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
95 if (!l_neighbor || !r_neighbor)
98 l_neighbor = l_neighbor->column_l();
99 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
101 if (l == l_neighbor && r == r_neighbor)
104 if (!l_neighbor || !r_neighbor)
108 Only declare loose if the bounds make a little sense. This means
109 some cases (two isolated, consecutive clef changes) won't be
110 nicely folded, but hey, then don't do that.
112 if ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
113 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor)))
120 If in doubt: we're not loose; the spacing engine should space for
121 it, risking suboptimal spacing.
123 (Otherwise, we might risk core dumps, and other weird stuff.)
130 Remove columns that are not tightly fitting from COLS. In the
131 removed columns, set 'between-cols to the columns where it is in
135 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
137 Link_array<Grob> newcols;
138 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
139 for (int i=0; i < cols->size (); i++)
141 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
143 newcols.push (cols->elem(i));
147 Grob *c = cols->elem(i);
148 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
150 SCM lns = c->get_grob_property ("left-neighbors");
151 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
153 SCM rns = c->get_grob_property ("right-neighbors");
154 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
157 Either object can be non existent, if the score ends
160 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
161 c->set_grob_property ("between-cols", gh_cons (lns,
165 Set distance constraints for loose columns
167 Drul_array<Grob*> next_door;
168 next_door[LEFT] =cols->elem (i - 1);
169 next_door[RIGHT] =cols->elem (i + 1);
171 Drul_array<Real> dists(0,0);
176 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
177 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
179 for (SCM s = lc->get_grob_property ("spacing-wishes");
180 gh_pair_p (s); s = gh_cdr (s))
182 Grob *sp = unsmob_grob (gh_car (s));
183 if (Note_spacing::left_column (sp) != lc
184 || Note_spacing::right_column (sp) != rc)
194 The note spacing should be taken from the musical
198 Real base = note_spacing (me, lc, rc, shortest, &dummy);
199 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
203 dists[d] = dists[d] >? space;
207 Real space, fixed_space;
208 Staff_spacing::get_spacing_params (sp,
209 &space, &fixed_space);
211 dists[d] = dists[d] >? fixed_space;
216 while (flip (&d) != LEFT);
219 r.distance_f_ = dists[LEFT] + dists[RIGHT];
220 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
221 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
235 Set neighboring columns determined by the spacing-wishes grob property.
238 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
240 for (int i=0; i < cols.size(); i++)
242 SCM right_neighbors = SCM_EOL;
243 int min_rank = 100000; // inf.
246 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
247 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
249 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
251 Item * lc = wish->column_l ();
252 Grob * right = Note_spacing::right_column (wish);
257 Item * rc = dynamic_cast<Item*> (right);
259 int right_rank = Paper_column::rank_i (rc);
260 int left_rank = Paper_column::rank_i (lc);
263 update the left column.
265 if (right_rank <= min_rank)
267 if (right_rank < min_rank)
268 right_neighbors =SCM_EOL;
270 min_rank = right_rank;
271 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
275 update the right column of the wish.
278 SCM left_neighs = rc->get_grob_property ("left-neighbors");
279 if (gh_pair_p (left_neighs)
280 && unsmob_grob (gh_car (left_neighs)))
282 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
283 maxrank = Paper_column::rank_i (it->column_l());
286 if (left_rank >= maxrank)
288 if (left_rank > maxrank)
289 left_neighs = SCM_EOL;
291 left_neighs = gh_cons (wish->self_scm (), left_neighs);
292 rc->set_grob_property ("left-neighbors", right_neighbors);
296 if (gh_pair_p (right_neighbors))
298 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
304 Set neighboring columns that have no left/right-neighbor set
305 yet. Only do breakable non-musical columns, and musical columns.
308 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
310 for (int i = 0; i < cols.size (); i++)
312 Item * it = dynamic_cast<Item*>(cols[i]);
313 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
316 // it->breakable || it->musical
319 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
321 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
322 if (!gh_pair_p (ln) && i )
324 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
327 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
328 if (!gh_pair_p (rn) && i < cols.size () - 1)
330 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
336 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
338 Spacing_spanner::set_springs (SCM smob)
340 Grob *me = unsmob_grob (smob);
342 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
344 set_explicit_neighbor_columns (all);
346 Rational global_shortest = find_shortest (all);
347 prune_loose_colunms (me, &all, global_shortest);
348 set_implicit_neighbor_columns (all);
352 for (int i = 1; i < all.size (); i++)
355 if (Item::breakable_b (sc))
357 Link_array<Grob> measure (all.slice (j, i+1));
358 do_measure (global_shortest, me, &measure);
363 return SCM_UNSPECIFIED;
368 We want the shortest note that is also "common" in the piece, so we
369 find the shortest in each measure, and take the most frequently
372 This probably gives weird effects with modern music, where every
373 note has a different duration, but hey, don't write that kind of
378 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
381 ascending in duration
383 Array<Rational> durations;
386 Rational shortest_in_measure;
387 shortest_in_measure.set_infinite (1);
389 for (int i =0 ; i < cols.size (); i++)
391 if (Paper_column::musical_b (cols[i]))
393 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
396 ignore grace notes for shortest notes.
398 if (when && when->grace_part_)
401 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
402 Moment this_shortest = *unsmob_moment (st);
403 assert (this_shortest.to_bool());
404 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
406 else if (!shortest_in_measure.infty_b()
407 && Item::breakable_b (cols[i]))
410 for (; j < durations.size(); j++)
412 if (durations[j] > shortest_in_measure)
414 counts.insert (1, j);
415 durations.insert (shortest_in_measure, j);
418 else if (durations[j] == shortest_in_measure)
425 if (durations.size() == j)
427 durations.push (shortest_in_measure);
431 shortest_in_measure.set_infinite(1);
437 for (int i =durations.size(); i--;)
439 if (counts[i] >= max_count)
442 max_count = counts[i];
445 // printf ("duration %d/%d, count %d\n", durations[i].num (), durations[i].den (), counts[i]);
449 TODO: 1/8 should be adjustable?
451 Rational d = Rational (1,8);
453 d = d <? durations[max_idx] ;
459 Generate spacing for a single measure. We used to have code that did
460 per-measure spacing. Now we have piecewise spacing. We should fix
461 this to support "spacing-regions": some regions have different notes
462 (different time sigs) than others, and should be spaced differently.
465 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
468 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
469 for (int i= 0; i < cols->size () - 1; i++)
471 Item * l = dynamic_cast<Item*> (cols->elem (i));
472 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
474 Paper_column * lc = dynamic_cast<Paper_column*> (l);
475 Paper_column * rc = dynamic_cast<Paper_column*> (r);
477 if (!Paper_column::musical_b (l))
479 breakable_column_spacing (me, l, r, shortest);
483 The case that the right part is broken as well is rather
484 rare, but it is possible, eg. with a single empty measure,
485 or if one staff finishes a tad earlier than the rest.
488 Item *lb = l->find_prebroken_piece (RIGHT);
489 Item *rb = r->find_prebroken_piece (LEFT);
492 breakable_column_spacing (me, lb,r, shortest);
495 breakable_column_spacing (me, l, rb, shortest);
497 breakable_column_spacing (me, lb, rb, shortest);
503 musical_column_spacing (me, lc, rc, headwid, shortest);
504 if (Item *rb = r->find_prebroken_piece (LEFT))
505 musical_column_spacing (me, lc, rb, headwid, shortest);
511 Generate the space between two musical columns LC and RC, given spacing parameters INCR and SHORTEST.
514 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
516 bool expand_only = false;
517 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
519 Real max_note_space = -infinity_f;
520 Real max_fixed_note_space = -infinity_f;
522 SCM seq = lc->get_grob_property ("right-neighbors");
525 We adjust the space following a note only if the next note
526 happens after the current note (this is set in the grob
527 property SPACING-SEQUENCE.
529 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
531 Grob * wish = unsmob_grob (gh_car (s));
533 Item *wish_rcol = Note_spacing::right_column (wish);
534 if (Note_spacing::left_column (wish) != lc
535 || (wish_rcol != rc && wish_rcol != rc->original_l_))
539 This is probably a waste of time in the case of polyphonic
541 if (Note_spacing::has_interface (wish))
546 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
547 max_note_space = max_note_space >? space;
548 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);
563 Spaceable_grob::add_spring (lc, rc, distance, strength, false);
567 Spacing_spanner::standard_breakable_column_spacing (Grob * me, Item*l, Item*r,
568 Real * fixed, Real * space,
571 *fixed = l->extent (l, X_AXIS)[RIGHT] - r->extent (r, X_AXIS)[LEFT];
573 if (l->breakable_b (l) && r->breakable_b(r))
575 Moment *dt = unsmob_moment (l->get_grob_property ("measure-length"));
580 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
582 *space = *fixed + incr * double (mlen.main_part_ / shortest.main_part_) * 0.8;
586 Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
589 *space = *fixed + get_duration_space (me, dt, shortest.main_part_, &dummy);
597 Read hints from L and generate springs.
600 Spacing_spanner::breakable_column_spacing (Grob*me, Item* l, Item *r,Moment shortest)
602 Real max_fixed = -infinity_f;
603 Real max_space = -infinity_f;
605 standard_breakable_column_spacing (me, l, r, &max_fixed, &max_space ,
608 for (SCM s = l->get_grob_property ("spacing-wishes");
609 gh_pair_p (s); s = gh_cdr (s))
611 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
613 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
620 column for the left one settings should be ok due automatic
624 assert (spacing_grob-> column_l () == l);
626 Staff_spacing::get_spacing_params (spacing_grob,
627 &space, &fixed_space);
628 if (space > max_space)
631 max_fixed = fixed_space;
638 if (isinf (max_space))
640 programming_error ("No pref spacing found");
646 if (l->break_status_dir() == RIGHT
647 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
649 /* Start of line: this space is not stretchable */
650 max_fixed = max_space;
654 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
655 works on all architectures.
658 bool ragged = to_boolean (me->paper_l ()->get_scmvar ("raggedright"));
659 Real strength = (ragged) ? 1.0 : 1 / (max_space - max_fixed);
660 Real distance = (ragged) ? max_fixed : max_space;
661 Spaceable_grob::add_spring (l, r, distance, strength, false);
666 Get the measure wide ant for arithmetic spacing.
669 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
671 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
672 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
677 We don't space really short notes using the log of the
678 duration, since it would disproportionally stretches the long
679 notes in a piece. In stead, we use geometric spacing with constant 0.5
682 This should probably be tunable, to use other base numbers.
684 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
685 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
686 mm for 8th. (white space), suggesting that we use
688 (1.2 / 1.5)^{-log2(duration ratio)}
692 Rational ratio = d.main_part_ / shortest;
695 return ((k-1) + double (ratio)) * incr;
700 John S. Gourlay. ``Spacing a Line of Music,'' Technical
701 Report OSU-CISRC-10/87-TR35, Department of Computer and
702 Information Science, The Ohio State University, 1987.
704 Real log = log_2 (shortest);
706 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
707 *expand_only = false;
709 return (log_2 (compdur) + k) * incr;
714 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
715 Moment shortest, bool * expand_only)
717 Moment shortest_playing_len = 0;
718 SCM s = lc->get_grob_property ("shortest-playing-duration");
720 if (unsmob_moment (s))
721 shortest_playing_len = *unsmob_moment (s);
723 if (! shortest_playing_len.to_bool ())
725 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
726 shortest_playing_len = 1;
729 Moment lwhen = Paper_column::when_mom (lc);
730 Moment rwhen = Paper_column::when_mom (rc);
732 Moment delta_t = rwhen - lwhen;
736 In normal situations, the next column is at most
737 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
738 with durations, invalidating this assumption. Here we kludge
739 around to get chord tremolos to behave properly.
742 shortest_playing_len = shortest_playing_len >? delta_t;
743 if (delta_t.main_part_ && !lwhen.grace_part_)
745 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
746 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
748 else if (delta_t.grace_part_)
751 TODO: figure out how to space grace notes.
753 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
755 Real grace_fact = 1.0;
756 SCM gf = me->get_grob_property ("grace-space-factor");
757 if (gh_number_p (gf))
758 grace_fact = gh_scm2double (gf);
769 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
771 The space taken by a note is dependent on its duration. Doubling a
772 duration adds spacing-increment to the space. The most common shortest
773 note gets shortest-duration-space. Notes that are even shorter are
774 spaced proportonial to their duration.
776 Typically, the increment is the width of a black note head. In a
777 piece with lots of 8th notes, and some 16th notes, the eighth note
778 gets 2 note heads width (i.e. the space following a note is 1 note
779 head width) A 16th note is followed by 0.5 note head width. The
780 quarter note is followed by 3 NHW, the half by 4 NHW, etc.
782 "grace-space-factor spacing-increment shortest-duration-space");