lily/accidental-placement.cc

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