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--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #include "spacing-spanner.hh"
  10
  11 #include <math.h>
  12 #include <cstdio>
  13
  14 #include "spacing-options.hh"
  15 #include "international.hh"
  16 #include "main.hh"
  17 #include "moment.hh"
  18 #include "note-spacing.hh"
  19 #include "output-def.hh"
  20 #include "paper-column.hh"
  21 #include "paper-score.hh"
  22 #include "pointer-group-interface.hh"
  23 #include "separation-item.hh"
  24 #include "skyline-pair.hh"
  25 #include "spaceable-grob.hh"
  26 #include "spacing-interface.hh"
  27 #include "staff-spacing.hh"
  28 #include "system.hh"
  29 #include "warn.hh"
  30
  31 vector<Grob*>
  32 Spacing_spanner::get_columns (Grob *me_grob)
  33 {
  34   Spanner *me = dynamic_cast<Spanner*> (me_grob);
  35   vector<Grob*> all (get_root_system (me)->used_columns ());
  36   vsize start = binary_search (all, (Grob*)me->get_bound (LEFT),
  37                                &Paper_column::less_than);
  38   vsize end = binary_search (all, (Grob*) me->get_bound (RIGHT),
  39                              &Paper_column::less_than);
  40
  41   all = vector<Grob*>::vector<Grob*> (all.begin () + start,
  42                                       all.begin () + end + 1);
  43   return all;
  44 }
  45
  46 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
  47 SCM
  48 Spacing_spanner::set_springs (SCM smob)
  49 {
  50   Spanner *me = unsmob_spanner (smob);
  51
  52   /*
  53     can't use get_system () ? --hwn.
  54   */
  55   Spacing_options options;
  56   options.init_from_grob (me);
  57   vector<Grob*> cols = Spacing_spanner::get_columns (me);
  58   set_explicit_neighbor_columns (cols);
  59
  60   prune_loose_columns (me, &cols, &options);
  61   set_implicit_neighbor_columns (cols);
  62   generate_springs (me, cols, &options);
  63
  64   return SCM_UNSPECIFIED;
  65 }
  66
  67 /*
  68   We want the shortest note that is also "common" in the piece, so we
  69   find the shortest in each measure, and take the most frequently
  70   found duration.
  71
  72   This probably gives weird effects with modern music, where every
  73   note has a different duration, but hey, don't write that kind of
  74   stuff, then.
  75 */
  76
  77 MAKE_SCHEME_CALLBACK (Spacing_spanner, calc_common_shortest_duration, 1);
  78 SCM
  79 Spacing_spanner::calc_common_shortest_duration (SCM grob)
  80 {
  81   Spanner *me = unsmob_spanner (grob);
  82
  83   vector<Grob*> cols (get_columns (me));
  84
  85   /*
  86     ascending in duration
  87   */
  88   vector<Rational> durations;
  89   vector<int> counts;
  90
  91   Rational shortest_in_measure;
  92   shortest_in_measure.set_infinite (1);
  93
  94   for (vsize i = 0; i < cols.size (); i++)
  95     {
  96       if (Paper_column::is_musical (cols[i]))
  97         {
  98           Moment *when = unsmob_moment (cols[i]->get_property ("when"));
  99
 100           /*
 101             ignore grace notes for shortest notes.
 102           */
 103           if (when && when->grace_part_)
 104             continue;
 105
 106           SCM st = cols[i]->get_property ("shortest-starter-duration");
 107           Moment this_shortest = *unsmob_moment (st);
 108           assert (this_shortest.to_bool ());
 109           shortest_in_measure = min (shortest_in_measure, this_shortest.main_part_);
 110         }
 111       else if (!shortest_in_measure.is_infinity ()
 112                && Paper_column::is_breakable (cols[i]))
 113         {
 114           vsize j = 0;
 115           for (; j < durations.size (); j++)
 116             {
 117               if (durations[j] > shortest_in_measure)
 118                 {
 119                   counts.insert (counts.begin () + j, 1);
 120                   durations.insert (durations.begin () + j, shortest_in_measure);
 121                   break;
 122                 }
 123               else if (durations[j] == shortest_in_measure)
 124                 {
 125                   counts[j]++;
 126                   break;
 127                 }
 128             }
 129
 130           if (durations.size () == j)
 131             {
 132               durations.push_back (shortest_in_measure);
 133               counts.push_back (1);
 134             }
 135
 136           shortest_in_measure.set_infinite (1);
 137         }
 138     }
 139
 140   int max_idx = -1;
 141   int max_count = 0;
 142   for (vsize i = durations.size (); i--;)
 143     {
 144       if (counts[i] >= max_count)
 145         {
 146           max_idx = i;
 147           max_count = counts[i];
 148         }
 149     }
 150
 151   SCM bsd = me->get_property ("base-shortest-duration");
 152   Rational d = Rational (1, 8);
 153   if (Moment *m = unsmob_moment (bsd))
 154     d = m->main_part_;
 155
 156   if (max_idx >= 0)
 157     d = min (d, durations[max_idx]);
 158
 159   return Moment (d).smobbed_copy ();
 160 }
 161
 162 void
 163 Spacing_spanner::generate_pair_spacing (Grob *me,
 164                                         Paper_column *left_col, Paper_column *right_col,
 165                                         Paper_column *after_right_col,
 166                                         Spacing_options const *options)
 167 {
 168   if (Paper_column::is_musical (left_col))
 169     {
 170       if (!Paper_column::is_musical (right_col)
 171           && options->float_nonmusical_columns_
 172           && after_right_col
 173           && Paper_column::is_musical (after_right_col))
 174         {
 175           /*
 176             TODO: should generate rods to prevent collisions.
 177           */
 178           musical_column_spacing (me, left_col, after_right_col, options);
 179           right_col->set_object ("between-cols", scm_cons (left_col->self_scm (),
 180                                                            after_right_col->self_scm ()));
 181         }
 182       else
 183         musical_column_spacing (me, left_col, right_col, options);
 184
 185       if (Item *rb = right_col->find_prebroken_piece (LEFT))
 186         musical_column_spacing (me, left_col, rb, options);
 187     }
 188   else
 189     {
 190       /*
 191         The case that the right part is broken as well is rather
 192         rare, but it is possible, eg. with a single empty measure,
 193         or if one staff finishes a tad earlier than the rest.
 194       */
 195       Item *lb = left_col->find_prebroken_piece (RIGHT);
 196       Item *rb = right_col->find_prebroken_piece (LEFT);
 197
 198       if (left_col && right_col)
 199         breakable_column_spacing (me, left_col, right_col, options);
 200
 201       if (lb && right_col)
 202         breakable_column_spacing (me, lb, right_col, options);
 203
 204       if (left_col && rb)
 205         breakable_column_spacing (me, left_col, rb, options);
 206
 207       if (lb && rb)
 208         breakable_column_spacing (me, lb, rb, options);
 209     }
 210 }
 211
 212 static void
 213 set_column_rods (vector<Grob*> const &cols, Real padding)
 214 {
 215   /* distances[i] will be the minimum distance between column i and column i+1 */
 216   vector<Real> distances;
 217
 218   for (vsize i = 1; i < cols.size (); i++)
 219     {
 220       assert (distances.size () == i-1);
 221
 222       Item *r = dynamic_cast<Item*> (cols[i]);
 223       Item *rb = r->find_prebroken_piece (LEFT);
 224
 225       if (Separation_item::is_empty (r) && (!rb || Separation_item::is_empty (rb)))
 226         {
 227           distances.push_back (0);
 228           continue;
 229         }
 230
 231       Skyline_pair *skys = Skyline_pair::unsmob (r->get_property ("horizontal-skylines"));
 232       Real right_stickout = skys ? (*skys)[LEFT].max_height () : 0.0;
 233
 234       /* min rather than max because right-stickout will be negative if the right-hand column
 235          sticks out a lot to the left */
 236       right_stickout = min (right_stickout,
 237                             Separation_item::conditional_skyline (r, cols[i-1]).max_height ());
 238
 239       Drul_array<Item*> r_cols (r, rb);
 240       Drul_array<Real> cur_dist (0.0, 0.0);
 241
 242       /* This is an inner loop and hence it is potentially quadratic. However, we only continue
 243          as long as there is a rod to insert. Therefore, this loop will usually only execute
 244          a constant number of times per iteration of the outer loop. */
 245       for (vsize j = i; j--;)
 246         {
 247           Item *l = dynamic_cast<Item*> (cols[j]);
 248           Item *lb = l->find_prebroken_piece (RIGHT);
 249           Skyline_pair *skys = Skyline_pair::unsmob (l->get_property ("horizontal-skylines"));
 250           Real left_stickout = skys ? (*skys)[RIGHT].max_height () : 0.0;
 251           bool done = true;
 252
 253           Direction d = LEFT;
 254           do
 255             {
 256               if (j < i-1)
 257                 cur_dist[d] += distances[j];
 258
 259               Item *r_col = r_cols[d];
 260               bool touches = right_stickout - left_stickout + cur_dist[d] < 0.0;
 261               Real dist = 0.0;
 262
 263               /* we set a distance for the line-starter column even if it's non-broken counterpart
 264                  doesn't touch the right column. */
 265               if (lb)
 266                 Separation_item::set_distance (lb, r_col, padding);
 267
 268               if (touches || j == i-1)
 269                 dist = Separation_item::set_distance (l, r_col, padding);
 270
 271               if (j == i-1 && d == LEFT)
 272                 distances.push_back (dist);
 273
 274               if (j == i-1)
 275                 cur_dist[d] = distances[j];
 276
 277               done = done && !touches;
 278             }
 279           while (flip (&d) != LEFT && rb);
 280
 281           /* we need the empty check for gregorian notation, where there are a lot of
 282              extraneous paper-columns that we need to skip over */
 283           if (done && !Separation_item::is_empty (l))
 284             break;
 285         }
 286     }
 287 }
 288
 289
 290 void
 291 Spacing_spanner::generate_springs (Grob *me,
 292                                    vector<Grob*> const &cols,
 293                                    Spacing_options const *options)
 294 {
 295   Paper_column *prev = dynamic_cast<Paper_column*> (cols[0]);
 296   for (vsize i = 1; i < cols.size (); i++)
 297     {
 298       Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
 299       Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i+1]) : 0;
 300
 301       generate_pair_spacing (me, prev, col, next, options);
 302
 303       prev = col;
 304     }
 305
 306   set_column_rods (cols, 0.1); // FIXME: padding
 307 }
 308
 309 /*
 310   Generate the space between two musical columns LEFT_COL and RIGHT_COL.
 311 */
 312 void
 313 Spacing_spanner::musical_column_spacing (Grob *me,
 314                                          Item *left_col,
 315                                          Item *right_col,
 316                                          Spacing_options const *options)
 317 {
 318   Real base_note_space = note_spacing (me, left_col, right_col, options);
 319   Spring spring;
 320
 321   if (options->stretch_uniformly_)
 322     spring = Spring (base_note_space, 0.0);
 323   else
 324     {
 325       vector<Spring> springs;
 326       extract_grob_set (left_col, "right-neighbors", neighbors);
 327
 328       for (vsize i = 0; i < neighbors.size (); i++)
 329         {
 330           Grob *wish = neighbors[i];
 331
 332           Item *wish_rcol = Spacing_interface::right_column (wish);
 333           if (Spacing_interface::left_column (wish) != left_col
 334               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 335             continue;
 336
 337           /*
 338             This is probably a waste of time in the case of polyphonic
 339             music.  */
 340           if (Note_spacing::has_interface (wish))
 341             {
 342               Real inc = options->increment_;
 343               Grob *gsp = unsmob_grob (left_col->get_object ("grace-spacing"));
 344               if (gsp && Paper_column::when_mom (left_col).grace_part_)
 345                 {
 346                   Spacing_options grace_opts;
 347                   grace_opts.init_from_grob (gsp);
 348                   inc = grace_opts.increment_;
 349                 }
 350               springs.push_back (Note_spacing::get_spacing (wish, right_col, base_note_space, inc));
 351             }
 352         }
 353
 354       if (springs.empty ())
 355         {
 356
 357           if (!Paper_column::is_musical (right_col))
 358             {
 359               /*
 360                 There used to be code that examined left_col->extent
 361                 (X_AXIS), but this is resulted in unexpected wide
 362                 spacing, because the width of s^"text" output is also
 363                 taken into account here.
 364                */
 365               spring = Spring (max (base_note_space, options->increment_),
 366                                options->increment_);
 367             }
 368           else
 369             {
 370               /*
 371                 Fixed should be 0.0. If there are no spacing wishes, we're
 372                 likely dealing with polyphonic spacing of hemiolas.
 373
 374                 We used to have min_distance_ = options->increment_
 375
 376                 but this can lead to numeric instability problems when we
 377                 do
 378
 379                 inverse_strength = (distance_ - min_distance_)
 380
 381               */
 382               spring = Spring (base_note_space, 0.0);
 383             }
 384         }
 385       else
 386         spring = merge_springs (springs);
 387     }
 388
 389   if (Paper_column::when_mom (right_col).grace_part_
 390       && !Paper_column::when_mom (left_col).grace_part_)
 391     {
 392       /*
 393         Ugh. 0.8 is arbitrary.
 394       */
 395       spring *= 0.8;
 396     }
 397
 398   /*
 399     TODO: make sure that the space doesn't exceed the right margin.
 400   */
 401   if (options->packed_)
 402     {
 403       /*
 404         In packed mode, pack notes as tight as possible.  This makes
 405         sense mostly in combination with raggedright mode: the notes
 406         are then printed at minimum distance.  This is mostly useful
 407         for ancient notation, but may also be useful for some flavours
 408         of contemporary music.  If not in raggedright mode, lily will
 409         pack as much bars of music as possible into a line, but the
 410         line will then be stretched to fill the whole linewidth.
 411       */
 412       spring.set_distance (spring.min_distance ());
 413       spring.set_inverse_stretch_strength (1.0);
 414     }
 415
 416   Spaceable_grob::add_spring (left_col, right_col, spring);
 417 }
 418
 419 /*
 420   Check if COL fills the whole measure.
 421  */
 422 bool
 423 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 424 {
 425   System *sys = get_root_system (me);
 426   Item *next = sys->column (col->get_column ()->get_rank () + 1);
 427   if (!next)
 428     return false;
 429
 430   if (Paper_column::is_musical (next)
 431       || Paper_column::is_musical (left)
 432       || !Paper_column::is_musical (col)
 433       || !Paper_column::is_used (next))
 434     return false;
 435
 436   Moment dt =
 437     Paper_column::when_mom (next) - Paper_column::when_mom (col);
 438
 439   Moment *len = unsmob_moment (left->get_property ("measure-length"));
 440   if (!len)
 441     return false;
 442
 443   /*
 444     Don't check for exact measure length, since ending measures are
 445     often shortened due to pickups.
 446    */
 447   if (dt.main_part_ > len->main_part_ / Rational (2)
 448       && (next->is_broken ()
 449           || next->break_status_dir ()))
 450     return true;
 451
 452   return false;
 453 }
 454
 455 /*
 456   Read hints from L and generate springs.
 457 */
 458 void
 459 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 460                                            Spacing_options const *options)
 461 {
 462   vector<Spring> springs;
 463   Spring spring;
 464
 465   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 466
 467   if (dt == Moment (0, 0))
 468     {
 469       extract_grob_set (l, "spacing-wishes", wishes);
 470
 471       for (vsize i = 0; i < wishes.size (); i++)
 472         {
 473           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 474
 475           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 476             continue;
 477
 478           /*
 479             column for the left one settings should be ok due automatic
 480             pointer munging.
 481           */
 482           assert (spacing_grob->get_column () == l);
 483
 484           springs.push_back (Staff_spacing::get_spacing (spacing_grob, r));
 485         }
 486     }
 487
 488   if (springs.empty ())
 489     spring = standard_breakable_column_spacing (me, l, r, options);
 490   else
 491     spring = merge_springs (springs);
 492
 493   if (Paper_column::when_mom (r).grace_part_)
 494     {
 495       /*
 496         Correct for grace notes.
 497
 498         Ugh. The 0.8 is arbitrary.
 499       */
 500       spring *= 0.8;
 501     }
 502
 503   if (Paper_column::is_musical (r)
 504       && l->break_status_dir () == CENTER
 505       && fills_measure (me, l, r))
 506     {
 507       spring.set_distance (spring.distance () + 1.0);
 508       spring.set_default_strength ();
 509     }
 510
 511   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 512     {
 513       spring.set_min_distance (0.0);
 514       spring.set_default_strength ();
 515     }
 516
 517   Spaceable_grob::add_spring (l, r, spring);
 518 }
 519
 520 ADD_INTERFACE (Spacing_spanner,
 521                "The space taken by a note is dependent on its duration."
 522                "  Doubling a duration adds @code{spacing-increment} to the"
 523                " space.  The most common shortest note gets"
 524                " @code{shortest-duration-space}.  Notes that are even shorter"
 525                " are spaced proportonial to their duration.\n"
 526                "\n"
 527                "Typically, the increment is the width of a black note head."
 528                "  In a piece with lots of 8th notes, and some 16th notes, the"
 529                " eighth note gets a 2@tie{}note heads width (i.e., the space"
 530                " following a note is a 1@tie{}note head width).  A 16th note"
 531                " is followed by 0.5 note head width.  The quarter note is"
 532                " followed by 3@tie{}NHW, the half by 4@tie{}NHW, etc.",
 533
 534                /* properties */
 535                "average-spacing-wishes "
 536                "base-shortest-duration "
 537                "common-shortest-duration "
 538                "packed-spacing "
 539                "shortest-duration-space "
 540                "spacing-increment "
 541                "strict-grace-spacing "
 542                "strict-note-spacing "
 543                "uniform-stretching "
 544                );
 545