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 Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
38 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
39 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
40 static Rational find_shortest (Link_array<Grob> const &);
41 static void breakable_column_spacing (Item* l, Item *r);
42 static void find_loose_columns () {}
43 static void prune_loose_colunms (Grob*,Link_array<Grob> *cols, Rational);
44 static void find_loose_columns (Link_array<Grob> cols);
45 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
46 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
47 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
48 static void musical_column_spacing (Grob*,Item*,Item*, Real, Rational);
49 DECLARE_SCHEME_CALLBACK (set_springs, (SCM ));
53 Return whether COL is fixed to its neighbors by some kind of spacing
57 loose_column (Grob *l, Grob *c, Grob *r)
59 SCM rns = c->get_grob_property ("right-neighbors");
60 SCM lns = c->get_grob_property ("left-neighbors");
63 If this column doesn't have a proper neighbor, we should really
64 make it loose, but spacing it correctly is more than we can
67 (this happens in the following situation:
78 the column containing the clef is really loose, and should be
79 attached right to the first column, but that is a lot of work for
80 such a borderline case.)
83 if (!gh_pair_p (lns) || !gh_pair_p (rns))
86 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
87 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
89 if (!l_neighbor || !r_neighbor)
92 l_neighbor = l_neighbor->column_l();
93 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
95 if (l == l_neighbor && r == r_neighbor)
98 if (!l_neighbor || !r_neighbor)
102 Only declare loose if the bounds make a little sense. This means
103 some cases (two isolated, consecutive clef changes) won't be
104 nicely folded, but hey, then don't do that.
106 if ((Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
107 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor)))
114 If in doubt: we're not loose; the spacing engine should space for
115 it, risking suboptimal spacing.
117 (Otherwise, we might risk core dumps, and other weird stuff.)
124 Remove columns that are not tightly fitting from COLS. In the
125 removed columns, set 'between-cols to the columns where it is in
129 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
131 Link_array<Grob> newcols;
132 Real increment = gh_scm2double (me->get_grob_property ("spacing-increment"));
133 for (int i=0; i < cols->size (); i++)
135 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
137 newcols.push (cols->elem(i));
141 Grob *c = cols->elem(i);
142 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
144 SCM lns = c->get_grob_property ("left-neighbors");
145 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
147 SCM rns = c->get_grob_property ("right-neighbors");
148 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
151 Either object can be non existent, if the score ends
154 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
155 c->set_grob_property ("between-cols", gh_cons (lns,
159 Set distance constraints for loose columns
161 Drul_array<Grob*> next_door;
162 next_door[LEFT] =cols->elem (i - 1);
163 next_door[RIGHT] =cols->elem (i + 1);
165 Drul_array<Real> dists(0,0);
170 Item *lc = dynamic_cast<Item*> ((d == LEFT) ? next_door[LEFT] : c);
171 Item *rc = dynamic_cast<Item*> (d == LEFT ? c : next_door[RIGHT]);
173 for (SCM s = lc->get_grob_property ("spacing-wishes");
174 gh_pair_p (s); s = gh_cdr (s))
176 Grob *sp = unsmob_grob (gh_car (s));
177 if (Note_spacing::left_column (sp) != lc
178 || Note_spacing::right_column (sp) != rc)
184 Real base = note_spacing (me, lc, rc, shortest, &expand_only);
185 Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
188 dists[d] = dists[d] >? space;
191 while (flip (&d) != LEFT);
194 r.distance_f_ = dists[LEFT] + dists[RIGHT];
195 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
196 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
210 Set neighboring columns determined by the spacing-wishes grob property.
213 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
215 for (int i=0; i < cols.size(); i++)
217 SCM right_neighbors = SCM_EOL;
218 int min_rank = 100000; // inf.
221 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
222 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
224 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
226 Item * lc = wish->column_l ();
227 Grob * right = Note_spacing::right_column (wish);
232 Item * rc = dynamic_cast<Item*> (right);
234 int right_rank = Paper_column::rank_i (rc);
235 int left_rank = Paper_column::rank_i (lc);
238 update the left column.
240 if (right_rank <= min_rank)
242 if (right_rank < min_rank)
243 right_neighbors =SCM_EOL;
245 min_rank = right_rank;
246 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
250 update the right column of the wish.
253 SCM left_neighs = rc->get_grob_property ("left-neighbors");
254 if (gh_pair_p (left_neighs)
255 && unsmob_grob (gh_car (left_neighs)))
257 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
258 maxrank = Paper_column::rank_i (it->column_l());
261 if (left_rank >= maxrank)
263 if (left_rank > maxrank)
264 left_neighs = SCM_EOL;
266 left_neighs = gh_cons (wish->self_scm (), left_neighs);
267 rc->set_grob_property ("left-neighbors", right_neighbors);
271 if (gh_pair_p (right_neighbors))
273 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
279 Set neighboring columns that have no left/right-neighbor set
280 yet. Only do breakable non-musical columns, and musical columns.
283 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
285 for (int i = 0; i < cols.size (); i++)
287 Item * it = dynamic_cast<Item*>(cols[i]);
288 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
291 // it->breakable || it->musical
294 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
296 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
297 if (!gh_pair_p (ln) && i )
299 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
302 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
303 if (!gh_pair_p (rn) && i < cols.size () - 1)
305 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
311 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
313 Spacing_spanner::set_springs (SCM smob)
315 Grob *me = unsmob_grob (smob);
317 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
319 set_explicit_neighbor_columns (all);
321 Rational global_shortest = find_shortest (all);
322 prune_loose_colunms (me, &all, global_shortest);
323 set_implicit_neighbor_columns (all);
327 for (int i = 1; i < all.size (); i++)
330 if (Item::breakable_b (sc))
332 Link_array<Grob> measure (all.slice (j, i+1));
333 do_measure (global_shortest, me, &measure);
338 return SCM_UNSPECIFIED;
343 We want the shortest note that is also "common" in the piece, so we
344 find the shortest in each measure, and take the most frequently
347 This probably gives weird effects with modern music, where every
348 note has a different duration, but hey, don't write that kind of
353 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
356 ascending in duration
358 Array<Rational> durations;
361 Rational shortest_in_measure;
362 shortest_in_measure.set_infinite (1);
364 for (int i =0 ; i < cols.size (); i++)
366 if (Paper_column::musical_b (cols[i]))
368 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
371 ignore grace notes for shortest notes.
373 if (when && when->grace_part_)
376 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
377 Moment this_shortest = *unsmob_moment (st);
378 assert (this_shortest.to_bool());
379 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
381 else if (!shortest_in_measure.infty_b()
382 && Item::breakable_b (cols[i]))
385 for (; j < durations.size(); j++)
387 if (durations[j] > shortest_in_measure)
389 counts.insert (1, j);
390 durations.insert (shortest_in_measure, j);
393 else if (durations[j] == shortest_in_measure)
400 if (durations.size() == j)
402 durations.push (shortest_in_measure);
406 shortest_in_measure.set_infinite(1);
412 for (int i =durations.size(); i--;)
414 if (counts[i] >= max_count)
417 max_count = counts[i];
420 // printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
424 TODO: 1/8 should be adjustable?
426 Rational d = Rational (1,8);
428 d = d <? durations[max_idx] ;
434 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
437 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
438 for (int i= 0; i < cols->size () - 1; i++)
440 Item * l = dynamic_cast<Item*> (cols->elem (i));
441 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
443 Paper_column * lc = dynamic_cast<Paper_column*> (l);
444 Paper_column * rc = dynamic_cast<Paper_column*> (r);
446 if (!Paper_column::musical_b (l))
448 breakable_column_spacing (l, r);
452 The case that the right part is broken as well is rather
453 rare, but it is possible, eg. with a single empty measure,
454 or if one staff finishes a tad earlier than the rest.
457 Item *lb = l->find_prebroken_piece (RIGHT);
458 Item *rb = r->find_prebroken_piece (LEFT);
461 breakable_column_spacing (lb,r);
464 breakable_column_spacing (l, rb);
466 breakable_column_spacing (lb, rb);
472 musical_column_spacing (me, lc, rc, headwid, shortest);
473 if (Item *rb = r->find_prebroken_piece (LEFT))
474 musical_column_spacing (me, lc, rb, headwid, shortest);
479 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
481 bool expand_only = false;
482 Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
484 Real max_note_space = -infinity_f;
485 Real max_fixed_note_space = -infinity_f;
487 SCM seq = lc->get_grob_property ("right-neighbors");
490 We adjust the space following a note only if the next note
491 happens after the current note (this is set in the grob
492 property SPACING-SEQUENCE.
494 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
496 Grob * wish = unsmob_grob (gh_car (s));
498 Item *wish_rcol = Note_spacing::right_column (wish);
499 if (Note_spacing::left_column (wish) != lc
500 || (wish_rcol != rc && wish_rcol != rc->original_l_))
504 This is probably a waste of time in the case of polyphonic
506 if (Note_spacing::has_interface (wish))
511 Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
512 max_note_space = max_note_space >? space;
513 max_fixed_note_space = max_fixed_note_space >? fixed;
518 if (max_note_space < 0)
520 max_note_space = base_note_space;
521 max_fixed_note_space = increment;
524 Spaceable_grob::add_spring (lc, rc, max_note_space, 1 / (max_note_space -max_fixed_note_space), expand_only);
529 Read hints from L (todo: R) and generate springs.
532 Spacing_spanner::breakable_column_spacing (Item* l, Item *r)
534 Real max_fixed = -infinity_f;
535 Real max_space = -infinity_f;
537 for (SCM s = l->get_grob_property ("spacing-wishes");
538 gh_pair_p (s); s = gh_cdr (s))
540 Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
542 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
549 column for the left one settings should be ok due automatic
553 assert (spacing_grob-> column_l () == l);
555 Staff_spacing::get_spacing_params (spacing_grob,
556 &space, &fixed_space);
557 if (space > max_space)
560 max_fixed = fixed_space;
564 if (isinf (max_space))
566 programming_error ("No pref spacing found");
572 if (l->break_status_dir() == RIGHT
573 && Paper_column::when_mom (l) == Paper_column::when_mom (r))
575 /* Start of line: this space is not stretchable */
576 max_fixed = max_space;
580 Hmm. we do 1/0 in the next thing. Perhaps we should check if this
581 works on all architectures.
584 Spaceable_grob::add_spring (l, r, max_space, 1/(max_space - max_fixed), false);
589 Get the measure wide ant for arithmetic spacing.
592 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
594 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
598 Rational ratio = d.main_part_ / shortest;
601 return (0.5 + 0.5 * double (ratio)) * k ;
607 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
608 OSU-CISRC-10/87-TR35, Department of Computer and Information Science,
609 The Ohio State University, 1987.
611 Real log = log_2 (shortest);
613 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
614 *expand_only = false;
616 return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
621 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
622 Moment shortest, bool * expand_only)
624 Moment shortest_playing_len = 0;
625 SCM s = lc->get_grob_property ("shortest-playing-duration");
627 if (unsmob_moment (s))
628 shortest_playing_len = *unsmob_moment (s);
630 if (! shortest_playing_len.to_bool ())
632 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
633 shortest_playing_len = 1;
636 Moment delta_t = Paper_column::when_mom (rc) - Paper_column::when_mom (lc);
639 if (delta_t.main_part_)
641 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
642 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
644 else if (delta_t.grace_part_)
647 TODO: figure out how to space grace notes.
649 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
651 Real grace_fact = 1.0;
652 SCM gf = me->get_grob_property ("grace-space-factor");
653 if (gh_number_p (gf))
654 grace_fact = gh_scm2double (gf);