lily/accidental-placement.cc

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