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
  58   set_explicit_neighbor_columns (options.columns_);
  59
  60   prune_loose_columns (me, &options);
  61   set_implicit_neighbor_columns (options.columns_);
  62   generate_springs (me, &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                                    Spacing_options const *options)
 220 {
 221   Paper_column *prev = 0;
 222   for (vsize i = 0; i < options->columns_.size (); i++)
 223     {
 224       Paper_column *col = dynamic_cast<Paper_column *> (options->columns_[i]);
 225       Paper_column *next = (i < options->columns_.size()-1) ? dynamic_cast<Paper_column *> (options->columns_[i+1]) : 0;
 226
 227       if (i > 0)
 228         generate_pair_spacing (me, prev, col, next, options);
 229
 230       prev = col;
 231     }
 232 }
 233
 234 /*
 235   Generate the space between two musical columns LEFT_COL and RIGHT_COL, given
 236   spacing parameters INCR and SHORTEST.
 237 */
 238 void
 239 Spacing_spanner::musical_column_spacing (Grob *me,
 240                                          Item *left_col,
 241                                          Item *right_col,
 242                                          Spacing_options const *options)
 243 {
 244   bool expand_only = false;
 245   Real base_note_space = note_spacing (me, left_col, right_col, options, &expand_only);
 246
 247   Real max_fixed = 0;
 248   Real max_space = 0;
 249   Real compound_note_space = 0.0;
 250   Real compound_fixed_note_space = 0.0;
 251
 252   if (options->stretch_uniformly_)
 253     {
 254       compound_note_space = base_note_space;
 255
 256       if (!Paper_column::is_musical (right_col))
 257         {
 258           /*
 259             Crude fix for notes that lead up to barlines and time sigs.
 260           */
 261           Interval lext = right_col->extent (right_col, X_AXIS);
 262           if (!lext.is_empty ())
 263             compound_note_space += -lext[LEFT];
 264         }
 265     }
 266   else
 267     {
 268       int wish_count = 0;
 269
 270       extract_grob_set (left_col, "right-neighbors", neighbors);
 271
 272       /*
 273         We adjust the space following a note only if the next note
 274         happens after the current note (this is set in the grob
 275         property SPACING-SEQUENCE.
 276       */
 277       for (vsize i = 0; i < neighbors.size (); i++)
 278         {
 279           Grob *wish = neighbors[i];
 280
 281           Item *wish_rcol = Note_spacing::right_column (wish);
 282           if (Note_spacing::left_column (wish) != left_col
 283               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 284             continue;
 285
 286           /*
 287             This is probably a waste of time in the case of polyphonic
 288             music.  */
 289           if (Note_spacing::has_interface (wish))
 290             {
 291               Real space = 0.0;
 292               Real fixed = 0.0;
 293
 294               Note_spacing::get_spacing (wish, right_col, base_note_space, options->increment_, &space, &fixed);
 295
 296
 297               max_space = max (max_space, space);
 298               max_fixed = max (max_fixed, fixed);
 299
 300               compound_note_space += space;
 301               compound_fixed_note_space += fixed;
 302               wish_count++;
 303             }
 304         }
 305
 306       if (Paper_column::when_mom (right_col).grace_part_
 307           && !Paper_column::when_mom (left_col).grace_part_)
 308         {
 309           /*
 310             Ugh. 0.8 is arbitrary.
 311           */
 312           compound_note_space *= 0.8;
 313         }
 314
 315       if (compound_note_space < 0 || wish_count == 0)
 316         {
 317
 318           if (!Paper_column::is_musical (right_col))
 319             {
 320               Real left_col_stick_out = robust_relative_extent (left_col, left_col,  X_AXIS)[RIGHT];
 321               compound_fixed_note_space = max (left_col_stick_out, options->increment_);
 322
 323               compound_note_space = max (base_note_space,
 324                                          base_note_space - options->increment_ + left_col_stick_out);
 325             }
 326           else
 327             {
 328               /*
 329                 Fixed should be 0.0. If there are no spacing wishes, we're
 330                 likely dealing with polyphonic spacing of hemiolas.
 331
 332                 We used to have compound_fixed_note_space = options->increment_
 333
 334                 but this can lead to numeric instability problems when we
 335                 do
 336
 337                 inverse_strength = (compound_note_space - compound_fixed_note_space)
 338
 339               */
 340
 341               compound_note_space = base_note_space;
 342               compound_fixed_note_space = 0.0;
 343             }
 344         }
 345       else if (to_boolean (me->get_property ("average-spacing-wishes")))
 346         {
 347           compound_note_space /= wish_count;
 348           compound_fixed_note_space /= wish_count;
 349         }
 350       else
 351         {
 352           compound_fixed_note_space = max_fixed;
 353           compound_note_space = max_space;
 354         }
 355
 356       /*
 357         Whatever we do, the fixed space is smaller than the real
 358         space.
 359
 360         TODO: this criterion is discontinuous in the derivative.
 361         Maybe it should be continuous?
 362       */
 363       compound_fixed_note_space = min (compound_fixed_note_space,
 364                                        compound_note_space);
 365     }
 366
 367   Real inverse_strength = 1.0;
 368   Real distance = 1.0;
 369
 370   /*
 371     TODO: make sure that the space doesn't exceed the right margin.
 372   */
 373   if (options->packed_)
 374     {
 375       /*
 376         In packed mode, pack notes as tight as possible.  This makes
 377         sense mostly in combination with raggedright mode: the notes
 378         are then printed at minimum distance.  This is mostly useful
 379         for ancient notation, but may also be useful for some flavours
 380         of contemporary music.  If not in raggedright mode, lily will
 381         pack as much bars of music as possible into a line, but the
 382         line will then be stretched to fill the whole linewidth.
 383       */
 384       inverse_strength = 1.0;
 385       distance = compound_fixed_note_space;
 386     }
 387   else
 388     {
 389       inverse_strength = (compound_note_space - compound_fixed_note_space);
 390       distance = compound_note_space;
 391     }
 392
 393   Spaceable_grob::add_spring (left_col, right_col, distance, inverse_strength);
 394 }
 395
 396 bool
 397 Spacing_spanner::fills_measure (Grob *me, Item *l, Item *r)
 398 {
 399   return false;
 400   System *sys = get_root_system (me);
 401   Grob *next = sys->column (r->get_column()->get_rank () + 1);
 402   if (!next)
 403     return false;
 404
 405   Moment dt =
 406     Paper_column::when_mom (next) - Paper_column::when_mom (r);
 407
 408   Moment *len = unsmob_moment (l->get_property ("measure-length"));
 409   if (!len)
 410     return false;
 411
 412   if (dt.main_part_ == len->main_part_)
 413     return true;
 414
 415   return false;
 416 }
 417 /*
 418   Read hints from L and generate springs.
 419 */
 420 void
 421 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 422                                            Spacing_options const *options)
 423 {
 424   Real compound_fixed = 0.0;
 425   Real compound_space = 0.0;
 426   Real max_fixed = 0.0;
 427   Real max_space = 0.0;
 428
 429   int wish_count = 0;
 430
 431   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 432
 433   if (dt == Moment (0, 0))
 434     {
 435       extract_grob_set (l, "spacing-wishes", wishes);
 436
 437       for (vsize i = 0; i < wishes.size (); i++)
 438         {
 439           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 440
 441           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 442             continue;
 443
 444           Real space = 0.;
 445           Real fixed_space = 0.;
 446
 447           /*
 448             column for the left one settings should be ok due automatic
 449             pointer munging.
 450           */
 451           assert (spacing_grob->get_column () == l);
 452
 453           Staff_spacing::get_spacing_params (spacing_grob,
 454                                              &space, &fixed_space);
 455
 456           if (Paper_column::when_mom (r).grace_part_)
 457             {
 458               /*
 459                 Correct for grace notes.
 460
 461                 Ugh. The 0.8 is arbitrary.
 462               */
 463               space *= 0.8;
 464             }
 465
 466           max_space = max (max_space, space);
 467           max_fixed = max (max_fixed, fixed_space);
 468
 469           compound_space += space;
 470           compound_fixed += fixed_space;
 471           wish_count++;
 472         }
 473     }
 474
 475   if (compound_space <= 0.0 || !wish_count)
 476     {
 477       standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space,
 478                                          options);
 479       wish_count = 1;
 480     }
 481   else
 482     {
 483       if (to_boolean (me->get_property ("average-spacing-wishes")))
 484         {
 485           compound_space /= wish_count;
 486           compound_fixed /= wish_count;
 487         }
 488       else
 489         {
 490           compound_fixed = max_fixed;
 491           compound_space = max_space;
 492         }
 493
 494     }
 495
 496   if (fills_measure (me, l, r))
 497     {
 498       compound_space += 1.0;
 499     }
 500
 501   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 502     compound_fixed = 0.0;
 503
 504   assert (!isinf (compound_space));
 505   compound_space = max (compound_space, compound_fixed);
 506
 507   /*
 508     There used to be code that changed spacing depending on
 509     raggedright setting.  Ugh.
 510
 511     Do it more cleanly, or rename the property.
 512
 513   */
 514   Real inverse_strength = (compound_space - compound_fixed);
 515   Real distance = compound_space;
 516   Spaceable_grob::add_spring (l, r, distance, inverse_strength);
 517 }
 518
 519 ADD_INTERFACE (Spacing_spanner,
 520                "The space taken by a note is dependent on its duration. Doubling a\n"
 521                "duration adds spacing-increment to the space. The most common shortest\n"
 522                "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
 523                "spaced proportonial to their duration.\n"
 524                "\n"
 525                "Typically, the increment is the width of a black note head.  In a\n"
 526                "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
 527                "gets 2 note heads width (i.e. the space following a note is 1 note\n"
 528                "head width) A 16th note is followed by 0.5 note head width. The\n"
 529                "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
 530
 531
 532                "average-spacing-wishes "
 533                "base-shortest-duration "
 534                "common-shortest-duration "
 535                "packed-spacing "
 536                "shortest-duration-space "
 537                "spacing-increment "
 538                "strict-grace-spacing "
 539                "strict-note-spacing "
 540                "uniform-stretching "
 541
 542                );
 543
 544 ADD_INTERFACE (Spacing_interface,
 545                "Something to do with line breaking and spacing. "
 546                "Kill this one after determining line breaks.",
 547
 548                "");
 549