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