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       spring.set_distance (max (left_col->extent (left_col, X_AXIS)[RIGHT],
 409                                 spring.min_distance ()));
 410       spring.set_inverse_stretch_strength (1.0);
 411     }
 412
 413   Spaceable_grob::add_spring (left_col, right_col, spring);
 414 }
 415
 416 /*
 417   Check if COL fills the whole measure.
 418  */
 419 bool
 420 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 421 {
 422   System *sys = get_root_system (me);
 423   Item *next = sys->column (col->get_column ()->get_rank () + 1);
 424   if (!next)
 425     return false;
 426
 427   if (Paper_column::is_musical (next)
 428       || Paper_column::is_musical (left)
 429       || !Paper_column::is_musical (col)
 430       || !Paper_column::is_used (next))
 431     return false;
 432
 433   Moment dt =
 434     Paper_column::when_mom (next) - Paper_column::when_mom (col);
 435
 436   Moment *len = unsmob_moment (left->get_property ("measure-length"));
 437   if (!len)
 438     return false;
 439
 440   /*
 441     Don't check for exact measure length, since ending measures are
 442     often shortened due to pickups.
 443    */
 444   if (dt.main_part_ > len->main_part_ / Rational (2)
 445       && (next->is_broken ()
 446           || next->break_status_dir ()))
 447     return true;
 448
 449   return false;
 450 }
 451
 452 /*
 453   Read hints from L and generate springs.
 454 */
 455 void
 456 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 457                                            Spacing_options const *options)
 458 {
 459   vector<Spring> springs;
 460   Spring spring;
 461
 462   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 463
 464   if (dt == Moment (0, 0))
 465     {
 466       extract_grob_set (l, "spacing-wishes", wishes);
 467
 468       for (vsize i = 0; i < wishes.size (); i++)
 469         {
 470           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 471
 472           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 473             continue;
 474
 475           /*
 476             column for the left one settings should be ok due automatic
 477             pointer munging.
 478           */
 479           assert (spacing_grob->get_column () == l);
 480
 481           springs.push_back (Staff_spacing::get_spacing (spacing_grob, r));
 482         }
 483     }
 484
 485   if (springs.empty ())
 486     spring = standard_breakable_column_spacing (me, l, r, options);
 487   else
 488     spring = merge_springs (springs);
 489
 490   if (Paper_column::when_mom (r).grace_part_)
 491     {
 492       /*
 493         Correct for grace notes.
 494
 495         Ugh. The 0.8 is arbitrary.
 496       */
 497       spring *= 0.8;
 498     }
 499
 500   if (Paper_column::is_musical (r)
 501       && l->break_status_dir () == CENTER
 502       && fills_measure (me, l, r))
 503     {
 504       spring.set_distance (spring.distance () + 1.0);
 505       spring.set_default_strength ();
 506     }
 507
 508   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 509     {
 510       spring.set_min_distance (0.0);
 511       spring.set_default_strength ();
 512     }
 513
 514   Spaceable_grob::add_spring (l, r, spring);
 515 }
 516
 517 ADD_INTERFACE (Spacing_spanner,
 518                "The space taken by a note is dependent on its duration."
 519                "  Doubling a duration adds @code{spacing-increment} to the"
 520                " space.  The most common shortest note gets"
 521                " @code{shortest-duration-space}.  Notes that are even shorter"
 522                " are spaced proportonial to their duration.\n"
 523                "\n"
 524                "Typically, the increment is the width of a black note head."
 525                "  In a piece with lots of 8th notes, and some 16th notes, the"
 526                " eighth note gets a 2@tie{}note heads width (i.e., the space"
 527                " following a note is a 1@tie{}note head width).  A 16th note"
 528                " is followed by 0.5 note head width.  The quarter note is"
 529                " followed by 3@tie{}NHW, the half by 4@tie{}NHW, etc.",
 530
 531                /* properties */
 532                "average-spacing-wishes "
 533                "base-shortest-duration "
 534                "common-shortest-duration "
 535                "packed-spacing "
 536                "shortest-duration-space "
 537                "spacing-increment "
 538                "strict-grace-spacing "
 539                "strict-note-spacing "
 540                "uniform-stretching "
 541                );
 542