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 (Spanner *me)
  33 {
  34   vector<Grob*> all (get_root_system (me)->columns ());
  35   vsize start = binary_search (all, (Grob*)me->get_bound (LEFT),
  36                                &Paper_column::less_than);
  37   vsize end = binary_search (all, (Grob*) me->get_bound (RIGHT),
  38                              &Paper_column::less_than);
  39
  40   all = vector<Grob*>::vector<Grob*> (all.begin () + start,
  41                                       all.begin () + end + 1);
  42   return all;
  43 }
  44
  45 MAKE_SCHEME_CALLBACK (Spacing_spanner, set_springs, 1);
  46 SCM
  47 Spacing_spanner::set_springs (SCM smob)
  48 {
  49   Spanner *me = unsmob_spanner (smob);
  50
  51   /*
  52     can't use get_system() ? --hwn.
  53   */
  54   vector<Grob*> all (get_columns (me));
  55   set_explicit_neighbor_columns (all);
  56
  57   Spacing_options options;
  58   options.init_from_grob (me);
  59
  60   prune_loose_columns (me, &all, &options);
  61   set_implicit_neighbor_columns (all);
  62   generate_springs (me, all, &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       // printf ("duration %d/%d, count %d\n",
 151       // durations[i].num (), durations[i].den (), counts[i]);
 152     }
 153
 154   SCM bsd = me->get_property ("base-shortest-duration");
 155   Rational d = Rational (1, 8);
 156   if (Moment *m = unsmob_moment (bsd))
 157     d = m->main_part_;
 158
 159   if (max_idx >= 0)
 160     d = min (d, durations[max_idx]);
 161
 162   return Moment (d).smobbed_copy ();
 163 }
 164
 165 void
 166 Spacing_spanner::generate_pair_spacing (Grob *me,
 167                                         Paper_column *left_col, Paper_column *right_col,
 168                                         Paper_column *after_right_col,
 169                                         Spacing_options const *options)
 170 {
 171   if (Paper_column::is_musical (left_col))
 172     {
 173       bool skip_unbroken_right = false;
 174
 175       if (!Paper_column::is_musical (right_col)
 176           && options->float_nonmusical_columns_
 177           && after_right_col
 178           && Paper_column::is_musical (after_right_col))
 179         skip_unbroken_right = true;
 180
 181       if (skip_unbroken_right)
 182         {
 183           /*
 184             TODO: should generate rods to prevent collisions.
 185           */
 186           musical_column_spacing (me, left_col, after_right_col, options);
 187           right_col->set_object ("between-cols", scm_cons (left_col->self_scm (),
 188                                                            after_right_col->self_scm ()));
 189         }
 190       else
 191         musical_column_spacing (me, left_col, right_col, options);
 192
 193       if (Item *rb = right_col->find_prebroken_piece (LEFT))
 194         musical_column_spacing (me, left_col, rb, options);
 195     }
 196   else
 197     {
 198       /*
 199         The case that the right part is broken as well is rather
 200         rare, but it is possible, eg. with a single empty measure,
 201         or if one staff finishes a tad earlier than the rest.
 202       */
 203       Item *lb = left_col->find_prebroken_piece (RIGHT);
 204       Item *rb = right_col->find_prebroken_piece (LEFT);
 205
 206       if (left_col && right_col)
 207         breakable_column_spacing (me, left_col, right_col, options);
 208
 209       if (lb && right_col)
 210         breakable_column_spacing (me, lb, right_col, options);
 211
 212       if (left_col && rb)
 213         breakable_column_spacing (me, left_col, rb, options);
 214
 215       if (lb && rb)
 216         breakable_column_spacing (me, lb, rb, options);
 217     }
 218 }
 219
 220 void
 221 Spacing_spanner::generate_springs (Grob *me,
 222                                    vector<Grob*> const &cols,
 223                                    Spacing_options const *options)
 224 {
 225   Paper_column *prev = 0;
 226   for (vsize i = 0; i < cols.size (); i++)
 227     {
 228       Paper_column *col = dynamic_cast<Paper_column *> (cols[i]);
 229       Paper_column *next = (i + 1 < cols.size ()) ? dynamic_cast<Paper_column *> (cols[i+1]) : 0;
 230
 231       if (i > 0)
 232         generate_pair_spacing (me, prev, col, next, options);
 233
 234       prev = col;
 235     }
 236 }
 237
 238 /*
 239   Generate the space between two musical columns LEFT_COL and RIGHT_COL, given
 240   spacing parameters INCR and SHORTEST.
 241 */
 242 void
 243 Spacing_spanner::musical_column_spacing (Grob *me,
 244                                          Item *left_col,
 245                                          Item *right_col,
 246                                          Spacing_options const *options)
 247 {
 248   bool expand_only = false;
 249   Real base_note_space = note_spacing (me, left_col, right_col, options, &expand_only);
 250
 251   Real max_fixed = 0;
 252   Real max_space = 0;
 253   Real compound_note_space = 0.0;
 254   Real compound_fixed_note_space = 0.0;
 255
 256   if (options->stretch_uniformly_)
 257     {
 258       compound_note_space = base_note_space;
 259
 260       if (!Paper_column::is_musical (right_col))
 261         {
 262           /*
 263             Crude fix for notes that lead up to barlines and time sigs.
 264           */
 265           Interval lext = right_col->extent (right_col, X_AXIS);
 266           if (!lext.is_empty ())
 267             compound_note_space += -lext[LEFT];
 268         }
 269     }
 270   else
 271     {
 272       int wish_count = 0;
 273
 274       extract_grob_set (left_col, "right-neighbors", neighbors);
 275
 276       /*
 277         We adjust the space following a note only if the next note
 278         happens after the current note (this is set in the grob
 279         property SPACING-SEQUENCE.
 280       */
 281       for (vsize i = 0; i < neighbors.size (); i++)
 282         {
 283           Grob *wish = neighbors[i];
 284
 285           Item *wish_rcol = Note_spacing::right_column (wish);
 286           if (Note_spacing::left_column (wish) != left_col
 287               || (wish_rcol != right_col && wish_rcol != right_col->original ()))
 288             continue;
 289
 290           /*
 291             This is probably a waste of time in the case of polyphonic
 292             music.  */
 293           if (Note_spacing::has_interface (wish))
 294             {
 295               Real space = 0.0;
 296               Real fixed = 0.0;
 297
 298               Note_spacing::get_spacing (wish, right_col, base_note_space, options->increment_, &space, &fixed);
 299
 300
 301               max_space = max (max_space, space);
 302               max_fixed = max (max_fixed, fixed);
 303
 304               compound_note_space += space;
 305               compound_fixed_note_space += fixed;
 306               wish_count++;
 307             }
 308         }
 309
 310       if (Paper_column::when_mom (right_col).grace_part_
 311           && !Paper_column::when_mom (left_col).grace_part_)
 312         {
 313           /*
 314             Ugh. 0.8 is arbitrary.
 315           */
 316           compound_note_space *= 0.8;
 317         }
 318
 319       if (compound_note_space < 0 || wish_count == 0)
 320         {
 321
 322           if (!Paper_column::is_musical (right_col))
 323             {
 324               /*
 325                 reconsider this: breaks with wide marks/tempos/etc.
 326                */
 327               Real left_col_stick_out = robust_relative_extent (left_col, left_col,  X_AXIS)[RIGHT];
 328               compound_fixed_note_space = max (left_col_stick_out, options->increment_);
 329
 330               compound_note_space = max (base_note_space,
 331                                          base_note_space - options->increment_ + left_col_stick_out);
 332             }
 333           else
 334             {
 335               /*
 336                 Fixed should be 0.0. If there are no spacing wishes, we're
 337                 likely dealing with polyphonic spacing of hemiolas.
 338
 339                 We used to have compound_fixed_note_space = options->increment_
 340
 341                 but this can lead to numeric instability problems when we
 342                 do
 343
 344                 inverse_strength = (compound_note_space - compound_fixed_note_space)
 345
 346               */
 347
 348               compound_note_space = base_note_space;
 349               compound_fixed_note_space = 0.0;
 350             }
 351         }
 352       else if (to_boolean (me->get_property ("average-spacing-wishes")))
 353         {
 354           compound_note_space /= wish_count;
 355           compound_fixed_note_space /= wish_count;
 356         }
 357       else
 358         {
 359           compound_fixed_note_space = max_fixed;
 360           compound_note_space = max_space;
 361         }
 362
 363       /*
 364         Whatever we do, the fixed space is smaller than the real
 365         space.
 366
 367         TODO: this criterion is discontinuous in the derivative.
 368         Maybe it should be continuous?
 369       */
 370       compound_fixed_note_space = min (compound_fixed_note_space,
 371                                        compound_note_space);
 372     }
 373
 374   Real inverse_strength = 1.0;
 375   Real distance = 1.0;
 376
 377   /*
 378     TODO: make sure that the space doesn't exceed the right margin.
 379   */
 380   if (options->packed_)
 381     {
 382       /*
 383         In packed mode, pack notes as tight as possible.  This makes
 384         sense mostly in combination with raggedright mode: the notes
 385         are then printed at minimum distance.  This is mostly useful
 386         for ancient notation, but may also be useful for some flavours
 387         of contemporary music.  If not in raggedright mode, lily will
 388         pack as much bars of music as possible into a line, but the
 389         line will then be stretched to fill the whole linewidth.
 390       */
 391       inverse_strength = 1.0;
 392       distance = compound_fixed_note_space;
 393     }
 394   else
 395     {
 396       inverse_strength = (compound_note_space - compound_fixed_note_space);
 397       distance = compound_note_space;
 398     }
 399
 400   Spaceable_grob::add_spring (left_col, right_col, distance, inverse_strength);
 401 }
 402
 403
 404 /*
 405   Read hints from L and generate springs.
 406 */
 407 void
 408 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 409                                            Spacing_options const *options)
 410 {
 411   Real compound_fixed = 0.0;
 412   Real compound_space = 0.0;
 413   Real max_fixed = 0.0;
 414   Real max_space = 0.0;
 415
 416   int wish_count = 0;
 417
 418   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 419
 420   if (dt == Moment (0, 0))
 421     {
 422       extract_grob_set (l, "spacing-wishes", wishes);
 423
 424       for (vsize i = 0; i < wishes.size (); i++)
 425         {
 426           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 427
 428           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 429             continue;
 430
 431           Real space;
 432           Real fixed_space;
 433
 434           /*
 435             column for the left one settings should be ok due automatic
 436             pointer munging.
 437
 438           */
 439           assert (spacing_grob->get_column () == l);
 440
 441           Staff_spacing::get_spacing_params (spacing_grob,
 442                                              &space, &fixed_space);
 443
 444           if (Paper_column::when_mom (r).grace_part_)
 445             {
 446               /*
 447                 Correct for grace notes.
 448
 449                 Ugh. The 0.8 is arbitrary.
 450               */
 451               space *= 0.8;
 452             }
 453
 454           max_space = max (max_space, space);
 455           max_fixed = max (max_fixed, fixed_space);
 456
 457           compound_space += space;
 458           compound_fixed += fixed_space;
 459           wish_count++;
 460         }
 461     }
 462
 463   if (compound_space <= 0.0 || !wish_count)
 464     {
 465       standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space,
 466                                          options);
 467       wish_count = 1;
 468     }
 469   else
 470     {
 471       if (to_boolean (me->get_property ("average-spacing-wishes")))
 472         {
 473           compound_space /= wish_count;
 474           compound_fixed /= wish_count;
 475         }
 476       else
 477         {
 478           compound_fixed = max_fixed;
 479           compound_space = max_space;
 480         }
 481
 482     }
 483
 484   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 485     compound_fixed = 0.0;
 486
 487   assert (!isinf (compound_space));
 488   compound_space = max (compound_space, compound_fixed);
 489
 490   /*
 491     There used to be code that changed spacing depending on
 492     raggedright setting.  Ugh.
 493
 494     Do it more cleanly, or rename the property.
 495
 496   */
 497   Real inverse_strength = (compound_space - compound_fixed);
 498   Real distance = compound_space;
 499   Spaceable_grob::add_spring (l, r, distance, inverse_strength);
 500 }
 501
 502 ADD_INTERFACE (Spacing_spanner, "spacing-spanner-interface",
 503                "The space taken by a note is dependent on its duration. Doubling a\n"
 504                "duration adds spacing-increment to the space. The most common shortest\n"
 505                "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
 506                "spaced proportonial to their duration.\n"
 507                "\n"
 508                "Typically, the increment is the width of a black note head.  In a\n"
 509                "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
 510                "gets 2 note heads width (i.e. the space following a note is 1 note\n"
 511                "head width) A 16th note is followed by 0.5 note head width. The\n"
 512                "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
 513
 514
 515                "average-spacing-wishes "
 516                "base-shortest-duration "
 517                "common-shortest-duration "
 518                "packed-spacing "
 519                "shortest-duration-space "
 520                "spacing-increment "
 521                "strict-grace-spacing "
 522                "strict-note-spacing "
 523                "uniform-stretching "
 524
 525                );
 526
 527 ADD_INTERFACE (Spacing_interface, "spacing-interface",
 528                "Something to do with line breaking and spacing. "
 529                "Kill this one after determining line breaks.",
 530
 531                "");
 532