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 < cols.size()-1) ? 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               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   Read hints from L and generate springs.
 402 */
 403 void
 404 Spacing_spanner::breakable_column_spacing (Grob *me, Item *l, Item *r,
 405                                            Spacing_options const *options)
 406 {
 407   Real compound_fixed = 0.0;
 408   Real compound_space = 0.0;
 409   Real max_fixed = 0.0;
 410   Real max_space = 0.0;
 411
 412   int wish_count = 0;
 413
 414   Moment dt = Paper_column::when_mom (r) - Paper_column::when_mom (l);
 415
 416   if (dt == Moment (0, 0))
 417     {
 418       extract_grob_set (l, "spacing-wishes", wishes);
 419
 420       for (vsize i = 0; i < wishes.size (); i++)
 421         {
 422           Item *spacing_grob = dynamic_cast<Item *> (wishes[i]);
 423
 424           if (!spacing_grob || !Staff_spacing::has_interface (spacing_grob))
 425             continue;
 426
 427           Real space;
 428           Real fixed_space;
 429
 430           /*
 431             column for the left one settings should be ok due automatic
 432             pointer munging.
 433
 434           */
 435           assert (spacing_grob->get_column () == l);
 436
 437           Staff_spacing::get_spacing_params (spacing_grob,
 438                                              &space, &fixed_space);
 439
 440           if (Paper_column::when_mom (r).grace_part_)
 441             {
 442               /*
 443                 Correct for grace notes.
 444
 445                 Ugh. The 0.8 is arbitrary.
 446               */
 447               space *= 0.8;
 448             }
 449
 450           max_space = max (max_space, space);
 451           max_fixed = max (max_fixed, fixed_space);
 452
 453           compound_space += space;
 454           compound_fixed += fixed_space;
 455           wish_count++;
 456         }
 457     }
 458
 459   if (compound_space <= 0.0 || !wish_count)
 460     {
 461       standard_breakable_column_spacing (me, l, r, &compound_fixed, &compound_space,
 462                                          options);
 463       wish_count = 1;
 464     }
 465   else
 466     {
 467       if (to_boolean (me->get_property ("average-spacing-wishes")))
 468         {
 469           compound_space /= wish_count;
 470           compound_fixed /= wish_count;
 471         }
 472       else
 473         {
 474           compound_fixed = max_fixed;
 475           compound_space = max_space;
 476         }
 477
 478     }
 479
 480   if (options->stretch_uniformly_ && l->break_status_dir () != RIGHT)
 481     compound_fixed = 0.0;
 482
 483   assert (!isinf (compound_space));
 484   compound_space = max (compound_space, compound_fixed);
 485
 486   /*
 487     There used to be code that changed spacing depending on
 488     raggedright setting.  Ugh.
 489
 490     Do it more cleanly, or rename the property.
 491
 492   */
 493   Real inverse_strength = (compound_space - compound_fixed);
 494   Real distance = compound_space;
 495   Spaceable_grob::add_spring (l, r, distance, inverse_strength);
 496 }
 497
 498 ADD_INTERFACE (Spacing_spanner,
 499                "The space taken by a note is dependent on its duration. Doubling a\n"
 500                "duration adds spacing-increment to the space. The most common shortest\n"
 501                "note gets @code{shortest-duration-space}. Notes that are even shorter are\n"
 502                "spaced proportonial to their duration.\n"
 503                "\n"
 504                "Typically, the increment is the width of a black note head.  In a\n"
 505                "piece with lots of 8th notes, and some 16th notes, the eighth note\n"
 506                "gets 2 note heads width (i.e. the space following a note is 1 note\n"
 507                "head width) A 16th note is followed by 0.5 note head width. The\n"
 508                "quarter note is followed by  3 NHW, the half by 4 NHW, etc.\n",
 509
 510
 511                "average-spacing-wishes "
 512                "base-shortest-duration "
 513                "common-shortest-duration "
 514                "packed-spacing "
 515                "shortest-duration-space "
 516                "spacing-increment "
 517                "strict-grace-spacing "
 518                "strict-note-spacing "
 519                "uniform-stretching "
 520
 521                );
 522
 523 ADD_INTERFACE (Spacing_interface,
 524                "Something to do with line breaking and spacing. "
 525                "Kill this one after determining line breaks.",
 526
 527                "");
 528