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       Item *r = dynamic_cast<Item*> (cols[i]);
 220       Item *rb = r->find_prebroken_piece (LEFT);
 221
 222       if (Separation_item::is_empty (r) && (!rb || Separation_item::is_empty (rb)))
 223         continue;
 224
 225       Skyline_pair *skys = Skyline_pair::unsmob (r->get_property ("horizontal-skylines"));
 226       Real right_stickout = skys ? (*skys)[LEFT].max_height () : 0.0;
 227
 228       Drul_array<Item*> r_cols (r, rb);
 229       Drul_array<Real> cur_dist (0.0, 0.0);
 230
 231       /* This is an inner loop and hence it is potentially quadratic. However, we only continue
 232          as long as there is a rod to insert. Therefore, this loop will usually only execute
 233          a constant number of times per iteration of the outer loop. */
 234       for (vsize j = i; j--;)
 235         {
 236           Item *l = dynamic_cast<Item*> (cols[j]);
 237           Item *lb = l->find_prebroken_piece (RIGHT);
 238           Skyline_pair *skys = Skyline_pair::unsmob (l->get_property ("horizontal-skylines"));
 239           Real left_stickout = skys ? (*skys)[RIGHT].max_height () : 0.0;
 240           bool done = true;
 241
 242           Direction d = LEFT;
 243           do
 244             {
 245               if (j < i-1)
 246                 cur_dist[d] += distances[j];
 247
 248               Item *r_col = r_cols[d];
 249               bool touches = right_stickout - left_stickout + cur_dist[d] < 0.0;
 250               Real dist = 0.0;
 251
 252               /* we set a distance for the line-starter column even if it's non-broken counterpart
 253                  doesn't touch the right column. */
 254               if (lb)
 255                 Separation_item::set_distance (lb, r_col, padding);
 256
 257               if (touches || j == i-1)
 258                 dist = Separation_item::set_distance (l, r_col, padding);
 259
 260               if (j == i-1 && d == LEFT)
 261                 distances.push_back (dist);
 262
 263               if (j == i-1)
 264                 cur_dist[d] = distances[j];
 265
 266               done = done && !touches;
 267             }
 268           while (flip (&d) != LEFT && rb);
 269
 270           /* we need the empty check for gregorian notation, where there are a lot of
 271              extraneous paper-columns that we need to skip over */
 272           if (done && !Separation_item::is_empty (l))
 273             break;
 274         }
 275     }
 276 }
 277
 278
 279 void
 280 Spacing_spanner::generate_springs (Grob *me,
 281                                    vector<Grob*> const &cols,
 282                                    Spacing_options const *options)
 283 {
 284   Paper_column *prev = dynamic_cast<Paper_column*> (cols[0]);
 285   for (vsize i = 1; i < cols.size (); i++)
 286     {
 287       Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
 288       Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i+1]) : 0;
 289
 290       generate_pair_spacing (me, prev, col, next, options);
 291
 292       prev = col;
 293     }
 294
 295   set_column_rods (cols, 0.1); // FIXME: padding
 296 }
 297
 298 /*
 299   Generate the space between two musical columns LEFT_COL and RIGHT_COL.
 300 */
 301 void
 302 Spacing_spanner::musical_column_spacing (Grob *me,
 303                                          Item *left_col,
 304                                          Item *right_col,
 305                                          Spacing_options const *options)
 306 {
 307   Real base_note_space = note_spacing (me, left_col, right_col, options);
 308   Spring spring;
 309
 310   if (options->stretch_uniformly_)
 311     spring = Spring (base_note_space, 0.0);
 312   else
 313     {
 314       vector<Spring> springs;
 315       extract_grob_set (left_col, "right-neighbors", neighbors);
 316
 317       for (vsize i = 0; i < neighbors.size (); i++)
 318         {
 319           Grob *wish = neighbors[i];
 320
 321           Item *wish_rcol = Spacing_interface::right_column (wish);
 322           if (Spacing_interface::left_column (wish) != left_col
 323               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 324             continue;
 325
 326           /*
 327             This is probably a waste of time in the case of polyphonic
 328             music.  */
 329           if (Note_spacing::has_interface (wish))
 330             springs.push_back (Note_spacing::get_spacing (wish, right_col, base_note_space, options->increment_));
 331         }
 332
 333       if (springs.empty ())
 334         {
 335
 336           if (!Paper_column::is_musical (right_col))
 337             {
 338               /*
 339                 There used to be code that examined left_col->extent
 340                 (X_AXIS), but this is resulted in unexpected wide
 341                 spacing, because the width of s^"text" output is also
 342                 taken into account here.
 343                */
 344               spring = Spring (max (base_note_space, options->increment_),
 345                                options->increment_);
 346             }
 347           else
 348             {
 349               /*
 350                 Fixed should be 0.0. If there are no spacing wishes, we're
 351                 likely dealing with polyphonic spacing of hemiolas.
 352
 353                 We used to have min_distance_ = options->increment_
 354
 355                 but this can lead to numeric instability problems when we
 356                 do
 357
 358                 inverse_strength = (distance_ - min_distance_)
 359
 360               */
 361               spring = Spring (base_note_space, 0.0);
 362             }
 363         }
 364       else
 365         spring = merge_springs (springs);
 366     }
 367
 368   if (Paper_column::when_mom (right_col).grace_part_
 369       && !Paper_column::when_mom (left_col).grace_part_)
 370     {
 371       /*
 372         Ugh. 0.8 is arbitrary.
 373       */
 374       spring *= 0.8;
 375     }
 376
 377   /*
 378     TODO: make sure that the space doesn't exceed the right margin.
 379   */
 380   if (options->packed_)
 381     {
 382       /*
 383         In packed mode, pack notes as tight as possible.  This makes
 384         sense mostly in combination with raggedright mode: the notes
 385         are then printed at minimum distance.  This is mostly useful
 386         for ancient notation, but may also be useful for some flavours
 387         of contemporary music.  If not in raggedright mode, lily will
 388         pack as much bars of music as possible into a line, but the
 389         line will then be stretched to fill the whole linewidth.
 390       */
 391       spring.set_distance (spring.min_distance ());
 392       spring.set_inverse_stretch_strength (1.0);
 393     }
 394
 395   Spaceable_grob::add_spring (left_col, right_col, spring);
 396 }
 397
 398 /*
 399   Check if COL fills the whole measure.
 400  */
 401 bool
 402 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 403 {
 404   System *sys = get_root_system (me);
 405   Item *next = sys->column (col->get_column ()->get_rank () + 1);
 406   if (!next)
 407     return false;
 408
 409   if (Paper_column::is_musical (next)
 410       || Paper_column::is_musical (left)
 411       || !Paper_column::is_musical (col)
 412       || !Paper_column::is_used (next))
 413     return false;
 414
 415   Moment dt =
 416     Paper_column::when_mom (next) - Paper_column::when_mom (col);
 417
 418   Moment *len = unsmob_moment (left->get_property ("measure-length"));
 419   if (!len)
 420     return false;
 421
 422   /*
 423     Don't check for exact measure length, since ending measures are
 424     often shortened due to pickups.
 425    */
 426   if (dt.main_part_ > len->main_part_ / Rational (2)
 427       && (next->is_broken ()
 428           || next->break_status_dir ()))
 429     return true;
 430
 431   return false;
 432 }
 433
 434 /*
 435   Read hints from L and generate springs.
 436 */
 437 void
 438 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 439                                            Spacing_options const *options)
 440 {
 441   vector<Spring> springs;
 442   Spring spring;
 443
 444   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 445
 446   if (dt == Moment (0, 0))
 447     {
 448       extract_grob_set (l, "spacing-wishes", wishes);
 449
 450       for (vsize i = 0; i < wishes.size (); i++)
 451         {
 452           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 453
 454           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 455             continue;
 456
 457           /*
 458             column for the left one settings should be ok due automatic
 459             pointer munging.
 460           */
 461           assert (spacing_grob->get_column () == l);
 462
 463           springs.push_back (Staff_spacing::get_spacing (spacing_grob, r));
 464         }
 465     }
 466
 467   if (springs.empty ())
 468     spring = standard_breakable_column_spacing (me, l, r, options);
 469   else
 470     spring = merge_springs (springs);
 471
 472   if (Paper_column::when_mom (r).grace_part_)
 473     {
 474       /*
 475         Correct for grace notes.
 476
 477         Ugh. The 0.8 is arbitrary.
 478       */
 479       spring *= 0.8;
 480     }
 481
 482   if (Paper_column::is_musical (r)
 483       && l->break_status_dir () == CENTER
 484       && fills_measure (me, l, r))
 485     {
 486       spring.set_distance (spring.distance () + 1.0);
 487       spring.set_default_strength ();
 488     }
 489
 490   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 491     {
 492       spring.set_min_distance (0.0);
 493       spring.set_default_strength ();
 494     }
 495
 496   Spaceable_grob::add_spring (l, r, spring);
 497 }
 498
 499 ADD_INTERFACE (Spacing_spanner,
 500                "The space taken by a note is dependent on its duration. Doubling a\n"
 501                "duration adds spacing-increment to the space. The most common shortest\n"
 502                "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
 503                "spaced proportonial to their duration.\n"
 504                "\n"
 505                "Typically, the increment is the width of a black note head.  In a\n"
 506                "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
 507                "gets 2 note heads width (i.e. the space following a note is 1 note\n"
 508                "head width) A 16th note is followed by 0.5 note head width. The\n"
 509                "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
 510
 511
 512                "average-spacing-wishes "
 513                "base-shortest-duration "
 514                "common-shortest-duration "
 515                "packed-spacing "
 516                "shortest-duration-space "
 517                "spacing-increment "
 518                "strict-grace-spacing "
 519                "strict-note-spacing "
 520                "uniform-stretching "
 521
 522                );
 523