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