2 accidental-placement.cc -- implement Accidental_placement
4 source file of the GNU LilyPond music typesetter
6 (c) 2002--2003 Han-Wen Nienhuys <hanwen@cs.uu.nl>
11 #include <libc-extension.hh>
17 #include "accidental-placement.hh"
18 #include "note-column.hh"
19 #include "group-interface.hh"
20 #include "note-collision.hh"
21 #include "accidental-interface.hh"
23 MAKE_SCHEME_CALLBACK(Accidental_placement
,alignment_callback
, 2);
25 Accidental_placement::alignment_callback(SCM s
, SCM
)
27 Grob
* me
=unsmob_grob (s
);
29 Grob
* par
= me
->get_parent (X_AXIS
);
30 if (!to_boolean (par
->get_grob_property ("alignment-done")))
32 par
->set_grob_property ("alignment-done", SCM_BOOL_T
);
33 position_accidentals (par
);
36 return scm_int2num (0);
41 Accidental_placement::add_accidental (Grob
* me
, Grob
* a
)
43 a
->set_parent (me
, X_AXIS
);
44 a
->add_offset_callback (alignment_callback_proc
, X_AXIS
);
45 SCM cause
= a
->get_parent (Y_AXIS
)->get_grob_property("cause");
47 Music
*mcause
=unsmob_music (cause
);
50 programming_error ("Note head has no music cause!");
54 Pitch
*p
= unsmob_pitch (mcause
->get_mus_property ("pitch"));
56 int n
= p
->get_notename ();
58 SCM accs
= me
->get_grob_property ("accidental-grobs");
59 SCM key
= scm_int2num (n
);
60 SCM entry
= scm_assq (key
, accs
);
61 if (entry
== SCM_BOOL_F
)
66 entry
= gh_cdr (entry
);
68 entry
= gh_cons (a
->self_scm (), entry
);
70 accs
= scm_assq_set_x (accs
, key
, entry
);
72 me
->set_grob_property ("accidental-grobs", accs
);
76 Split into break reminders.
79 Accidental_placement::split_accidentals (Grob
* accs
,
80 Link_array
<Grob
> *break_reminder
,
81 Link_array
<Grob
> *real_acc
)
83 for (SCM acs
=accs
->get_grob_property ("accidental-grobs"); gh_pair_p (acs
);
85 for (SCM s
= gh_cdar (acs
); gh_pair_p (s
); s
= gh_cdr (s
))
87 Grob
*a
= unsmob_grob (gh_car (s
));
89 if (unsmob_grob (a
->get_grob_property ("tie")))
90 break_reminder
->push (a
);
97 Accidentals are special, because they appear and disappear after
101 Accidental_placement::get_relevant_accidental_extent (Grob
*me
,
105 Link_array
<Grob
> br
, ra
;
106 Link_array
<Grob
> *which
= 0;
108 Accidental_placement::split_accidentals (me
, &br
, &ra
);
111 if (dynamic_cast<Item
*>(left_object
)->break_status_dir () == RIGHT
)
117 for (int i
= 0; i
< which
->size(); i
++)
119 extent
.unite (which
->elem(i
)->extent (item_col
, X_AXIS
));
122 if (!extent
.empty_b())
124 Real p
= gh_scm2double (me
->get_grob_property ("left-padding"));
133 struct Accidental_placement_entry
135 Array
<Skyline_entry
> left_skyline_
;
136 Array
<Skyline_entry
> right_skyline_
;
137 Interval vertical_extent_
;
139 Link_array
<Grob
> grobs_
;
142 Accidental_placement_entry()
149 static Interval all_accidental_vertical_extent
;
150 Real
ape_priority (Accidental_placement_entry
const * a
)
152 return a
->vertical_extent_
[UP
];
157 int ape_compare (Accidental_placement_entry
*const &a
,
158 Accidental_placement_entry
*const &b
)
160 return sign (ape_priority (a
) - ape_priority(b
));
163 int ape_rcompare (Accidental_placement_entry
*const &a
,
164 Accidental_placement_entry
*const &b
)
166 return -sign (ape_priority (a
) - ape_priority(b
));
181 stagger_apes (Link_array
<Accidental_placement_entry
> *apes
)
183 Link_array
<Accidental_placement_entry
> asc
= *apes
;
186 asc
.sort (&ape_compare
);
192 while (i
< asc
.size())
194 Accidental_placement_entry
* a
= 0;
211 This routine computes placements of accidentals. During
212 add_accidental(), accidentals are already grouped by note, so that
213 octaves are placed above each other; they form columns. Then the
214 columns are sorted: the biggest columns go closest to the note.
215 Then the columns are spaced as closely as possible (using skyline
219 TODO: more advanced placement. Typically, the accs should be placed
220 to form a C shape, like this
229 The naturals should be left of the C as well; they should
232 Note that this placement problem looks NP hard, so we just use a
233 simple strategy, not an optimal choice.
238 Accidental_placement::position_accidentals (Grob
* me
)
241 return SCM_UNSPECIFIED
;
243 SCM accs
= me
->get_grob_property ("accidental-grobs");
246 TODO: there is a bug in this code. If two accs are on the same
247 Y-position, they share an Ape, and will be pritned in overstrike.
249 Link_array
<Accidental_placement_entry
> apes
;
250 for (SCM s
= accs
; gh_pair_p (s
); s
=gh_cdr (s
))
252 Accidental_placement_entry
*ape
= new Accidental_placement_entry
;
253 ape
->notename_
= gh_scm2int (gh_caar (s
));
255 for (SCM t
= gh_cdar (s
); gh_pair_p (t
); t
=gh_cdr (t
))
256 ape
->grobs_
.push (unsmob_grob (gh_car (t
)));
262 Grob
*common
[] = {me
, 0};
265 First we must extract *all* pointers. We can only determine
266 extents if we're sure that we've found the right common refpoint
268 Link_array
<Grob
> note_cols
, heads
;
269 for (int i
= apes
.size (); i
--;)
271 Accidental_placement_entry
* ape
= apes
[i
];
272 for (int j
= ape
->grobs_
.size(); j
--;)
274 Grob
* a
= ape
->grobs_
[j
];
277 common
[Y_AXIS
] = common
[Y_AXIS
]->common_refpoint (a
, Y_AXIS
);
281 Grob
*head
= a
->get_parent (Y_AXIS
);
283 Grob
* col
= head
->get_parent (X_AXIS
);
284 if (Note_column::has_interface (col
))
285 note_cols
.push (col
);
292 This is a little kludgy: to get all notes, we look if there are
295 for (int i
= note_cols
.size() ; i
--;)
297 Grob
*c
= note_cols
[i
]->get_parent (X_AXIS
);
298 if (Note_collision_interface::has_interface (c
))
300 Link_array
<Grob
> gs
=
301 Pointer_group_interface__extract_grobs (c
, (Grob
*)0, "elements");
303 note_cols
.concat (gs
);
307 for (int i
= note_cols
.size() ; i
--;)
309 heads
.concat (Pointer_group_interface__extract_grobs (note_cols
[i
],
314 heads
.default_sort();
316 common
[Y_AXIS
] = common_refpoint_of_array (heads
, common
[Y_AXIS
], Y_AXIS
);
319 for (int i
= apes
.size (); i
--;)
321 Accidental_placement_entry
* ape
= apes
[i
];
322 ape
->left_skyline_
= empty_skyline (LEFT
);
323 ape
->right_skyline_
= empty_skyline (RIGHT
);
325 for (int j
= apes
[i
]->grobs_
.size(); j
--;)
327 Grob
* a
= apes
[i
]->grobs_
[j
];
329 Array
<Box
> boxes
= Accidental_interface::accurate_boxes (a
, common
);
331 ape
->extents_
.concat (boxes
);
332 for (int j
= boxes
.size(); j
--;)
334 insert_extent_into_skyline (&ape
->left_skyline_
, boxes
[j
], Y_AXIS
, LEFT
);
335 insert_extent_into_skyline (&ape
->right_skyline_
, boxes
[j
], Y_AXIS
, RIGHT
);
342 for (int i
= apes
.size(); i
--;)
346 for (int j
= apes
[i
]->extents_
.size(); j
--;)
348 y
.unite (apes
[i
]->extents_
[j
][Y_AXIS
]);
350 apes
[i
]->vertical_extent_
= y
;
353 all_accidental_vertical_extent
= total
;
354 stagger_apes (&apes
);
356 Accidental_placement_entry
* head_ape
= new Accidental_placement_entry
;
357 common
[X_AXIS
] = common_refpoint_of_array (heads
, common
[X_AXIS
], X_AXIS
);
358 Array
<Skyline_entry
> head_skyline (empty_skyline (LEFT
));
359 Array
<Box
> head_extents
;
360 for (int i
= heads
.size(); i
--;)
362 Box
b(heads
[i
]->extent (common
[X_AXIS
] , X_AXIS
),
363 heads
[i
]->extent (common
[Y_AXIS
], Y_AXIS
));
365 insert_extent_into_skyline (&head_skyline
, b
, Y_AXIS
, LEFT
);
368 head_ape
-> left_skyline_
= head_skyline
;
369 head_ape
->offset_
= 0.0;
371 SCM rs
= me
->get_grob_property ("right-padding");
372 if (gh_number_p (rs
))
373 head_ape
->offset_
-= gh_scm2double (rs
);
377 SCM spad
= me
->get_grob_property ("padding");
378 if (gh_number_p (spad
))
379 padding
= gh_scm2double (spad
);
385 There is a bug in this code: the left_skylines should be
386 accumulated, otherwise the b will collide with bb in
393 apes
.push (head_ape
);
394 for (int i
= apes
.size () -1 ; i
-- > 0;)
396 Accidental_placement_entry
*ape
= apes
[i
];
400 d
= - skyline_meshing_distance (ape
->right_skyline_
,
401 apes
[j
]->left_skyline_
);
404 || j
+ 1 == apes
.size())
414 ape
->offset_
+= apes
[j
]->offset_
+ d
;
418 for (int i
= apes
.size(); i
--;)
420 Accidental_placement_entry
* ape
= apes
[i
];
421 for (int j
= ape
->grobs_
.size(); j
--;)
423 ape
->grobs_
[j
]->translate_axis (ape
->offset_
, X_AXIS
);
428 Interval left_extent
, right_extent
;
429 Accidental_placement_entry
*ape
= apes
[0];
431 for (int i
= ape
->extents_
.size(); i
--;)
432 left_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
435 for (int i
= ape
->extents_
.size(); i
--;)
436 right_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
438 SCM ls
= me
->get_grob_property ("left-padding");
439 if (gh_number_p (rs
))
440 left_extent
[LEFT
] -= gh_scm2double (ls
);
443 Interval
width(left_extent
[LEFT
], right_extent
[RIGHT
]);
445 SCM scm_width
= ly_interval2scm (width
);
446 me
->set_extent (scm_width
, X_AXIS
);
448 for (int i
= apes
.size(); i
--;)
451 return SCM_UNSPECIFIED
;
454 ADD_INTERFACE(Accidental_placement
,
455 "accidental-placement-interface",
456 "Take care of complex accidental collisions.",
457 "left-padding padding right-padding accidental-grobs alignment-done")