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 a->set_property ("X-offset", Grob::x_parent_positioning_proc);
60 long n = p->get_notename ();
62 SCM accs = me->get_object ("accidental-grobs");
63 SCM key = scm_cons (scm_from_int (n), scm_from_long (stagger ? context_hash : 1));
64 // assoc because we're dealing with pairs
65 SCM entry = scm_assoc (key, accs);
66 if (scm_is_false (entry))
69 entry = scm_cdr (entry);
71 entry = scm_cons (a->self_scm (), entry);
73 accs = scm_assoc_set_x (accs, key, entry);
75 me->set_object ("accidental-grobs", accs);
79 Split into break reminders.
82 Accidental_placement::split_accidentals (Grob *accs,
83 vector<Grob *> *break_reminder,
84 vector<Grob *> *real_acc)
86 for (SCM acs = accs->get_object ("accidental-grobs"); scm_is_pair (acs);
88 for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
90 Grob *a = unsmob<Grob> (scm_car (s));
92 if (unsmob<Grob> (a->get_object ("tie"))
93 && !to_boolean (a->get_property ("forced")))
94 break_reminder->push_back (a);
96 real_acc->push_back (a);
101 Accidental_placement::get_relevant_accidentals (vector<Grob *> const &elts, Grob *left)
106 bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
108 for (vsize i = 0; i < elts.size (); i++)
110 split_accidentals (elts[i], &br, &ra);
112 ret.insert (ret.end (), ra.begin (), ra.end ());
115 ret.insert (ret.end (), br.begin (), br.end ());
120 struct Accidental_placement_entry
122 Skyline_pair horizontal_skylines_;
123 vector<Grob *> grobs_;
126 Real ape_priority (Accidental_placement_entry const *a)
128 // right is up because we're horizontal
129 return a->horizontal_skylines_.right ();
132 bool ape_less (Accidental_placement_entry *const &a,
133 Accidental_placement_entry *const &b)
135 vsize size_a = a->grobs_.size ();
136 vsize size_b = b->grobs_.size ();
137 if (size_a != size_b)
138 return size_b < size_a;
140 return ape_priority (a) < ape_priority (b);
144 This function provides a method for sorting accidentals that belong to the
145 same note. The accidentals that this function considers to be "smallest"
146 will be placed to the left of the "larger" accidentals.
148 Naturals are the largest (so that they don't get confused with cancellation
149 naturals); apart from that, we order according to the alteration (so
150 double-flats are the smallest).
152 Precondition: the accidentals are attached to NoteHeads of the same note
153 name -- the octaves, however, may be different.
156 acc_less (Grob *const &a, Grob *const &b)
158 Pitch *p = accidental_pitch (a);
159 Pitch *q = accidental_pitch (b);
163 programming_error ("these accidentals do not have a pitch");
167 if (p->get_octave () != q->get_octave ())
168 return p->get_octave () < q->get_octave ();
170 if (p->get_alteration () == Rational (0))
172 if (q->get_alteration () == Rational (0))
175 return p->get_alteration () < q->get_alteration ();
187 stagger_apes (vector<Accidental_placement_entry *> *apes)
189 vector<Accidental_placement_entry *> asc = *apes;
191 vector_sort (asc, &ape_less);
192 // we do the staggering below based on size
193 // this ensures that if a placement has 4 entries, it will
194 // always be closer to the NoteColumn than a placement with 1
195 // this allows accidentals to be on-average closer to notes
196 // while still preserving octave alignment
197 vector<vector<Accidental_placement_entry *> > ascs;
200 for (vsize i = 0; i < asc.size (); i++)
202 vsize my_sz = asc[i]->grobs_.size ();
204 ascs.push_back (vector<Accidental_placement_entry *> ());
205 ascs.back ().push_back (asc[i]);
211 for (vsize i = 0; i < ascs.size (); i++)
214 for (vsize j = 0; j < ascs[i].size ();)
216 Accidental_placement_entry *a = 0;
233 static vector<Accidental_placement_entry *>
234 build_apes (SCM accs)
236 vector<Accidental_placement_entry *> apes;
237 for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
239 Accidental_placement_entry *ape = new Accidental_placement_entry;
241 for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
242 ape->grobs_.push_back (unsmob<Grob> (scm_car (t)));
244 apes.push_back (ape);
251 set_ape_skylines (Accidental_placement_entry *ape,
252 Grob **common, Real padding)
254 vector<Grob *> accs (ape->grobs_);
255 vector_sort (accs, &acc_less);
257 /* We know that each accidental has the same note name and we assume that
258 accidentals in different octaves won't collide. If two or more
259 accidentals are in the same octave:
260 1) if they are the same accidental, print them in overstrike
261 2) otherwise, shift one to the left so they don't overlap. */
264 Real last_offset = 0;
265 Rational last_alteration (0);
266 for (vsize i = accs.size (); i--;)
269 Pitch *p = accidental_pitch (a);
274 if (i == accs.size () - 1 || p->get_octave () != last_octave)
277 offset = a->extent (a, X_AXIS)[LEFT] - padding;
279 else if (p->get_alteration () == last_alteration)
280 a->translate_axis (last_offset, X_AXIS);
281 else /* Our alteration is different from the last one */
283 Real this_offset = offset - a->extent (a, X_AXIS)[RIGHT];
284 a->translate_axis (this_offset, X_AXIS);
286 last_offset = this_offset;
287 offset -= a->extent (a, X_AXIS).length () + padding;
290 if (Skyline_pair *sky = unsmob<Skyline_pair> (a->get_property ("horizontal-skylines")))
292 Skyline_pair copy (*sky);
293 copy.raise (a->relative_coordinate (common[X_AXIS], X_AXIS));
294 copy.shift (a->relative_coordinate (common[Y_AXIS], Y_AXIS));
295 ape->horizontal_skylines_.merge (copy);
298 last_octave = p->get_octave ();
299 last_alteration = p->get_alteration ();
303 static vector<Grob *>
304 extract_heads_and_stems (vector<Accidental_placement_entry *> const &apes)
306 vector<Grob *> note_cols;
309 for (vsize i = apes.size (); i--;)
311 Accidental_placement_entry *ape = apes[i];
312 for (vsize j = ape->grobs_.size (); j--;)
314 Grob *acc = ape->grobs_[j];
315 Grob *head = acc->get_parent (Y_AXIS);
316 Grob *col = head->get_parent (X_AXIS);
318 if (has_interface<Note_column> (col))
319 note_cols.push_back (col);
321 ret.push_back (head);
326 This is a little kludgy: in case there are note columns without
327 accidentals, we get them from the Note_collision objects.
329 for (vsize i = note_cols.size (); i--;)
331 Grob *c = note_cols[i]->get_parent (X_AXIS);
332 if (has_interface<Note_collision_interface> (c))
334 extract_grob_set (c, "elements", columns);
335 concat (note_cols, columns);
339 /* Now that we have all of the columns, grab all of the note-heads */
340 for (vsize i = note_cols.size (); i--;)
341 concat (ret, extract_grob_array (note_cols[i], "note-heads"));
343 /* Now that we have all of the heads, grab all of the stems */
344 for (vsize i = ret.size (); i--;)
345 if (Grob *s = Rhythmic_head::get_stem (ret[i]))
353 common_refpoint_of_accidentals (vector<Accidental_placement_entry *> const &apes, Axis a)
357 for (vsize i = apes.size (); i--;)
358 for (vsize j = apes[i]->grobs_.size (); j--;)
361 ret = apes[i]->grobs_[j];
363 ret = ret->common_refpoint (apes[i]->grobs_[j], a);
370 build_heads_skyline (vector<Grob *> const &heads_and_stems,
373 vector<Box> head_extents;
374 for (vsize i = heads_and_stems.size (); i--;)
375 head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
376 heads_and_stems[i]->pure_y_extent (common[Y_AXIS], 0, INT_MAX)));
378 return Skyline (head_extents, Y_AXIS, LEFT);
382 Position the apes, starting from the right, so that they don't collide.
383 Return the total width.
386 position_apes (Grob *me,
387 vector<Accidental_placement_entry *> const &apes,
388 Skyline const &heads_skyline)
390 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
391 Skyline left_skyline = heads_skyline;
392 left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
395 Add accs entries right-to-left.
398 Real last_offset = 0.0;
399 for (vsize i = apes.size (); i-- > 0;)
401 Accidental_placement_entry *ape = apes[i];
403 Real offset = -ape->horizontal_skylines_[RIGHT]
404 .distance (left_skyline, 0.1);
406 offset = last_offset;
410 Skyline new_left_skyline = ape->horizontal_skylines_[LEFT];
411 new_left_skyline.raise (offset);
412 new_left_skyline.merge (left_skyline);
413 left_skyline = new_left_skyline;
415 /* Shift all of the accidentals in this ape */
416 for (vsize j = ape->grobs_.size (); j--;)
417 ape->grobs_[j]->translate_axis (offset, X_AXIS);
419 for (LEFT_and_RIGHT (d))
421 Real mh = ape->horizontal_skylines_[d].max_height ();
423 width.add_point (mh + offset);
426 last_offset = offset;
433 This routine computes placements of accidentals. During
434 add_accidental (), accidentals are already grouped by note, so that
435 octaves are placed above each other; they form columns. Then the
436 columns are sorted: the biggest columns go closest to the note.
437 Then the columns are spaced as closely as possible (using skyline
441 TODO: more advanced placement. Typically, the accs should be placed
442 to form a C shape, like this
450 The naturals should be left of the C as well; they should
453 Note that this placement problem looks NP hard, so we just use a
454 simple strategy, not an optimal choice.
458 TODO: there should be more space in the following situation
471 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
473 Accidental_placement::calc_positioning_done (SCM smob)
475 Grob *me = unsmob<Grob> (smob);
479 me->set_property ("positioning-done", SCM_BOOL_T);
481 SCM accs = me->get_object ("accidental-grobs");
482 if (!scm_is_pair (accs))
485 vector<Accidental_placement_entry *> apes = build_apes (accs);
487 Grob *common[] = {me, 0};
489 vector<Grob *> heads_and_stems = extract_heads_and_stems (apes);
491 common[Y_AXIS] = common_refpoint_of_accidentals (apes, Y_AXIS);
492 common[Y_AXIS] = common_refpoint_of_array (heads_and_stems, common[Y_AXIS], Y_AXIS);
493 common[X_AXIS] = common_refpoint_of_array (heads_and_stems, me, X_AXIS);
494 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
496 for (vsize i = apes.size (); i--;)
497 set_ape_skylines (apes[i], common, padding);
498 Skyline heads_skyline = build_heads_skyline (heads_and_stems, common);
500 stagger_apes (&apes);
501 Interval width = position_apes (me, apes, heads_skyline);
503 me->flush_extent_cache (X_AXIS);
504 me->set_property ("X-extent", ly_interval2scm (width));
506 junk_pointers (apes);
511 ADD_INTERFACE (Accidental_placement,
512 "Resolve accidental collisions.",