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