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