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