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