lily/spacing-spanner.cc

   1 /*
   2   spacing-spanner.cc -- implement Spacing_spanner
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1999--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #include "spacing-spanner.hh"
  10
  11 #include <math.h>
  12 #include <cstdio>
  13
  14 #include "spacing-options.hh"
  15 #include "international.hh"
  16 #include "main.hh"
  17 #include "moment.hh"
  18 #include "note-spacing.hh"
  19 #include "output-def.hh"
  20 #include "paper-column.hh"
  21 #include "paper-score.hh"
  22 #include "pointer-group-interface.hh"
  23 #include "separation-item.hh"
  24 #include "spaceable-grob.hh"
  25 #include "spacing-interface.hh"
  26 #include "staff-spacing.hh"
  27 #include "system.hh"
  28 #include "warn.hh"
  29
  30 vector<Grob*>
  31 Spacing_spanner::get_columns (Grob *me_grob)
  32 {
  33   Spanner *me = dynamic_cast<Spanner*> (me_grob);
  34   vector<Grob*> all (get_root_system (me)->used_columns ());
  35   vsize start = binary_search (all, (Grob*)me->get_bound (LEFT),
  36                                &Paper_column::less_than);
  37   vsize end = binary_search (all, (Grob*) me->get_bound (RIGHT),
  38                              &Paper_column::less_than);
  39
  40   all = vector<Grob*>::vector<Grob*> (all.begin () + start,
  41                                       all.begin () + end + 1);
  42   return all;
  43 }
  44
  45 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
  46 SCM
  47 Spacing_spanner::set_springs (SCM smob)
  48 {
  49   Spanner *me = unsmob_spanner (smob);
  50
  51   /*
  52     can't use get_system () ? --hwn.
  53   */
  54   Spacing_options options;
  55   options.init_from_grob (me);
  56   vector<Grob*> cols = Spacing_spanner::get_columns (me);
  57   set_explicit_neighbor_columns (cols);
  58
  59   prune_loose_columns (me, &cols, &options);
  60   set_implicit_neighbor_columns (cols);
  61   generate_springs (me, cols, &options);
  62
  63   return SCM_UNSPECIFIED;
  64 }
  65
  66 /*
  67   We want the shortest note that is also "common" in the piece, so we
  68   find the shortest in each measure, and take the most frequently
  69   found duration.
  70
  71   This probably gives weird effects with modern music, where every
  72   note has a different duration, but hey, don't write that kind of
  73   stuff, then.
  74 */
  75
  76 MAKE_SCHEME_CALLBACK (Spacing_spanner, calc_common_shortest_duration, 1);
  77 SCM
  78 Spacing_spanner::calc_common_shortest_duration (SCM grob)
  79 {
  80   Spanner *me = unsmob_spanner (grob);
  81
  82   vector<Grob*> cols (get_columns (me));
  83
  84   /*
  85     ascending in duration
  86   */
  87   vector<Rational> durations;
  88   vector<int> counts;
  89
  90   Rational shortest_in_measure;
  91   shortest_in_measure.set_infinite (1);
  92
  93   for (vsize i = 0; i < cols.size (); i++)
  94     {
  95       if (Paper_column::is_musical (cols[i]))
  96         {
  97           Moment *when = unsmob_moment (cols[i]->get_property ("when"));
  98
  99           /*
 100             ignore grace notes for shortest notes.
 101           */
 102           if (when && when->grace_part_)
 103             continue;
 104
 105           SCM st = cols[i]->get_property ("shortest-starter-duration");
 106           Moment this_shortest = *unsmob_moment (st);
 107           assert (this_shortest.to_bool ());
 108           shortest_in_measure = min (shortest_in_measure, this_shortest.main_part_);
 109         }
 110       else if (!shortest_in_measure.is_infinity ()
 111                && Paper_column::is_breakable (cols[i]))
 112         {
 113           vsize j = 0;
 114           for (; j < durations.size (); j++)
 115             {
 116               if (durations[j] > shortest_in_measure)
 117                 {
 118                   counts.insert (counts.begin () + j, 1);
 119                   durations.insert (durations.begin () + j, shortest_in_measure);
 120                   break;
 121                 }
 122               else if (durations[j] == shortest_in_measure)
 123                 {
 124                   counts[j]++;
 125                   break;
 126                 }
 127             }
 128
 129           if (durations.size () == j)
 130             {
 131               durations.push_back (shortest_in_measure);
 132               counts.push_back (1);
 133             }
 134
 135           shortest_in_measure.set_infinite (1);
 136         }
 137     }
 138
 139   int max_idx = -1;
 140   int max_count = 0;
 141   for (vsize i = durations.size (); i--;)
 142     {
 143       if (counts[i] >= max_count)
 144         {
 145           max_idx = i;
 146           max_count = counts[i];
 147         }
 148     }
 149
 150   SCM bsd = me->get_property ("base-shortest-duration");
 151   Rational d = Rational (1, 8);
 152   if (Moment *m = unsmob_moment (bsd))
 153     d = m->main_part_;
 154
 155   if (max_idx >= 0)
 156     d = min (d, durations[max_idx]);
 157
 158   return Moment (d).smobbed_copy ();
 159 }
 160
 161 void
 162 Spacing_spanner::generate_pair_spacing (Grob *me,
 163                                         Paper_column *left_col, Paper_column *right_col,
 164                                         Paper_column *after_right_col,
 165                                         Spacing_options const *options)
 166 {
 167   if (Paper_column::is_musical (left_col))
 168     {
 169       if (!Paper_column::is_musical (right_col)
 170           && options->float_nonmusical_columns_
 171           && after_right_col
 172           && Paper_column::is_musical (after_right_col))
 173         {
 174           /*
 175             TODO: should generate rods to prevent collisions.
 176           */
 177           musical_column_spacing (me, left_col, after_right_col, options);
 178           right_col->set_object ("between-cols", scm_cons (left_col->self_scm (),
 179                                                            after_right_col->self_scm ()));
 180         }
 181       else
 182         musical_column_spacing (me, left_col, right_col, options);
 183
 184       if (Item *rb = right_col->find_prebroken_piece (LEFT))
 185         musical_column_spacing (me, left_col, rb, options);
 186     }
 187   else
 188     {
 189       /*
 190         The case that the right part is broken as well is rather
 191         rare, but it is possible, eg. with a single empty measure,
 192         or if one staff finishes a tad earlier than the rest.
 193       */
 194       Item *lb = left_col->find_prebroken_piece (RIGHT);
 195       Item *rb = right_col->find_prebroken_piece (LEFT);
 196
 197       if (left_col && right_col)
 198         breakable_column_spacing (me, left_col, right_col, options);
 199
 200       if (lb && right_col)
 201         breakable_column_spacing (me, lb, right_col, options);
 202
 203       if (left_col && rb)
 204         breakable_column_spacing (me, left_col, rb, options);
 205
 206       if (lb && rb)
 207         breakable_column_spacing (me, lb, rb, options);
 208     }
 209 }
 210
 211 static void
 212 set_column_rods (vector<Grob*> const &cols, Real padding)
 213 {
 214   /* distances[i] will be the minimum distance between column i and column i+1 */
 215   vector<Real> distances;
 216
 217   for (vsize i = 1; i < cols.size (); i++)
 218     {
 219       assert (distances.size () == i-1);
 220
 221       Item *r = dynamic_cast<Item*> (cols[i]);
 222       Item *rb = r->find_prebroken_piece (LEFT);
 223
 224       if (Separation_item::is_empty (r) && (!rb || Separation_item::is_empty (rb)))
 225         {
 226           distances.push_back (0);
 227           continue;
 228         }
 229
 230       Skyline_pair *skys = Skyline_pair::unsmob (r->get_property ("horizontal-skylines"));
 231       Real right_stickout = skys ? (*skys)[LEFT].max_height () : 0.0;
 232
 233       Drul_array<Item*> r_cols (r, rb);
 234       Drul_array<Real> cur_dist (0.0, 0.0);
 235
 236       /* This is an inner loop and hence it is potentially quadratic. However, we only continue
 237          as long as there is a rod to insert. Therefore, this loop will usually only execute
 238          a constant number of times per iteration of the outer loop. */
 239       for (vsize j = i; j--;)
 240         {
 241           Item *l = dynamic_cast<Item*> (cols[j]);
 242           Item *lb = l->find_prebroken_piece (RIGHT);
 243           Skyline_pair *skys = Skyline_pair::unsmob (l->get_property ("horizontal-skylines"));
 244           Real left_stickout = skys ? (*skys)[RIGHT].max_height () : 0.0;
 245           bool done = true;
 246
 247           Direction d = LEFT;
 248           do
 249             {
 250               if (j < i-1)
 251                 cur_dist[d] += distances[j];
 252
 253               Item *r_col = r_cols[d];
 254               bool touches = right_stickout - left_stickout + cur_dist[d] < 0.0;
 255               Real dist = 0.0;
 256
 257               /* we set a distance for the line-starter column even if it's non-broken counterpart
 258                  doesn't touch the right column. */
 259               if (lb)
 260                 Separation_item::set_distance (lb, r_col, padding);
 261
 262               if (touches || j == i-1)
 263                 dist = Separation_item::set_distance (l, r_col, padding);
 264
 265               if (j == i-1 && d == LEFT)
 266                 distances.push_back (dist);
 267
 268               if (j == i-1)
 269                 cur_dist[d] = distances[j];
 270
 271               done = done && !touches;
 272             }
 273           while (flip (&d) != LEFT && rb);
 274
 275           /* we need the empty check for gregorian notation, where there are a lot of
 276              extraneous paper-columns that we need to skip over */
 277           if (done && !Separation_item::is_empty (l))
 278             break;
 279         }
 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   set_column_rods (cols, 0.1); // FIXME: padding
 301 }
 302
 303 /*
 304   Generate the space between two musical columns LEFT_COL and RIGHT_COL.
 305 */
 306 void
 307 Spacing_spanner::musical_column_spacing (Grob *me,
 308                                          Item *left_col,
 309                                          Item *right_col,
 310                                          Spacing_options const *options)
 311 {
 312   Real base_note_space = note_spacing (me, left_col, right_col, options);
 313   Spring spring;
 314
 315   if (options->stretch_uniformly_)
 316     spring = Spring (base_note_space, 0.0);
 317   else
 318     {
 319       vector<Spring> springs;
 320       extract_grob_set (left_col, "right-neighbors", neighbors);
 321
 322       for (vsize i = 0; i < neighbors.size (); i++)
 323         {
 324           Grob *wish = neighbors[i];
 325
 326           Item *wish_rcol = Spacing_interface::right_column (wish);
 327           if (Spacing_interface::left_column (wish) != left_col
 328               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 329             continue;
 330
 331           /*
 332             This is probably a waste of time in the case of polyphonic
 333             music.  */
 334           if (Note_spacing::has_interface (wish))
 335             springs.push_back (Note_spacing::get_spacing (wish, right_col, base_note_space, options->increment_));
 336         }
 337
 338       if (springs.empty ())
 339         {
 340
 341           if (!Paper_column::is_musical (right_col))
 342             {
 343               /*
 344                 There used to be code that examined left_col->extent
 345                 (X_AXIS), but this is resulted in unexpected wide
 346                 spacing, because the width of s^"text" output is also
 347                 taken into account here.
 348                */
 349               spring = Spring (max (base_note_space, options->increment_),
 350                                options->increment_);
 351             }
 352           else
 353             {
 354               /*
 355                 Fixed should be 0.0. If there are no spacing wishes, we're
 356                 likely dealing with polyphonic spacing of hemiolas.
 357
 358                 We used to have min_distance_ = options->increment_
 359
 360                 but this can lead to numeric instability problems when we
 361                 do
 362
 363                 inverse_strength = (distance_ - min_distance_)
 364
 365               */
 366               spring = Spring (base_note_space, 0.0);
 367             }
 368         }
 369       else
 370         spring = merge_springs (springs);
 371     }
 372
 373   if (Paper_column::when_mom (right_col).grace_part_
 374       && !Paper_column::when_mom (left_col).grace_part_)
 375     {
 376       /*
 377         Ugh. 0.8 is arbitrary.
 378       */
 379       spring *= 0.8;
 380     }
 381
 382   /*
 383     TODO: make sure that the space doesn't exceed the right margin.
 384   */
 385   if (options->packed_)
 386     {
 387       /*
 388         In packed mode, pack notes as tight as possible.  This makes
 389         sense mostly in combination with raggedright mode: the notes
 390         are then printed at minimum distance.  This is mostly useful
 391         for ancient notation, but may also be useful for some flavours
 392         of contemporary music.  If not in raggedright mode, lily will
 393         pack as much bars of music as possible into a line, but the
 394         line will then be stretched to fill the whole linewidth.
 395       */
 396       spring.set_distance (spring.min_distance ());
 397       spring.set_inverse_stretch_strength (1.0);
 398     }
 399
 400   Spaceable_grob::add_spring (left_col, right_col, spring);
 401 }
 402
 403 /*
 404   Check if COL fills the whole measure.
 405  */
 406 bool
 407 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 408 {
 409   System *sys = get_root_system (me);
 410   Item *next = sys->column (col->get_column ()->get_rank () + 1);
 411   if (!next)
 412     return false;
 413
 414   if (Paper_column::is_musical (next)
 415       || Paper_column::is_musical (left)
 416       || !Paper_column::is_musical (col)
 417       || !Paper_column::is_used (next))
 418     return false;
 419
 420   Moment dt =
 421     Paper_column::when_mom (next) - Paper_column::when_mom (col);
 422
 423   Moment *len = unsmob_moment (left->get_property ("measure-length"));
 424   if (!len)
 425     return false;
 426
 427   /*
 428     Don't check for exact measure length, since ending measures are
 429     often shortened due to pickups.
 430    */
 431   if (dt.main_part_ > len->main_part_ / Rational (2)
 432       && (next->is_broken ()
 433           || next->break_status_dir ()))
 434     return true;
 435
 436   return false;
 437 }
 438
 439 /*
 440   Read hints from L and generate springs.
 441 */
 442 void
 443 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 444                                            Spacing_options const *options)
 445 {
 446   vector<Spring> springs;
 447   Spring spring;
 448
 449   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 450
 451   if (dt == Moment (0, 0))
 452     {
 453       extract_grob_set (l, "spacing-wishes", wishes);
 454
 455       for (vsize i = 0; i < wishes.size (); i++)
 456         {
 457           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 458
 459           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 460             continue;
 461
 462           /*
 463             column for the left one settings should be ok due automatic
 464             pointer munging.
 465           */
 466           assert (spacing_grob->get_column () == l);
 467
 468           springs.push_back (Staff_spacing::get_spacing (spacing_grob, r));
 469         }
 470     }
 471
 472   if (springs.empty ())
 473     spring = standard_breakable_column_spacing (me, l, r, options);
 474   else
 475     spring = merge_springs (springs);
 476
 477   if (Paper_column::when_mom (r).grace_part_)
 478     {
 479       /*
 480         Correct for grace notes.
 481
 482         Ugh. The 0.8 is arbitrary.
 483       */
 484       spring *= 0.8;
 485     }
 486
 487   if (Paper_column::is_musical (r)
 488       && l->break_status_dir () == CENTER
 489       && fills_measure (me, l, r))
 490     {
 491       spring.set_distance (spring.distance () + 1.0);
 492       spring.set_default_strength ();
 493     }
 494
 495   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 496     {
 497       spring.set_min_distance (0.0);
 498       spring.set_default_strength ();
 499     }
 500
 501   Spaceable_grob::add_spring (l, r, spring);
 502 }
 503
 504 ADD_INTERFACE (Spacing_spanner,
 505                "The space taken by a note is dependent on its duration. Doubling a\n"
 506                "duration adds spacing-increment to the space. The most common shortest\n"
 507                "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
 508                "spaced proportonial to their duration.\n"
 509                "\n"
 510                "Typically, the increment is the width of a black note head.  In a\n"
 511                "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
 512                "gets 2 note heads width (i.e. the space following a note is 1 note\n"
 513                "head width) A 16th note is followed by 0.5 note head width. The\n"
 514                "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
 515
 516
 517                "average-spacing-wishes "
 518                "base-shortest-duration "
 519                "common-shortest-duration "
 520                "packed-spacing "
 521                "shortest-duration-space "
 522                "spacing-increment "
 523                "strict-grace-spacing "
 524                "strict-note-spacing "
 525                "uniform-stretching "
 526
 527                );
 528