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--2007 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           break_reminder->push_back (a);
  73         else
  74           real_acc->push_back (a);
  75       }
  76 }
  77
  78 vector<Grob*>
  79 Accidental_placement::get_relevant_accidentals (vector<Grob*> const &elts, Grob *left)
  80 {
  81   vector<Grob*> br;
  82   vector<Grob*> ra;
  83   vector<Grob*> ret;
  84   bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
  85
  86   for (vsize i = 0; i < elts.size (); i++)
  87     {
  88       split_accidentals (elts[i], &br, &ra);
  89
  90       ret.insert (ret.end (), ra.begin (), ra.end ());
  91
  92       if (right)
  93         ret.insert (ret.end (), br.begin (), br.end ());
  94     }
  95   return ret;
  96 }
  97
  98 struct Accidental_placement_entry
  99 {
 100   Skyline left_skyline_;
 101   Skyline right_skyline_;
 102   Interval vertical_extent_;
 103   vector<Box> extents_;
 104   vector<Grob*> grobs_;
 105   Real offset_;
 106   int notename_;
 107   Accidental_placement_entry ()
 108   {
 109     offset_ = 0.0;
 110     notename_ = -1;
 111   }
 112 };
 113
 114 static Interval all_accidental_vertical_extent;
 115 Real ape_priority (Accidental_placement_entry const *a)
 116 {
 117   return a->vertical_extent_[UP];
 118 }
 119
 120 int ape_compare (Accidental_placement_entry *const &a,
 121                  Accidental_placement_entry *const &b)
 122 {
 123   return sign (ape_priority (a) - ape_priority (b));
 124 }
 125
 126 bool ape_less (Accidental_placement_entry *const &a,
 127                Accidental_placement_entry *const &b)
 128 {
 129   return ape_priority (a) < ape_priority (b);
 130 }
 131
 132 int ape_rcompare (Accidental_placement_entry *const &a,
 133                   Accidental_placement_entry *const &b)
 134 {
 135   return -sign (ape_priority (a) - ape_priority (b));
 136 }
 137
 138 /*
 139   TODO: should favor
 140
 141   b
 142   b
 143
 144   placement
 145 */
 146 void
 147 stagger_apes (vector<Accidental_placement_entry*> *apes)
 148 {
 149   vector<Accidental_placement_entry*> asc = *apes;
 150
 151   vector_sort (asc, &ape_less);
 152
 153   apes->clear ();
 154
 155   int parity = 1;
 156   for (vsize i = 0; i < asc.size ();)
 157     {
 158       Accidental_placement_entry *a = 0;
 159       if (parity)
 160         {
 161           a = asc.back ();
 162           asc.pop_back ();
 163         }
 164       else
 165         a = asc[i++];
 166
 167       apes->push_back (a);
 168       parity = !parity;
 169     }
 170
 171   reverse (*apes);
 172 }
 173
 174 /*
 175   This routine computes placements of accidentals. During
 176   add_accidental (), accidentals are already grouped by note, so that
 177   octaves are placed above each other; they form columns. Then the
 178   columns are sorted: the biggest columns go closest to the note.
 179   Then the columns are spaced as closely as possible (using skyline
 180   spacing).
 181
 182
 183   TODO: more advanced placement. Typically, the accs should be placed
 184   to form a C shape, like this
 185
 186
 187   ##
 188   b b
 189   # #
 190   b
 191   b b
 192
 193   The naturals should be left of the C as well; they should
 194   be separate accs.
 195
 196   Note that this placement problem looks NP hard, so we just use a
 197   simple strategy, not an optimal choice.
 198 */
 199
 200 /*
 201   TODO: there should be more space in the following situation
 202
 203
 204   Natural + downstem
 205
 206   *
 207   *  |_
 208   *  | |    X
 209   *  |_|   |
 210   *    |   |
 211   *
 212
 213 */
 214
 215 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
 216 SCM
 217 Accidental_placement::calc_positioning_done (SCM smob)
 218 {
 219   Grob *me = unsmob_grob (smob);
 220   if (!me->is_live ())
 221     return SCM_BOOL_T;
 222
 223   me->set_property ("positioning-done", SCM_BOOL_T);
 224
 225   SCM accs = me->get_object ("accidental-grobs");
 226   if (!scm_is_pair (accs))
 227     return SCM_BOOL_T;
 228
 229   /*
 230     TODO: there is a bug in this code. If two accs are on the same
 231     Y-position, they share an Ape, and will be printed in overstrike.
 232   */
 233   vector<Accidental_placement_entry*> apes;
 234   for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
 235     {
 236       Accidental_placement_entry *ape = new Accidental_placement_entry;
 237       ape->notename_ = scm_to_int (scm_caar (s));
 238
 239       for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
 240         ape->grobs_.push_back (unsmob_grob (scm_car (t)));
 241
 242       apes.push_back (ape);
 243     }
 244
 245   Grob *common[] = {me, 0};
 246
 247   /*
 248     First we must extract *all* pointers. We can only determine
 249     extents if we're sure that we've found the right common refpoint
 250   */
 251   vector<Grob*> note_cols, heads;
 252   for (vsize i = apes.size (); i--;)
 253     {
 254       Accidental_placement_entry *ape = apes[i];
 255       for (vsize j = ape->grobs_.size (); j--;)
 256         {
 257           Grob *a = ape->grobs_[j];
 258
 259           if (common[Y_AXIS])
 260             common[Y_AXIS] = common[Y_AXIS]->common_refpoint (a, Y_AXIS);
 261           else
 262             common[Y_AXIS] = a;
 263
 264           Grob *head = a->get_parent (Y_AXIS);
 265
 266           Grob *col = head->get_parent (X_AXIS);
 267           if (Note_column::has_interface (col))
 268             note_cols.push_back (col);
 269           else
 270             heads.push_back (head);
 271         }
 272     }
 273
 274   /*
 275     This is a little kludgy: to get all notes, we look if there are
 276     collisions as well.
 277   */
 278   for (vsize i = note_cols.size (); i--;)
 279     {
 280       Grob *c = note_cols[i]->get_parent (X_AXIS);
 281       if (Note_collision_interface::has_interface (c))
 282         {
 283           extract_grob_set (c, "elements", gs);
 284
 285           concat (note_cols, gs);
 286         }
 287     }
 288
 289   for (vsize i = note_cols.size (); i--;)
 290     concat (heads, extract_grob_array (note_cols[i], "note-heads"));
 291
 292   vector_sort (heads, less<Grob*> ());
 293   uniq (heads);
 294
 295   vector<Grob *> stems;
 296   for (vsize i = 0; i < heads.size  (); i++)
 297     {
 298       if (Grob *s = Rhythmic_head::get_stem (heads[i]))
 299         stems.push_back (s);
 300     }
 301
 302   vector_sort (stems, less<Grob*> ());
 303   uniq (stems);
 304
 305   common[Y_AXIS] = common_refpoint_of_array (heads, common[Y_AXIS], Y_AXIS);
 306   common[Y_AXIS] = common_refpoint_of_array (stems, common[Y_AXIS], Y_AXIS);
 307
 308   for (vsize i = 0; i < heads.size  (); i++)
 309     {
 310       if (Grob *s = Rhythmic_head::get_stem (heads[i]))
 311         {
 312           stems.push_back (s);
 313           common[Y_AXIS] = s->common_refpoint (common[Y_AXIS], Y_AXIS);
 314         }
 315     }
 316
 317   vector_sort (stems, less<Grob*> ());
 318   uniq (stems);
 319
 320
 321   for (vsize i = apes.size (); i--;)
 322     {
 323       Accidental_placement_entry *ape = apes[i];
 324
 325       for (vsize j = apes[i]->grobs_.size (); j--;)
 326         {
 327           Grob *a = apes[i]->grobs_[j];
 328           vector<Box> boxes = Accidental_interface::accurate_boxes (a, common);
 329
 330           ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ());
 331         }
 332       ape->left_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, LEFT);
 333       ape->right_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, RIGHT);
 334     }
 335
 336   Interval total;
 337   for (vsize i = apes.size (); i--;)
 338     {
 339       Interval y;
 340
 341       for (vsize j = apes[i]->extents_.size (); j--;)
 342         y.unite (apes[i]->extents_[j][Y_AXIS]);
 343       apes[i]->vertical_extent_ = y;
 344       total.unite (y);
 345     }
 346   all_accidental_vertical_extent = total;
 347   stagger_apes (&apes);
 348
 349   Accidental_placement_entry *head_ape = new Accidental_placement_entry;
 350   common[X_AXIS] = common_refpoint_of_array (heads, common[X_AXIS], X_AXIS);
 351
 352   vector<Box> head_extents;
 353   for (vsize i = heads.size (); i--;)
 354     head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS),
 355                                  heads[i]->extent (common[Y_AXIS], Y_AXIS)));
 356
 357   for (vsize i = 0; i < stems.size (); i ++)
 358     {
 359       int very_large = INT_MAX;
 360
 361       head_extents.push_back (Box (stems[i]->extent (common[X_AXIS], X_AXIS),
 362                                    stems[i]->pure_height (common[Y_AXIS], 0, very_large)));
 363     }
 364
 365   head_ape->left_skyline_ = Skyline (head_extents, 0, Y_AXIS, LEFT);
 366   head_ape->offset_ = 0.0;
 367
 368   Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
 369
 370   Skyline left_skyline = head_ape->left_skyline_;
 371   left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
 372
 373   /*
 374     Add accs entries right-to-left.
 375   */
 376   for (vsize i = apes.size (); i-- > 0;)
 377     {
 378       Real offset = -apes[i]->right_skyline_.distance (left_skyline);
 379       if (isinf (offset))
 380         offset = (i + 1 < apes.size ()) ? apes[i + 1]->offset_ : 0.0;
 381       else
 382         offset -= padding;
 383
 384       apes[i]->offset_ = offset;
 385
 386       Skyline new_left_skyline = apes[i]->left_skyline_;
 387       new_left_skyline.raise (apes[i]->offset_);
 388       new_left_skyline.merge (left_skyline);
 389       left_skyline = new_left_skyline;
 390     }
 391
 392   for (vsize i = apes.size (); i--;)
 393     {
 394       Accidental_placement_entry *ape = apes[i];
 395       for (vsize j = ape->grobs_.size (); j--;)
 396         ape->grobs_[j]->translate_axis (ape->offset_, X_AXIS);
 397     }
 398
 399   Interval left_extent, right_extent;
 400   Accidental_placement_entry *ape = apes[0];
 401
 402   for (vsize i = ape->extents_.size (); i--;)
 403     left_extent.unite (ape->offset_ + ape->extents_[i][X_AXIS]);
 404
 405   ape = apes.back ();
 406   for (vsize i = ape->extents_.size (); i--;)
 407     right_extent.unite (ape->offset_ + ape->extents_[i][X_AXIS]);
 408
 409   left_extent[LEFT] -= robust_scm2double (me->get_property ("left-padding"), 0);
 410   Interval width (left_extent[LEFT], right_extent[RIGHT]);
 411
 412   SCM scm_width = ly_interval2scm (width);
 413   me->flush_extent_cache (X_AXIS);
 414   me->set_property ("X-extent", scm_width);
 415
 416   junk_pointers (apes);
 417
 418   delete head_ape;
 419
 420   return SCM_BOOL_T;
 421 }
 422
 423 ADD_INTERFACE (Accidental_placement,
 424                "Resolve accidental collisions.",
 425
 426                /* properties */
 427                "accidental-grobs "
 428                "left-padding "
 429                "padding "
 430                "positioning-done "
 431                "right-padding "
 432                "script-priority "
 433                )