2 accidental-placement.cc -- implement Accidental_placement
4 source file of the GNU LilyPond music typesetter
6 (c) 2002--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
11 #include <libc-extension.hh>
18 #include "accidental-placement.hh"
19 #include "note-column.hh"
20 #include "group-interface.hh"
21 #include "note-collision.hh"
22 #include "accidental-interface.hh"
24 MAKE_SCHEME_CALLBACK (Accidental_placement
,alignment_callback
, 2);
26 Accidental_placement::alignment_callback (SCM s
, SCM
)
28 Grob
* me
=unsmob_grob (s
);
30 Grob
* par
= me
->get_parent (X_AXIS
);
31 if (!to_boolean (par
->get_property ("positioning-done")))
33 par
->set_property ("positioning-done", SCM_BOOL_T
);
34 position_accidentals (par
);
37 return scm_int2num (0);
42 Accidental_placement::add_accidental (Grob
* me
, Grob
* a
)
44 a
->set_parent (me
, X_AXIS
);
45 a
->add_offset_callback (alignment_callback_proc
, X_AXIS
);
46 SCM cause
= a
->get_parent (Y_AXIS
)->get_property ("cause");
48 Music
*mcause
=unsmob_music (cause
);
51 programming_error ("Note head has no music cause!");
55 Pitch
*p
= unsmob_pitch (mcause
->get_property ("pitch"));
57 int n
= p
->get_notename ();
59 SCM accs
= me
->get_property ("accidental-grobs");
60 SCM key
= scm_int2num (n
);
61 SCM entry
= scm_assq (key
, accs
);
62 if (entry
== SCM_BOOL_F
)
67 entry
= gh_cdr (entry
);
69 entry
= gh_cons (a
->self_scm (), entry
);
71 accs
= scm_assq_set_x (accs
, key
, entry
);
73 me
->set_property ("accidental-grobs", accs
);
77 Split into break reminders.
80 Accidental_placement::split_accidentals (Grob
* accs
,
81 Link_array
<Grob
> *break_reminder
,
82 Link_array
<Grob
> *real_acc
)
84 for (SCM acs
=accs
->get_property ("accidental-grobs"); gh_pair_p (acs
);
86 for (SCM s
= gh_cdar (acs
); gh_pair_p (s
); s
= gh_cdr (s
))
88 Grob
*a
= unsmob_grob (gh_car (s
));
90 if (unsmob_grob (a
->get_property ("tie")))
91 break_reminder
->push (a
);
98 Accidentals are special, because they appear and disappear after
102 Accidental_placement::get_relevant_accidental_extent (Grob
*me
,
106 Link_array
<Grob
> br
, ra
;
107 Link_array
<Grob
> *which
= 0;
109 Accidental_placement::split_accidentals (me
, &br
, &ra
);
112 if (dynamic_cast<Item
*>(left_object
)->break_status_dir () == RIGHT
)
118 for (int i
= 0; i
< which
->size (); i
++)
120 extent
.unite (which
->elem (i
)->extent (item_col
, X_AXIS
));
123 if (!extent
.is_empty ())
125 Real p
= robust_scm2double (me
->get_property ("left-padding"), 0.2);
134 struct Accidental_placement_entry
136 Array
<Skyline_entry
> left_skyline_
;
137 Array
<Skyline_entry
> right_skyline_
;
138 Interval vertical_extent_
;
140 Link_array
<Grob
> grobs_
;
143 Accidental_placement_entry ()
150 static Interval all_accidental_vertical_extent
;
151 Real
ape_priority (Accidental_placement_entry
const * a
)
153 return a
->vertical_extent_
[UP
];
158 int ape_compare (Accidental_placement_entry
*const &a
,
159 Accidental_placement_entry
*const &b
)
161 return sign (ape_priority (a
) - ape_priority (b
));
164 int ape_rcompare (Accidental_placement_entry
*const &a
,
165 Accidental_placement_entry
*const &b
)
167 return -sign (ape_priority (a
) - ape_priority (b
));
182 stagger_apes (Link_array
<Accidental_placement_entry
> *apes
)
184 Link_array
<Accidental_placement_entry
> asc
= *apes
;
187 asc
.sort (&ape_compare
);
193 while (i
< asc
.size ())
195 Accidental_placement_entry
* a
= 0;
212 This routine computes placements of accidentals. During
213 add_accidental (), accidentals are already grouped by note, so that
214 octaves are placed above each other; they form columns. Then the
215 columns are sorted: the biggest columns go closest to the note.
216 Then the columns are spaced as closely as possible (using skyline
220 TODO: more advanced placement. Typically, the accs should be placed
221 to form a C shape, like this
230 The naturals should be left of the C as well; they should
233 Note that this placement problem looks NP hard, so we just use a
234 simple strategy, not an optimal choice.
239 TODO: there should be more space in the following situation
251 Accidental_placement::position_accidentals (Grob
* me
)
254 return SCM_UNSPECIFIED
;
256 SCM accs
= me
->get_property ("accidental-grobs");
259 TODO: there is a bug in this code. If two accs are on the same
260 Y-position, they share an Ape, and will be printed in overstrike.
262 Link_array
<Accidental_placement_entry
> apes
;
263 for (SCM s
= accs
; gh_pair_p (s
); s
=gh_cdr (s
))
265 Accidental_placement_entry
*ape
= new Accidental_placement_entry
;
266 ape
->notename_
= gh_scm2int (gh_caar (s
));
268 for (SCM t
= gh_cdar (s
); gh_pair_p (t
); t
=gh_cdr (t
))
269 ape
->grobs_
.push (unsmob_grob (gh_car (t
)));
275 Grob
*common
[] = {me
, 0};
278 First we must extract *all* pointers. We can only determine
279 extents if we're sure that we've found the right common refpoint
281 Link_array
<Grob
> note_cols
, heads
;
282 for (int i
= apes
.size (); i
--;)
284 Accidental_placement_entry
* ape
= apes
[i
];
285 for (int j
= ape
->grobs_
.size (); j
--;)
287 Grob
* a
= ape
->grobs_
[j
];
290 common
[Y_AXIS
] = common
[Y_AXIS
]->common_refpoint (a
, Y_AXIS
);
294 Grob
*head
= a
->get_parent (Y_AXIS
);
296 Grob
* col
= head
->get_parent (X_AXIS
);
297 if (Note_column::has_interface (col
))
298 note_cols
.push (col
);
305 This is a little kludgy: to get all notes, we look if there are
308 for (int i
= note_cols
.size () ; i
--;)
310 Grob
*c
= note_cols
[i
]->get_parent (X_AXIS
);
311 if (Note_collision_interface::has_interface (c
))
313 Link_array
<Grob
> gs
=
314 Pointer_group_interface__extract_grobs (c
, (Grob
*)0, "elements");
316 note_cols
.concat (gs
);
320 for (int i
= note_cols
.size () ; i
--;)
322 heads
.concat (Pointer_group_interface__extract_grobs (note_cols
[i
],
327 heads
.default_sort ();
329 common
[Y_AXIS
] = common_refpoint_of_array (heads
, common
[Y_AXIS
], Y_AXIS
);
332 for (int i
= apes
.size (); i
--;)
334 Accidental_placement_entry
* ape
= apes
[i
];
335 ape
->left_skyline_
= empty_skyline (LEFT
);
336 ape
->right_skyline_
= empty_skyline (RIGHT
);
338 for (int j
= apes
[i
]->grobs_
.size (); j
--;)
340 Grob
* a
= apes
[i
]->grobs_
[j
];
342 Array
<Box
> boxes
= Accidental_interface::accurate_boxes (a
, common
);
344 ape
->extents_
.concat (boxes
);
345 for (int j
= boxes
.size (); j
--;)
347 insert_extent_into_skyline (&ape
->left_skyline_
, boxes
[j
], Y_AXIS
, LEFT
);
348 insert_extent_into_skyline (&ape
->right_skyline_
, boxes
[j
], Y_AXIS
, RIGHT
);
355 for (int i
= apes
.size (); i
--;)
359 for (int j
= apes
[i
]->extents_
.size (); j
--;)
361 y
.unite (apes
[i
]->extents_
[j
][Y_AXIS
]);
363 apes
[i
]->vertical_extent_
= y
;
366 all_accidental_vertical_extent
= total
;
367 stagger_apes (&apes
);
369 Accidental_placement_entry
* head_ape
= new Accidental_placement_entry
;
370 common
[X_AXIS
] = common_refpoint_of_array (heads
, common
[X_AXIS
], X_AXIS
);
371 Array
<Skyline_entry
> head_skyline (empty_skyline (LEFT
));
372 Array
<Box
> head_extents
;
373 for (int i
= heads
.size (); i
--;)
375 Box
b (heads
[i
]->extent (common
[X_AXIS
] , X_AXIS
),
376 heads
[i
]->extent (common
[Y_AXIS
], Y_AXIS
));
378 insert_extent_into_skyline (&head_skyline
, b
, Y_AXIS
, LEFT
);
381 head_ape
-> left_skyline_
= head_skyline
;
382 head_ape
->offset_
= 0.0;
384 Real padding
= robust_scm2double (me
->get_property ("padding"),0.2);
386 Array
<Skyline_entry
> left_skyline
= head_ape
->left_skyline_
;
387 heighten_skyline (&left_skyline
,
388 -robust_scm2double (me
->get_property ("right-padding"), 0));
390 Add accs entries right-to-left.
392 for (int i
= apes
.size (); i
-- > 0;)
395 -skyline_meshing_distance (apes
[i
]->right_skyline_
, left_skyline
);
397 offset
= (i
< apes
.size () - 1) ? apes
[i
+1]->offset_
: 0.0;
401 apes
[i
]->offset_
= offset
;
403 Array
<Skyline_entry
> new_left_skyline
= apes
[i
]->left_skyline_
;
404 heighten_skyline (&new_left_skyline
, apes
[i
]->offset_
);
405 merge_skyline (&new_left_skyline
, left_skyline
, LEFT
);
406 left_skyline
= new_left_skyline
;
409 for (int i
= apes
.size (); i
--;)
411 Accidental_placement_entry
* ape
= apes
[i
];
412 for (int j
= ape
->grobs_
.size (); j
--;)
414 ape
->grobs_
[j
]->translate_axis (ape
->offset_
, X_AXIS
);
419 Interval left_extent
, right_extent
;
420 Accidental_placement_entry
*ape
= apes
[0];
422 for (int i
= ape
->extents_
.size (); i
--;)
423 left_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
426 for (int i
= ape
->extents_
.size (); i
--;)
427 right_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
430 left_extent
[LEFT
] -= robust_scm2double (me
->get_property ("left-padding"), 0);
433 Interval
width (left_extent
[LEFT
], right_extent
[RIGHT
]);
435 SCM scm_width
= ly_interval2scm (width
);
436 me
->set_extent (scm_width
, X_AXIS
);
438 for (int i
= apes
.size (); i
--;)
441 return SCM_UNSPECIFIED
;
444 ADD_INTERFACE (Accidental_placement
,
445 "accidental-placement-interface",
446 "Resolve accidental collisions.",
447 "left-padding padding right-padding accidental-grobs positioning-done")