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