2 accidental-placement.cc -- implement Accidental_placement
4 source file of the GNU LilyPond music typesetter
6 (c) 2002--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
10 #include "accidental-placement.hh"
13 #include "rhythmic-head.hh"
14 #include "accidental-interface.hh"
16 #include "note-collision.hh"
17 #include "note-column.hh"
18 #include "pointer-group-interface.hh"
20 #include "stream-event.hh"
25 Accidental_placement::add_accidental (Grob
*me
, Grob
*a
)
27 a
->set_parent (me
, X_AXIS
);
28 a
->set_property ("X-offset", Grob::x_parent_positioning_proc
);
29 SCM cause
= a
->get_parent (Y_AXIS
)->get_property ("cause");
31 Stream_event
*mcause
= unsmob_stream_event (cause
);
34 programming_error ("note head has no event cause");
38 Pitch
*p
= unsmob_pitch (mcause
->get_property ("pitch"));
40 int n
= p
->get_notename ();
42 SCM accs
= me
->get_object ("accidental-grobs");
43 SCM key
= scm_from_int (n
);
44 SCM entry
= scm_assq (key
, accs
);
45 if (entry
== SCM_BOOL_F
)
48 entry
= scm_cdr (entry
);
50 entry
= scm_cons (a
->self_scm (), entry
);
52 accs
= scm_assq_set_x (accs
, key
, entry
);
54 me
->set_object ("accidental-grobs", accs
);
58 Split into break reminders.
61 Accidental_placement::split_accidentals (Grob
*accs
,
62 vector
<Grob
*> *break_reminder
,
63 vector
<Grob
*> *real_acc
)
65 for (SCM acs
= accs
->get_object ("accidental-grobs"); scm_is_pair (acs
);
67 for (SCM s
= scm_cdar (acs
); scm_is_pair (s
); s
= scm_cdr (s
))
69 Grob
*a
= unsmob_grob (scm_car (s
));
71 if (unsmob_grob (a
->get_object ("tie"))
72 && !to_boolean (a
->get_property ("forced")))
73 break_reminder
->push_back (a
);
75 real_acc
->push_back (a
);
80 Accidental_placement::get_relevant_accidentals (vector
<Grob
*> const &elts
, Grob
*left
)
85 bool right
= dynamic_cast<Item
*> (left
)->break_status_dir () == RIGHT
;
87 for (vsize i
= 0; i
< elts
.size (); i
++)
89 split_accidentals (elts
[i
], &br
, &ra
);
91 ret
.insert (ret
.end (), ra
.begin (), ra
.end ());
94 ret
.insert (ret
.end (), br
.begin (), br
.end ());
99 struct Accidental_placement_entry
101 Skyline left_skyline_
;
102 Skyline right_skyline_
;
103 Interval vertical_extent_
;
104 vector
<Box
> extents_
;
105 vector
<Grob
*> grobs_
;
108 Accidental_placement_entry ()
115 static Interval all_accidental_vertical_extent
;
116 Real
ape_priority (Accidental_placement_entry
const *a
)
118 return a
->vertical_extent_
[UP
];
121 int ape_compare (Accidental_placement_entry
*const &a
,
122 Accidental_placement_entry
*const &b
)
124 return sign (ape_priority (a
) - ape_priority (b
));
127 bool ape_less (Accidental_placement_entry
*const &a
,
128 Accidental_placement_entry
*const &b
)
130 return ape_priority (a
) < ape_priority (b
);
133 int ape_rcompare (Accidental_placement_entry
*const &a
,
134 Accidental_placement_entry
*const &b
)
136 return -sign (ape_priority (a
) - ape_priority (b
));
148 stagger_apes (vector
<Accidental_placement_entry
*> *apes
)
150 vector
<Accidental_placement_entry
*> asc
= *apes
;
152 vector_sort (asc
, &ape_less
);
157 for (vsize i
= 0; i
< asc
.size ();)
159 Accidental_placement_entry
*a
= 0;
176 This routine computes placements of accidentals. During
177 add_accidental (), accidentals are already grouped by note, so that
178 octaves are placed above each other; they form columns. Then the
179 columns are sorted: the biggest columns go closest to the note.
180 Then the columns are spaced as closely as possible (using skyline
184 TODO: more advanced placement. Typically, the accs should be placed
185 to form a C shape, like this
194 The naturals should be left of the C as well; they should
197 Note that this placement problem looks NP hard, so we just use a
198 simple strategy, not an optimal choice.
202 TODO: there should be more space in the following situation
216 MAKE_SCHEME_CALLBACK (Accidental_placement
, calc_positioning_done
, 1);
218 Accidental_placement::calc_positioning_done (SCM smob
)
220 Grob
*me
= unsmob_grob (smob
);
224 me
->set_property ("positioning-done", SCM_BOOL_T
);
226 SCM accs
= me
->get_object ("accidental-grobs");
227 if (!scm_is_pair (accs
))
231 TODO: there is a bug in this code. If two accs are on the same
232 Y-position, they share an Ape, and will be printed in overstrike.
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
;
238 ape
->notename_
= scm_to_int (scm_caar (s
));
240 for (SCM t
= scm_cdar (s
); scm_is_pair (t
); t
= scm_cdr (t
))
241 ape
->grobs_
.push_back (unsmob_grob (scm_car (t
)));
243 apes
.push_back (ape
);
246 Grob
*common
[] = {me
, 0};
249 First we must extract *all* pointers. We can only determine
250 extents if we're sure that we've found the right common refpoint
252 vector
<Grob
*> note_cols
, heads
;
253 for (vsize i
= apes
.size (); i
--;)
255 Accidental_placement_entry
*ape
= apes
[i
];
256 for (vsize j
= ape
->grobs_
.size (); j
--;)
258 Grob
*a
= ape
->grobs_
[j
];
261 common
[Y_AXIS
] = common
[Y_AXIS
]->common_refpoint (a
, Y_AXIS
);
265 Grob
*head
= a
->get_parent (Y_AXIS
);
267 Grob
*col
= head
->get_parent (X_AXIS
);
268 if (Note_column::has_interface (col
))
269 note_cols
.push_back (col
);
271 heads
.push_back (head
);
276 This is a little kludgy: to get all notes, we look if there are
279 for (vsize i
= note_cols
.size (); i
--;)
281 Grob
*c
= note_cols
[i
]->get_parent (X_AXIS
);
282 if (Note_collision_interface::has_interface (c
))
284 extract_grob_set (c
, "elements", gs
);
286 concat (note_cols
, gs
);
290 for (vsize i
= note_cols
.size (); i
--;)
291 concat (heads
, extract_grob_array (note_cols
[i
], "note-heads"));
293 vector_sort (heads
, less
<Grob
*> ());
296 vector
<Grob
*> stems
;
297 for (vsize i
= 0; i
< heads
.size (); i
++)
299 if (Grob
*s
= Rhythmic_head::get_stem (heads
[i
]))
303 vector_sort (stems
, less
<Grob
*> ());
306 common
[Y_AXIS
] = common_refpoint_of_array (heads
, common
[Y_AXIS
], Y_AXIS
);
307 common
[Y_AXIS
] = common_refpoint_of_array (stems
, common
[Y_AXIS
], Y_AXIS
);
309 for (vsize i
= 0; i
< heads
.size (); i
++)
311 if (Grob
*s
= Rhythmic_head::get_stem (heads
[i
]))
314 common
[Y_AXIS
] = s
->common_refpoint (common
[Y_AXIS
], Y_AXIS
);
318 vector_sort (stems
, less
<Grob
*> ());
322 for (vsize i
= apes
.size (); i
--;)
324 Accidental_placement_entry
*ape
= apes
[i
];
326 for (vsize j
= apes
[i
]->grobs_
.size (); j
--;)
328 Grob
*a
= apes
[i
]->grobs_
[j
];
329 vector
<Box
> boxes
= Accidental_interface::accurate_boxes (a
, common
);
331 ape
->extents_
.insert (ape
->extents_
.end (), boxes
.begin (), boxes
.end ());
333 ape
->left_skyline_
= Skyline (ape
->extents_
, 0, Y_AXIS
, LEFT
);
334 ape
->right_skyline_
= Skyline (ape
->extents_
, 0, Y_AXIS
, RIGHT
);
338 for (vsize i
= apes
.size (); i
--;)
342 for (vsize j
= apes
[i
]->extents_
.size (); j
--;)
343 y
.unite (apes
[i
]->extents_
[j
][Y_AXIS
]);
344 apes
[i
]->vertical_extent_
= y
;
347 all_accidental_vertical_extent
= total
;
348 stagger_apes (&apes
);
350 Accidental_placement_entry
*head_ape
= new Accidental_placement_entry
;
351 common
[X_AXIS
] = common_refpoint_of_array (heads
, common
[X_AXIS
], X_AXIS
);
353 vector
<Box
> head_extents
;
354 for (vsize i
= heads
.size (); i
--;)
355 head_extents
.push_back (Box (heads
[i
]->extent (common
[X_AXIS
], X_AXIS
),
356 heads
[i
]->extent (common
[Y_AXIS
], Y_AXIS
)));
358 for (vsize i
= 0; i
< stems
.size (); i
++)
360 int very_large
= INT_MAX
;
362 head_extents
.push_back (Box (stems
[i
]->extent (common
[X_AXIS
], X_AXIS
),
363 stems
[i
]->pure_height (common
[Y_AXIS
], 0, very_large
)));
366 head_ape
->left_skyline_
= Skyline (head_extents
, 0, Y_AXIS
, LEFT
);
367 head_ape
->offset_
= 0.0;
369 Real padding
= robust_scm2double (me
->get_property ("padding"), 0.2);
371 Skyline left_skyline
= head_ape
->left_skyline_
;
372 left_skyline
.raise (-robust_scm2double (me
->get_property ("right-padding"), 0));
375 Add accs entries right-to-left.
377 for (vsize i
= apes
.size (); i
-- > 0;)
379 Real offset
= -apes
[i
]->right_skyline_
.distance (left_skyline
);
381 offset
= (i
+ 1 < apes
.size ()) ? apes
[i
+ 1]->offset_
: 0.0;
385 apes
[i
]->offset_
= offset
;
387 Skyline new_left_skyline
= apes
[i
]->left_skyline_
;
388 new_left_skyline
.raise (apes
[i
]->offset_
);
389 new_left_skyline
.merge (left_skyline
);
390 left_skyline
= new_left_skyline
;
393 for (vsize i
= apes
.size (); i
--;)
395 Accidental_placement_entry
*ape
= apes
[i
];
396 for (vsize j
= ape
->grobs_
.size (); j
--;)
397 ape
->grobs_
[j
]->translate_axis (ape
->offset_
, X_AXIS
);
400 Interval left_extent
, right_extent
;
401 Accidental_placement_entry
*ape
= apes
[0];
403 for (vsize i
= ape
->extents_
.size (); i
--;)
404 left_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
407 for (vsize i
= ape
->extents_
.size (); i
--;)
408 right_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
410 left_extent
[LEFT
] -= robust_scm2double (me
->get_property ("left-padding"), 0);
411 Interval
width (left_extent
[LEFT
], right_extent
[RIGHT
]);
413 SCM scm_width
= ly_interval2scm (width
);
414 me
->flush_extent_cache (X_AXIS
);
415 me
->set_property ("X-extent", scm_width
);
417 junk_pointers (apes
);
424 ADD_INTERFACE (Accidental_placement
,
425 "Resolve accidental collisions.",