2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2002--2012 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"
35 accidental_pitch (Grob *acc)
37 SCM cause = acc->get_parent (Y_AXIS)->get_property ("cause");
39 Stream_event *mcause = unsmob_stream_event (cause);
42 programming_error ("note head has no event cause");
46 return unsmob_pitch (mcause->get_property ("pitch"));
50 Accidental_placement::add_accidental (Grob *me, Grob *a, bool stagger, long context_hash)
52 Pitch *p = accidental_pitch (a);
56 a->set_parent (me, X_AXIS);
57 a->set_property ("X-offset", Grob::x_parent_positioning_proc);
58 long n = p->get_notename ();
60 SCM accs = me->get_object ("accidental-grobs");
61 SCM key = scm_cons (scm_from_int (n), scm_from_long (stagger ? context_hash : 1));
62 // assoc because we're dealing with pairs
63 SCM entry = scm_assoc (key, accs);
64 if (entry == SCM_BOOL_F)
67 entry = scm_cdr (entry);
69 entry = scm_cons (a->self_scm (), entry);
71 accs = scm_assoc_set_x (accs, key, entry);
73 me->set_object ("accidental-grobs", accs);
77 Split into break reminders.
80 Accidental_placement::split_accidentals (Grob *accs,
81 vector<Grob *> *break_reminder,
82 vector<Grob *> *real_acc)
84 for (SCM acs = accs->get_object ("accidental-grobs"); scm_is_pair (acs);
86 for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
88 Grob *a = unsmob_grob (scm_car (s));
90 if (unsmob_grob (a->get_object ("tie"))
91 && !to_boolean (a->get_property ("forced")))
92 break_reminder->push_back (a);
94 real_acc->push_back (a);
99 Accidental_placement::get_relevant_accidentals (vector<Grob *> const &elts, Grob *left)
104 bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
106 for (vsize i = 0; i < elts.size (); i++)
108 split_accidentals (elts[i], &br, &ra);
110 ret.insert (ret.end (), ra.begin (), ra.end ());
113 ret.insert (ret.end (), br.begin (), br.end ());
118 struct Accidental_placement_entry
120 Skyline_pair horizontal_skylines_;
121 vector<Grob *> grobs_;
124 Real ape_priority (Accidental_placement_entry const *a)
126 // right is up because we're horizontal
127 return a->horizontal_skylines_.right ();
130 bool ape_less (Accidental_placement_entry *const &a,
131 Accidental_placement_entry *const &b)
133 vsize size_a = a->grobs_.size ();
134 vsize size_b = b->grobs_.size ();
135 if (size_a != size_b)
136 return size_b < size_a;
138 return ape_priority (a) < ape_priority (b);
142 This function provides a method for sorting accidentals that belong to the
143 same note. The accidentals that this function considers to be "smallest"
144 will be placed to the left of the "larger" accidentals.
146 Naturals are the largest (so that they don't get confused with cancellation
147 naturals); apart from that, we order according to the alteration (so
148 double-flats are the smallest).
150 Precondition: the accidentals are attached to NoteHeads of the same note
151 name -- the octaves, however, may be different.
154 acc_less (Grob *const &a, Grob *const &b)
156 Pitch *p = accidental_pitch (a);
157 Pitch *q = accidental_pitch (b);
161 programming_error ("these accidentals do not have a pitch");
165 if (p->get_octave () != q->get_octave ())
166 return p->get_octave () < q->get_octave ();
168 if (p->get_alteration () == Rational (0))
170 if (q->get_alteration () == Rational (0))
173 return p->get_alteration () < q->get_alteration ();
185 stagger_apes (vector<Accidental_placement_entry *> *apes)
187 vector<Accidental_placement_entry *> asc = *apes;
189 vector_sort (asc, &ape_less);
190 // we do the staggering below based on size
191 // this ensures that if a placement has 4 entries, it will
192 // always be closer to the NoteColumn than a placement with 1
193 // this allows accidentals to be on-average closer to notes
194 // while still preserving octave alignment
195 vector<vector<Accidental_placement_entry *> > ascs;
198 for (vsize i = 0; i < asc.size (); i++)
200 vsize my_sz = asc[i]->grobs_.size ();
202 ascs.push_back (vector<Accidental_placement_entry *> ());
203 ascs.back ().push_back (asc[i]);
209 for (vsize i = 0; i < ascs.size (); i++)
212 for (vsize j = 0; j < ascs[i].size ();)
214 Accidental_placement_entry *a = 0;
231 static vector<Accidental_placement_entry *>
232 build_apes (SCM accs)
234 vector<Accidental_placement_entry *> apes;
235 for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
237 Accidental_placement_entry *ape = new Accidental_placement_entry;
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)));
242 apes.push_back (ape);
249 set_ape_skylines (Accidental_placement_entry *ape,
250 Grob **common, Real padding)
252 vector<Grob *> accs (ape->grobs_);
253 vector_sort (accs, &acc_less);
255 /* We know that each accidental has the same note name and we assume that
256 accidentals in different octaves won't collide. If two or more
257 accidentals are in the same octave:
258 1) if they are the same accidental, print them in overstrike
259 2) otherwise, shift one to the left so they don't overlap. */
262 Real last_offset = 0;
263 Rational last_alteration (0);
264 for (vsize i = accs.size (); i--;)
267 Pitch *p = accidental_pitch (a);
272 if (i == accs.size () - 1 || p->get_octave () != last_octave)
275 offset = a->extent (a, X_AXIS)[LEFT] - padding;
277 else if (p->get_alteration () == last_alteration)
278 a->translate_axis (last_offset, X_AXIS);
279 else /* Our alteration is different from the last one */
281 Real this_offset = offset - a->extent (a, X_AXIS)[RIGHT];
282 a->translate_axis (this_offset, X_AXIS);
284 last_offset = this_offset;
285 offset -= a->extent (a, X_AXIS).length () + padding;
288 if (Skyline_pair *sky = Skyline_pair::unsmob (a->get_property ("horizontal-skylines")))
290 Skyline_pair copy (*sky);
291 copy.raise (a->relative_coordinate (common[X_AXIS], X_AXIS));
292 copy.shift (a->relative_coordinate (common[Y_AXIS], Y_AXIS));
293 ape->horizontal_skylines_.merge (copy);
296 last_octave = p->get_octave ();
297 last_alteration = p->get_alteration ();
301 static vector<Grob *>
302 extract_heads_and_stems (vector<Accidental_placement_entry *> const &apes)
304 vector<Grob *> note_cols;
307 for (vsize i = apes.size (); i--;)
309 Accidental_placement_entry *ape = apes[i];
310 for (vsize j = ape->grobs_.size (); j--;)
312 Grob *acc = ape->grobs_[j];
313 Grob *head = acc->get_parent (Y_AXIS);
314 Grob *col = head->get_parent (X_AXIS);
316 if (Note_column::has_interface (col))
317 note_cols.push_back (col);
319 ret.push_back (head);
324 This is a little kludgy: in case there are note columns without
325 accidentals, we get them from the Note_collision objects.
327 for (vsize i = note_cols.size (); i--;)
329 Grob *c = note_cols[i]->get_parent (X_AXIS);
330 if (Note_collision_interface::has_interface (c))
332 extract_grob_set (c, "elements", columns);
333 concat (note_cols, columns);
337 /* Now that we have all of the columns, grab all of the note-heads */
338 for (vsize i = note_cols.size (); i--;)
339 concat (ret, extract_grob_array (note_cols[i], "note-heads"));
341 /* Now that we have all of the heads, grab all of the stems */
342 for (vsize i = ret.size (); i--;)
343 if (Grob *s = Rhythmic_head::get_stem (ret[i]))
351 common_refpoint_of_accidentals (vector<Accidental_placement_entry *> const &apes, Axis a)
355 for (vsize i = apes.size (); i--;)
356 for (vsize j = apes[i]->grobs_.size (); j--;)
359 ret = apes[i]->grobs_[j];
361 ret = ret->common_refpoint (apes[i]->grobs_[j], a);
368 build_heads_skyline (vector<Grob *> const &heads_and_stems,
371 vector<Box> head_extents;
372 for (vsize i = heads_and_stems.size (); i--;)
373 head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
374 heads_and_stems[i]->pure_height (common[Y_AXIS], 0, INT_MAX)));
376 return Skyline (head_extents, Y_AXIS, LEFT);
380 Position the apes, starting from the right, so that they don't collide.
381 Return the total width.
384 position_apes (Grob *me,
385 vector<Accidental_placement_entry *> const &apes,
386 Skyline const &heads_skyline)
388 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
389 Skyline left_skyline = heads_skyline;
390 left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
393 Add accs entries right-to-left.
396 Real last_offset = 0.0;
397 for (vsize i = apes.size (); i-- > 0;)
399 Accidental_placement_entry *ape = apes[i];
401 Real offset = -ape->horizontal_skylines_[RIGHT].distance (left_skyline);
403 offset = last_offset;
407 Skyline new_left_skyline = ape->horizontal_skylines_[LEFT];
408 new_left_skyline.raise (offset);
409 new_left_skyline.merge (left_skyline);
410 left_skyline = new_left_skyline;
412 /* Shift all of the accidentals in this ape */
413 for (vsize j = ape->grobs_.size (); j--;)
414 ape->grobs_[j]->translate_axis (offset, X_AXIS);
416 for (LEFT_and_RIGHT (d))
418 Real mh = ape->horizontal_skylines_[d].max_height ();
420 width.add_point (mh);
423 last_offset = offset;
430 This routine computes placements of accidentals. During
431 add_accidental (), accidentals are already grouped by note, so that
432 octaves are placed above each other; they form columns. Then the
433 columns are sorted: the biggest columns go closest to the note.
434 Then the columns are spaced as closely as possible (using skyline
438 TODO: more advanced placement. Typically, the accs should be placed
439 to form a C shape, like this
447 The naturals should be left of the C as well; they should
450 Note that this placement problem looks NP hard, so we just use a
451 simple strategy, not an optimal choice.
455 TODO: there should be more space in the following situation
468 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
470 Accidental_placement::calc_positioning_done (SCM smob)
472 Grob *me = unsmob_grob (smob);
476 me->set_property ("positioning-done", SCM_BOOL_T);
478 SCM accs = me->get_object ("accidental-grobs");
479 if (!scm_is_pair (accs))
482 vector<Accidental_placement_entry *> apes = build_apes (accs);
484 Grob *common[] = {me, 0};
486 vector<Grob *> heads_and_stems = extract_heads_and_stems (apes);
488 common[Y_AXIS] = common_refpoint_of_accidentals (apes, Y_AXIS);
489 common[Y_AXIS] = common_refpoint_of_array (heads_and_stems, common[Y_AXIS], Y_AXIS);
490 common[X_AXIS] = common_refpoint_of_array (heads_and_stems, me, X_AXIS);
491 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
493 for (vsize i = apes.size (); i--;)
494 set_ape_skylines (apes[i], common, padding);
495 Skyline heads_skyline = build_heads_skyline (heads_and_stems, common);
497 stagger_apes (&apes);
498 Interval width = position_apes (me, apes, heads_skyline);
500 me->flush_extent_cache (X_AXIS);
501 me->set_property ("X-extent", ly_interval2scm (width));
503 junk_pointers (apes);
508 ADD_INTERFACE (Accidental_placement,
509 "Resolve accidental collisions.",