lily/accidental-placement.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2002--2012 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "accidental-placement.hh"
  21
  22 #include "accidental-interface.hh"
  23 #include "item.hh"
  24 #include "music.hh"
  25 #include "note-collision.hh"
  26 #include "note-column.hh"
  27 #include "pointer-group-interface.hh"
  28 #include "rhythmic-head.hh"
  29 #include "skyline.hh"
  30 #include "stream-event.hh"
  31 #include "warn.hh"
  32
  33 static Pitch *
  34 accidental_pitch (Grob *acc)
  35 {
  36   SCM cause = acc->get_parent (Y_AXIS)->get_property ("cause");
  37
  38   Stream_event *mcause = unsmob_stream_event (cause);
  39   if (!mcause)
  40     {
  41       programming_error ("note head has no event cause");
  42       return 0;
  43     }
  44
  45   return unsmob_pitch (mcause->get_property ("pitch"));
  46 }
  47
  48 void
  49 Accidental_placement::add_accidental (Grob *me, Grob *a)
  50 {
  51   Pitch *p = accidental_pitch (a);
  52   if (!p)
  53     return;
  54
  55   a->set_parent (me, X_AXIS);
  56   a->set_property ("X-offset", Grob::x_parent_positioning_proc);
  57   int n = p->get_notename ();
  58
  59   SCM accs = me->get_object ("accidental-grobs");
  60   SCM key = scm_from_int (n);
  61   SCM entry = scm_assq (key, accs);
  62   if (entry == SCM_BOOL_F)
  63     entry = SCM_EOL;
  64   else
  65     entry = scm_cdr (entry);
  66
  67   entry = scm_cons (a->self_scm (), entry);
  68
  69   accs = scm_assq_set_x (accs, key, entry);
  70
  71   me->set_object ("accidental-grobs", accs);
  72 }
  73
  74 /*
  75   Split into break reminders.
  76 */
  77 void
  78 Accidental_placement::split_accidentals (Grob *accs,
  79                                          vector<Grob *> *break_reminder,
  80                                          vector<Grob *> *real_acc)
  81 {
  82   for (SCM acs = accs->get_object ("accidental-grobs"); scm_is_pair (acs);
  83        acs = scm_cdr (acs))
  84     for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
  85       {
  86         Grob *a = unsmob_grob (scm_car (s));
  87
  88         if (unsmob_grob (a->get_object ("tie"))
  89             && !to_boolean (a->get_property ("forced")))
  90           break_reminder->push_back (a);
  91         else
  92           real_acc->push_back (a);
  93       }
  94 }
  95
  96 vector<Grob *>
  97 Accidental_placement::get_relevant_accidentals (vector<Grob *> const &elts, Grob *left)
  98 {
  99   vector<Grob *> br;
 100   vector<Grob *> ra;
 101   vector<Grob *> ret;
 102   bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
 103
 104   for (vsize i = 0; i < elts.size (); i++)
 105     {
 106       split_accidentals (elts[i], &br, &ra);
 107
 108       ret.insert (ret.end (), ra.begin (), ra.end ());
 109
 110       if (right)
 111         ret.insert (ret.end (), br.begin (), br.end ());
 112     }
 113   return ret;
 114 }
 115
 116 struct Accidental_placement_entry
 117 {
 118   Skyline left_skyline_;
 119   Skyline right_skyline_;
 120   Interval vertical_extent_;
 121   vector<Box> extents_;
 122   vector<Grob *> grobs_;
 123 };
 124
 125 Real ape_priority (Accidental_placement_entry const *a)
 126 {
 127   return a->vertical_extent_[UP];
 128 }
 129
 130 bool ape_less (Accidental_placement_entry *const &a,
 131                Accidental_placement_entry *const &b)
 132 {
 133   return ape_priority (a) < ape_priority (b);
 134 }
 135
 136 /*
 137   This function provides a method for sorting accidentals that belong to the
 138   same note. The accidentals that this function considers to be "smallest"
 139   will be placed to the left of the "larger" accidentals.
 140
 141   Naturals are the largest (so that they don't get confused with cancellation
 142   naturals); apart from that, we order according to the alteration (so
 143   double-flats are the smallest).
 144
 145   Precondition: the accidentals are attached to NoteHeads of the same note
 146   name -- the octaves, however, may be different.
 147 */
 148 static bool
 149 acc_less (Grob *const &a, Grob *const &b)
 150 {
 151   Pitch *p = accidental_pitch (a);
 152   Pitch *q = accidental_pitch (b);
 153
 154   if (!p || !q)
 155     {
 156       programming_error ("these accidentals do not have a pitch");
 157       return false;
 158     }
 159
 160   if (p->get_octave () != q->get_octave ())
 161     return p->get_octave () < q->get_octave ();
 162
 163   if (p->get_alteration () == Rational (0))
 164     return false;
 165   if (q->get_alteration () == Rational (0))
 166     return true;
 167
 168   return p->get_alteration () < q->get_alteration ();
 169 }
 170
 171 /*
 172   TODO: should favor
 173
 174   *  b
 175   * b
 176
 177   placement
 178 */
 179 void
 180 stagger_apes (vector<Accidental_placement_entry *> *apes)
 181 {
 182   vector<Accidental_placement_entry *> asc = *apes;
 183
 184   vector_sort (asc, &ape_less);
 185
 186   apes->clear ();
 187
 188   int parity = 1;
 189   for (vsize i = 0; i < asc.size ();)
 190     {
 191       Accidental_placement_entry *a = 0;
 192       if (parity)
 193         {
 194           a = asc.back ();
 195           asc.pop_back ();
 196         }
 197       else
 198         a = asc[i++];
 199
 200       apes->push_back (a);
 201       parity = !parity;
 202     }
 203
 204   reverse (*apes);
 205 }
 206
 207 static vector<Accidental_placement_entry *>
 208 build_apes (SCM accs)
 209 {
 210   vector<Accidental_placement_entry *> apes;
 211   for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
 212     {
 213       Accidental_placement_entry *ape = new Accidental_placement_entry;
 214
 215       for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
 216         ape->grobs_.push_back (unsmob_grob (scm_car (t)));
 217
 218       apes.push_back (ape);
 219     }
 220
 221   return apes;
 222 }
 223
 224 static void
 225 set_ape_skylines (Accidental_placement_entry *ape,
 226                   Grob **common, Real padding)
 227 {
 228   vector<Grob *> accs (ape->grobs_);
 229   vector_sort (accs, &acc_less);
 230
 231   /* We know that each accidental has the same note name and we assume that
 232      accidentals in different octaves won't collide. If two or more
 233      accidentals are in the same octave:
 234      1) if they are the same accidental, print them in overstrike
 235      2) otherwise, shift one to the left so they don't overlap. */
 236   int last_octave = 0;
 237   Real offset = 0;
 238   Real last_offset = 0;
 239   Rational last_alteration (0);
 240   for (vsize i = accs.size (); i--;)
 241     {
 242       Grob *a = accs[i];
 243       Pitch *p = accidental_pitch (a);
 244
 245       if (!p)
 246         continue;
 247
 248       if (i == accs.size () - 1 || p->get_octave () != last_octave)
 249         {
 250           last_offset = 0;
 251           offset = a->extent (a, X_AXIS)[LEFT] - padding;
 252         }
 253       else if (p->get_alteration () == last_alteration)
 254         a->translate_axis (last_offset, X_AXIS);
 255       else /* Our alteration is different from the last one */
 256         {
 257           Real this_offset = offset - a->extent (a, X_AXIS)[RIGHT];
 258           a->translate_axis (this_offset, X_AXIS);
 259
 260           last_offset = this_offset;
 261           offset -= a->extent (a, X_AXIS).length () + padding;
 262         }
 263
 264       vector<Box> boxes = Accidental_interface::accurate_boxes (a, common);
 265       ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ());
 266
 267       for (vsize j = boxes.size (); j--;)
 268         ape->vertical_extent_.unite (boxes[j][Y_AXIS]);
 269
 270       last_octave = p->get_octave ();
 271       last_alteration = p->get_alteration ();
 272     }
 273   ape->left_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, LEFT);
 274   ape->right_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, RIGHT);
 275 }
 276
 277 static vector<Grob *>
 278 extract_heads_and_stems (vector<Accidental_placement_entry *> const &apes)
 279 {
 280   vector<Grob *> note_cols;
 281   vector<Grob *> ret;
 282
 283   for (vsize i = apes.size (); i--;)
 284     {
 285       Accidental_placement_entry *ape = apes[i];
 286       for (vsize j = ape->grobs_.size (); j--;)
 287         {
 288           Grob *acc = ape->grobs_[j];
 289           Grob *head = acc->get_parent (Y_AXIS);
 290           Grob *col = head->get_parent (X_AXIS);
 291
 292           if (Note_column::has_interface (col))
 293             note_cols.push_back (col);
 294           else
 295             ret.push_back (head);
 296         }
 297     }
 298
 299   /*
 300     This is a little kludgy: in case there are note columns without
 301     accidentals, we get them from the Note_collision objects.
 302   */
 303   for (vsize i = note_cols.size (); i--;)
 304     {
 305       Grob *c = note_cols[i]->get_parent (X_AXIS);
 306       if (Note_collision_interface::has_interface (c))
 307         {
 308           extract_grob_set (c, "elements", columns);
 309           concat (note_cols, columns);
 310         }
 311     }
 312
 313   /* Now that we have all of the columns, grab all of the note-heads */
 314   for (vsize i = note_cols.size (); i--;)
 315     concat (ret, extract_grob_array (note_cols[i], "note-heads"));
 316
 317   /* Now that we have all of the heads, grab all of the stems */
 318   for (vsize i = ret.size (); i--;)
 319     if (Grob *s = Rhythmic_head::get_stem (ret[i]))
 320       ret.push_back (s);
 321
 322   vector_sort (ret, less<Grob *> ());
 323   uniq (ret);
 324   return ret;
 325 }
 326
 327 static Grob *
 328 common_refpoint_of_accidentals (vector<Accidental_placement_entry *> const &apes, Axis a)
 329 {
 330   Grob *ret = 0;
 331
 332   for (vsize i = apes.size (); i--;)
 333     for (vsize j = apes[i]->grobs_.size (); j--;)
 334       {
 335         if (!ret)
 336           ret = apes[i]->grobs_[j];
 337         else
 338           ret = ret->common_refpoint (apes[i]->grobs_[j], a);
 339       }
 340
 341   return ret;
 342 }
 343
 344 static Skyline
 345 build_heads_skyline (vector<Grob *> const &heads_and_stems,
 346                      Grob **common)
 347 {
 348   vector<Box> head_extents;
 349   for (vsize i = heads_and_stems.size (); i--;)
 350     head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
 351                                  heads_and_stems[i]->pure_height (common[Y_AXIS], 0, INT_MAX)));
 352
 353   return Skyline (head_extents, 0, Y_AXIS, LEFT);
 354 }
 355
 356 /*
 357   Position the apes, starting from the right, so that they don't collide.
 358   Return the total width.
 359 */
 360 static Interval
 361 position_apes (Grob *me,
 362                vector<Accidental_placement_entry *> const &apes,
 363                Skyline const &heads_skyline)
 364 {
 365   Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
 366   Skyline left_skyline = heads_skyline;
 367   left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
 368
 369   /*
 370     Add accs entries right-to-left.
 371   */
 372   Interval width;
 373   Real last_offset = 0.0;
 374   for (vsize i = apes.size (); i-- > 0;)
 375     {
 376       Accidental_placement_entry *ape = apes[i];
 377
 378       Real offset = -ape->right_skyline_.distance (left_skyline);
 379       if (isinf (offset))
 380         offset = last_offset;
 381       else
 382         offset -= padding;
 383
 384       Skyline new_left_skyline = ape->left_skyline_;
 385       new_left_skyline.raise (offset);
 386       new_left_skyline.merge (left_skyline);
 387       left_skyline = new_left_skyline;
 388
 389       /* Shift all of the accidentals in this ape */
 390       for (vsize j = ape->grobs_.size (); j--;)
 391         ape->grobs_[j]->translate_axis (offset, X_AXIS);
 392
 393       for (vsize j = ape->extents_.size (); j--;)
 394         width.unite (offset + ape->extents_[j][X_AXIS]);
 395
 396       last_offset = offset;
 397     }
 398
 399   return width;
 400 }
 401
 402 /*
 403   This routine computes placements of accidentals. During
 404   add_accidental (), accidentals are already grouped by note, so that
 405   octaves are placed above each other; they form columns. Then the
 406   columns are sorted: the biggest columns go closest to the note.
 407   Then the columns are spaced as closely as possible (using skyline
 408   spacing).
 409
 410
 411   TODO: more advanced placement. Typically, the accs should be placed
 412   to form a C shape, like this
 413
 414   *     ##
 415   *  b b
 416   * # #
 417   *  b
 418   *    b b
 419
 420   The naturals should be left of the C as well; they should
 421   be separate accs.
 422
 423   Note that this placement problem looks NP hard, so we just use a
 424   simple strategy, not an optimal choice.
 425 */
 426
 427 /*
 428   TODO: there should be more space in the following situation
 429
 430
 431   Natural + downstem
 432
 433   *
 434   *  |_
 435   *  | |    X
 436   *  |_|   |
 437   *    |   |
 438   *
 439 */
 440
 441 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
 442 SCM
 443 Accidental_placement::calc_positioning_done (SCM smob)
 444 {
 445   Grob *me = unsmob_grob (smob);
 446   if (!me->is_live ())
 447     return SCM_BOOL_T;
 448
 449   me->set_property ("positioning-done", SCM_BOOL_T);
 450
 451   SCM accs = me->get_object ("accidental-grobs");
 452   if (!scm_is_pair (accs))
 453     return SCM_BOOL_T;
 454
 455   vector<Accidental_placement_entry *> apes = build_apes (accs);
 456
 457   Grob *common[] = {me, 0};
 458
 459   vector<Grob *> heads_and_stems = extract_heads_and_stems (apes);
 460
 461   common[Y_AXIS] = common_refpoint_of_accidentals (apes, Y_AXIS);
 462   common[Y_AXIS] = common_refpoint_of_array (heads_and_stems, common[Y_AXIS], Y_AXIS);
 463   common[X_AXIS] = common_refpoint_of_array (heads_and_stems, me, X_AXIS);
 464   Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
 465
 466   for (vsize i = apes.size (); i--;)
 467     set_ape_skylines (apes[i], common, padding);
 468   Skyline heads_skyline = build_heads_skyline (heads_and_stems, common);
 469
 470   stagger_apes (&apes);
 471   Interval width = position_apes (me, apes, heads_skyline);
 472
 473   me->flush_extent_cache (X_AXIS);
 474   me->set_property ("X-extent", ly_interval2scm (width));
 475
 476   junk_pointers (apes);
 477
 478   return SCM_BOOL_T;
 479 }
 480
 481 ADD_INTERFACE (Accidental_placement,
 482                "Resolve accidental collisions.",
 483
 484                /* properties */
 485                "accidental-grobs "
 486                "direction "
 487                "padding "
 488                "positioning-done "
 489                "right-padding "
 490                "script-priority "
 491               );