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);
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"));
670 Real incr = gh_scm2double (me->get_grob_property ("spacing-increment"));
675 We don't space really short notes using the log of the
676 duration, since it would disproportionally stretches the long
677 notes in a piece. In stead, we use geometric spacing with constant 0.5
680 This should probably be tunable, to use other base numbers.
682 In Mozart hrn3 by EB., we have 8th note = 3.9 mm (total), 16th note =
683 3.6 mm (total). head-width = 2.4, so we 1.2mm for 16th, 1.5
684 mm for 8th. (white space), suggesting that we use
686 (1.2 / 1.5)^{-log2(duration ratio)}
690 Rational ratio = d.main_part_ / shortest;
693 return ((k-1) + double (ratio)) * incr;
698 John S. Gourlay. ``Spacing a Line of Music,'' Technical
699 Report OSU-CISRC-10/87-TR35, Department of Computer and
700 Information Science, The Ohio State University, 1987.
702 Real log = log_2 (shortest);
704 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
705 *expand_only = false;
707 return (log_2 (compdur) + k) * incr;
712 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
713 Moment shortest, bool * expand_only)
715 Moment shortest_playing_len = 0;
716 SCM s = lc->get_grob_property ("shortest-playing-duration");
718 if (unsmob_moment (s))
719 shortest_playing_len = *unsmob_moment (s);
721 if (! shortest_playing_len.to_bool ())
723 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
724 shortest_playing_len = 1;
727 Moment lwhen = Paper_column::when_mom (lc);
728 Moment rwhen = Paper_column::when_mom (rc);
730 Moment delta_t = rwhen - lwhen;
734 In normal situations, the next column is at most
735 SHORTEST_PLAYING_LEN away. However chord-tremolos do funky faking stuff
736 with durations, invalidating this assumption. Here we kludge
737 around to get chord tremolos to behave properly.
740 shortest_playing_len = shortest_playing_len >? delta_t;
741 if (delta_t.main_part_ && !lwhen.grace_part_)
743 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
744 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
746 else if (delta_t.grace_part_)
749 TODO: figure out how to space grace notes.
751 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
753 Real grace_fact = 1.0;
754 SCM gf = me->get_grob_property ("grace-space-factor");
755 if (gh_number_p (gf))
756 grace_fact = gh_scm2double (gf);
767 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
769 The space taken by a note is dependent on its duration. Doubling a
770 duration adds spacing-increment to the space. The most common shortest
771 note gets shortest-duration-space. Notes that are even shorter are
772 spaced proportonial to their duration.
774 Typically, the increment is the width of a black note head. In a
775 piece with lots of 8th notes, and some 16th notes, the eighth note
776 gets 2 note heads width (i.e. the space following a note is 1 note
777 head width) A 16th note is followed by 0.5 note head width. The
778 quarter note is followed by 3 NHW, the half by 4 NHW, etc.
780 "grace-space-factor spacing-increment shortest-duration-space");