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