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
  35 class Spacing_spanner
  36 {
  37 public:
  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 ));
  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
  84   */
  85   if (!gh_pair_p (lns) || !gh_pair_p (rns))
  86     return false;
  87
  88   Item * l_neighbor = dynamic_cast<Item*>  (unsmob_grob (gh_car (lns)));
  89   Item * r_neighbor = dynamic_cast<Item*>  (unsmob_grob (gh_car (rns)));
  90
  91   if (!l_neighbor || !r_neighbor)
  92     return false;
  93
  94   l_neighbor = l_neighbor->column_l();
  95   r_neighbor = dynamic_cast<Item*> (Note_spacing::right_column  (r_neighbor));
  96
  97   if (l == l_neighbor && r == r_neighbor)
  98     return false;
  99
 100   if (!l_neighbor || !r_neighbor)
 101     return false;
 102
 103   /*
 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.
 107   */
 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)))
 110     {
 111       return true;
 112     }
 113
 114
 115   /*
 116     If in doubt: we're not loose; the spacing engine should space for
 117     it, risking suboptimal spacing.
 118
 119     (Otherwise, we might risk core dumps, and other weird stuff.)
 120
 121   */
 122   return false;
 123 }
 124
 125 /*
 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
 128   between.
 129 */
 130 void
 131 Spacing_spanner::prune_loose_colunms (Link_array<Grob> *cols)
 132 {
 133   Link_array<Grob> newcols;
 134
 135   for (int i=0; i < cols->size ();  i++)
 136     {
 137       if (Item::breakable_b (cols->elem(i)) || Paper_column::musical_b (cols->elem (i)))
 138         {
 139           newcols.push (cols->elem(i));
 140           continue;
 141         }
 142
 143       Grob *c = cols->elem(i);
 144       if (loose_column (cols->elem (i-1), c, cols->elem (i+1)))
 145         {
 146           SCM lns = c->get_grob_property ("left-neighbors");
 147           lns = gh_pair_p (lns) ? gh_car (lns) : SCM_BOOL_F;
 148
 149           SCM rns = c->get_grob_property ("right-neighbors");
 150           rns = gh_pair_p (rns) ? gh_car (rns) : SCM_BOOL_F;
 151
 152           /*
 153             Either object can be non existent, if the score ends
 154             prematurely.
 155            */
 156           rns = gh_car (unsmob_grob (rns)->get_grob_property ("right-items"));
 157           c->set_grob_property ("between-cols", gh_cons (lns,
 158                                                          rns));
 159
 160           /*
 161             Set distance constraints for loose columns
 162           */
 163           Drul_array<Grob*> next_door;
 164           next_door[LEFT] =cols->elem (i - 1);
 165           next_door[RIGHT] =cols->elem (i + 1);
 166           Direction d = LEFT;
 167           Drul_array<Real> dists(0,0);
 168
 169           do
 170             {
 171               dists[d] = 0.0;
 172               Grob *lc = (d == LEFT)  ? next_door[LEFT] : c;
 173               Grob *rc = d == LEFT  ? c : next_door[RIGHT];
 174
 175               for (SCM s = lc->get_grob_property ("spacing-wishes");
 176                    gh_pair_p (s); s = gh_cdr (s))
 177                 {
 178                   Grob *sp = unsmob_grob (gh_car (s));
 179                   if (Note_spacing::left_column (sp) != lc
 180                       || Note_spacing::right_column (sp) != rc)
 181                     continue;
 182
 183                   dists[d] = dists[d] >? Note_spacing::get_spacing (sp);
 184                 }
 185             }
 186           while (flip (&d) != LEFT);
 187
 188           Rod r;
 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));
 192
 193           r.add_to_cols ();
 194         }
 195       else
 196         {
 197           newcols.push (c);
 198         }
 199     }
 200
 201   *cols = newcols;
 202 }
 203
 204 /*
 205   Set neighboring columns determined by the spacing-wishes grob property.
 206 */
 207 void
 208 Spacing_spanner::set_explicit_neighbor_columns (Link_array<Grob> cols)
 209 {
 210   for (int i=0; i < cols.size(); i++)
 211     {
 212       SCM right_neighbors = SCM_EOL;
 213       int min_rank = 100000;    // inf.
 214
 215
 216       SCM wishes=  cols[i]->get_grob_property ("spacing-wishes");
 217       for (SCM s =wishes; gh_pair_p (s); s = gh_cdr (s))
 218         {
 219           Item * wish = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
 220
 221           Item * lc = wish->column_l ();
 222           Grob * right = Note_spacing::right_column (wish);
 223
 224           if (!right)
 225             continue;
 226
 227           Item * rc = dynamic_cast<Item*> (right);
 228
 229           int right_rank = Paper_column::rank_i (rc);
 230           int left_rank = Paper_column::rank_i (lc);
 231
 232           /*
 233             update the left column.
 234            */
 235           if (right_rank <= min_rank)
 236             {
 237               if (right_rank < min_rank)
 238                 right_neighbors  =SCM_EOL;
 239
 240               min_rank = right_rank;
 241               right_neighbors = gh_cons (wish->self_scm (), right_neighbors);
 242             }
 243
 244           /*
 245             update the right column of the wish.
 246            */
 247           int maxrank = 0;
 248           SCM left_neighs = rc->get_grob_property ("left-neighbors");
 249           if (gh_pair_p (left_neighs)
 250               && unsmob_grob (gh_car (left_neighs)))
 251             {
 252               Item * it = dynamic_cast<Item*> (unsmob_grob (gh_car (left_neighs)));
 253               maxrank = Paper_column::rank_i (it->column_l());
 254             }
 255
 256           if (left_rank >= maxrank)
 257             {
 258               if (left_rank > maxrank)
 259                 left_neighs = SCM_EOL;
 260
 261               left_neighs = gh_cons (wish->self_scm (), left_neighs);
 262               rc->set_grob_property ("left-neighbors", right_neighbors);
 263             }
 264         }
 265
 266       if (gh_pair_p (right_neighbors))
 267         {
 268           cols[i]->set_grob_property ("right-neighbors", right_neighbors);
 269         }
 270     }
 271 }
 272
 273 /*
 274   Set neighboring columns that have no left/right-neighbor set
 275   yet. Only do breakable non-musical columns, and musical columns.
 276 */
 277 void
 278 Spacing_spanner::set_implicit_neighbor_columns (Link_array<Grob> cols)
 279 {
 280   for (int i = 0; i < cols.size (); i++)
 281     {
 282       Item * it = dynamic_cast<Item*>(cols[i]);
 283       if (!Item::breakable_b (it) && !Paper_column::musical_b (it))
 284         continue;
 285
 286       // it->breakable || it->musical
 287
 288       /*
 289         sloppy with typnig left/right-neighbors should take list, but paper-column found instead.
 290        */
 291       SCM ln = cols[i] ->get_grob_property ("left-neighbors");
 292       if (!gh_pair_p (ln) && i )
 293         {
 294           cols[i]->set_grob_property ("left-neighbors", gh_cons (cols[i-1]->self_scm(), SCM_EOL));
 295         }
 296
 297       SCM rn = cols[i] ->get_grob_property ("right-neighbors");
 298       if (!gh_pair_p (rn) && i < cols.size () - 1)
 299         {
 300           cols[i]->set_grob_property ("right-neighbors", gh_cons (cols[i + 1]->self_scm(), SCM_EOL));
 301         }
 302     }
 303 }
 304
 305
 306 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs,1);
 307 SCM
 308 Spacing_spanner::set_springs (SCM smob)
 309 {
 310   Grob *me = unsmob_grob (smob);
 311
 312   Link_array<Grob> all (me->pscore_l_->line_l_->column_l_arr ()) ;
 313
 314   set_explicit_neighbor_columns (all);
 315   prune_loose_colunms (&all);
 316   set_implicit_neighbor_columns (all);
 317
 318   Rational global_shortest = find_shortest (all);
 319
 320   int j = 0;
 321   for (int i = 1; i < all.size (); i++)
 322     {
 323       Grob *sc = all[i];
 324       if (Item::breakable_b (sc))
 325         {
 326           Link_array<Grob> measure (all.slice (j, i+1));
 327           do_measure (global_shortest, me, &measure);
 328           j = i;
 329         }
 330     }
 331
 332   return SCM_UNSPECIFIED;
 333 }
 334
 335
 336 /*
 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
 339   found duration.
 340
 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
 343   stuff, then.
 344
 345 */
 346 Rational
 347 Spacing_spanner::find_shortest (Link_array<Grob> const &cols)
 348 {
 349   /*
 350     ascending in duration
 351    */
 352   Array<Rational> durations;
 353   Array<int> counts;
 354
 355   Rational shortest_in_measure;
 356   shortest_in_measure.set_infinite (1);
 357
 358   for (int i =0 ; i < cols.size (); i++)
 359     {
 360       if (Paper_column::musical_b (cols[i]))
 361         {
 362           Moment *when = unsmob_moment (cols[i]->get_grob_property  ("when"));
 363
 364           /*
 365             ignore grace notes for shortest notes.
 366           */
 367           if (when && when->grace_part_)
 368             continue;
 369
 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_;
 374         }
 375       else if (!shortest_in_measure.infty_b()
 376                && Item::breakable_b (cols[i]))
 377         {
 378           int j = 0;
 379           for (; j < durations.size(); j++)
 380             {
 381               if (durations[j] > shortest_in_measure)
 382                 {
 383                   counts.insert (1, j);
 384                   durations.insert (shortest_in_measure, j);
 385                   break;
 386                 }
 387               else if (durations[j] == shortest_in_measure)
 388                 {
 389                   counts[j]++;
 390                   break;
 391                 }
 392             }
 393
 394           if (durations.size() == j)
 395             {
 396               durations.push (shortest_in_measure);
 397               counts.push (1);
 398             }
 399
 400           shortest_in_measure.set_infinite(1);
 401         }
 402     }
 403
 404   int max_idx = -1;
 405   int max_count = 0;
 406   for (int i =durations.size(); i--;)
 407     {
 408       if (counts[i] >= max_count)
 409         {
 410           max_idx = i;
 411           max_count = counts[i];
 412         }
 413
 414       //      printf ("Den %d/%d, c %d\n", durations[i].num (), durations[i].den (), counts[i]);
 415     }
 416
 417   /*
 418     TODO: 1/8 should be adjustable?
 419    */
 420   Rational d = Rational (1,8);
 421   if (max_idx >= 0)
 422     d = d <? durations[max_idx] ;
 423
 424   return d;
 425 }
 426
 427 void
 428 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
 429 {
 430
 431   Real headwid =       gh_scm2double (me->get_grob_property ("spacing-increment"));
 432   for (int i= 0; i < cols->size () - 1; i++)
 433     {
 434       Item * l = dynamic_cast<Item*> (cols->elem (i));
 435       Item * r =  dynamic_cast<Item*> (cols->elem (i+1));
 436
 437       Paper_column * lc = dynamic_cast<Paper_column*> (l);
 438       Paper_column * rc = dynamic_cast<Paper_column*> (r);
 439
 440       if (!Paper_column::musical_b (l))
 441         {
 442           breakable_column_spacing (l, r);
 443
 444           /*
 445
 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.
 449
 450            */
 451           Item *lb = l->find_prebroken_piece (RIGHT);
 452           Item *rb = r->find_prebroken_piece (LEFT);
 453
 454           if (lb)
 455             breakable_column_spacing (lb,r);
 456
 457           if (rb)
 458             breakable_column_spacing (l, rb);
 459           if (lb && rb)
 460             breakable_column_spacing (lb, rb);
 461
 462           continue ;
 463         }
 464       bool expand_only = false;
 465       Real note_space = note_spacing (me, lc, rc, shortest, &expand_only);
 466
 467       Real hinterfleisch = note_space;
 468
 469
 470       SCM seq  = lc->get_grob_property ("right-neighbors");
 471
 472       /*
 473         hinterfleisch = hind-meat = amount of space following a note.
 474
 475
 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.  */
 479
 480       Real stretch_distance = note_space;
 481
 482       hinterfleisch = -1.0;
 483       Real max_factor = 0.0;
 484       for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
 485         {
 486           Grob * wish = unsmob_grob (gh_car (s));
 487
 488           if (Note_spacing::left_column (wish) != lc
 489               || Note_spacing::right_column (wish) != rc)
 490             continue;
 491
 492           /*
 493             This is probably a waste of time in the case of polyphonic
 494             music.  */
 495           if (Note_spacing::has_interface (wish))
 496             {
 497               hinterfleisch = hinterfleisch >?
 498                 ( - headwid +
 499
 500                   (note_space + Note_spacing::get_spacing (wish))
 501                   *gh_scm2double (wish->get_grob_property ("space-factor"))
 502
 503                   + Note_spacing::stem_dir_correction (wish));
 504             }
 505         }
 506
 507       if (hinterfleisch < 0)
 508         {
 509           // maybe should issue a programming error.
 510           hinterfleisch = note_space;
 511         }
 512       else
 513         stretch_distance -= headwid; // why?
 514
 515       if (max_factor == 0.0)
 516         max_factor = 1.0;
 517
 518       Spaceable_grob::add_spring (l, r, max_factor *  hinterfleisch,  1 / stretch_distance, expand_only);
 519
 520       /*
 521         TODO: we should have a separate routine determining this distance!
 522        */
 523       if (Item *rb = r->find_prebroken_piece (LEFT))
 524         {
 525           Spaceable_grob::add_spring (l, rb, max_factor *  hinterfleisch,  1 / stretch_distance, expand_only);
 526         }
 527     }
 528
 529 }
 530
 531 /*
 532   Read hints from L (todo: R) and generate springs.
 533  */
 534 void
 535 Spacing_spanner::breakable_column_spacing (Item* l, Item *r)
 536 {
 537   Real max_fixed = -infinity_f;
 538   Real max_space = -infinity_f;
 539
 540   for (SCM s = l->get_grob_property ("spacing-wishes");
 541        gh_pair_p (s); s = gh_cdr (s))
 542     {
 543       Grob * spacing_grob = unsmob_grob (gh_car (s));
 544
 545       if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 546         continue;
 547
 548       Real space;
 549       Real fixed_space;
 550
 551       Staff_spacing::get_spacing_params (spacing_grob,
 552                                          &space, &fixed_space);
 553       if (space > max_space)
 554         {
 555           max_space = space;
 556           max_fixed = fixed_space;
 557         }
 558     }
 559
 560   if (isinf (max_space))
 561     {
 562       programming_error ("No pref spacing found");
 563       max_space = 2.0;
 564       max_fixed = 1.0;
 565     }
 566
 567   Spaceable_grob::add_spring (l, r, max_space,  1/(max_space - max_fixed), false);
 568 }
 569
 570
 571 /**
 572   Get the measure wide ant for arithmetic spacing.
 573   */
 574 Real
 575 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
 576 {
 577   Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
 578
 579   if (d < shortest)
 580     {
 581       Rational ratio = d.main_part_ / shortest;
 582
 583       *expand_only = true;
 584       return (0.5 + 0.5 * double (ratio)) * k ;
 585     }
 586   else
 587     {
 588       /*
 589           @see
 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.
 593        */
 594       Real log =  log_2 (shortest);
 595       k -= log;
 596       Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
 597       *expand_only = false;
 598
 599       return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
 600     }
 601 }
 602
 603 Real
 604 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
 605                                Moment shortest, bool * expand_only)
 606 {
 607   Moment shortest_playing_len = 0;
 608   SCM s = lc->get_grob_property ("shortest-playing-duration");
 609
 610   if (unsmob_moment (s))
 611     shortest_playing_len = *unsmob_moment (s);
 612
 613   if (! shortest_playing_len.to_bool ())
 614     {
 615       programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
 616       shortest_playing_len = 1;
 617     }
 618
 619   Moment delta_t = Paper_column::when_mom (rc) - Paper_column::when_mom (lc);
 620   Real dist = 0.0;
 621
 622   if (delta_t.main_part_)
 623     {
 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_);
 626     }
 627   else if (delta_t.grace_part_)
 628     {
 629       /*
 630         TODO: figure out how to space grace notes.
 631       */
 632       dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
 633
 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);
 638
 639       dist *= grace_fact;
 640     }
 641
 642
 643   return dist;
 644 }
 645