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--2009 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   vsize max_idx = VPOS;
 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 != VPOS)
 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   Real padding = robust_scm2double (prev->get_property ("padding"), 0.1);
 307   set_column_rods (cols, padding);
 308 }
 309
 310 /*
 311   Generate the space between two musical columns LEFT_COL and RIGHT_COL.
 312 */
 313 void
 314 Spacing_spanner::musical_column_spacing (Grob *me,
 315                                          Item *left_col,
 316                                          Item *right_col,
 317                                          Spacing_options const *options)
 318 {
 319   Real base_note_space = note_spacing (me, left_col, right_col, options);
 320   Spring spring;
 321
 322   if (options->stretch_uniformly_)
 323     spring = Spring (base_note_space, 0.0);
 324   else
 325     {
 326       vector<Spring> springs;
 327       extract_grob_set (left_col, "right-neighbors", neighbors);
 328
 329       for (vsize i = 0; i < neighbors.size (); i++)
 330         {
 331           Grob *wish = neighbors[i];
 332
 333           Item *wish_rcol = Spacing_interface::right_column (wish);
 334           if (Spacing_interface::left_column (wish) != left_col
 335               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 336             continue;
 337
 338           /*
 339             This is probably a waste of time in the case of polyphonic
 340             music.  */
 341           if (Note_spacing::has_interface (wish))
 342             {
 343               Real inc = options->increment_;
 344               Grob *gsp = unsmob_grob (left_col->get_object ("grace-spacing"));
 345               if (gsp && Paper_column::when_mom (left_col).grace_part_)
 346                 {
 347                   Spacing_options grace_opts;
 348                   grace_opts.init_from_grob (gsp);
 349                   inc = grace_opts.increment_;
 350                 }
 351               springs.push_back (Note_spacing::get_spacing (wish, right_col, base_note_space, inc));
 352             }
 353         }
 354
 355       if (springs.empty ())
 356         {
 357
 358           if (!Paper_column::is_musical (right_col))
 359             {
 360               /*
 361                 There used to be code that examined left_col->extent
 362                 (X_AXIS), but this is resulted in unexpected wide
 363                 spacing, because the width of s^"text" output is also
 364                 taken into account here.
 365                */
 366               spring = Spring (max (base_note_space, options->increment_),
 367                                options->increment_);
 368             }
 369           else
 370             {
 371               /*
 372                 Min distance should be 0.0. If there are no spacing
 373                 wishes, we're probably dealing with polyphonic spacing
 374                 of hemiolas.
 375               */
 376               spring = Spring (base_note_space, 0.0);
 377             }
 378         }
 379       else
 380         spring = merge_springs (springs);
 381     }
 382
 383   if (Paper_column::when_mom (right_col).grace_part_
 384       && !Paper_column::when_mom (left_col).grace_part_)
 385     {
 386       /*
 387         Ugh. 0.8 is arbitrary.
 388       */
 389       spring *= 0.8;
 390     }
 391
 392   /*
 393     TODO: make sure that the space doesn't exceed the right margin.
 394   */
 395   if (options->packed_)
 396     {
 397       /*
 398         In packed mode, pack notes as tight as possible.  This makes
 399         sense mostly in combination with ragged-right mode: the notes
 400         are then printed at minimum distance.  This is mostly useful
 401         for ancient notation, but may also be useful for some flavours
 402         of contemporary music.  If not in ragged-right mode, lily will
 403         pack as many bars of music as possible into a line, but the
 404         line will then be stretched to fill the whole linewidth.
 405
 406         Note that we don't actually pack things as tightly as possible:
 407         we don't allow the next column to begin before this one ends.
 408       */
 409       /* FIXME: the else clause below is the "right" thing to do,
 410          but we can't do it because of all the empty columns that the
 411          ligature-engravers leave lying around. In that case, the extent of
 412          the column is incorrect because it includes note-heads that aren't
 413          there. We get around this by only including the column extent if
 414          the left-hand column is "genuine". This is a dirty hack and it
 415          should be fixed in the ligature-engravers. --jneem
 416       */
 417       if (Paper_column::is_extraneous_column_from_ligature (left_col))
 418         spring.set_distance (spring.min_distance ());
 419       else
 420         spring.set_distance (max (left_col->extent (left_col, X_AXIS)[RIGHT],
 421                                   spring.min_distance ()));
 422
 423       spring.set_inverse_stretch_strength (1.0);
 424     }
 425
 426   Spaceable_grob::add_spring (left_col, right_col, spring);
 427 }
 428
 429 /*
 430   Check if COL fills the whole measure.
 431  */
 432 bool
 433 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 434 {
 435   System *sys = get_root_system (me);
 436   Item *next = sys->column (col->get_column ()->get_rank () + 1);
 437   if (!next)
 438     return false;
 439
 440   if (Paper_column::is_musical (next)
 441       || Paper_column::is_musical (left)
 442       || !Paper_column::is_musical (col)
 443       || !Paper_column::is_used (next))
 444     return false;
 445
 446   Moment dt =
 447     Paper_column::when_mom (next) - Paper_column::when_mom (col);
 448
 449   Moment *len = unsmob_moment (left->get_property ("measure-length"));
 450   if (!len)
 451     return false;
 452
 453   /*
 454     Don't check for exact measure length, since ending measures are
 455     often shortened due to pickups.
 456    */
 457   if (dt.main_part_ > len->main_part_ / Rational (2)
 458       && (next->is_broken ()
 459           || next->break_status_dir ()))
 460     return true;
 461
 462   return false;
 463 }
 464
 465 /*
 466   Read hints from L and generate springs.
 467 */
 468 void
 469 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 470                                            Spacing_options const *options)
 471 {
 472   vector<Spring> springs;
 473   Spring spring;
 474
 475   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 476
 477   if (dt == Moment (0, 0))
 478     {
 479       extract_grob_set (l, "spacing-wishes", wishes);
 480
 481       for (vsize i = 0; i < wishes.size (); i++)
 482         {
 483           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 484
 485           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 486             continue;
 487
 488           /*
 489             column for the left one settings should be ok due automatic
 490             pointer munging.
 491           */
 492           assert (spacing_grob->get_column () == l);
 493
 494           springs.push_back (Staff_spacing::get_spacing (spacing_grob, r));
 495         }
 496     }
 497
 498   if (springs.empty ())
 499     spring = standard_breakable_column_spacing (me, l, r, options);
 500   else
 501     spring = merge_springs (springs);
 502
 503   if (Paper_column::when_mom (r).grace_part_)
 504     {
 505       /*
 506         Correct for grace notes.
 507
 508         Ugh. The 0.8 is arbitrary.
 509       */
 510       spring *= 0.8;
 511     }
 512
 513   if (Paper_column::is_musical (r)
 514       && l->break_status_dir () == CENTER
 515       && fills_measure (me, l, r))
 516     {
 517       Real full_measure_extra_space = robust_scm2double (l->get_property ("full-measure-extra-space"), 1.0);
 518       spring.set_distance (spring.distance () + full_measure_extra_space);
 519       spring.set_default_strength ();
 520     }
 521
 522   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 523     {
 524       spring.set_min_distance (0.0);
 525       spring.set_default_strength ();
 526     }
 527
 528   Spaceable_grob::add_spring (l, r, spring);
 529 }
 530
 531 ADD_INTERFACE (Spacing_spanner,
 532                "The space taken by a note is dependent on its duration."
 533                "  Doubling a duration adds @code{spacing-increment} to the"
 534                " space.  The most common shortest note gets"
 535                " @code{shortest-duration-space}.  Notes that are even shorter"
 536                " are spaced proportonial to their duration.\n"
 537                "\n"
 538                "Typically, the increment is the width of a black note head."
 539                "  In a piece with lots of 8th notes, and some 16th notes, the"
 540                " eighth note gets a 2@tie{}note heads width (i.e., the space"
 541                " following a note is a 1@tie{}note head width).  A 16th note"
 542                " is followed by 0.5 note head width.  The quarter note is"
 543                " followed by 3@tie{}NHW, the half by 4@tie{}NHW, etc.",
 544
 545                /* properties */
 546                "average-spacing-wishes "
 547                "base-shortest-duration "
 548                "common-shortest-duration "
 549                "packed-spacing "
 550                "shortest-duration-space "
 551                "spacing-increment "
 552                "strict-grace-spacing "
 553                "strict-note-spacing "
 554                "uniform-stretching "
 555                );
 556