lily/spacing-spanner.cc

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