1 /*
2 This file is part of LilyPond, the GNU music typesetter.
3
4 Copyright (C) 2002--2021 Han-Wen Nienhuys <hanwen@xs4all.nl>
5
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.
10
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.
15
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/>.
18 */
19
20 #include "accidental-placement.hh"
21
22 #include "accidental-interface.hh"
23 #include "item.hh"
24 #include "music.hh"
25 #include "note-collision.hh"
26 #include "note-column.hh"
27 #include "pointer-group-interface.hh"
28 #include "rhythmic-head.hh"
29 #include "skyline.hh"
30 #include "skyline-pair.hh"
31 #include "stream-event.hh"
32 #include "warn.hh"
33
34 #include <algorithm>
35 #include <functional>
36 #include <memory>
37 #include <vector>
38
39 using std::unique_ptr;
40 using std::vector;
41
42 static Pitch *
accidental_pitch(Grob * acc)43 accidental_pitch (Grob *acc)
44 {
45 Stream_event *mcause = acc->get_y_parent ()->event_cause ();
46
47 if (!mcause)
48 {
49 programming_error ("note head has no event cause");
50 return 0;
51 }
52
53 return unsmob<Pitch> (get_property (mcause, "pitch"));
54 }
55
56 void
add_accidental(Grob * me,Grob * a,bool stagger,const void * hash_key)57 Accidental_placement::add_accidental (Grob *me, Grob *a, bool stagger,
58 const void *hash_key)
59 {
60 Pitch *p = accidental_pitch (a);
61 if (!p)
62 return;
63
64 a->set_x_parent (me);
65
66 SCM accs = get_object (me, "accidental-grobs");
67 SCM key = scm_cons (to_scm (p->get_notename ()),
68 to_scm (stagger
69 ? std::hash<const void *> () (hash_key)
70 : 1));
71 // assoc because we're dealing with pairs
72 SCM entry = ly_assoc (key, accs);
73 if (scm_is_false (entry))
74 entry = SCM_EOL;
75 else
76 entry = scm_cdr (entry);
77
78 entry = scm_cons (a->self_scm (), entry);
79
80 accs = scm_assoc_set_x (accs, key, entry);
81
82 set_object (me, "accidental-grobs", accs);
83 }
84
85 /*
86 Split into break reminders.
87 */
88 void
split_accidentals(Grob * accs,vector<Grob * > * break_reminder,vector<Grob * > * real_acc)89 Accidental_placement::split_accidentals (Grob *accs,
90 vector<Grob *> *break_reminder,
91 vector<Grob *> *real_acc)
92 {
93 for (SCM acs = get_object (accs, "accidental-grobs"); scm_is_pair (acs);
94 acs = scm_cdr (acs))
95 for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
96 {
97 Grob *a = unsmob<Grob> (scm_car (s));
98
99 if (unsmob<Grob> (get_object (a, "tie"))
100 && !from_scm<bool> (get_property (a, "forced")))
101 break_reminder->push_back (a);
102 else
103 real_acc->push_back (a);
104 }
105 }
106
107 vector<Grob *>
get_relevant_accidentals(vector<Grob * > const & elts,Grob * left)108 Accidental_placement::get_relevant_accidentals (vector<Grob *> const &elts, Grob *left)
109 {
110 vector<Grob *> br;
111 vector<Grob *> ra;
112 vector<Grob *> ret;
113 bool right = dynamic_cast<Item *> (left)->break_status_dir () == RIGHT;
114
115 for (vsize i = 0; i < elts.size (); i++)
116 {
117 split_accidentals (elts[i], &br, &ra);
118
119 ret.insert (ret.end (), ra.begin (), ra.end ());
120
121 if (right)
122 ret.insert (ret.end (), br.begin (), br.end ());
123 }
124 return ret;
125 }
126
127 struct Accidental_placement_entry
128 {
129 Skyline_pair horizontal_skylines_;
130 vector<Grob *> grobs_;
131 };
132
ape_priority(Accidental_placement_entry const * a)133 Real ape_priority (Accidental_placement_entry const *a)
134 {
135 // right is up because we're horizontal
136 return a->horizontal_skylines_.right ();
137 }
138
ape_less(unique_ptr<Accidental_placement_entry> const & a,unique_ptr<Accidental_placement_entry> const & b)139 bool ape_less (unique_ptr<Accidental_placement_entry> const &a,
140 unique_ptr<Accidental_placement_entry> const &b)
141 {
142 vsize size_a = a->grobs_.size ();
143 vsize size_b = b->grobs_.size ();
144 if (size_a != size_b)
145 return size_b < size_a;
146
147 return ape_priority (a.get ()) < ape_priority (b.get ());
148 }
149
150 /*
151 This function provides a method for sorting accidentals that belong to the
152 same note. The accidentals that this function considers to be "smallest"
153 will be placed to the left of the "larger" accidentals.
154
155 Naturals are the largest (so that they don't get confused with cancellation
156 naturals); apart from that, we order according to the alteration (so
157 double-flats are the smallest).
158
159 Precondition: the accidentals are attached to NoteHeads of the same note
160 name -- the octaves, however, may be different.
161 */
162 static bool
acc_less(Grob * const & a,Grob * const & b)163 acc_less (Grob *const &a, Grob *const &b)
164 {
165 Pitch *p = accidental_pitch (a);
166 Pitch *q = accidental_pitch (b);
167
168 if (!p || !q)
169 {
170 programming_error ("these accidentals do not have a pitch");
171 return false;
172 }
173
174 if (p->get_octave () != q->get_octave ())
175 return p->get_octave () < q->get_octave ();
176
177 if (p->get_alteration () == Rational (0))
178 return false;
179 if (q->get_alteration () == Rational (0))
180 return true;
181
182 return p->get_alteration () < q->get_alteration ();
183 }
184
185 /*
186 TODO: should favor
187
188 * b
189 * b
190
191 placement
192 */
193 void
stagger_apes(vector<unique_ptr<Accidental_placement_entry>> * apes)194 stagger_apes (vector<unique_ptr<Accidental_placement_entry>> *apes)
195 {
196 std::sort (apes->begin (), apes->end (), &ape_less);
197 // we do the staggering below based on size
198 // this ensures that if a placement has 4 entries, it will
199 // always be closer to the NoteColumn than a placement with 1
200 // this allows accidentals to be on-average closer to notes
201 // while still preserving octave alignment
202 vector<vector<unique_ptr<Accidental_placement_entry>>> ascs;
203
204 vsize sz = INT_MAX;
205 for (vsize i = 0; i < apes->size (); i++)
206 {
207 auto a = std::move ((*apes)[i]);
208 vsize my_sz = a->grobs_.size ();
209 if (sz != my_sz)
210 ascs.push_back ({}); // empty vector
211 ascs.back ().push_back (std::move (a));
212 sz = my_sz;
213 }
214
215 apes->clear ();
216
217 for (vsize i = 0; i < ascs.size (); i++)
218 {
219 int parity = 1;
220 for (vsize j = 0; j < ascs[i].size ();)
221 {
222 unique_ptr<Accidental_placement_entry> a;
223 if (parity)
224 {
225 a = std::move (ascs[i].back ());
226 ascs[i].pop_back ();
227 }
228 else
229 a = std::move (ascs[i][j++]);
230
231 apes->push_back (std::move (a));
232 parity = !parity;
233 }
234 }
235
236 std::reverse (apes->begin (), apes->end ());
237 }
238
239 static vector<unique_ptr<Accidental_placement_entry>>
build_apes(SCM accs)240 build_apes (SCM accs)
241 {
242 vector<unique_ptr<Accidental_placement_entry>> apes;
243 for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
244 {
245 unique_ptr<Accidental_placement_entry>
246 ape (new Accidental_placement_entry);
247
248 for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
249 ape->grobs_.push_back (unsmob<Grob> (scm_car (t)));
250
251 apes.push_back (std::move (ape));
252 }
253
254 return apes;
255 }
256
257 static void
set_ape_skylines(Accidental_placement_entry * ape,Grob ** common,Real padding)258 set_ape_skylines (Accidental_placement_entry *ape,
259 Grob **common, Real padding)
260 {
261 vector<Grob *> accs (ape->grobs_);
262 std::sort (accs.begin (), accs.end (), &acc_less);
263
264 /* We know that each accidental has the same note name and we assume that
265 accidentals in different octaves won't collide. If two or more
266 accidentals are in the same octave:
267 1) if they are the same accidental, print them in overstrike
268 2) otherwise, shift one to the left so they don't overlap. */
269 int last_octave = 0;
270 Real offset = 0;
271 Real last_offset = 0;
272 Rational last_alteration (0);
273 for (vsize i = accs.size (); i--;)
274 {
275 Grob *a = accs[i];
276 Pitch *p = accidental_pitch (a);
277
278 if (!p)
279 continue;
280
281 if (i == accs.size () - 1 || p->get_octave () != last_octave)
282 {
283 last_offset = 0;
284 offset = a->extent (a, X_AXIS)[LEFT] - padding;
285 }
286 else if (p->get_alteration () == last_alteration)
287 a->translate_axis (last_offset, X_AXIS);
288 else /* Our alteration is different from the last one */
289 {
290 Real this_offset = offset - a->extent (a, X_AXIS)[RIGHT];
291 a->translate_axis (this_offset, X_AXIS);
292
293 last_offset = this_offset;
294 offset -= a->extent (a, X_AXIS).length () + padding;
295 }
296
297 if (Skyline_pair *sky = unsmob<Skyline_pair> (get_property (a, "horizontal-skylines")))
298 {
299 Skyline_pair copy (*sky);
300 copy.raise (a->relative_coordinate (common[X_AXIS], X_AXIS));
301 copy.shift (a->relative_coordinate (common[Y_AXIS], Y_AXIS));
302 ape->horizontal_skylines_.merge (copy);
303 }
304
305 last_octave = p->get_octave ();
306 last_alteration = p->get_alteration ();
307 }
308 }
309
310 static vector<Grob *>
extract_heads_and_stems(vector<unique_ptr<Accidental_placement_entry>> const & apes)311 extract_heads_and_stems (vector<unique_ptr<Accidental_placement_entry>> const &apes)
312 {
313 vector<Grob *> note_cols;
314 vector<Grob *> ret;
315
316 for (vsize i = apes.size (); i--;)
317 {
318 Accidental_placement_entry *ape = apes[i].get ();
319 for (vsize j = ape->grobs_.size (); j--;)
320 {
321 Grob *acc = ape->grobs_[j];
322 Grob *head = acc->get_y_parent ();
323 Grob *col = head->get_x_parent ();
324
325 if (has_interface<Note_column> (col))
326 note_cols.push_back (col);
327 else
328 ret.push_back (head);
329 }
330 }
331
332 /*
333 This is a little kludgy: in case there are note columns without
334 accidentals, we get them from the Note_collision objects.
335 */
336 for (vsize i = note_cols.size (); i--;)
337 {
338 Grob *c = note_cols[i]->get_x_parent ();
339 if (has_interface<Note_collision_interface> (c))
340 {
341 extract_grob_set (c, "elements", columns);
342 note_cols.insert (note_cols.end (), columns.begin (), columns.end ());
343 }
344 }
345
346 /* Now that we have all of the columns, grab all of the note-heads */
347 for (vsize i = note_cols.size (); i--;)
348 {
349 const auto ¬e_heads = extract_grob_array (note_cols[i], "note-heads");
350 ret.insert (ret.end (), note_heads.begin (), note_heads.end ());
351 }
352
353 /* Now that we have all of the heads, grab all of the stems */
354 for (vsize i = ret.size (); i--;)
355 if (Grob *s = Rhythmic_head::get_stem (ret[i]))
356 ret.push_back (s);
357
358 uniquify (ret);
359 return ret;
360 }
361
362 static Grob *
common_refpoint_of_accidentals(vector<unique_ptr<Accidental_placement_entry>> const & apes,Axis a)363 common_refpoint_of_accidentals (vector<unique_ptr<Accidental_placement_entry>> const &apes,
364 Axis a)
365 {
366 Grob *ret = 0;
367
368 for (vsize i = apes.size (); i--;)
369 for (vsize j = apes[i]->grobs_.size (); j--;)
370 {
371 if (!ret)
372 ret = apes[i]->grobs_[j];
373 else
374 ret = ret->common_refpoint (apes[i]->grobs_[j], a);
375 }
376
377 return ret;
378 }
379
380 static Skyline
build_heads_skyline(vector<Grob * > const & heads_and_stems,Grob ** common)381 build_heads_skyline (vector<Grob *> const &heads_and_stems,
382 Grob **common)
383 {
384 vector<Box> head_extents;
385 for (vsize i = heads_and_stems.size (); i--;)
386 head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS),
387 heads_and_stems[i]->pure_y_extent (common[Y_AXIS], 0, INT_MAX)));
388
389 return Skyline (head_extents, Y_AXIS, LEFT);
390 }
391
392 /*
393 Position the apes, starting from the right, so that they don't collide.
394 Return the total width.
395 */
396 static Interval
position_apes(Grob * me,vector<unique_ptr<Accidental_placement_entry>> const & apes,Skyline const & heads_skyline)397 position_apes (Grob *me,
398 vector<unique_ptr<Accidental_placement_entry>> const &apes,
399 Skyline const &heads_skyline)
400 {
401 Real padding = from_scm<double> (get_property (me, "padding"), 0.2);
402 Skyline left_skyline = heads_skyline;
403 left_skyline.raise (-from_scm<double> (get_property (me, "right-padding"), 0));
404
405 /*
406 Add accs entries right-to-left.
407 */
408 Interval width;
409 Real last_offset = 0.0;
410 for (vsize i = apes.size (); i-- > 0;)
411 {
412 Accidental_placement_entry *ape = apes[i].get ();
413
414 Real offset = -ape->horizontal_skylines_[RIGHT]
415 .distance (left_skyline, 0.1);
416 if (std::isinf (offset))
417 offset = last_offset;
418 else
419 offset -= padding;
420
421 Skyline new_left_skyline = ape->horizontal_skylines_[LEFT];
422 new_left_skyline.raise (offset);
423 new_left_skyline.merge (left_skyline);
424 left_skyline = new_left_skyline;
425
426 /* Shift all of the accidentals in this ape */
427 for (vsize j = ape->grobs_.size (); j--;)
428 ape->grobs_[j]->translate_axis (offset, X_AXIS);
429
430 for (const auto d : {LEFT, RIGHT})
431 {
432 Real mh = ape->horizontal_skylines_[d].max_height ();
433 if (!std::isinf (mh))
434 width.add_point (mh + offset);
435 }
436
437 last_offset = offset;
438 }
439
440 return width;
441 }
442
443 /*
444 This routine computes placements of accidentals. During
445 add_accidental (), accidentals are already grouped by note, so that
446 octaves are placed above each other; they form columns. Then the
447 columns are sorted: the biggest columns go closest to the note.
448 Then the columns are spaced as closely as possible (using skyline
449 spacing).
450
451
452 TODO: more advanced placement. Typically, the accs should be placed
453 to form a C shape, like this
454
455 * ##
456 * b b
457 * # #
458 * b
459 * b b
460
461 The naturals should be left of the C as well; they should
462 be separate accs.
463
464 Note that this placement problem looks NP hard, so we just use a
465 simple strategy, not an optimal choice.
466 */
467
468 /*
469 TODO: there should be more space in the following situation
470
471
472 Natural + downstem
473
474 *
475 * |_
476 * | | X
477 * |_| |
478 * | |
479 *
480 */
481
482 MAKE_SCHEME_CALLBACK (Accidental_placement, calc_positioning_done, 1);
483 SCM
calc_positioning_done(SCM smob)484 Accidental_placement::calc_positioning_done (SCM smob)
485 {
486 Grob *me = unsmob<Grob> (smob);
487 if (!me->is_live ())
488 return SCM_BOOL_T;
489
490 set_property (me, "positioning-done", SCM_BOOL_T);
491
492 SCM accs = get_object (me, "accidental-grobs");
493 if (!scm_is_pair (accs))
494 return SCM_BOOL_T;
495
496 vector<unique_ptr<Accidental_placement_entry>> apes = build_apes (accs);
497
498 Grob *common[] = {me, 0};
499
500 vector<Grob *> heads_and_stems = extract_heads_and_stems (apes);
501
502 common[Y_AXIS] = common_refpoint_of_accidentals (apes, Y_AXIS);
503 common[Y_AXIS] = common_refpoint_of_array (heads_and_stems, common[Y_AXIS], Y_AXIS);
504 common[X_AXIS] = common_refpoint_of_array (heads_and_stems, me, X_AXIS);
505 Real padding = from_scm<double> (get_property (me, "padding"), 0.2);
506
507 for (vsize i = apes.size (); i--;)
508 set_ape_skylines (apes[i].get (), common, padding);
509 Skyline heads_skyline = build_heads_skyline (heads_and_stems, common);
510
511 stagger_apes (&apes);
512 Interval width = position_apes (me, apes, heads_skyline);
513
514 me->flush_extent_cache (X_AXIS);
515 set_property (me, "X-extent", to_scm (width));
516
517 return SCM_BOOL_T;
518 }
519
520 ADD_INTERFACE (Accidental_placement,
521 "Resolve accidental collisions.",
522
523 /* properties */
524 "accidental-grobs "
525 "direction "
526 "padding "
527 "positioning-done "
528 "right-padding "
529 "script-priority "
530 );
531