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 expand_only;
 184                   Real base = note_spacing (me, lc, rc, shortest, &expand_only);
 185                   Note_spacing::get_spacing (sp, rc, base, increment, &space, &fixed);
 186                   space -=base;
 187
 188                   dists[d] = dists[d] >? space;
 189                 }
 190             }
 191           while (flip (&d) != LEFT);
 192
 193           Rod r;
 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));
 197
 198           r.add_to_cols ();
 199         }
 200       else
 201         {
 202           newcols.push (c);
 203         }
 204     }
 205
 206   *cols = newcols;
 207 }
 208
 209 /*
 210   Set neighboring columns determined by the spacing-wishes grob property.
 211 */
 212 void
 213 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
 214 {
 215   for (int i=0; i < cols.size(); i++)
 216     {
 217       SCM right_neighbors = SCM_EOL;
 218       int min_rank = 100000;    // inf.
 219
 220
 221       SCM wishes=  cols[i]->get_grob_property ("spacing-wishes");
 222       for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
 223         {
 224           Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
 225
 226           Item * lc = wish->column_l ();
 227           Grob * right = Note_spacing::right_column (wish);
 228
 229           if (!right)
 230             continue;
 231
 232           Item * rc = dynamic_cast<Item*> (right);
 233
 234           int right_rank = Paper_column::rank_i (rc);
 235           int left_rank = Paper_column::rank_i (lc);
 236
 237           /*
 238             update the left column.
 239            */
 240           if (right_rank <= min_rank)
 241             {
 242               if (right_rank < min_rank)
 243                 right_neighbors  =SCM_EOL;
 244
 245               min_rank = right_rank;
 246               right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
 247             }
 248
 249           /*
 250             update the right column of the wish.
 251            */
 252           int maxrank = 0;
 253           SCM left_neighs = rc->get_grob_property ("left-neighbors");
 254           if (gh_pair_p (left_neighs)
 255               && unsmob_grob (gh_car (left_neighs)))
 256             {
 257               Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
 258               maxrank = Paper_column::rank_i (it->column_l());
 259             }
 260
 261           if (left_rank >= maxrank)
 262             {
 263               if (left_rank > maxrank)
 264                 left_neighs = SCM_EOL;
 265
 266               left_neighs = gh_cons (wish->self_scm (), left_neighs);
 267               rc->set_grob_property ("left-neighbors", right_neighbors);
 268             }
 269         }
 270
 271       if (gh_pair_p (right_neighbors))
 272         {
 273           cols[i]->set_grob_property ("right-neighbors", right_neighbors);
 274         }
 275     }
 276 }
 277
 278 /*
 279   Set neighboring columns that have no left/right-neighbor set
 280   yet. Only do breakable non-musical columns, and musical columns.
 281 */
 282 void
 283 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
 284 {
 285   for (int i = 0; i < cols.size (); i++)
 286     {
 287       Item * it = dynamic_cast<Item*>(cols[i]);
 288       if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
 289         continue;
 290
 291       // it->breakable || it->musical
 292
 293       /*
 294         sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
 295        */
 296       SCM ln = cols[i] ->get_grob_property ("left-neighbors");
 297       if (!gh_pair_p (ln) && i )
 298         {
 299           cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
 300         }
 301
 302       SCM rn = cols[i] ->get_grob_property ("right-neighbors");
 303       if (!gh_pair_p (rn) && i < cols.size () - 1)
 304         {
 305           cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
 306         }
 307     }
 308 }
 309
 310
 311 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
 312 SCM
 313 Spacing_spanner::set_springs (SCM smob)
 314 {
 315   Grob *me = unsmob_grob (smob);
 316
 317   Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
 318
 319   set_explicit_neighbor_columns (all);
 320
 321   Rational global_shortest = find_shortest (all);
 322   prune_loose_colunms (me, &all, global_shortest);
 323   set_implicit_neighbor_columns (all);
 324
 325
 326   int j = 0;
 327   for (int i = 1; i < all.size (); i++)
 328     {
 329       Grob *sc = all[i];
 330       if (Item::breakable_b (sc))
 331         {
 332           Link_array<Grob> measure (all.slice (j, i+1));
 333           do_measure (global_shortest, me, &measure);
 334           j = i;
 335         }
 336     }
 337
 338   return SCM_UNSPECIFIED;
 339 }
 340
 341
 342 /*
 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
 345   found duration.
 346
 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
 349   stuff, then.
 350
 351 */
 352 Rational
 353 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
 354 {
 355   /*
 356     ascending in duration
 357    */
 358   Array<Rational> durations;
 359   Array<int> counts;
 360
 361   Rational shortest_in_measure;
 362   shortest_in_measure.set_infinite (1);
 363
 364   for (int i =0 ; i < cols.size (); i++)
 365     {
 366       if (Paper_column::musical_b (cols[i]))
 367         {
 368           Moment *when = unsmob_moment (cols[i]->get_grob_property  ("when"));
 369
 370           /*
 371             ignore grace notes for shortest notes.
 372           */
 373           if (when && when->grace_part_)
 374             continue;
 375
 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_;
 380         }
 381       else if (!shortest_in_measure.infty_b()
 382                && Item::breakable_b (cols[i]))
 383         {
 384           int j = 0;
 385           for (; j < durations.size(); j++)
 386             {
 387               if (durations[j] > shortest_in_measure)
 388                 {
 389                   counts.insert (1, j);
 390                   durations.insert (shortest_in_measure, j);
 391                   break;
 392                 }
 393               else if (durations[j] == shortest_in_measure)
 394                 {
 395                   counts[j]++;
 396                   break;
 397                 }
 398             }
 399
 400           if (durations.size() == j)
 401             {
 402               durations.push (shortest_in_measure);
 403               counts.push (1);
 404             }
 405
 406           shortest_in_measure.set_infinite(1);
 407         }
 408     }
 409
 410   int max_idx = -1;
 411   int max_count = 0;
 412   for (int i =durations.size(); i--;)
 413     {
 414       if (counts[i] >= max_count)
 415         {
 416           max_idx = i;
 417           max_count = counts[i];
 418         }
 419
 420       //      printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
 421     }
 422
 423   /*
 424     TODO: 1/8 should be adjustable?
 425    */
 426   Rational d = Rational (1,8);
 427   if (max_idx >= 0)
 428     d = d <? durations[max_idx] ;
 429
 430   return d;
 431 }
 432
 433 /*
 434   Generate spacing for a single measure. We used to have code that did
 435   per-measure spacing. Now we have piecewise spacing. We should fix
 436   this to support "spacing-regions": some regions have different notes
 437   (different time sigs) than others, and should be spaced differently.
 438  */
 439 void
 440 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
 441 {
 442
 443   Real headwid =       gh_scm2double (me->get_grob_property ("spacing-increment"));
 444   for (int i= 0; i < cols->size () - 1; i++)
 445     {
 446       Item * l = dynamic_cast<Item*> (cols->elem (i));
 447       Item * r =  dynamic_cast<Item*> (cols->elem (i+1));
 448
 449       Paper_column * lc = dynamic_cast<Paper_column*> (l);
 450       Paper_column * rc = dynamic_cast<Paper_column*> (r);
 451
 452       if (!Paper_column::musical_b (l))
 453         {
 454           breakable_column_spacing (l, r);
 455
 456           /*
 457
 458             The case that the right part is broken as well is rather
 459             rare, but it is possible, eg. with a single empty measure,
 460             or if one staff finishes a tad earlier than the rest.
 461
 462            */
 463           Item *lb = l->find_prebroken_piece (RIGHT);
 464           Item *rb = r->find_prebroken_piece (LEFT);
 465
 466           if (lb)
 467             breakable_column_spacing (lb,r);
 468
 469           if (rb)
 470             breakable_column_spacing (l, rb);
 471           if (lb && rb)
 472             breakable_column_spacing (lb, rb);
 473
 474           continue ;
 475         }
 476
 477
 478       musical_column_spacing (me, lc, rc, headwid, shortest);
 479       if (Item *rb = r->find_prebroken_piece (LEFT))
 480         musical_column_spacing (me, lc, rb, headwid, shortest);
 481     }
 482 }
 483
 484
 485 /*
 486   Generate the space between two musical columns LC and RC, given spacing parameters INCR and SHRTEST.
 487  */
 488 void
 489 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
 490 {
 491   bool expand_only = false;
 492   Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
 493
 494   Real max_note_space = -infinity_f;
 495   Real max_fixed_note_space = -infinity_f;
 496
 497   SCM seq  = lc->get_grob_property ("right-neighbors");
 498
 499   /*
 500     We adjust the space following a note only if the next note
 501     happens after the current note (this is set in the grob
 502     property SPACING-SEQUENCE.
 503   */
 504   for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
 505     {
 506       Grob * wish = unsmob_grob (gh_car (s));
 507
 508       Item *wish_rcol = Note_spacing::right_column (wish);
 509       if (Note_spacing::left_column (wish) != lc
 510           || (wish_rcol != rc && wish_rcol != rc->original_l_))
 511         continue;
 512
 513       /*
 514         This is probably a waste of time in the case of polyphonic
 515         music.  */
 516       if (Note_spacing::has_interface (wish))
 517         {
 518           Real space =0.0;
 519           Real fixed =0.0;
 520
 521           Note_spacing::get_spacing (wish, rc, base_note_space, increment, &space, &fixed);
 522           max_note_space = max_note_space >? space;
 523           max_fixed_note_space = max_fixed_note_space >? fixed;
 524         }
 525
 526     }
 527
 528   if (max_note_space < 0)
 529     {
 530       max_note_space = base_note_space;
 531       max_fixed_note_space = increment;
 532     }
 533
 534   Spaceable_grob::add_spring (lc, rc, max_note_space,  1 / (max_note_space -max_fixed_note_space), expand_only);
 535 }
 536
 537
 538 /*
 539   Read hints from L (todo: R) and generate springs.
 540  */
 541 void
 542 Spacing_spanner::breakable_column_spacing (Item* l, Item *r)
 543 {
 544   Real max_fixed = -infinity_f;
 545   Real max_space = -infinity_f;
 546
 547   for (SCM s = l->get_grob_property ("spacing-wishes");
 548        gh_pair_p (s); s = gh_cdr (s))
 549     {
 550       Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
 551
 552       if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 553         continue;
 554
 555       Real space;
 556       Real fixed_space;
 557
 558       /*
 559         column for the left one settings should be ok due automatic
 560         pointer munging.
 561
 562       */
 563       assert (spacing_grob-> column_l () == l);
 564
 565       Staff_spacing::get_spacing_params (spacing_grob,
 566                                          &space, &fixed_space);
 567       if (space > max_space)
 568         {
 569           max_space = space;
 570           max_fixed = fixed_space;
 571         }
 572     }
 573
 574   if (isinf (max_space))
 575     {
 576       programming_error ("No pref spacing found");
 577       max_space = 2.0;
 578       max_fixed = 1.0;
 579     }
 580
 581
 582   if (l->break_status_dir() == RIGHT
 583       && Paper_column::when_mom (l) == Paper_column::when_mom (r))
 584     {
 585       /* Start of line: this space is not stretchable */
 586       max_fixed = max_space;
 587     }
 588
 589   /*
 590     Hmm.  we do 1/0 in the next thing. Perhaps we should check if this
 591     works on all architectures.
 592    */
 593
 594   Spaceable_grob::add_spring (l, r, max_space,  1/(max_space - max_fixed), false);
 595 }
 596
 597
 598 /**
 599   Get the measure wide ant for arithmetic spacing.
 600   */
 601 Real
 602 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
 603 {
 604   Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
 605
 606   if (d < shortest)
 607     {
 608       Rational ratio = d.main_part_ / shortest;
 609
 610       *expand_only = true;
 611       return (0.5 + 0.5 * double (ratio)) * k ;
 612     }
 613   else
 614     {
 615       /*
 616           @see
 617   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 618   OSU-CISRC-10/87-TR35, Department of Computer and Information Science,
 619   The Ohio State University, 1987.
 620        */
 621       Real log =  log_2 (shortest);
 622       k -= log;
 623       Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
 624       *expand_only = false;
 625
 626       return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
 627     }
 628 }
 629
 630 Real
 631 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
 632                                Moment shortest, bool * expand_only)
 633 {
 634   Moment shortest_playing_len = 0;
 635   SCM s = lc->get_grob_property ("shortest-playing-duration");
 636
 637   if (unsmob_moment (s))
 638     shortest_playing_len = *unsmob_moment (s);
 639
 640   if (! shortest_playing_len.to_bool ())
 641     {
 642       programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
 643       shortest_playing_len = 1;
 644     }
 645
 646   Moment delta_t = Paper_column::when_mom (rc) - Paper_column::when_mom (lc);
 647   Real dist = 0.0;
 648
 649   if (delta_t.main_part_)
 650     {
 651       dist = get_duration_space (me, shortest_playing_len, shortest.main_part_, expand_only);
 652       dist *= (double) (delta_t.main_part_ / shortest_playing_len.main_part_);
 653     }
 654   else if (delta_t.grace_part_)
 655     {
 656       /*
 657         TODO: figure out how to space grace notes.
 658       */
 659       dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
 660
 661       Real grace_fact = 1.0;
 662       SCM gf = me->get_grob_property ("grace-space-factor");
 663       if (gh_number_p (gf))
 664         grace_fact = gh_scm2double (gf);
 665
 666       dist *= grace_fact;
 667     }
 668
 669
 670   return dist;
 671 }
 672