lily/spacing-spanner.cc

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