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       if (!Paper_column::is_musical (right_col)
 171           && options->float_nonmusical_columns_
 172           && after_right_col
 173           && Paper_column::is_musical (after_right_col))
 174         {
 175           /*
 176             TODO: should generate rods to prevent collisions.
 177           */
 178           musical_column_spacing (me, left_col, after_right_col, options);
 179           right_col->set_object ("between-cols", scm_cons (left_col->self_scm (),
 180                                                            after_right_col->self_scm ()));
 181         }
 182       else
 183         musical_column_spacing (me, left_col, right_col, options);
 184
 185       if (Item *rb = right_col->find_prebroken_piece (LEFT))
 186         musical_column_spacing (me, left_col, rb, options);
 187     }
 188   else
 189     {
 190       /*
 191         The case that the right part is broken as well is rather
 192         rare, but it is possible, eg. with a single empty measure,
 193         or if one staff finishes a tad earlier than the rest.
 194       */
 195       Item *lb = left_col->find_prebroken_piece (RIGHT);
 196       Item *rb = right_col->find_prebroken_piece (LEFT);
 197
 198       if (left_col && right_col)
 199         breakable_column_spacing (me, left_col, right_col, options);
 200
 201       if (lb && right_col)
 202         breakable_column_spacing (me, lb, right_col, options);
 203
 204       if (left_col && rb)
 205         breakable_column_spacing (me, left_col, rb, options);
 206
 207       if (lb && rb)
 208         breakable_column_spacing (me, lb, rb, options);
 209     }
 210 }
 211
 212 void
 213 Spacing_spanner::generate_springs (Grob *me,
 214                                    vector<Grob*> const &cols,
 215                                    Spacing_options const *options)
 216 {
 217   Paper_column *prev = 0;
 218   for (vsize i = 0; i < cols.size (); i++)
 219     {
 220       Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
 221       Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i+1]) : 0;
 222
 223       if (i > 0)
 224         generate_pair_spacing (me, prev, col, next, options);
 225
 226       prev = col;
 227     }
 228 }
 229
 230 /*
 231   Generate the space between two musical columns LEFT_COL and RIGHT_COL.
 232 */
 233 void
 234 Spacing_spanner::musical_column_spacing (Grob *me,
 235                                          Item *left_col,
 236                                          Item *right_col,
 237                                          Spacing_options const *options)
 238 {
 239   Real base_note_space = note_spacing (me, left_col, right_col, options);
 240
 241   Real max_fixed = 0;
 242   Real max_space = 0;
 243   Real compound_note_space = 0.0;
 244   Real compound_fixed_note_space = 0.0;
 245
 246   if (options->stretch_uniformly_)
 247     {
 248       compound_note_space = base_note_space;
 249
 250       if (!Paper_column::is_musical (right_col))
 251         {
 252           /*
 253             Crude fix for notes that lead up to barlines and time sigs.
 254           */
 255           Interval lext = right_col->extent (right_col, X_AXIS);
 256           if (!lext.is_empty ())
 257             compound_note_space += -lext[LEFT];
 258         }
 259     }
 260   else
 261     {
 262       int wish_count = 0;
 263
 264       extract_grob_set (left_col, "right-neighbors", neighbors);
 265
 266       /*
 267         We adjust the space following a note only if the next note
 268         happens after the current note (this is set in the grob
 269         property SPACING-SEQUENCE.
 270       */
 271       for (vsize i = 0; i < neighbors.size (); i++)
 272         {
 273           Grob *wish = neighbors[i];
 274
 275           Item *wish_rcol = Note_spacing::right_column (wish);
 276           if (Note_spacing::left_column (wish) != left_col
 277               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 278             continue;
 279
 280           /*
 281             This is probably a waste of time in the case of polyphonic
 282             music.  */
 283           if (Note_spacing::has_interface (wish))
 284             {
 285               Real space = 0.0;
 286               Real fixed = 0.0;
 287
 288               Note_spacing::get_spacing (wish, right_col, base_note_space, options->increment_, &space, &fixed);
 289
 290
 291               max_space = max (max_space, space);
 292               max_fixed = max (max_fixed, fixed);
 293
 294               compound_note_space += space;
 295               compound_fixed_note_space += fixed;
 296               wish_count++;
 297             }
 298         }
 299
 300       if (Paper_column::when_mom (right_col).grace_part_
 301           && !Paper_column::when_mom (left_col).grace_part_)
 302         {
 303           /*
 304             Ugh. 0.8 is arbitrary.
 305           */
 306           compound_note_space *= 0.8;
 307         }
 308
 309       if (compound_note_space < 0 || wish_count == 0)
 310         {
 311
 312           if (!Paper_column::is_musical (right_col))
 313             {
 314               /*
 315                 There used to be code that examined left_col->extent
 316                 (X_AXIS), but this is resulted in unexpected wide
 317                 spacing, because the width of s^"text" output is also
 318                 taken into account here.
 319                */
 320               compound_fixed_note_space = options->increment_;
 321               compound_note_space = max (base_note_space,
 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 compound_fixed_note_space = options->increment_
 331
 332                 but this can lead to numeric instability problems when we
 333                 do
 334
 335                 inverse_strength = (compound_note_space - compound_fixed_note_space)
 336
 337               */
 338
 339               compound_note_space = base_note_space;
 340               compound_fixed_note_space = 0.0;
 341             }
 342         }
 343       else if (to_boolean (me->get_property ("average-spacing-wishes")))
 344         {
 345           compound_note_space /= wish_count;
 346           compound_fixed_note_space /= wish_count;
 347         }
 348       else
 349         {
 350           compound_fixed_note_space = max_fixed;
 351           compound_note_space = max_space;
 352         }
 353
 354       /*
 355         Whatever we do, the fixed space is smaller than the real
 356         space.
 357
 358         TODO: this criterion is discontinuous in the derivative.
 359         Maybe it should be continuous?
 360       */
 361       compound_fixed_note_space = min (compound_fixed_note_space,
 362                                        compound_note_space);
 363     }
 364
 365   Real inverse_strength = 1.0;
 366   Real distance = 1.0;
 367
 368   /*
 369     TODO: make sure that the space doesn't exceed the right margin.
 370   */
 371   if (options->packed_)
 372     {
 373       /*
 374         In packed mode, pack notes as tight as possible.  This makes
 375         sense mostly in combination with raggedright mode: the notes
 376         are then printed at minimum distance.  This is mostly useful
 377         for ancient notation, but may also be useful for some flavours
 378         of contemporary music.  If not in raggedright mode, lily will
 379         pack as much bars of music as possible into a line, but the
 380         line will then be stretched to fill the whole linewidth.
 381       */
 382       inverse_strength = 1.0;
 383       distance = compound_fixed_note_space;
 384     }
 385   else
 386     {
 387       inverse_strength = (compound_note_space - compound_fixed_note_space);
 388       distance = compound_note_space;
 389     }
 390
 391   Spaceable_grob::add_spring (left_col, right_col, distance, inverse_strength);
 392 }
 393
 394 /*
 395   Check if COL fills the whole measure.
 396  */
 397 bool
 398 Spacing_spanner::fills_measure (Grob *me, Item *left, Item *col)
 399 {
 400   System *sys = get_root_system (me);
 401   Item *next = sys->column (col->get_column ()->get_rank () + 1);
 402   if (!next)
 403     return false;
 404
 405   if (Paper_column::is_musical (next)
 406       || Paper_column::is_musical (left)
 407       || !Paper_column::is_musical (col)
 408       || !Paper_column::is_used (next))
 409     return false;
 410
 411   Moment dt =
 412     Paper_column::when_mom (next) - Paper_column::when_mom (col);
 413
 414   Moment *len = unsmob_moment (left->get_property ("measure-length"));
 415   if (!len)
 416     return false;
 417
 418   /*
 419     Don't check for exact measure length, since ending measures are
 420     often shortened due to pickups.
 421    */
 422   if (dt.main_part_ > len->main_part_ / Rational (2)
 423       && (next->is_broken ()
 424           || next->break_status_dir ()))
 425     return true;
 426
 427   return false;
 428 }
 429
 430 /*
 431   Read hints from L and generate springs.
 432 */
 433 void
 434 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 435                                            Spacing_options const *options)
 436 {
 437   Real compound_fixed = 0.0;
 438   Real compound_space = 0.0;
 439   Real max_fixed = 0.0;
 440   Real max_space = 0.0;
 441
 442   int wish_count = 0;
 443
 444   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 445
 446   if (dt == Moment (0, 0))
 447     {
 448       extract_grob_set (l, "spacing-wishes", wishes);
 449
 450       for (vsize i = 0; i < wishes.size (); i++)
 451         {
 452           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 453
 454           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 455             continue;
 456
 457           /*
 458             column for the left one settings should be ok due automatic
 459             pointer munging.
 460           */
 461           assert (spacing_grob->get_column () == l);
 462
 463           Spring sp = Staff_spacing::get_spacing_params (spacing_grob);
 464           Real space = sp.distance_;
 465           Real fixed = sp.distance_ - sp.inverse_compress_strength_;
 466
 467           if (Paper_column::when_mom (r).grace_part_)
 468             {
 469               /*
 470                 Correct for grace notes.
 471
 472                 Ugh. The 0.8 is arbitrary.
 473               */
 474               space *= 0.8;
 475             }
 476
 477           max_space = max (max_space, space);
 478           max_fixed = max (max_fixed, fixed);
 479
 480           compound_space += space;
 481           compound_fixed += fixed;
 482           wish_count++;
 483         }
 484     }
 485
 486   if (compound_space <= 0.0 || !wish_count)
 487     {
 488       standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space,
 489                                          options);
 490       wish_count = 1;
 491     }
 492   else
 493     {
 494       if (to_boolean (me->get_property ("average-spacing-wishes")))
 495         {
 496           compound_space /= wish_count;
 497           compound_fixed /= wish_count;
 498         }
 499       else
 500         {
 501           compound_fixed = max_fixed;
 502           compound_space = max_space;
 503         }
 504
 505     }
 506
 507   if (Paper_column::is_musical (r)
 508       && l->break_status_dir () == CENTER
 509       && fills_measure (me, l, r))
 510     {
 511       compound_space += 1.0;
 512     }
 513
 514   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 515     compound_fixed = 0.0;
 516
 517   assert (!isinf (compound_space));
 518   compound_space = max (compound_space, compound_fixed);
 519
 520   Real inverse_strength = (compound_space - compound_fixed);
 521   Real distance = compound_space;
 522   message (_f ("adding spring of length %f", distance));
 523   Spaceable_grob::add_spring (l, r, distance, inverse_strength);
 524 }
 525
 526 ADD_INTERFACE (Spacing_spanner,
 527                "The space taken by a note is dependent on its duration. Doubling a\n"
 528                "duration adds spacing-increment to the space. The most common shortest\n"
 529                "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
 530                "spaced proportonial to their duration.\n"
 531                "\n"
 532                "Typically, the increment is the width of a black note head.  In a\n"
 533                "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
 534                "gets 2 note heads width (i.e. the space following a note is 1 note\n"
 535                "head width) A 16th note is followed by 0.5 note head width. The\n"
 536                "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
 537
 538
 539                "average-spacing-wishes "
 540                "base-shortest-duration "
 541                "common-shortest-duration "
 542                "packed-spacing "
 543                "shortest-duration-space "
 544                "spacing-increment "
 545                "strict-grace-spacing "
 546                "strict-note-spacing "
 547                "uniform-stretching "
 548
 549                );
 550