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