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 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8  */
   9
  10 #include <math.h>
  11 #include <libc-extension.hh>
  12 #include "item.hh"
  13 #include "skyline.hh"
  14 #include "music.hh"
  15 #include "pitch.hh"
  16 #include "warn.hh"
  17 #include "accidental-placement.hh"
  18 #include "note-column.hh"
  19 #include "group-interface.hh"
  20 #include "note-collision.hh"
  21 #include "accidental-interface.hh"
  22
  23 /*
  24   Hmm. why not group-extent?
  25  */
  26 MAKE_SCHEME_CALLBACK(Accidental_placement,extent_callback, 2);
  27 SCM
  28 Accidental_placement::extent_callback(SCM s, SCM axis)
  29 {
  30   Grob * me =unsmob_grob (s);
  31   Axis a = Axis (gh_scm2int (axis));
  32
  33   assert (a == X_AXIS);
  34
  35   SCM w = position_accidentals (me);
  36   return w;
  37 }
  38
  39 MAKE_SCHEME_CALLBACK(Accidental_placement,alignment_callback, 2);
  40 SCM
  41 Accidental_placement::alignment_callback(SCM s, SCM )
  42 {
  43   Grob * me =unsmob_grob (s);
  44
  45   Grob * par = me->get_parent (X_AXIS);
  46   if (!to_boolean (par->get_grob_property ("alignment-done")))
  47     {
  48       par->set_grob_property ("alignment-done", SCM_BOOL_T);
  49       position_accidentals (par);
  50     }
  51
  52   return gh_int2scm (0);
  53 }
  54
  55
  56
  57 void
  58 Accidental_placement::add_accidental (Grob* me, Grob* a)
  59 {
  60   a->set_parent (me, X_AXIS);
  61   a->add_offset_callback (alignment_callback_proc, X_AXIS);
  62   SCM cause = a->get_parent (Y_AXIS)->get_grob_property("cause");
  63
  64   Music *mcause =unsmob_music (cause);
  65   if (!mcause)
  66     {
  67       programming_error ("Note head has no music cause!");
  68       return;
  69     }
  70
  71   Pitch *p= unsmob_pitch (mcause->get_mus_property ("pitch"));
  72
  73   int n = p->notename_i_;
  74
  75   SCM accs = me->get_grob_property ("accidentals");
  76   SCM key = gh_int2scm (n);
  77   SCM entry = scm_assq (key, accs);
  78   if (entry == SCM_BOOL_F)
  79     {
  80       entry = SCM_EOL;
  81     }
  82   else
  83     entry = gh_cdr (entry);
  84
  85   entry = gh_cons (a->self_scm (), entry);
  86
  87   accs = scm_assq_set_x (accs,  key, entry);
  88
  89   me->set_grob_property ("accidentals", accs);
  90 }
  91
  92 /*
  93   Split into break reminders.
  94  */
  95 void
  96 Accidental_placement::split_accidentals (Grob * accs,
  97                                          Link_array<Grob> *break_reminder,
  98                                          Link_array<Grob> *real_acc)
  99 {
 100   for (SCM acs =accs->get_grob_property ("accidentals"); gh_pair_p (acs);
 101        acs =gh_cdr (acs))
 102     for (SCM s = gh_cdar (acs); gh_pair_p (s); s = gh_cdr (s))
 103       {
 104         Grob *a = unsmob_grob (gh_car (s));
 105
 106         if (unsmob_grob (a->get_grob_property ("tie")))
 107           break_reminder->push (a);
 108         else
 109           real_acc->push (a);
 110       }
 111 }
 112
 113 /*
 114   Accidentals are special, because they appear and disappear before
 115   and after ties at will.
 116 */
 117 Interval
 118 Accidental_placement::get_relevant_accidental_extent (Grob *me,
 119                                                       Item *item_col,
 120                                                       Grob *left_object)
 121 {
 122   Link_array<Grob> br, ra;
 123   Link_array<Grob> *which = 0;
 124
 125   Accidental_placement::split_accidentals (me, &br, &ra);
 126   br.concat (ra);
 127
 128   if (dynamic_cast<Item*>(left_object)->break_status_dir () == RIGHT)
 129     which = & br;
 130   else
 131     which = & ra;
 132
 133   Interval extent;
 134   for (int i = 0; i < which->size(); i++)
 135     {
 136       extent.unite (which->elem(i)->extent (item_col, X_AXIS));
 137     }
 138
 139   if (!extent.empty_b())
 140     {
 141       Real p = gh_scm2double (me->get_grob_property ("left-padding"));
 142       extent[LEFT] -= p;
 143     }
 144
 145   return extent;
 146 }
 147
 148
 149
 150 struct Accidental_placement_entry
 151 {
 152   Array<Skyline_entry> left_skyline_;
 153   Array<Skyline_entry> right_skyline_;
 154   Interval vertical_extent_;
 155   Array<Box> extents_;
 156   Link_array<Grob> grobs_;
 157   Real offset_;
 158   int notename_;
 159   Accidental_placement_entry()
 160   {
 161     offset_ =0.0;
 162     notename_ = -1;
 163   }
 164 };
 165
 166 static Interval all_accidental_vertical_extent;
 167 Real ape_priority (Accidental_placement_entry const * a)
 168 {
 169   return a->vertical_extent_[UP];
 170 }
 171
 172
 173
 174 int ape_compare (Accidental_placement_entry *const &a,
 175                  Accidental_placement_entry *const &b)
 176 {
 177   return sign (ape_priority (a) - ape_priority(b));
 178 }
 179
 180 int ape_rcompare (Accidental_placement_entry *const &a,
 181                  Accidental_placement_entry *const &b)
 182 {
 183   return -sign (ape_priority (a) - ape_priority(b));
 184 }
 185
 186
 187 /*
 188
 189 TODO: should favor
 190
 191   b
 192  b
 193
 194 placement
 195
 196 */
 197 void
 198 stagger_apes (Link_array<Accidental_placement_entry> *apes)
 199 {
 200   Link_array<Accidental_placement_entry> asc = *apes;
 201
 202
 203   asc.sort (&ape_compare);
 204
 205   apes->clear();
 206
 207   int i =0;
 208   int parity = 1;
 209   while (i < asc.size())
 210     {
 211       Accidental_placement_entry * a = 0;
 212       if (parity)
 213         a = asc.pop();
 214       else
 215         a = asc[i++];
 216
 217       apes->push (a);
 218       parity = !parity;
 219     }
 220
 221   apes->reverse();
 222 }
 223
 224
 225
 226 /*
 227   Return: width as SCM interval.
 228
 229
 230   This routine computes placements of accidentals. During
 231   add_accidental(), accidentals are already grouped by note, so that
 232   octaves are placed above each other; they form columns. Then the
 233   columns are sorted: the biggest columns go closest to the note.
 234   Then the columns are spaced as closely as possible (using skyline
 235   spacing).
 236
 237
 238   TODO: more advanced placement. Typically, the accs should be placed
 239   to form a C shape, like this
 240
 241
 242            ##
 243         b b
 244        # #
 245         b
 246           b b
 247
 248    The naturals should be left of the C as well; they should
 249    be separate accs.
 250
 251    Note that this placement problem looks NP hard, so we just use a
 252    simple strategy, not an optimal choice.
 253
 254 */
 255
 256 SCM
 257 Accidental_placement::position_accidentals (Grob * me)
 258 {
 259   SCM accs = me->get_grob_property ("accidentals");
 260
 261   /*
 262     TODO: there is a bug in this code. If two accs are on the same
 263     Y-position, they share an Ape, and will be pritned in overstrike.
 264    */
 265   Link_array<Accidental_placement_entry> apes;
 266   for (SCM s = accs; gh_pair_p (s); s =gh_cdr (s))
 267     {
 268       Accidental_placement_entry *ape = new Accidental_placement_entry;
 269       ape->notename_ = gh_scm2int (gh_caar (s));
 270
 271       for (SCM t = gh_cdar (s); gh_pair_p (t); t =gh_cdr (t))
 272         ape->grobs_.push (unsmob_grob (gh_car (t)));
 273
 274       apes.push (ape);
 275     }
 276
 277
 278   Grob *common[] = {me, 0};
 279
 280   /*
 281     First we must extract *all* pointers. We can only determine
 282     extents if we're sure that we've found the right common refpoint
 283    */
 284   Link_array<Grob> note_cols, heads;
 285   for (int i= apes.size (); i--;)
 286     {
 287       Accidental_placement_entry * ape = apes[i];
 288       for (int j = ape->grobs_.size(); j--;)
 289         {
 290           Grob * a = ape->grobs_[j];
 291
 292           if (common[Y_AXIS])
 293             common[Y_AXIS] = common[Y_AXIS]->common_refpoint (a, Y_AXIS);
 294           else
 295             common[Y_AXIS] = a;
 296
 297           Grob *head = a->get_parent (Y_AXIS);
 298
 299           Grob * col = head->get_parent (X_AXIS);
 300           if (Note_column::has_interface (col))
 301             note_cols.push (col);
 302           else
 303             heads.push (head);
 304         }
 305     }
 306
 307   /*
 308     This is a little kludgy: to get all notes, we look if there are
 309     collisions as well.
 310    */
 311   for (int i = note_cols.size() ; i--;)
 312     {
 313       Grob *c = note_cols[i]->get_parent (X_AXIS);
 314       if (Note_collision_interface::has_interface (c))
 315         {
 316           Link_array<Grob> gs =
 317             Pointer_group_interface__extract_grobs (c, (Grob*)0, "elements");
 318
 319           note_cols.concat (gs);
 320         }
 321     }
 322
 323   for (int i = note_cols.size() ; i--;)
 324     {
 325       heads.concat (Pointer_group_interface__extract_grobs (note_cols[i],
 326                                                             (Grob*)0,
 327                                                             "note-heads"));
 328
 329     }
 330   heads.default_sort();
 331   heads.uniq();
 332   common[Y_AXIS] = common_refpoint_of_array (heads, common[Y_AXIS], Y_AXIS);
 333
 334
 335   for (int i= apes.size (); i--;)
 336     {
 337       Accidental_placement_entry * ape = apes[i];
 338       ape->left_skyline_ = empty_skyline (LEFT);
 339       ape->right_skyline_ = empty_skyline (RIGHT);
 340
 341       for (int j = apes[i]->grobs_.size(); j--;)
 342         {
 343           Grob * a = apes[i]->grobs_[j];
 344
 345           Array<Box> boxes = Accidental_interface::accurate_boxes (a, common);
 346
 347           ape->extents_.concat (boxes);
 348           for (int j  = boxes.size(); j--;)
 349             {
 350               insert_extent_into_skyline (&ape->left_skyline_, boxes[j], Y_AXIS, LEFT);
 351               insert_extent_into_skyline (&ape->right_skyline_ , boxes[j], Y_AXIS, RIGHT);
 352             }
 353         }
 354     }
 355
 356
 357   Interval total;
 358   for (int i = apes.size(); i--;)
 359     {
 360       Interval y ;
 361
 362       for (int j = apes[i]->extents_.size(); j--;)
 363         {
 364           y.unite (apes[i]->extents_[j][Y_AXIS]);
 365         }
 366       apes[i]->vertical_extent_ = y;
 367       total.unite (y);
 368     }
 369   all_accidental_vertical_extent = total;
 370   stagger_apes (&apes);
 371
 372   Accidental_placement_entry * head_ape = new Accidental_placement_entry;
 373   common[X_AXIS] = common_refpoint_of_array (heads, common[X_AXIS], X_AXIS);
 374   Array<Skyline_entry> head_skyline (empty_skyline (LEFT));
 375   Array<Box> head_extents;
 376   for (int i = heads.size(); i--;)
 377     {
 378       Box b(heads[i]->extent (common[X_AXIS] , X_AXIS),
 379             heads[i]->extent (common[Y_AXIS], Y_AXIS));
 380
 381       insert_extent_into_skyline (&head_skyline, b , Y_AXIS, LEFT);
 382     }
 383
 384   head_ape-> left_skyline_ = head_skyline;
 385   head_ape->offset_ = 0.0;
 386
 387   SCM rs = me->get_grob_property ("right-padding");
 388   if (gh_number_p (rs))
 389     head_ape->offset_ -= gh_scm2double (rs);
 390
 391
 392   Real padding = 0.2;
 393   SCM spad = me->get_grob_property ("padding");
 394   if (gh_number_p (spad))
 395     padding = gh_scm2double (spad);
 396
 397
 398   /*
 399     TODO:
 400
 401     There is a bug in this code: the left_skylines should be
 402     accumulated, otherwise the b will collide with bb in
 403
 404       bb
 405     b
 406       n
 407
 408    */
 409   apes.push (head_ape);
 410   for (int i= apes.size () -1 ; i-- > 0;)
 411     {
 412       Accidental_placement_entry *ape = apes[i];
 413       Real d = 0.0;
 414       int j = i+1;
 415       do {
 416         d = - skyline_meshing_distance (ape->right_skyline_,
 417                                         apes[j]->left_skyline_);
 418
 419         if (!isinf(d)
 420             || j + 1 == apes.size())
 421           break;
 422
 423         j = j+ 1;
 424       } while (1);
 425
 426       if (isinf(d))
 427         d = 0.0;
 428
 429       d -= padding;
 430       ape->offset_ += apes[j]->offset_ + d;
 431     }
 432
 433   apes.pop();
 434   for (int i = apes.size(); i--;)
 435     {
 436       Accidental_placement_entry* ape = apes[i];
 437       for (int j  = ape->grobs_.size(); j--;)
 438         {
 439           ape->grobs_[j]->translate_axis (ape->offset_, X_AXIS);
 440         }
 441     }
 442
 443
 444   Interval left_extent, right_extent;
 445   Accidental_placement_entry *ape = apes[0];
 446
 447   for (int i = ape->extents_.size(); i--;)
 448     left_extent.unite (ape->offset_ +  ape->extents_[i][X_AXIS]);
 449
 450   ape = apes.top();
 451   for (int i = ape->extents_.size(); i--;)
 452     right_extent.unite (ape->offset_  + ape->extents_[i][X_AXIS]);
 453
 454   SCM ls = me->get_grob_property ("left-padding");
 455   if (gh_number_p (rs))
 456     left_extent[LEFT] -= gh_scm2double (ls);
 457
 458
 459   Interval width(left_extent[LEFT], right_extent[RIGHT]);
 460
 461   SCM scm_width = ly_interval2scm (width);
 462   me->set_extent (scm_width, X_AXIS);
 463
 464   for (int i = apes.size(); i--;)
 465     delete apes[i];
 466
 467   return scm_width;
 468 }
 469
 470 ADD_INTERFACE(Accidental_placement,
 471               "accidental-placement-interface",
 472               "Take care of complex accidental collisions.",
 473               "left-padding padding right-padding accidentals alignment-done")