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