]> git.donarmstrong.com Git - lilypond.git/blob - lily/spacing-spanner.cc
2fff9c08e6d954c68c197fd5b33f49c6b92ed000
[lilypond.git] / lily / spacing-spanner.cc
1 /*   
2   spacing-spanner.cc -- implement Spacing_spanner
3   
4   source file of the GNU LilyPond music typesetter
5   
6   (c) 1999--2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
7   
8  */
9
10 #include <math.h>
11 #include <stdio.h>
12
13 #include "line-of-score.hh"
14 #include "paper-score.hh"
15 #include "paper-column.hh"
16 #include "item.hh"
17 #include "moment.hh"
18 #include "note-spacing.hh"
19 #include "misc.hh"
20 #include "warn.hh"
21 #include "staff-spacing.hh"
22 #include "spring.hh"
23 #include "paper-column.hh"
24 #include "spaceable-grob.hh"
25
26 /*
27   paper-column:
28
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?
32     
33  */
34 class Spacing_spanner
35 {
36 public:
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 ));
50 };
51
52 /*
53   Return whether COL is fixed to its neighbors by some kind of spacing
54   constraint.
55 */
56 static bool
57 loose_column (Grob *l, Grob *c, Grob *r) 
58 {
59   SCM rns = c->get_grob_property ("right-neighbors");
60   SCM lns = c->get_grob_property ("left-neighbors");
61
62  /*
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
65     currently can handle.
66
67     (this happens in the following situation:
68
69        |
70        |    clef G 
71       *
72
73        |               |      ||
74        |               |      || 
75       O               O       ||
76
77
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.)
81     
82   */  
83   if (!gh_pair_p (lns) || !gh_pair_p (rns))
84     return false;
85
86   Item * l_neighbor = dynamic_cast<Item*>  (unsmob_grob (gh_car (lns)));
87   Item * r_neighbor = dynamic_cast<Item*>  (unsmob_grob (gh_car (rns)));
88
89   if (!l_neighbor || !r_neighbor)
90     return false;
91
92   l_neighbor = l_neighbor->column_l();
93   r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column  (r_neighbor));
94
95   if (l == l_neighbor && r == r_neighbor)
96     return false;
97
98   if (!l_neighbor || !r_neighbor)
99     return false;
100
101   /*
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.
105   */
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)))
108     {
109       return true;
110     }
111
112
113   /*
114     If in doubt: we're not loose; the spacing engine should space for
115     it, risking suboptimal spacing.
116
117     (Otherwise, we might risk core dumps, and other weird stuff.)
118
119   */
120   return false;
121 }
122
123 /*
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
126   between.
127 */
128 void
129 Spacing_spanner::prune_loose_colunms (Grob*me,Link_array<Grob> *cols, Rational shortest)
130 {
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++)
134     {
135       if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
136         {
137           newcols.push (cols->elem(i));
138           continue;
139         }
140
141       Grob *c = cols->elem(i);
142       if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
143         {
144           SCM lns = c->get_grob_property ("left-neighbors");
145           lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
146
147           SCM rns = c->get_grob_property ("right-neighbors");
148           rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
149
150           /*
151             Either object can be non existent, if the score ends
152             prematurely.
153            */
154           rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
155           c->set_grob_property ("between-cols", gh_cons (lns,
156                                                          rns));
157
158           /*
159             Set distance constraints for loose columns
160           */
161           Drul_array<Grob*> next_door;
162           next_door[LEFT] =cols->elem (i - 1);
163           next_door[RIGHT] =cols->elem (i + 1);   
164           Direction d = LEFT;
165           Drul_array<Real> dists(0,0);
166
167           do
168             {
169               dists[d] = 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]);
172
173               for (SCM s = lc->get_grob_property ("spacing-wishes");
174                    gh_pair_p (s); s = gh_cdr (s))
175                 {
176                   Grob *sp = unsmob_grob (gh_car (s));
177                   if (Note_spacing::left_column (sp) != lc
178                       || Note_spacing::right_column (sp) != rc)
179                     continue;
180
181                   Real space, fixed;
182                   fixed = 0.0;
183                   bool dummy;
184
185                   if (d == LEFT)
186                     {
187                       /*
188                         The note spacing should be taken from the musical
189                         columns.
190                     
191                       */
192                       Real base = note_spacing (me, lc, rc, shortest, &dummy);
193                       Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
194
195                       space -= increment; 
196                   
197                       dists[d] = dists[d] >? space;
198                     }
199                   else
200                     {
201                       Real space, fixed_space;
202                       Staff_spacing::get_spacing_params (sp,
203                                                          &space, &fixed_space);
204
205                       dists[d] = dists[d] >? fixed_space;
206                     }
207                   
208                 }
209             }
210           while (flip (&d) != LEFT);
211
212           Rod r;
213           r.distance_f_ = dists[LEFT] + dists[RIGHT];
214           r.item_l_drul_[LEFT] = dynamic_cast<Item*> (cols->elem(i-1));
215           r.item_l_drul_[RIGHT] = dynamic_cast<Item*> (cols->elem (i+1));
216
217           r.add_to_cols ();
218         }
219       else
220         {
221           newcols.push (c);
222         }
223     }
224
225   *cols = newcols;
226 }
227
228 /*
229   Set neighboring columns determined by the spacing-wishes grob property.  
230 */
231 void
232 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
233 {
234   for (int i=0; i < cols.size(); i++)
235     {
236       SCM right_neighbors = SCM_EOL;
237       int min_rank = 100000;    // inf.
238
239
240       SCM wishes=  cols[i]->get_grob_property ("spacing-wishes");
241       for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
242         {
243           Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
244
245           Item * lc = wish->column_l ();
246           Grob * right = Note_spacing::right_column (wish);
247
248           if (!right)
249             continue;
250
251           Item * rc = dynamic_cast<Item*> (right);
252
253           int right_rank = Paper_column::rank_i (rc);
254           int left_rank = Paper_column::rank_i (lc);      
255
256           /*
257             update the left column.
258            */
259           if (right_rank <= min_rank)
260             {
261               if (right_rank < min_rank)
262                 right_neighbors  =SCM_EOL;
263               
264               min_rank = right_rank;
265               right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
266             }
267
268           /*
269             update the right column of the wish.
270            */
271           int maxrank = 0;
272           SCM left_neighs = rc->get_grob_property ("left-neighbors");
273           if (gh_pair_p (left_neighs)
274               && unsmob_grob (gh_car (left_neighs)))
275             {
276               Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
277               maxrank = Paper_column::rank_i (it->column_l());
278             }
279
280           if (left_rank >= maxrank)
281             {
282               if (left_rank > maxrank)
283                 left_neighs = SCM_EOL;
284
285               left_neighs = gh_cons (wish->self_scm (), left_neighs);
286               rc->set_grob_property ("left-neighbors", right_neighbors);
287             }
288         }
289
290       if (gh_pair_p (right_neighbors))
291         {
292           cols[i]->set_grob_property ("right-neighbors", right_neighbors);
293         }
294     }
295 }
296
297 /*
298   Set neighboring columns that have no left/right-neighbor set
299   yet. Only do breakable non-musical columns, and musical columns. 
300 */
301 void
302 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
303 {
304   for (int i = 0; i < cols.size (); i++)
305     {
306       Item * it = dynamic_cast<Item*>(cols[i]);
307       if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
308         continue;
309
310       // it->breakable || it->musical
311
312       /*
313         sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
314        */
315       SCM ln = cols[i] ->get_grob_property ("left-neighbors");
316       if (!gh_pair_p (ln) && i ) 
317         {
318           cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
319         }
320
321       SCM rn = cols[i] ->get_grob_property ("right-neighbors");
322       if (!gh_pair_p (rn) && i < cols.size () - 1) 
323         {
324           cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
325         }
326     }
327 }
328
329
330 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
331 SCM
332 Spacing_spanner::set_springs (SCM smob)
333 {
334   Grob *me = unsmob_grob (smob);
335
336   Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
337
338   set_explicit_neighbor_columns (all);
339
340   Rational global_shortest = find_shortest (all);
341   prune_loose_colunms (me, &all, global_shortest);
342   set_implicit_neighbor_columns (all);
343
344   
345   int j = 0;
346   for (int i = 1; i < all.size (); i++)
347     {
348       Grob *sc = all[i];
349       if (Item::breakable_b (sc))
350         {
351           Link_array<Grob> measure (all.slice (j, i+1));          
352           do_measure (global_shortest, me, &measure);
353           j = i;
354         }
355     }
356
357   return SCM_UNSPECIFIED;
358 }
359
360
361 /*
362   We want the shortest note that is also "common" in the piece, so we
363   find the shortest in each measure, and take the most frequently
364   found duration.
365
366   This probably gives weird effects with modern music, where every
367   note has a different duration, but hey, don't write that kind of
368   stuff, then.
369
370 */
371 Rational
372 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
373 {
374   /*
375     ascending in duration
376    */
377   Array<Rational> durations; 
378   Array<int> counts;
379   
380   Rational shortest_in_measure;
381   shortest_in_measure.set_infinite (1);
382   
383   for (int i =0 ; i < cols.size (); i++)  
384     {
385       if (Paper_column::musical_b (cols[i]))
386         {
387           Moment *when = unsmob_moment (cols[i]->get_grob_property  ("when"));
388
389           /*
390             ignore grace notes for shortest notes.
391           */
392           if (when && when->grace_part_)
393             continue;
394           
395           SCM  st = cols[i]->get_grob_property ("shortest-starter-duration");
396           Moment this_shortest = *unsmob_moment (st);
397           assert (this_shortest.to_bool());
398           shortest_in_measure = shortest_in_measure <? this_shortest.main_part_;
399         }
400       else if (!shortest_in_measure.infty_b()
401                && Item::breakable_b (cols[i]))
402         {
403           int j = 0;
404           for (; j < durations.size(); j++)
405             {
406               if (durations[j] > shortest_in_measure)
407                 {
408                   counts.insert (1, j);
409                   durations.insert (shortest_in_measure, j);
410                   break;
411                 }
412               else if (durations[j] == shortest_in_measure)
413                 {
414                   counts[j]++;
415                   break;
416                 }
417             }
418
419           if (durations.size() == j)
420             {
421               durations.push (shortest_in_measure);
422               counts.push (1);
423             }
424
425           shortest_in_measure.set_infinite(1); 
426         }
427     }
428
429   int max_idx = -1;
430   int max_count = 0;
431   for (int i =durations.size(); i--;)
432     {
433       if (counts[i] >= max_count)
434         {
435           max_idx = i;
436           max_count = counts[i];
437         }
438
439       //      printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
440     }
441
442   /*
443     TODO: 1/8 should be adjustable?
444    */
445   Rational d = Rational (1,8);
446   if (max_idx >= 0)
447     d = d <? durations[max_idx] ;
448
449   return d;
450 }
451
452 /*
453   Generate spacing for a single measure. We used to have code that did
454   per-measure spacing. Now we have piecewise spacing. We should fix
455   this to support "spacing-regions": some regions have different notes
456   (different time sigs) than others, and should be spaced differently.
457  */
458 void
459 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols) 
460 {
461
462   Real headwid =       gh_scm2double (me->get_grob_property ("spacing-increment"));
463   for (int i= 0; i < cols->size () - 1; i++)
464     {
465       Item * l = dynamic_cast<Item*> (cols->elem (i));
466       Item * r =  dynamic_cast<Item*> (cols->elem (i+1));
467
468       Paper_column * lc = dynamic_cast<Paper_column*> (l);
469       Paper_column * rc = dynamic_cast<Paper_column*> (r);
470
471       if (!Paper_column::musical_b (l))
472         {
473           breakable_column_spacing (l, r);
474
475           /*
476             
477             The case that the right part is broken as well is rather
478             rare, but it is possible, eg. with a single empty measure,
479             or if one staff finishes a tad earlier than the rest.
480             
481            */
482           Item *lb = l->find_prebroken_piece (RIGHT);
483           Item *rb = r->find_prebroken_piece (LEFT);
484           
485           if (lb)
486             breakable_column_spacing (lb,r);
487
488           if (rb)
489             breakable_column_spacing (l, rb);
490           if (lb && rb)
491             breakable_column_spacing (lb, rb);
492           
493           continue ; 
494         }
495
496
497       musical_column_spacing (me, lc, rc, headwid, shortest);
498       if (Item *rb = r->find_prebroken_piece (LEFT))
499         musical_column_spacing (me, lc, rb, headwid, shortest);
500     }    
501 }
502
503
504 /*
505   Generate the space between two musical columns LC and RC, given spacing parameters INCR and SHRTEST.
506  */
507 void
508 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
509 {
510   bool expand_only = false;
511   Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
512
513   Real max_note_space = -infinity_f;
514   Real max_fixed_note_space = -infinity_f;
515
516   SCM seq  = lc->get_grob_property ("right-neighbors");
517
518   /*
519     We adjust the space following a note only if the next note
520     happens after the current note (this is set in the grob
521     property SPACING-SEQUENCE.
522   */
523   for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
524     {
525       Grob * wish = unsmob_grob (gh_car (s));
526
527       Item *wish_rcol = Note_spacing::right_column (wish);
528       if (Note_spacing::left_column (wish) != lc
529           || (wish_rcol != rc && wish_rcol != rc->original_l_))
530         continue;
531
532       /*
533         This is probably a waste of time in the case of polyphonic
534         music.  */
535       if (Note_spacing::has_interface (wish))
536         {
537           Real space =0.0;
538           Real fixed =0.0;
539           
540           Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
541           max_note_space = max_note_space >? space;
542           max_fixed_note_space = max_fixed_note_space >? fixed;
543         }
544
545     }
546
547   if (max_note_space < 0)
548     {
549       max_note_space = base_note_space;
550       max_fixed_note_space = increment;
551     }
552
553   Spaceable_grob::add_spring (lc, rc, max_note_space,  1 / (max_note_space -max_fixed_note_space), expand_only);
554 }
555
556
557 /*
558   Read hints from L and generate springs.
559  */
560 void
561 Spacing_spanner::breakable_column_spacing (Item* l, Item *r)
562 {
563   Real max_fixed = -infinity_f;
564   Real max_space = -infinity_f;
565   
566   for (SCM s = l->get_grob_property ("spacing-wishes");
567        gh_pair_p (s); s = gh_cdr (s))
568     {
569       Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
570
571       if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
572         continue;
573
574       Real space;
575       Real fixed_space;
576
577       /*
578         column for the left one settings should be ok due automatic
579         pointer munging.
580
581       */
582       assert (spacing_grob-> column_l () == l);
583
584       Staff_spacing::get_spacing_params (spacing_grob,
585                                          &space, &fixed_space);  
586       if (space > max_space)
587         {
588           max_space = space;
589           max_fixed = fixed_space;
590         }
591     }
592
593   if (isinf (max_space))
594     {
595       programming_error ("No pref spacing found");
596       max_space = 2.0;
597       max_fixed = 1.0;
598     }
599
600   
601   if (l->break_status_dir() == RIGHT
602       && Paper_column::when_mom (l) == Paper_column::when_mom (r))
603     {
604       /* Start of line: this space is not stretchable */
605       max_fixed = max_space;
606     }
607
608   /*
609     Hmm.  we do 1/0 in the next thing. Perhaps we should check if this
610     works on all architectures.
611    */
612   
613   Spaceable_grob::add_spring (l, r, max_space,  1/(max_space - max_fixed), false);  
614 }
615
616
617 /**
618   Get the measure wide ant for arithmetic spacing.
619   */
620 Real
621 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only) 
622 {
623   Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
624     
625   if (d < shortest)
626     {
627       Rational ratio = d.main_part_ / shortest;
628       
629       *expand_only = true;
630       return (0.5 + 0.5 * double (ratio)) * k ;
631     }
632   else
633     {
634       /*
635           @see
636   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
637   OSU-CISRC-10/87-TR35, Department of Computer and Information Science,
638   The Ohio State University, 1987.
639        */
640       Real log =  log_2 (shortest);
641       k -= log;
642       Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
643       *expand_only = false;      
644    
645       return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
646     }
647 }
648
649 Real
650 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
651                                Moment shortest, bool * expand_only) 
652 {
653   Moment shortest_playing_len = 0;
654   SCM s = lc->get_grob_property ("shortest-playing-duration");
655
656   if (unsmob_moment (s))
657     shortest_playing_len = *unsmob_moment (s);
658   
659   if (! shortest_playing_len.to_bool ())
660     {
661       programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
662       shortest_playing_len = 1;
663     }
664   
665   Moment delta_t = Paper_column::when_mom (rc) - Paper_column::when_mom (lc);
666   Real dist = 0.0;
667
668   if (delta_t.main_part_)
669     {
670       dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
671       dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
672     }
673   else if (delta_t.grace_part_)
674     {
675       /*
676         TODO: figure out how to space grace notes.
677       */
678       dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
679
680       Real grace_fact = 1.0;
681       SCM gf = me->get_grob_property ("grace-space-factor");
682       if (gh_number_p (gf))
683         grace_fact = gh_scm2double (gf);
684
685       dist *= grace_fact;
686     }
687
688   
689   return dist;
690 }
691
692
693
694 ADD_INTERFACE (Spacing_spanner,"spacing-spanner-interface",
695   " SPACE = arithmetic_multiplier * ( C + log2 (TIME) ))
696 The space taken by a note is determined by the formula 
697
698
699
700 where TIME is the amount of time a note occupies.  The value of C is
701 chosen such that the smallest space within a measure is
702 arithmetic_basicspace:
703
704 C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8)) 
705
706 The smallest space is the one following the shortest note in the
707 measure, or the space following a hypothetical 1/8 note.  Typically
708 arithmetic_basicspace is set to a value so that the shortest note
709 takes about two noteheads of space (ie, is followed by a notehead of
710 space):
711
712 @example
713 2*quartwidth = arithmetic_multiplier * ( C + log2 (SHORTEST) ))
714
715 @{ using: C = arithmetic_basicspace - log2 (mininum (SHORTEST, 1/8)) @}
716 @{ assuming: SHORTEST <= 1/8 @}
717
718 = arithmetic_multiplier *
719 ( arithmetic_basicspace - log2 (SHORTEST) + log2 (SHORTEST) )
720
721 = arithmetic_multiplier * arithmetic_basicspace
722
723 @{ choose: arithmetic_multiplier = 1.0*quartwidth (why?) @}
724
725 = quartwidth * arithmetic_basicspace
726
727 =>             
728
729 arithmetic_basicspace = 2/1 = 2
730
731
732 If you want to space your music wider, use something like:
733
734 arithmetic_basicspace = 4.;
735
736 @end example",
737   "spacing-increment shortest-duration-space");
738