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