2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2002--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
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.
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.
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/>.
20 #include "accidental-placement.hh"
22 #include "accidental-interface.hh"
25 #include "note-collision.hh"
26 #include "note-column.hh"
27 #include "pointer-group-interface.hh"
28 #include "rhythmic-head.hh"
30 #include "skyline-pair.hh"
31 #include "stream-event.hh"
37 accidental_pitch (Grob *acc)
39 SCM cause = acc->get_parent (Y_AXIS)->get_property ("cause");
41 Stream_event *mcause = unsmob<Stream_event> (cause);
44 programming_error ("note head has no event cause");
48 return unsmob<Pitch> (mcause->get_property ("pitch"));
52 Accidental_placement::add_accidental (Grob *me, Grob *a, bool stagger, long context_hash)
54 Pitch *p = accidental_pitch (a);
58 a->set_parent (me, X_AXIS);
59 long n = p->get_notename ();
61 SCM accs = me->get_object ("accidental-grobs");
62 SCM key = scm_cons (scm_from_int (n), scm_from_long (stagger ? context_hash : 1));
63 // assoc because we're dealing with pairs
64 SCM entry = scm_assoc (key, accs);
65 if (scm_is_false (entry))
68 entry = scm_cdr (entry);
70 entry = scm_cons (a->self_scm (), entry);
72 accs = scm_assoc_set_x (accs, key, entry);
74 me->set_object ("accidental-grobs", accs);
78 Split into break reminders.
81 Accidental_placement::split_accidentals (Grob *accs,
82 vector<Grob *> *break_reminder,
83 vector<Grob *> *real_acc)
85 for (SCM acs = accs->get_object ("accidental-grobs"); scm_is_pair (acs);
87 for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
89 Grob *a = unsmob<Grob> (scm_car (s));
91 if (unsmob<Grob> (a->get_object ("tie"))
92 && !to_boolean (a->get_property ("forced")))
93 break_reminder->push_back (a);
95 real_acc->push_back (a);
100 Accidental_placement::get_relevant_accidentals (vector<Grob *> const &elts, Grob *left)
105 bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
107 for (vsize i = 0; i < elts.size (); i++)
109 split_accidentals (elts[i], &br, &ra);
111 ret.insert (ret.end (), ra.begin (), ra.end ());
114 ret.insert (ret.end (), br.begin (), br.end ());
119 struct Accidental_placement_entry
121 Skyline_pair horizontal_skylines_;
122 vector<Grob *> grobs_;
125 Real ape_priority (Accidental_placement_entry const *a)
127 // right is up because we're horizontal
128 return a->horizontal_skylines_.right ();
131 bool ape_less (Accidental_placement_entry *const &a,
132 Accidental_placement_entry *const &b)
134 vsize size_a = a->grobs_.size ();
135 vsize size_b = b->grobs_.size ();
136 if (size_a != size_b)
137 return size_b < size_a;
139 return ape_priority (a) < ape_priority (b);
143 This function provides a method for sorting accidentals that belong to the
144 same note. The accidentals that this function considers to be "smallest"
145 will be placed to the left of the "larger" accidentals.
147 Naturals are the largest (so that they don't get confused with cancellation
148 naturals); apart from that, we order according to the alteration (so
149 double-flats are the smallest).
151 Precondition: the accidentals are attached to NoteHeads of the same note
152 name -- the octaves, however, may be different.
155 acc_less (Grob *const &a, Grob *const &b)
157 Pitch *p = accidental_pitch (a);
158 Pitch *q = accidental_pitch (b);
162 programming_error ("these accidentals do not have a pitch");
166 if (p->get_octave () != q->get_octave ())
167 return p->get_octave () < q->get_octave ();
169 if (p->get_alteration () == Rational (0))
171 if (q->get_alteration () == Rational (0))
174 return p->get_alteration () < q->get_alteration ();
186 stagger_apes (vector<Accidental_placement_entry *> *apes)
188 vector<Accidental_placement_entry *> asc = *apes;
190 vector_sort (asc, &ape_less);
191 // we do the staggering below based on size
192 // this ensures that if a placement has 4 entries, it will
193 // always be closer to the NoteColumn than a placement with 1
194 // this allows accidentals to be on-average closer to notes
195 // while still preserving octave alignment
196 vector<vector<Accidental_placement_entry *> > ascs;
199 for (vsize i = 0; i < asc.size (); i++)
201 vsize my_sz = asc[i]->grobs_.size ();
203 ascs.push_back (vector<Accidental_placement_entry *> ());
204 ascs.back ().push_back (asc[i]);
210 for (vsize i = 0; i < ascs.size (); i++)
213 for (vsize j = 0; j < ascs[i].size ();)
215 Accidental_placement_entry *a = 0;
232 static vector<Accidental_placement_entry *>
233 build_apes (SCM accs)
235 vector<Accidental_placement_entry *> apes;
236 for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
238 Accidental_placement_entry *ape = new Accidental_placement_entry;
240 for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
241 ape->grobs_.push_back (unsmob<Grob> (scm_car (t)));
243 apes.push_back (ape);
250 set_ape_skylines (Accidental_placement_entry *ape,
251 Grob **common, Real padding)
253 vector<Grob *> accs (ape->grobs_);
254 vector_sort (accs, &acc_less);
256 /* We know that each accidental has the same note name and we assume that
257 accidentals in different octaves won't collide. If two or more
258 accidentals are in the same octave:
259 1) if they are the same accidental, print them in overstrike
260 2) otherwise, shift one to the left so they don't overlap. */
263 Real last_offset = 0;
264 Rational last_alteration (0);
265 for (vsize i = accs.size (); i--;)
268 Pitch *p = accidental_pitch (a);
273 if (i == accs.size () - 1 || p->get_octave () != last_octave)
276 offset = a->extent (a, X_AXIS)[LEFT] - padding;
278 else if (p->get_alteration () == last_alteration)
279 a->translate_axis (last_offset, X_AXIS);
280 else /* Our alteration is different from the last one */
282 Real this_offset = offset - a->extent (a, X_AXIS)[RIGHT];
283 a->translate_axis (this_offset, X_AXIS);
285 last_offset = this_offset;
286 offset -= a->extent (a, X_AXIS).length () + padding;
289 if (Skyline_pair *sky = unsmob<Skyline_pair> (a->get_property ("horizontal-skylines")))
291 Skyline_pair copy (*sky);
292 copy.raise (a->relative_coordinate (common[X_AXIS], X_AXIS));
293 copy.shift (a->relative_coordinate (common[Y_AXIS], Y_AXIS));
294 ape->horizontal_skylines_.merge (copy);
297 last_octave = p->get_octave ();
298 last_alteration = p->get_alteration ();
302 static vector<Grob *>
303 extract_heads_and_stems (vector<Accidental_placement_entry *> const &apes)
305 vector<Grob *> note_cols;
308 for (vsize i = apes.size (); i--;)
310 Accidental_placement_entry *ape = apes[i];
311 for (vsize j = ape->grobs_.size (); j--;)
313 Grob *acc = ape->grobs_[j];
314 Grob *head = acc->get_parent (Y_AXIS);
315 Grob *col = head->get_parent (X_AXIS);
317 if (has_interface<Note_column> (col))
318 note_cols.push_back (col);
320 ret.push_back (head);
325 This is a little kludgy: in case there are note columns without
326 accidentals, we get them from the Note_collision objects.
328 for (vsize i = note_cols.size (); i--;)
330 Grob *c = note_cols[i]->get_parent (X_AXIS);
331 if (has_interface<Note_collision_interface> (c))
333 extract_grob_set (c, "elements", columns);
334 concat (note_cols, columns);
338 /* Now that we have all of the columns, grab all of the note-heads */
339 for (vsize i = note_cols.size (); i--;)
340 concat (ret, extract_grob_array (note_cols[i], "note-heads"));
342 /* Now that we have all of the heads, grab all of the stems */
343 for (vsize i = ret.size (); i--;)
344 if (Grob *s = Rhythmic_head::get_stem (ret[i]))
352 common_refpoint_of_accidentals (vector<Accidental_placement_entry *> const &apes, Axis a)
356 for (vsize i = apes.size (); i--;)
357 for (vsize j = apes[i]->grobs_.size (); j--;)
360 ret = apes[i]->grobs_[j];
362 ret = ret->common_refpoint (apes[i]->grobs_[j], a);
369 build_heads_skyline (vector<Grob *> const &heads_and_stems,
372 vector<Box> head_extents;
373 for (vsize i = heads_and_stems.size (); i--;)
374 head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
375 heads_and_stems[i]->pure_y_extent (common[Y_AXIS], 0, INT_MAX)));
377 return Skyline (head_extents, Y_AXIS, LEFT);
381 Position the apes, starting from the right, so that they don't collide.
382 Return the total width.
385 position_apes (Grob *me,
386 vector<Accidental_placement_entry *> const &apes,
387 Skyline const &heads_skyline)
389 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
390 Skyline left_skyline = heads_skyline;
391 left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
394 Add accs entries right-to-left.
397 Real last_offset = 0.0;
398 for (vsize i = apes.size (); i-- > 0;)
400 Accidental_placement_entry *ape = apes[i];
402 Real offset = -ape->horizontal_skylines_[RIGHT]
403 .distance (left_skyline, 0.1);
405 offset = last_offset;
409 Skyline new_left_skyline = ape->horizontal_skylines_[LEFT];
410 new_left_skyline.raise (offset);
411 new_left_skyline.merge (left_skyline);
412 left_skyline = new_left_skyline;
414 /* Shift all of the accidentals in this ape */
415 for (vsize j = ape->grobs_.size (); j--;)
416 ape->grobs_[j]->translate_axis (offset, X_AXIS);
418 for (LEFT_and_RIGHT (d))
420 Real mh = ape->horizontal_skylines_[d].max_height ();
422 width.add_point (mh + offset);
425 last_offset = offset;
432 This routine computes placements of accidentals. During
433 add_accidental (), accidentals are already grouped by note, so that
434 octaves are placed above each other; they form columns. Then the
435 columns are sorted: the biggest columns go closest to the note.
436 Then the columns are spaced as closely as possible (using skyline
440 TODO: more advanced placement. Typically, the accs should be placed
441 to form a C shape, like this
449 The naturals should be left of the C as well; they should
452 Note that this placement problem looks NP hard, so we just use a
453 simple strategy, not an optimal choice.
457 TODO: there should be more space in the following situation
470 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
472 Accidental_placement::calc_positioning_done (SCM smob)
474 Grob *me = unsmob<Grob> (smob);
478 me->set_property ("positioning-done", SCM_BOOL_T);
480 SCM accs = me->get_object ("accidental-grobs");
481 if (!scm_is_pair (accs))
484 vector<Accidental_placement_entry *> apes = build_apes (accs);
486 Grob *common[] = {me, 0};
488 vector<Grob *> heads_and_stems = extract_heads_and_stems (apes);
490 common[Y_AXIS] = common_refpoint_of_accidentals (apes, Y_AXIS);
491 common[Y_AXIS] = common_refpoint_of_array (heads_and_stems, common[Y_AXIS], Y_AXIS);
492 common[X_AXIS] = common_refpoint_of_array (heads_and_stems, me, X_AXIS);
493 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
495 for (vsize i = apes.size (); i--;)
496 set_ape_skylines (apes[i], common, padding);
497 Skyline heads_skyline = build_heads_skyline (heads_and_stems, common);
499 stagger_apes (&apes);
500 Interval width = position_apes (me, apes, heads_skyline);
502 me->flush_extent_cache (X_AXIS);
503 me->set_property ("X-extent", ly_interval2scm (width));
505 junk_pointers (apes);
510 ADD_INTERFACE (Accidental_placement,
511 "Resolve accidental collisions.",