lily/accidental-placement.cc

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