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