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?
38 static Real default_bar_spacing (Grob*,Grob*,Grob*,Moment);
39 static Real note_spacing (Grob*,Grob*,Grob*,Moment, bool*);
40 static Real get_duration_space (Grob*,Moment dur, Rational shortest, bool*);
41 static Rational find_shortest (Link_array<Grob> const &);
42 static void breakable_column_spacing (Item* l, Item *r);
43 static void find_loose_columns () {}
44 static void prune_loose_colunms (Link_array<Grob> *cols);
45 static void find_loose_columns (Link_array<Grob> cols);
46 static void set_explicit_neighbor_columns (Link_array<Grob> cols);
47 static void set_implicit_neighbor_columns (Link_array<Grob> cols);
48 static void do_measure (Rational, Grob*me,Link_array<Grob> *cols);
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.
85 if (!gh_pair_p (lns) || !gh_pair_p (rns))
88 Item * l_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (lns)));
89 Item * r_neighbor = dynamic_cast<Item*> (unsmob_grob (gh_car (rns)));
91 if (!l_neighbor || !r_neighbor)
94 l_neighbor = l_neighbor->column_l();
95 r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column (r_neighbor));
97 if (l == l_neighbor && r == r_neighbor)
100 if (!l_neighbor || !r_neighbor)
104 Only declare loose if the bounds make a little sense. This means
105 some cases (two isolated, consecutive clef changes) won't be
106 nicely folded, but hey, then don't do that.
108 if( (Paper_column::musical_b (l_neighbor) || Item::breakable_b (l_neighbor))
109 && (Paper_column::musical_b (r_neighbor) || Item::breakable_b (r_neighbor)))
116 If in doubt: we're not loose; the spacing engine should space for
117 it, risking suboptimal spacing.
119 (Otherwise, we might risk core dumps, and other weird stuff.)
126 Remove columns that are not tightly fitting from COLS. In the
127 removed columns, set 'between-cols to the columns where it is in
131 Spacing_spanner::prune_loose_colunms (Link_array<Grob> *cols)
133 Link_array<Grob> newcols;
135 for (int i=0; i < cols->size (); i++)
137 if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
139 newcols.push (cols->elem(i));
143 Grob *c = cols->elem(i);
144 if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
146 SCM lns = c->get_grob_property ("left-neighbors");
147 lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
149 SCM rns = c->get_grob_property ("right-neighbors");
150 rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
153 Either object can be non existent, if the score ends
156 rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
157 c->set_grob_property ("between-cols", gh_cons (lns,
161 Set distance constraints for loose columns
163 Drul_array<Grob*> next_door;
164 next_door[LEFT] =cols->elem (i - 1);
165 next_door[RIGHT] =cols->elem (i + 1);
167 Drul_array<Real> dists(0,0);
172 Grob *lc = (d == LEFT) ? next_door[LEFT] : c;
173 Grob *rc = d == LEFT ? c : next_door[RIGHT];
175 for (SCM s = lc->get_grob_property ("spacing-wishes");
176 gh_pair_p (s); s = gh_cdr (s))
178 Grob *sp = unsmob_grob (gh_car (s));
179 if (Note_spacing::left_column (sp) != lc
180 || Note_spacing::right_column (sp) != rc)
183 dists[d] = dists[d] >? Note_spacing::get_spacing (sp);
186 while (flip (&d) != LEFT);
189 r.distance_f_ = dists[LEFT] + dists[RIGHT];
190 r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
191 r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
205 Set neighboring columns determined by the spacing-wishes grob property.
208 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
210 for (int i=0; i < cols.size(); i++)
212 SCM right_neighbors = SCM_EOL;
213 int min_rank = 100000; // inf.
216 SCM wishes= cols[i]->get_grob_property ("spacing-wishes");
217 for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
219 Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
221 Item * lc = wish->column_l ();
222 Grob * right = Note_spacing::right_column (wish);
227 Item * rc = dynamic_cast<Item*> (right);
229 int right_rank = Paper_column::rank_i (rc);
230 int left_rank = Paper_column::rank_i (lc);
233 update the left column.
235 if (right_rank <= min_rank)
237 if (right_rank < min_rank)
238 right_neighbors =SCM_EOL;
240 min_rank = right_rank;
241 right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
245 update the right column of the wish.
248 SCM left_neighs = rc->get_grob_property ("left-neighbors");
249 if (gh_pair_p (left_neighs)
250 && unsmob_grob (gh_car (left_neighs)))
252 Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
253 maxrank = Paper_column::rank_i (it->column_l());
256 if (left_rank >= maxrank)
258 if (left_rank > maxrank)
259 left_neighs = SCM_EOL;
261 left_neighs = gh_cons (wish->self_scm (), left_neighs);
262 rc->set_grob_property ("left-neighbors", right_neighbors);
266 if (gh_pair_p (right_neighbors))
268 cols[i]->set_grob_property ("right-neighbors", right_neighbors);
274 Set neighboring columns that have no left/right-neighbor set
275 yet. Only do breakable non-musical columns, and musical columns.
278 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
280 for (int i = 0; i < cols.size (); i++)
282 Item * it = dynamic_cast<Item*>(cols[i]);
283 if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
286 // it->breakable || it->musical
289 sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
291 SCM ln = cols[i] ->get_grob_property ("left-neighbors");
292 if (!gh_pair_p (ln) && i )
294 cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
297 SCM rn = cols[i] ->get_grob_property ("right-neighbors");
298 if (!gh_pair_p (rn) && i < cols.size () - 1)
300 cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
306 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
308 Spacing_spanner::set_springs (SCM smob)
310 Grob *me = unsmob_grob (smob);
312 Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
314 set_explicit_neighbor_columns (all);
315 prune_loose_colunms (&all);
316 set_implicit_neighbor_columns (all);
318 Rational global_shortest = find_shortest (all);
321 for (int i = 1; i < all.size (); i++)
324 if (Item::breakable_b (sc))
326 Link_array<Grob> measure (all.slice (j, i+1));
327 do_measure (global_shortest, me, &measure);
332 return SCM_UNSPECIFIED;
337 We want the shortest note that is also "common" in the piece, so we
338 find the shortest in each measure, and take the most frequently
341 This probably gives weird effects with modern music, where every
342 note has a different duration, but hey, don't write that kind of
347 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
350 ascending in duration
352 Array<Rational> durations;
355 Rational shortest_in_measure;
356 shortest_in_measure.set_infinite (1);
358 for (int i =0 ; i < cols.size (); i++)
360 if (Paper_column::musical_b (cols[i]))
362 Moment *when = unsmob_moment (cols[i]->get_grob_property ("when"));
365 ignore grace notes for shortest notes.
367 if (when && when->grace_part_)
370 SCM st = cols[i]->get_grob_property ("shortest-starter-duration");
371 Moment this_shortest = *unsmob_moment (st);
372 assert (this_shortest.to_bool());
373 shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
375 else if (!shortest_in_measure.infty_b()
376 && Item::breakable_b (cols[i]))
379 for (; j < durations.size(); j++)
381 if (durations[j] > shortest_in_measure)
383 counts.insert (1, j);
384 durations.insert (shortest_in_measure, j);
387 else if (durations[j] == shortest_in_measure)
394 if (durations.size() == j)
396 durations.push (shortest_in_measure);
400 shortest_in_measure.set_infinite(1);
406 for (int i =durations.size(); i--;)
408 if (counts[i] >= max_count)
411 max_count = counts[i];
414 // printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
418 TODO: 1/8 should be adjustable?
420 Rational d = Rational (1,8);
422 d = d <? durations[max_idx] ;
428 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
431 Real headwid = gh_scm2double (me->get_grob_property ("spacing-increment"));
432 for (int i= 0; i < cols->size () - 1; i++)
434 Item * l = dynamic_cast<Item*> (cols->elem (i));
435 Item * r = dynamic_cast<Item*> (cols->elem (i+1));
437 Paper_column * lc = dynamic_cast<Paper_column*> (l);
438 Paper_column * rc = dynamic_cast<Paper_column*> (r);
440 if (!Paper_column::musical_b (l))
442 breakable_column_spacing (l, r);
446 The case that the right part is broken as well is rather
447 rare, but it is possible, eg. with a single empty measure,
448 or if one staff finishes a tad earlier than the rest.
451 Item *lb = l->find_prebroken_piece (RIGHT);
452 Item *rb = r->find_prebroken_piece (LEFT);
455 breakable_column_spacing (lb,r);
458 breakable_column_spacing (l, rb);
460 breakable_column_spacing (lb, rb);
464 bool expand_only = false;
465 Real note_space = note_spacing (me, lc, rc, shortest, &expand_only);
467 Real hinterfleisch = note_space;
470 SCM seq = lc->get_grob_property ("right-neighbors");
473 hinterfleisch = hind-meat = amount of space following a note.
476 We adjust the space following a note only if the next note
477 happens after the current note (this is set in the grob
478 property SPACING-SEQUENCE. */
480 Real stretch_distance = note_space;
482 hinterfleisch = -1.0;
483 Real max_factor = 0.0;
484 for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
486 Grob * wish = unsmob_grob (gh_car (s));
488 if (Note_spacing::left_column (wish) != lc
489 || Note_spacing::right_column (wish) != rc)
493 This is probably a waste of time in the case of polyphonic
495 if (Note_spacing::has_interface (wish))
497 hinterfleisch = hinterfleisch >?
500 (note_space + Note_spacing::get_spacing (wish))
501 *gh_scm2double (wish->get_grob_property ("space-factor"))
503 + Note_spacing::stem_dir_correction (wish));
507 if (hinterfleisch < 0)
509 // maybe should issue a programming error.
510 hinterfleisch = note_space;
513 stretch_distance -= headwid; // why?
515 if (max_factor == 0.0)
518 Spaceable_grob::add_spring (l, r, max_factor * hinterfleisch, 1 / stretch_distance, expand_only);
521 TODO: we should have a separate routine determining this distance!
523 if (Item *rb = r->find_prebroken_piece (LEFT))
525 Spaceable_grob::add_spring (l, rb, max_factor * hinterfleisch, 1 / stretch_distance, expand_only);
532 Read hints from L (todo: R) and generate springs.
535 Spacing_spanner::breakable_column_spacing (Item* l, Item *r)
537 Real max_fixed = -infinity_f;
538 Real max_space = -infinity_f;
540 for (SCM s = l->get_grob_property ("spacing-wishes");
541 gh_pair_p (s); s = gh_cdr (s))
543 Grob * spacing_grob = unsmob_grob (gh_car (s));
545 if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
551 Staff_spacing::get_spacing_params (spacing_grob,
552 &space, &fixed_space);
553 if (space > max_space)
556 max_fixed = fixed_space;
560 if (isinf (max_space))
562 programming_error ("No pref spacing found");
567 Spaceable_grob::add_spring (l, r, max_space, 1/(max_space - max_fixed), false);
572 Get the measure wide ant for arithmetic spacing.
575 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
577 Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
581 Rational ratio = d.main_part_ / shortest;
584 return (0.5 + 0.5 * double (ratio)) * k ;
590 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
591 OSU-CISRC-10/87-TR35, Department of Computer and Information Science,
592 The Ohio State University, 1987.
594 Real log = log_2 (shortest);
596 Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
597 *expand_only = false;
599 return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
604 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
605 Moment shortest, bool * expand_only)
607 Moment shortest_playing_len = 0;
608 SCM s = lc->get_grob_property ("shortest-playing-duration");
610 if (unsmob_moment (s))
611 shortest_playing_len = *unsmob_moment (s);
613 if (! shortest_playing_len.to_bool ())
615 programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
616 shortest_playing_len = 1;
619 Moment delta_t = Paper_column::when_mom (rc) - Paper_column::when_mom (lc);
622 if (delta_t.main_part_)
624 dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
625 dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
627 else if (delta_t.grace_part_)
630 TODO: figure out how to space grace notes.
632 dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
634 Real grace_fact = 1.0;
635 SCM gf = me->get_grob_property ("grace-space-factor");
636 if (gh_number_p (gf))
637 grace_fact = gh_scm2double (gf);