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   uniquify (ret);
 347   return ret;
 348 }
 349
 350 static Grob *
 351 common_refpoint_of_accidentals (vector<Accidental_placement_entry *> const &apes, Axis a)
 352 {
 353   Grob *ret = 0;
 354
 355   for (vsize i = apes.size (); i--;)
 356     for (vsize j = apes[i]->grobs_.size (); j--;)
 357       {
 358         if (!ret)
 359           ret = apes[i]->grobs_[j];
 360         else
 361           ret = ret->common_refpoint (apes[i]->grobs_[j], a);
 362       }
 363
 364   return ret;
 365 }
 366
 367 static Skyline
 368 build_heads_skyline (vector<Grob *> const &heads_and_stems,
 369                      Grob **common)
 370 {
 371   vector<Box> head_extents;
 372   for (vsize i = heads_and_stems.size (); i--;)
 373     head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
 374                                  heads_and_stems[i]->pure_height (common[Y_AXIS], 0, INT_MAX)));
 375
 376   return Skyline (head_extents, Y_AXIS, LEFT);
 377 }
 378
 379 /*
 380   Position the apes, starting from the right, so that they don't collide.
 381   Return the total width.
 382 */
 383 static Interval
 384 position_apes (Grob *me,
 385                vector<Accidental_placement_entry *> const &apes,
 386                Skyline const &heads_skyline)
 387 {
 388   Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
 389   Skyline left_skyline = heads_skyline;
 390   left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
 391
 392   /*
 393     Add accs entries right-to-left.
 394   */
 395   Interval width;
 396   Real last_offset = 0.0;
 397   for (vsize i = apes.size (); i-- > 0;)
 398     {
 399       Accidental_placement_entry *ape = apes[i];
 400
 401       Real offset = -ape->horizontal_skylines_[RIGHT].distance (left_skyline);
 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);
 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               );