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