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