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