lily/spacing-spanner.cc

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