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