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 "stream-event.hh"
34 accidental_pitch (Grob *acc)
36 SCM cause = acc->get_parent (Y_AXIS)->get_property ("cause");
38 Stream_event *mcause = unsmob_stream_event (cause);
41 programming_error ("note head has no event cause");
45 return unsmob_pitch (mcause->get_property ("pitch"));
49 Accidental_placement::add_accidental (Grob *me, Grob *a)
51 Pitch *p = accidental_pitch (a);
55 a->set_parent (me, X_AXIS);
56 a->set_property ("X-offset", Grob::x_parent_positioning_proc);
57 int n = p->get_notename ();
59 SCM accs = me->get_object ("accidental-grobs");
60 SCM key = scm_from_int (n);
61 SCM entry = scm_assq (key, accs);
62 if (entry == SCM_BOOL_F)
65 entry = scm_cdr (entry);
67 entry = scm_cons (a->self_scm (), entry);
69 accs = scm_assq_set_x (accs, key, entry);
71 me->set_object ("accidental-grobs", accs);
75 Split into break reminders.
78 Accidental_placement::split_accidentals (Grob *accs,
79 vector<Grob *> *break_reminder,
80 vector<Grob *> *real_acc)
82 for (SCM acs = accs->get_object ("accidental-grobs"); scm_is_pair (acs);
84 for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
86 Grob *a = unsmob_grob (scm_car (s));
88 if (unsmob_grob (a->get_object ("tie"))
89 && !to_boolean (a->get_property ("forced")))
90 break_reminder->push_back (a);
92 real_acc->push_back (a);
97 Accidental_placement::get_relevant_accidentals (vector<Grob *> const &elts, Grob *left)
102 bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
104 for (vsize i = 0; i < elts.size (); i++)
106 split_accidentals (elts[i], &br, &ra);
108 ret.insert (ret.end (), ra.begin (), ra.end ());
111 ret.insert (ret.end (), br.begin (), br.end ());
116 struct Accidental_placement_entry
118 Skyline left_skyline_;
119 Skyline right_skyline_;
120 Interval vertical_extent_;
121 vector<Box> extents_;
122 vector<Grob *> grobs_;
125 Real ape_priority (Accidental_placement_entry const *a)
127 return a->vertical_extent_[UP];
130 bool ape_less (Accidental_placement_entry *const &a,
131 Accidental_placement_entry *const &b)
133 return ape_priority (a) < ape_priority (b);
137 This function provides a method for sorting accidentals that belong to the
138 same note. The accidentals that this function considers to be "smallest"
139 will be placed to the left of the "larger" accidentals.
141 Naturals are the largest (so that they don't get confused with cancellation
142 naturals); apart from that, we order according to the alteration (so
143 double-flats are the smallest).
145 Precondition: the accidentals are attached to NoteHeads of the same note
146 name -- the octaves, however, may be different.
149 acc_less (Grob *const &a, Grob *const &b)
151 Pitch *p = accidental_pitch (a);
152 Pitch *q = accidental_pitch (b);
156 programming_error ("these accidentals do not have a pitch");
160 if (p->get_octave () != q->get_octave ())
161 return p->get_octave () < q->get_octave ();
163 if (p->get_alteration () == Rational (0))
165 if (q->get_alteration () == Rational (0))
168 return p->get_alteration () < q->get_alteration ();
180 stagger_apes (vector<Accidental_placement_entry *> *apes)
182 vector<Accidental_placement_entry *> asc = *apes;
184 vector_sort (asc, &ape_less);
189 for (vsize i = 0; i < asc.size ();)
191 Accidental_placement_entry *a = 0;
207 static vector<Accidental_placement_entry *>
208 build_apes (SCM accs)
210 vector<Accidental_placement_entry *> apes;
211 for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
213 Accidental_placement_entry *ape = new Accidental_placement_entry;
215 for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
216 ape->grobs_.push_back (unsmob_grob (scm_car (t)));
218 apes.push_back (ape);
225 set_ape_skylines (Accidental_placement_entry *ape,
226 Grob **common, Real padding)
228 vector<Grob *> accs (ape->grobs_);
229 vector_sort (accs, &acc_less);
231 /* We know that each accidental has the same note name and we assume that
232 accidentals in different octaves won't collide. If two or more
233 accidentals are in the same octave:
234 1) if they are the same accidental, print them in overstrike
235 2) otherwise, shift one to the left so they don't overlap. */
238 Real last_offset = 0;
239 Rational last_alteration (0);
240 for (vsize i = accs.size (); i--;)
243 Pitch *p = accidental_pitch (a);
248 if (i == accs.size () - 1 || p->get_octave () != last_octave)
251 offset = a->extent (a, X_AXIS)[LEFT] - padding;
253 else if (p->get_alteration () == last_alteration)
254 a->translate_axis (last_offset, X_AXIS);
255 else /* Our alteration is different from the last one */
257 Real this_offset = offset - a->extent (a, X_AXIS)[RIGHT];
258 a->translate_axis (this_offset, X_AXIS);
260 last_offset = this_offset;
261 offset -= a->extent (a, X_AXIS).length () + padding;
264 vector<Box> boxes = Accidental_interface::accurate_boxes (a, common);
265 ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ());
267 for (vsize j = boxes.size (); j--;)
268 ape->vertical_extent_.unite (boxes[j][Y_AXIS]);
270 last_octave = p->get_octave ();
271 last_alteration = p->get_alteration ();
273 ape->left_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, LEFT);
274 ape->right_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, RIGHT);
277 static vector<Grob *>
278 extract_heads_and_stems (vector<Accidental_placement_entry *> const &apes)
280 vector<Grob *> note_cols;
283 for (vsize i = apes.size (); i--;)
285 Accidental_placement_entry *ape = apes[i];
286 for (vsize j = ape->grobs_.size (); j--;)
288 Grob *acc = ape->grobs_[j];
289 Grob *head = acc->get_parent (Y_AXIS);
290 Grob *col = head->get_parent (X_AXIS);
292 if (Note_column::has_interface (col))
293 note_cols.push_back (col);
295 ret.push_back (head);
300 This is a little kludgy: in case there are note columns without
301 accidentals, we get them from the Note_collision objects.
303 for (vsize i = note_cols.size (); i--;)
305 Grob *c = note_cols[i]->get_parent (X_AXIS);
306 if (Note_collision_interface::has_interface (c))
308 extract_grob_set (c, "elements", columns);
309 concat (note_cols, columns);
313 /* Now that we have all of the columns, grab all of the note-heads */
314 for (vsize i = note_cols.size (); i--;)
315 concat (ret, extract_grob_array (note_cols[i], "note-heads"));
317 /* Now that we have all of the heads, grab all of the stems */
318 for (vsize i = ret.size (); i--;)
319 if (Grob *s = Rhythmic_head::get_stem (ret[i]))
322 vector_sort (ret, less<Grob *> ());
328 common_refpoint_of_accidentals (vector<Accidental_placement_entry *> const &apes, Axis a)
332 for (vsize i = apes.size (); i--;)
333 for (vsize j = apes[i]->grobs_.size (); j--;)
336 ret = apes[i]->grobs_[j];
338 ret = ret->common_refpoint (apes[i]->grobs_[j], a);
345 build_heads_skyline (vector<Grob *> const &heads_and_stems,
348 vector<Box> head_extents;
349 for (vsize i = heads_and_stems.size (); i--;)
350 head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
351 heads_and_stems[i]->pure_height (common[Y_AXIS], 0, INT_MAX)));
353 return Skyline (head_extents, 0, Y_AXIS, LEFT);
357 Position the apes, starting from the right, so that they don't collide.
358 Return the total width.
361 position_apes (Grob *me,
362 vector<Accidental_placement_entry *> const &apes,
363 Skyline const &heads_skyline)
365 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
366 Skyline left_skyline = heads_skyline;
367 left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0));
370 Add accs entries right-to-left.
373 Real last_offset = 0.0;
374 for (vsize i = apes.size (); i-- > 0;)
376 Accidental_placement_entry *ape = apes[i];
378 Real offset = -ape->right_skyline_.distance (left_skyline);
380 offset = last_offset;
384 Skyline new_left_skyline = ape->left_skyline_;
385 new_left_skyline.raise (offset);
386 new_left_skyline.merge (left_skyline);
387 left_skyline = new_left_skyline;
389 /* Shift all of the accidentals in this ape */
390 for (vsize j = ape->grobs_.size (); j--;)
391 ape->grobs_[j]->translate_axis (offset, X_AXIS);
393 for (vsize j = ape->extents_.size (); j--;)
394 width.unite (offset + ape->extents_[j][X_AXIS]);
396 last_offset = offset;
403 This routine computes placements of accidentals. During
404 add_accidental (), accidentals are already grouped by note, so that
405 octaves are placed above each other; they form columns. Then the
406 columns are sorted: the biggest columns go closest to the note.
407 Then the columns are spaced as closely as possible (using skyline
411 TODO: more advanced placement. Typically, the accs should be placed
412 to form a C shape, like this
420 The naturals should be left of the C as well; they should
423 Note that this placement problem looks NP hard, so we just use a
424 simple strategy, not an optimal choice.
428 TODO: there should be more space in the following situation
441 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
443 Accidental_placement::calc_positioning_done (SCM smob)
445 Grob *me = unsmob_grob (smob);
449 me->set_property ("positioning-done", SCM_BOOL_T);
451 SCM accs = me->get_object ("accidental-grobs");
452 if (!scm_is_pair (accs))
455 vector<Accidental_placement_entry *> apes = build_apes (accs);
457 Grob *common[] = {me, 0};
459 vector<Grob *> heads_and_stems = extract_heads_and_stems (apes);
461 common[Y_AXIS] = common_refpoint_of_accidentals (apes, Y_AXIS);
462 common[Y_AXIS] = common_refpoint_of_array (heads_and_stems, common[Y_AXIS], Y_AXIS);
463 common[X_AXIS] = common_refpoint_of_array (heads_and_stems, me, X_AXIS);
464 Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
466 for (vsize i = apes.size (); i--;)
467 set_ape_skylines (apes[i], common, padding);
468 Skyline heads_skyline = build_heads_skyline (heads_and_stems, common);
470 stagger_apes (&apes);
471 Interval width = position_apes (me, apes, heads_skyline);
473 me->flush_extent_cache (X_AXIS);
474 me->set_property ("X-extent", ly_interval2scm (width));
476 junk_pointers (apes);
481 ADD_INTERFACE (Accidental_placement,
482 "Resolve accidental collisions.",