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, vsize idx, Real padding)
 213 {
 214
 215   /*
 216     This is an inner loop: look for the first normal (unbroken) Left
 217     grob.  This looks like an inner loop (ie. quadratic total), but in
 218     most cases, the interesting L will just be the first entry of
 219     NEXT, making it linear in most of the cases.
 220   */
 221   Item *r = dynamic_cast<Item*> (cols[idx]);
 222
 223   if (Separation_item::is_empty (r))
 224     return;
 225
 226   bool constraint = false;
 227   bool grace = false;
 228
 229   idx--;
 230   do
 231     {
 232       Item *l = dynamic_cast<Item*> (cols[idx]);
 233       Item *lb = l->find_prebroken_piece (RIGHT);
 234
 235       if (Separation_item::is_empty (l) && (!lb || Separation_item::is_empty (lb)))
 236         continue;
 237
 238       if (lb)
 239         Separation_item::set_distance (Drul_array<Item*> (lb, r), padding);
 240       constraint = Separation_item::set_distance (Drul_array<Item *> (l, r), padding);
 241
 242
 243       /*
 244         This check is because grace notes are set very tight, and
 245         the accidentals of main note may stick out so far to cover
 246         a barline preceding the grace note.
 247       */
 248       grace = spanned_time_interval (l, r).length ().main_part_ == Rational (0);
 249
 250       /*
 251         this grob doesn't cause a constraint. We look further until we
 252         find one that does.
 253       */
 254     }
 255   while (idx-- && (!constraint || grace));
 256 }
 257
 258 void
 259 Spacing_spanner::generate_springs (Grob *me,
 260                                    vector<Grob*> const &cols,
 261                                    Spacing_options const *options)
 262 {
 263   Paper_column *prev = 0;
 264   for (vsize i = 0; i < cols.size (); i++)
 265     {
 266       Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
 267       Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i+1]) : 0;
 268
 269       if (i > 0)
 270         {
 271           generate_pair_spacing (me, prev, col, next, options);
 272           set_column_rods (cols, i, 0.1); // FIXME
 273         }
 274
 275       prev = col;
 276     }
 277 }
 278
 279 /*
 280   Generate the space between two musical columns LEFT_COL and RIGHT_COL.
 281 */
 282 void
 283 Spacing_spanner::musical_column_spacing (Grob *me,
 284                                          Item *left_col,
 285                                          Item *right_col,
 286                                          Spacing_options const *options)
 287 {
 288   Real base_note_space = note_spacing (me, left_col, right_col, options);
 289   Spring spring;
 290
 291   if (options->stretch_uniformly_)
 292     spring = Spring (base_note_space, 0.0);
 293   else
 294     {
 295       vector<Spring> springs;
 296       extract_grob_set (left_col, "right-neighbors", neighbors);
 297
 298       for (vsize i = 0; i < neighbors.size (); i++)
 299         {
 300           Grob *wish = neighbors[i];
 301
 302           Item *wish_rcol = Spacing_interface::right_column (wish);
 303           if (Spacing_interface::left_column (wish) != left_col
 304               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 305             continue;
 306
 307           /*
 308             This is probably a waste of time in the case of polyphonic
 309             music.  */
 310           if (Note_spacing::has_interface (wish))
 311             springs.push_back (Note_spacing::get_spacing (wish, right_col, base_note_space, options->increment_));
 312         }
 313
 314       if (springs.empty ())
 315         {
 316
 317           if (!Paper_column::is_musical (right_col))
 318             {
 319               /*
 320                 There used to be code that examined left_col->extent
 321                 (X_AXIS), but this is resulted in unexpected wide
 322                 spacing, because the width of s^"text" output is also
 323                 taken into account here.
 324                */
 325               spring = Spring (max (base_note_space, options->increment_),
 326                                options->increment_);
 327             }
 328           else
 329             {
 330               /*
 331                 Fixed should be 0.0. If there are no spacing wishes, we're
 332                 likely dealing with polyphonic spacing of hemiolas.
 333
 334                 We used to have min_distance_ = options->increment_
 335
 336                 but this can lead to numeric instability problems when we
 337                 do
 338
 339                 inverse_strength = (distance_ - min_distance_)
 340
 341               */
 342               spring = Spring (base_note_space, 0.0);
 343             }
 344         }
 345       else
 346         spring = merge_springs (springs);
 347     }
 348
 349   if (Paper_column::when_mom (right_col).grace_part_
 350       && !Paper_column::when_mom (left_col).grace_part_)
 351     {
 352       /*
 353         Ugh. 0.8 is arbitrary.
 354       */
 355       spring *= 0.8;
 356     }
 357
 358   /*
 359     TODO: make sure that the space doesn't exceed the right margin.
 360   */
 361   if (options->packed_)
 362     {
 363       /*
 364         In packed mode, pack notes as tight as possible.  This makes
 365         sense mostly in combination with raggedright mode: the notes
 366         are then printed at minimum distance.  This is mostly useful
 367         for ancient notation, but may also be useful for some flavours
 368         of contemporary music.  If not in raggedright mode, lily will
 369         pack as much bars of music as possible into a line, but the
 370         line will then be stretched to fill the whole linewidth.
 371       */
 372       spring.set_distance (spring.min_distance ());
 373       spring.set_inverse_stretch_strength (1.0);
 374     }
 375
 376   Spaceable_grob::add_spring (left_col, right_col, spring);
 377 }
 378
 379 /*
 380   Check if COL fills the whole measure.
 381  */
 382 bool
 383 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 384 {
 385   System *sys = get_root_system (me);
 386   Item *next = sys->column (col->get_column ()->get_rank () + 1);
 387   if (!next)
 388     return false;
 389
 390   if (Paper_column::is_musical (next)
 391       || Paper_column::is_musical (left)
 392       || !Paper_column::is_musical (col)
 393       || !Paper_column::is_used (next))
 394     return false;
 395
 396   Moment dt =
 397     Paper_column::when_mom (next) - Paper_column::when_mom (col);
 398
 399   Moment *len = unsmob_moment (left->get_property ("measure-length"));
 400   if (!len)
 401     return false;
 402
 403   /*
 404     Don't check for exact measure length, since ending measures are
 405     often shortened due to pickups.
 406    */
 407   if (dt.main_part_ > len->main_part_ / Rational (2)
 408       && (next->is_broken ()
 409           || next->break_status_dir ()))
 410     return true;
 411
 412   return false;
 413 }
 414
 415 /*
 416   Read hints from L and generate springs.
 417 */
 418 void
 419 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 420                                            Spacing_options const *options)
 421 {
 422   vector<Spring> springs;
 423   Spring spring;
 424
 425   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 426
 427   if (dt == Moment (0, 0))
 428     {
 429       extract_grob_set (l, "spacing-wishes", wishes);
 430
 431       for (vsize i = 0; i < wishes.size (); i++)
 432         {
 433           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 434
 435           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 436             continue;
 437
 438           /*
 439             column for the left one settings should be ok due automatic
 440             pointer munging.
 441           */
 442           assert (spacing_grob->get_column () == l);
 443
 444           springs.push_back (Staff_spacing::get_spacing (spacing_grob, r));
 445         }
 446     }
 447
 448   if (springs.empty ())
 449     spring = standard_breakable_column_spacing (me, l, r, options);
 450   else
 451     spring = merge_springs (springs);
 452
 453   if (Paper_column::when_mom (r).grace_part_)
 454     {
 455       /*
 456         Correct for grace notes.
 457
 458         Ugh. The 0.8 is arbitrary.
 459       */
 460       spring *= 0.8;
 461     }
 462
 463   if (Paper_column::is_musical (r)
 464       && l->break_status_dir () == CENTER
 465       && fills_measure (me, l, r))
 466     {
 467       spring.set_distance (spring.distance () + 1.0);
 468       spring.set_default_strength ();
 469     }
 470
 471   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 472     {
 473       spring.set_min_distance (0.0);
 474       spring.set_default_strength ();
 475     }
 476
 477   Spaceable_grob::add_spring (l, r, spring);
 478 }
 479
 480 ADD_INTERFACE (Spacing_spanner,
 481                "The space taken by a note is dependent on its duration. Doubling a\n"
 482                "duration adds spacing-increment to the space. The most common shortest\n"
 483                "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
 484                "spaced proportonial to their duration.\n"
 485                "\n"
 486                "Typically, the increment is the width of a black note head.  In a\n"
 487                "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
 488                "gets 2 note heads width (i.e. the space following a note is 1 note\n"
 489                "head width) A 16th note is followed by 0.5 note head width. The\n"
 490                "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
 491
 492
 493                "average-spacing-wishes "
 494                "base-shortest-duration "
 495                "common-shortest-duration "
 496                "packed-spacing "
 497                "shortest-duration-space "
 498                "spacing-increment "
 499                "strict-grace-spacing "
 500                "strict-note-spacing "
 501                "uniform-stretching "
 502
 503                );
 504