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 void
 434 Spacing_spanner::do_measure (Rational shortest, Grob*me, Link_array<Grob> *cols)
 435 {
 436
 437   Real headwid =       gh_scm2double (me->get_grob_property ("spacing-increment"));
 438   for (int i= 0; i < cols->size () - 1; i++)
 439     {
 440       Item * l = dynamic_cast<Item*> (cols->elem (i));
 441       Item * r =  dynamic_cast<Item*> (cols->elem (i+1));
 442
 443       Paper_column * lc = dynamic_cast<Paper_column*> (l);
 444       Paper_column * rc = dynamic_cast<Paper_column*> (r);
 445
 446       if (!Paper_column::musical_b (l))
 447         {
 448           breakable_column_spacing (l, r);
 449
 450           /*
 451
 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.
 455
 456            */
 457           Item *lb = l->find_prebroken_piece (RIGHT);
 458           Item *rb = r->find_prebroken_piece (LEFT);
 459
 460           if (lb)
 461             breakable_column_spacing (lb,r);
 462
 463           if (rb)
 464             breakable_column_spacing (l, rb);
 465           if (lb && rb)
 466             breakable_column_spacing (lb, rb);
 467
 468           continue ;
 469         }
 470
 471
 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);
 475     }
 476 }
 477
 478 void
 479 Spacing_spanner::musical_column_spacing (Grob *me, Item * lc, Item *rc, Real increment, Rational shortest)
 480 {
 481   bool expand_only = false;
 482   Real base_note_space = note_spacing (me, lc, rc, shortest, &expand_only);
 483
 484   Real max_note_space = -infinity_f;
 485   Real max_fixed_note_space = -infinity_f;
 486
 487   SCM seq  = lc->get_grob_property ("right-neighbors");
 488
 489   /*
 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.
 493   */
 494   for (SCM s = seq; gh_pair_p (s); s = ly_cdr (s))
 495     {
 496       Grob * wish = unsmob_grob (gh_car (s));
 497
 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_))
 501         continue;
 502
 503       /*
 504         This is probably a waste of time in the case of polyphonic
 505         music.  */
 506       if (Note_spacing::has_interface (wish))
 507         {
 508           Real space =0.0;
 509           Real fixed =0.0;
 510
 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;
 514         }
 515
 516     }
 517
 518   if (max_note_space < 0)
 519     {
 520       max_note_space = base_note_space;
 521       max_fixed_note_space = increment;
 522     }
 523
 524   Spaceable_grob::add_spring (lc, rc, max_note_space,  1 / (max_note_space -max_fixed_note_space), expand_only);
 525 }
 526
 527
 528 /*
 529   Read hints from L (todo: R) and generate springs.
 530  */
 531 void
 532 Spacing_spanner::breakable_column_spacing (Item* l, Item *r)
 533 {
 534   Real max_fixed = -infinity_f;
 535   Real max_space = -infinity_f;
 536
 537   for (SCM s = l->get_grob_property ("spacing-wishes");
 538        gh_pair_p (s); s = gh_cdr (s))
 539     {
 540       Item * spacing_grob = dynamic_cast<Item*> (unsmob_grob (gh_car (s)));
 541
 542       if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 543         continue;
 544
 545       Real space;
 546       Real fixed_space;
 547
 548       /*
 549         column for the left one settings should be ok due automatic
 550         pointer munging.
 551
 552       */
 553       assert (spacing_grob-> column_l () == l);
 554
 555       Staff_spacing::get_spacing_params (spacing_grob,
 556                                          &space, &fixed_space);
 557       if (space > max_space)
 558         {
 559           max_space = space;
 560           max_fixed = fixed_space;
 561         }
 562     }
 563
 564   if (isinf (max_space))
 565     {
 566       programming_error ("No pref spacing found");
 567       max_space = 2.0;
 568       max_fixed = 1.0;
 569     }
 570
 571
 572   if (l->break_status_dir() == RIGHT
 573       && Paper_column::when_mom (l) == Paper_column::when_mom (r))
 574     {
 575       /* Start of line: this space is not stretchable */
 576       max_fixed = max_space;
 577     }
 578
 579   /*
 580     Hmm.  we do 1/0 in the next thing. Perhaps we should check if this
 581     works on all architectures.
 582    */
 583
 584   Spaceable_grob::add_spring (l, r, max_space,  1/(max_space - max_fixed), false);
 585 }
 586
 587
 588 /**
 589   Get the measure wide ant for arithmetic spacing.
 590   */
 591 Real
 592 Spacing_spanner::get_duration_space (Grob*me, Moment d, Rational shortest, bool * expand_only)
 593 {
 594   Real k = gh_scm2double (me->get_grob_property ("shortest-duration-space"));
 595
 596   if (d < shortest)
 597     {
 598       Rational ratio = d.main_part_ / shortest;
 599
 600       *expand_only = true;
 601       return (0.5 + 0.5 * double (ratio)) * k ;
 602     }
 603   else
 604     {
 605       /*
 606           @see
 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.
 610        */
 611       Real log =  log_2 (shortest);
 612       k -= log;
 613       Rational compdur = d.main_part_ + d.grace_part_ /Rational (3);
 614       *expand_only = false;
 615
 616       return (log_2 (compdur) + k) * gh_scm2double (me->get_grob_property ("spacing-increment"));
 617     }
 618 }
 619
 620 Real
 621 Spacing_spanner::note_spacing (Grob*me, Grob *lc, Grob *rc,
 622                                Moment shortest, bool * expand_only)
 623 {
 624   Moment shortest_playing_len = 0;
 625   SCM s = lc->get_grob_property ("shortest-playing-duration");
 626
 627   if (unsmob_moment (s))
 628     shortest_playing_len = *unsmob_moment (s);
 629
 630   if (! shortest_playing_len.to_bool ())
 631     {
 632       programming_error ("can't find a ruling note at " + Paper_column::when_mom (lc).str ());
 633       shortest_playing_len = 1;
 634     }
 635
 636   Moment delta_t = Paper_column::when_mom (rc) - Paper_column::when_mom (lc);
 637   Real dist = 0.0;
 638
 639   if (delta_t.main_part_)
 640     {
 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_);
 643     }
 644   else if (delta_t.grace_part_)
 645     {
 646       /*
 647         TODO: figure out how to space grace notes.
 648       */
 649       dist = get_duration_space (me, shortest, shortest.main_part_, expand_only);
 650
 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);
 655
 656       dist *= grace_fact;
 657     }
 658
 659
 660   return dist;
 661 }
 662