lily/beaming-pattern.cc

   1 /*
   2   beaming-info.cc -- implement Beam_rhythmic_element, Beaming_pattern
   3
   4   A Beaming_pattern object takes a set of stems at given moments and calculates
   5   the pattern of their beam. That is, it works out, for each stem, how many
   6   beams should be connected to the right and left sides of that stem. In
   7   calculating this, Beaming_pattern takes into account
   8    - the rhythmic position of the stems
   9    - the options that are defined in Beaming_options
  10
  11   source file of the GNU LilyPond music typesetter
  12
  13   (c) 1999--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
  14 */
  15
  16 #include "beaming-pattern.hh"
  17 #include "context.hh"
  18
  19 Beam_rhythmic_element::Beam_rhythmic_element ()
  20 {
  21   start_moment_ = 0;
  22   beam_count_drul_[LEFT] = 0;
  23   beam_count_drul_[RIGHT] = 0;
  24   invisible_ = false;
  25
  26 }
  27
  28 Beam_rhythmic_element::Beam_rhythmic_element (Moment m, int i, bool inv)
  29 {
  30   start_moment_ = m;
  31   beam_count_drul_[LEFT] = i;
  32   beam_count_drul_[RIGHT] = i;
  33   invisible_ = inv;
  34 }
  35
  36
  37 void
  38 Beam_rhythmic_element::de_grace ()
  39 {
  40   if (start_moment_.grace_part_)
  41     {
  42       start_moment_.main_part_ = start_moment_.grace_part_;
  43       start_moment_.grace_part_ = 0;
  44     }
  45 }
  46
  47 int
  48 count_factor_twos (int x)
  49 {
  50   int c = 0;
  51   while (x && x % 2 == 0)
  52     {
  53       x /= 2;
  54       c ++;
  55     }
  56
  57   return c;
  58 }
  59
  60 /*
  61   Returns true if splitting at the given index will result in a gap
  62   between an invisible stem and a visible stem whose number of beams
  63   is larger than the number of beams of the invisible stem.
  64 */
  65 bool
  66 Beaming_pattern::is_next_to_invisible_stem (vsize i) const
  67 {
  68   if (i == 0)
  69     return false;
  70
  71   // In fact, we don't need to check that the visible stem has more beams
  72   // than the invisible stem. unbeam_invisible_stems() ensures that the
  73   // visible stem has at least as many stems as the invisible stem, so
  74   // we only need to check that they are not equal.
  75   return infos_[i].invisible_ != infos_[i-1].invisible_
  76     && infos_[i].beam_count_drul_[LEFT] != infos_[i-1].beam_count_drul_[RIGHT];
  77 }
  78
  79 /*
  80   Finds the best point at which to subdivide a beam. In order of priority
  81   (highest to lowest) this is
  82    - before or after an invisible beam
  83        - at the start of a beat group
  84        - at the start of a beat
  85        - whose position in its beat has the smallest denominator (that is,
  86          a stem that starts halfway through a beat will be preferred over stems
  87          that start 1/3 or 2/3s of the way through the beat).
  88    - any other beam
  89        - at the start of a beat group
  90        - at the start of a beat
  91        - whose position in its beat has the smallest denominator
  92
  93    If the split point occurs at the start of a beat group or at the start of a
  94    beat, at_boundary will be set to true. Otherwise, it will be set to false.
  95 */
  96 int
  97 Beaming_pattern::best_splitpoint_index (bool *at_boundary) const
  98 {
  99   bool require_invisible = false;
 100   for (vsize i = 0; i < infos_.size (); i++)
 101     require_invisible |= is_next_to_invisible_stem (i);
 102
 103   *at_boundary = true;
 104   for (vsize i = 1; i < infos_.size (); i++)
 105     {
 106       if (infos_[i].group_start_ == infos_[i].start_moment_
 107           && (!require_invisible || is_next_to_invisible_stem (i)))
 108         return i;
 109     }
 110
 111   for (vsize i = 1; i < infos_.size (); i++)
 112     {
 113       if (infos_[i].beat_start_ == infos_[i].start_moment_
 114           && (!require_invisible || is_next_to_invisible_stem (i)))
 115         return i;
 116     }
 117
 118   *at_boundary = false;
 119
 120   int min_den = INT_MAX;
 121   int min_index = -1;
 122
 123   for (vsize i = 1; i < infos_.size (); i++)
 124     {
 125       Moment dt = infos_[i].start_moment_ - infos_[i].beat_start_;
 126
 127       /*
 128         This is a kludge, for the most common case of 16th, 32nds
 129         etc. What should really happen is that \times x/y should
 130         locally introduce a voice-specific beat duration.  (or
 131         perhaps: a list of beat durations for nested tuplets.)
 132
 133        */
 134
 135       dt /= infos_[i].beat_length_;
 136
 137       if (dt.den () < min_den
 138           && (!require_invisible || is_next_to_invisible_stem (i)))
 139         {
 140           min_den = dt.den ();
 141           min_index = i;
 142         }
 143     }
 144
 145   return min_index;
 146 }
 147
 148 int
 149 Beaming_pattern::beam_extend_count (Direction d) const
 150 {
 151   if (infos_.size () == 1)
 152     return infos_[0].beam_count_drul_[d];
 153
 154   Beam_rhythmic_element thisbeam = boundary (infos_, d, 0);
 155   Beam_rhythmic_element next = boundary (infos_, d, 1);
 156
 157   return min (thisbeam.beam_count_drul_[-d], next.beam_count_drul_[d]);
 158 }
 159
 160 void
 161 Beaming_pattern::de_grace ()
 162 {
 163   for (vsize i = 0; i < infos_.size (); i ++)
 164     {
 165       infos_[i].de_grace ();
 166     }
 167 }
 168
 169 void
 170 Beaming_pattern::beamify (Beaming_options const &options)
 171 {
 172   unbeam_invisible_stems ();
 173
 174   if (infos_.size () <= 1)
 175     return;
 176
 177   if (infos_[0].start_moment_.grace_part_)
 178     de_grace ();
 179
 180   if (infos_[0].start_moment_ < Moment (0))
 181     for (vsize i = 0; i < infos_.size (); i++)
 182       infos_[i].start_moment_ += options.measure_length_;
 183
 184   Moment measure_pos (0);
 185
 186   vector<Moment> group_starts;
 187   vector<Moment> beat_starts;
 188
 189   // Find the starting moments of the beats and the groups.
 190   SCM grouping = options.grouping_;
 191   while (measure_pos <= infos_.back ().start_moment_)
 192     {
 193       int count = 2;
 194       if (scm_is_pair (grouping))
 195         {
 196           count = scm_to_int (scm_car (grouping));
 197           grouping = scm_cdr (grouping);
 198         }
 199
 200       group_starts.push_back (measure_pos);
 201       for (int i = 0; i < count; i++)
 202         {
 203           beat_starts.push_back (measure_pos + options.beat_length_ * i);
 204         }
 205       measure_pos += options.beat_length_ * count;
 206     }
 207
 208   // Set the group_start_ and beam_start_ properties of each stem.
 209   vsize j = 0;
 210   vsize k = 0;
 211   for (vsize i = 0; i  < infos_.size (); i++)
 212     {
 213       while (j + 1 < group_starts.size ()
 214              && group_starts[j+1] <= infos_[i].start_moment_)
 215         j++;
 216
 217       if (j < group_starts.size ())
 218         infos_[i].group_start_ = group_starts[j];
 219
 220       infos_[i].beat_length_ = options.beat_length_;
 221       while (k + 1 < beat_starts.size ()
 222              && beat_starts[k+1] <= infos_[i].start_moment_)
 223         k++;
 224
 225       if (k < beat_starts.size ())
 226         infos_[i].beat_start_ = beat_starts[k];
 227     }
 228
 229   beamify (options.subdivide_beams_);
 230 }
 231
 232
 233 /*
 234   Determines beaming patterns by splitting the list of stems recursively.
 235
 236   Given a list of stems, we split it at the most 'natural' place (eg. at
 237   the beginning of a beat) as determined by best_splitpoint_index. We
 238   then beamify both subsets of beams. Finally, we determine the number of
 239   beams between the subsets.
 240
 241   Note: if one of the subsets has only one element, we will not modify its
 242   beams. This ensure that, for every stem, we will modify its beam count on at
 243   most one side.
 244 */
 245 void
 246 Beaming_pattern::beamify (bool subdivide_beams)
 247 {
 248   if (infos_.size () <= 1)
 249     return;
 250
 251   Drul_array<Beaming_pattern> splits;
 252
 253   bool at_boundary = false;
 254   int m = best_splitpoint_index (&at_boundary);
 255
 256   splits[LEFT].infos_ = vector<Beam_rhythmic_element> (infos_.begin (),
 257                                                        infos_.begin () + m);
 258   splits[RIGHT].infos_ = vector<Beam_rhythmic_element> (infos_.begin () + m,
 259                                                         infos_.end ());
 260
 261   Direction d = LEFT;
 262
 263   do
 264     {
 265       splits[d].beamify (subdivide_beams);
 266     }
 267   while (flip (&d) != LEFT);
 268
 269   int middle_beams = (at_boundary && subdivide_beams)
 270                       ? 1
 271                       : min (splits[RIGHT].beam_extend_count (LEFT),
 272                              splits[LEFT].beam_extend_count (RIGHT));
 273
 274   do
 275     {
 276       if (splits[d].infos_.size () != 1)
 277         boundary (splits[d].infos_, -d, 0).beam_count_drul_[-d] = middle_beams;
 278     }
 279   while (flip (&d) != LEFT);
 280
 281   infos_ = splits[LEFT].infos_;
 282   infos_.insert (infos_.end (),
 283                  splits[RIGHT].infos_.begin (),
 284                  splits[RIGHT].infos_.end ());
 285 }
 286
 287
 288 /*
 289   Invisible stems should be treated as though they have the same number of
 290   beams as their least-beamed neighbour. Here we go through the stems and
 291   modify the invisible stems to satisfy this requirement.
 292 */
 293 void
 294 Beaming_pattern::unbeam_invisible_stems ()
 295 {
 296   for (vsize i = 1; i < infos_.size (); i++)
 297     if (infos_[i].invisible_)
 298       {
 299         int b = infos_[i-1].beam_count_drul_[LEFT];
 300         infos_[i].beam_count_drul_[LEFT] = b;
 301         infos_[i].beam_count_drul_[RIGHT] = b;
 302       }
 303
 304   for (vsize i = infos_.size (); i--;)
 305     if (infos_[i].invisible_)
 306       {
 307         int b = min (infos_[i].beam_count_drul_[LEFT], infos_[i+1].beam_count_drul_[LEFT]);
 308         infos_[i].beam_count_drul_[LEFT] = b;
 309         infos_[i].beam_count_drul_[RIGHT] = b;
 310       }
 311 }
 312
 313
 314 void
 315 Beaming_pattern::add_stem (Moment m, int b, bool invisible)
 316 {
 317   infos_.push_back (Beam_rhythmic_element (m, b, invisible));
 318 }
 319
 320 Beaming_pattern::Beaming_pattern ()
 321 {
 322 }
 323
 324 int
 325 Beaming_pattern::beamlet_count (int i, Direction d) const
 326 {
 327   return infos_.at (i).beam_count_drul_[d];
 328 }
 329
 330 void
 331 Beaming_options::from_context (Context *context)
 332 {
 333   grouping_ = context->get_property ("beatGrouping");
 334   subdivide_beams_ = to_boolean (context->get_property ("subdivideBeams"));
 335   beat_length_ = robust_scm2moment (context->get_property ("beatLength"), Moment (1, 4));
 336   measure_length_ = robust_scm2moment (context->get_property ("measureLength"), Moment (1, 4));
 337 }
 338
 339 Beaming_options::Beaming_options ()
 340 {
 341   grouping_ = SCM_EOL;
 342   subdivide_beams_ = false;
 343 }