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)
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 int n = p->get_notename ();
60 SCM accs = me->get_object ("accidental-grobs");
61 SCM key = scm_from_int (n);
62 SCM entry = scm_assq (key, accs);
63 if (entry == SCM_BOOL_F)
66 entry = scm_cdr (entry);
68 entry = scm_cons (a->self_scm (), entry);
70 accs = scm_assq_set_x (accs, key, entry);
72 me->set_object ("accidental-grobs", accs);
76 Split into break reminders.
79 Accidental_placement::split_accidentals (Grob *accs,
80 vector<Grob *> *break_reminder,
81 vector<Grob *> *real_acc)
83 for (SCM acs = accs->get_object ("accidental-grobs"); scm_is_pair (acs);
85 for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
87 Grob *a = unsmob_grob (scm_car (s));
89 if (unsmob_grob (a->get_object ("tie"))
90 && !to_boolean (a->get_property ("forced")))
91 break_reminder->push_back (a);
93 real_acc->push_back (a);
98 Accidental_placement::get_relevant_accidentals (vector<Grob *> const &elts, Grob *left)
103 bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
105 for (vsize i = 0; i < elts.size (); i++)
107 split_accidentals (elts[i], &br, &ra);
109 ret.insert (ret.end (), ra.begin (), ra.end ());
112 ret.insert (ret.end (), br.begin (), br.end ());
117 struct Accidental_placement_entry
119 Skyline_pair horizontal_skylines_;
120 vector<Grob *> grobs_;
123 Real ape_priority (Accidental_placement_entry const *a)
125 // right is up because we're horizontal
126 return a->horizontal_skylines_.right ();
129 bool ape_less (Accidental_placement_entry *const &a,
130 Accidental_placement_entry *const &b)
132 return ape_priority (a) < ape_priority (b);
136 This function provides a method for sorting accidentals that belong to the
137 same note. The accidentals that this function considers to be "smallest"
138 will be placed to the left of the "larger" accidentals.
140 Naturals are the largest (so that they don't get confused with cancellation
141 naturals); apart from that, we order according to the alteration (so
142 double-flats are the smallest).
144 Precondition: the accidentals are attached to NoteHeads of the same note
145 name -- the octaves, however, may be different.
148 acc_less (Grob *const &a, Grob *const &b)
150 Pitch *p = accidental_pitch (a);
151 Pitch *q = accidental_pitch (b);
155 programming_error ("these accidentals do not have a pitch");
159 if (p->get_octave () != q->get_octave ())
160 return p->get_octave () < q->get_octave ();
162 if (p->get_alteration () == Rational (0))
164 if (q->get_alteration () == Rational (0))
167 return p->get_alteration () < q->get_alteration ();
179 stagger_apes (vector<Accidental_placement_entry *> *apes)
181 vector<Accidental_placement_entry *> asc = *apes;
183 vector_sort (asc, &ape_less);
188 for (vsize i = 0; i < asc.size ();)
190 Accidental_placement_entry *a = 0;
206 static vector<Accidental_placement_entry *>
207 build_apes (SCM accs)
209 vector<Accidental_placement_entry *> apes;
210 for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
212 Accidental_placement_entry *ape = new Accidental_placement_entry;
214 for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
215 ape->grobs_.push_back (unsmob_grob (scm_car (t)));
217 apes.push_back (ape);
224 set_ape_skylines (Accidental_placement_entry *ape,
225 Grob **common, Real padding)
227 vector<Grob *> accs (ape->grobs_);
228 vector_sort (accs, &acc_less);
230 /* We know that each accidental has the same note name and we assume that
231 accidentals in different octaves won't collide. If two or more
232 accidentals are in the same octave:
233 1) if they are the same accidental, print them in overstrike
234 2) otherwise, shift one to the left so they don't overlap. */
237 Real last_offset = 0;
238 Rational last_alteration (0);
239 for (vsize i = accs.size (); i--;)
242 Pitch *p = accidental_pitch (a);
247 if (i == accs.size () - 1 || p->get_octave () != last_octave)
250 offset = a->extent (a, X_AXIS)[LEFT] - padding;
252 else if (p->get_alteration () == last_alteration)
253 a->translate_axis (last_offset, X_AXIS);
254 else /* Our alteration is different from the last one */
256 Real this_offset = offset - a->extent (a, X_AXIS)[RIGHT];
257 a->translate_axis (this_offset, X_AXIS);
259 last_offset = this_offset;
260 offset -= a->extent (a, X_AXIS).length () + padding;
263 if (Skyline_pair *sky = Skyline_pair::unsmob (a->get_property ("horizontal-skylines")))
265 Skyline_pair copy (*sky);
266 copy.raise (a->relative_coordinate (common[X_AXIS], X_AXIS));
267 copy.shift (a->relative_coordinate (common[Y_AXIS], Y_AXIS));
268 ape->horizontal_skylines_.merge (copy);
271 last_octave = p->get_octave ();
272 last_alteration = p->get_alteration ();
276 static vector<Grob *>
277 extract_heads_and_stems (vector<Accidental_placement_entry *> const &apes)
279 vector<Grob *> note_cols;
282 for (vsize i = apes.size (); i--;)
284 Accidental_placement_entry *ape = apes[i];
285 for (vsize j = ape->grobs_.size (); j--;)
287 Grob *acc = ape->grobs_[j];
288 Grob *head = acc->get_parent (Y_AXIS);
289 Grob *col = head->get_parent (X_AXIS);
291 if (Note_column::has_interface (col))
292 note_cols.push_back (col);
294 ret.push_back (head);
299 This is a little kludgy: in case there are note columns without
300 accidentals, we get them from the Note_collision objects.
302 for (vsize i = note_cols.size (); i--;)
304 Grob *c = note_cols[i]->get_parent (X_AXIS);
305 if (Note_collision_interface::has_interface (c))
307 extract_grob_set (c, "elements", columns);
308 concat (note_cols, columns);
312 /* Now that we have all of the columns, grab all of the note-heads */
313 for (vsize i = note_cols.size (); i--;)
314 concat (ret, extract_grob_array (note_cols[i], "note-heads"));
316 /* Now that we have all of the heads, grab all of the stems */
317 for (vsize i = ret.size (); i--;)
318 if (Grob *s = Rhythmic_head::get_stem (ret[i]))
321 vector_sort (ret, less<Grob *> ());
327 common_refpoint_of_accidentals (vector<Accidental_placement_entry *> const &apes, Axis a)
331 for (vsize i = apes.size (); i--;)
332 for (vsize j = apes[i]->grobs_.size (); j--;)
335 ret = apes[i]->grobs_[j];
337 ret = ret->common_refpoint (apes[i]->grobs_[j], a);
344 build_heads_skyline (vector<Grob *> const &heads_and_stems,
347 vector<Box> head_extents;
348 for (vsize i = heads_and_stems.size (); i--;)
349 head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
350 heads_and_stems[i]->pure_height (common[Y_AXIS], 0, INT_MAX)));
352 return Skyline (head_extents, Y_AXIS, LEFT);
356 Position the apes, starting from the right, so that they don't collide.
357 Return the total width.
360 position_apes (Grob *me,
361 vector<Accidental_placement_entry *> const &apes,
362 Skyline const &heads_skyline)
364 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
365 Skyline left_skyline = heads_skyline;
366 left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
369 Add accs entries right-to-left.
372 Real last_offset = 0.0;
373 for (vsize i = apes.size (); i-- > 0;)
375 Accidental_placement_entry *ape = apes[i];
377 Real offset = -ape->horizontal_skylines_[RIGHT].distance (left_skyline);
379 offset = last_offset;
383 Skyline new_left_skyline = ape->horizontal_skylines_[LEFT];
384 new_left_skyline.raise (offset);
385 new_left_skyline.merge (left_skyline);
386 left_skyline = new_left_skyline;
388 /* Shift all of the accidentals in this ape */
389 for (vsize j = ape->grobs_.size (); j--;)
390 ape->grobs_[j]->translate_axis (offset, X_AXIS);
392 for (LEFT_and_RIGHT (d))
394 Real mh = ape->horizontal_skylines_[d].max_height ();
396 width.add_point (mh);
399 last_offset = offset;
406 This routine computes placements of accidentals. During
407 add_accidental (), accidentals are already grouped by note, so that
408 octaves are placed above each other; they form columns. Then the
409 columns are sorted: the biggest columns go closest to the note.
410 Then the columns are spaced as closely as possible (using skyline
414 TODO: more advanced placement. Typically, the accs should be placed
415 to form a C shape, like this
423 The naturals should be left of the C as well; they should
426 Note that this placement problem looks NP hard, so we just use a
427 simple strategy, not an optimal choice.
431 TODO: there should be more space in the following situation
444 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
446 Accidental_placement::calc_positioning_done (SCM smob)
448 Grob *me = unsmob_grob (smob);
452 me->set_property ("positioning-done", SCM_BOOL_T);
454 SCM accs = me->get_object ("accidental-grobs");
455 if (!scm_is_pair (accs))
458 vector<Accidental_placement_entry *> apes = build_apes (accs);
460 Grob *common[] = {me, 0};
462 vector<Grob *> heads_and_stems = extract_heads_and_stems (apes);
464 common[Y_AXIS] = common_refpoint_of_accidentals (apes, Y_AXIS);
465 common[Y_AXIS] = common_refpoint_of_array (heads_and_stems, common[Y_AXIS], Y_AXIS);
466 common[X_AXIS] = common_refpoint_of_array (heads_and_stems, me, X_AXIS);
467 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
469 for (vsize i = apes.size (); i--;)
470 set_ape_skylines (apes[i], common, padding);
471 Skyline heads_skyline = build_heads_skyline (heads_and_stems, common);
473 stagger_apes (&apes);
474 Interval width = position_apes (me, apes, heads_skyline);
476 me->flush_extent_cache (X_AXIS);
477 me->set_property ("X-extent", ly_interval2scm (width));
479 junk_pointers (apes);
484 ADD_INTERFACE (Accidental_placement,
485 "Resolve accidental collisions.",