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