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