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