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);
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_grob_property("cause");
48 Music
*mcause
=unsmob_music (cause
);
51 programming_error ("Note head has no music cause!");
55 Pitch
*p
= unsmob_pitch (mcause
->get_mus_property ("pitch"));
57 int n
= p
->get_notename ();
59 SCM accs
= me
->get_grob_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_grob_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_grob_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_grob_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
.empty_b())
125 Real p
= gh_scm2double (me
->get_grob_property ("left-padding"));
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 Accidental_placement::position_accidentals (Grob
* me
)
242 return SCM_UNSPECIFIED
;
244 SCM accs
= me
->get_grob_property ("accidental-grobs");
247 TODO: there is a bug in this code. If two accs are on the same
248 Y-position, they share an Ape, and will be pritned in overstrike.
250 Link_array
<Accidental_placement_entry
> apes
;
251 for (SCM s
= accs
; gh_pair_p (s
); s
=gh_cdr (s
))
253 Accidental_placement_entry
*ape
= new Accidental_placement_entry
;
254 ape
->notename_
= gh_scm2int (gh_caar (s
));
256 for (SCM t
= gh_cdar (s
); gh_pair_p (t
); t
=gh_cdr (t
))
257 ape
->grobs_
.push (unsmob_grob (gh_car (t
)));
263 Grob
*common
[] = {me
, 0};
266 First we must extract *all* pointers. We can only determine
267 extents if we're sure that we've found the right common refpoint
269 Link_array
<Grob
> note_cols
, heads
;
270 for (int i
= apes
.size (); i
--;)
272 Accidental_placement_entry
* ape
= apes
[i
];
273 for (int j
= ape
->grobs_
.size(); j
--;)
275 Grob
* a
= ape
->grobs_
[j
];
278 common
[Y_AXIS
] = common
[Y_AXIS
]->common_refpoint (a
, Y_AXIS
);
282 Grob
*head
= a
->get_parent (Y_AXIS
);
284 Grob
* col
= head
->get_parent (X_AXIS
);
285 if (Note_column::has_interface (col
))
286 note_cols
.push (col
);
293 This is a little kludgy: to get all notes, we look if there are
296 for (int i
= note_cols
.size() ; i
--;)
298 Grob
*c
= note_cols
[i
]->get_parent (X_AXIS
);
299 if (Note_collision_interface::has_interface (c
))
301 Link_array
<Grob
> gs
=
302 Pointer_group_interface__extract_grobs (c
, (Grob
*)0, "elements");
304 note_cols
.concat (gs
);
308 for (int i
= note_cols
.size() ; i
--;)
310 heads
.concat (Pointer_group_interface__extract_grobs (note_cols
[i
],
315 heads
.default_sort();
317 common
[Y_AXIS
] = common_refpoint_of_array (heads
, common
[Y_AXIS
], Y_AXIS
);
320 for (int i
= apes
.size (); i
--;)
322 Accidental_placement_entry
* ape
= apes
[i
];
323 ape
->left_skyline_
= empty_skyline (LEFT
);
324 ape
->right_skyline_
= empty_skyline (RIGHT
);
326 for (int j
= apes
[i
]->grobs_
.size(); j
--;)
328 Grob
* a
= apes
[i
]->grobs_
[j
];
330 Array
<Box
> boxes
= Accidental_interface::accurate_boxes (a
, common
);
332 ape
->extents_
.concat (boxes
);
333 for (int j
= boxes
.size(); j
--;)
335 insert_extent_into_skyline (&ape
->left_skyline_
, boxes
[j
], Y_AXIS
, LEFT
);
336 insert_extent_into_skyline (&ape
->right_skyline_
, boxes
[j
], Y_AXIS
, RIGHT
);
343 for (int i
= apes
.size(); i
--;)
347 for (int j
= apes
[i
]->extents_
.size(); j
--;)
349 y
.unite (apes
[i
]->extents_
[j
][Y_AXIS
]);
351 apes
[i
]->vertical_extent_
= y
;
354 all_accidental_vertical_extent
= total
;
355 stagger_apes (&apes
);
357 Accidental_placement_entry
* head_ape
= new Accidental_placement_entry
;
358 common
[X_AXIS
] = common_refpoint_of_array (heads
, common
[X_AXIS
], X_AXIS
);
359 Array
<Skyline_entry
> head_skyline (empty_skyline (LEFT
));
360 Array
<Box
> head_extents
;
361 for (int i
= heads
.size(); i
--;)
363 Box
b(heads
[i
]->extent (common
[X_AXIS
] , X_AXIS
),
364 heads
[i
]->extent (common
[Y_AXIS
], Y_AXIS
));
366 insert_extent_into_skyline (&head_skyline
, b
, Y_AXIS
, LEFT
);
369 head_ape
-> left_skyline_
= head_skyline
;
370 head_ape
->offset_
= 0.0;
372 SCM rs
= me
->get_grob_property ("right-padding");
373 if (gh_number_p (rs
))
374 head_ape
->offset_
-= gh_scm2double (rs
);
378 SCM spad
= me
->get_grob_property ("padding");
379 if (gh_number_p (spad
))
380 padding
= gh_scm2double (spad
);
386 There is a bug in this code: the left_skylines should be
387 accumulated, otherwise the b will collide with bb in
394 apes
.push (head_ape
);
395 for (int i
= apes
.size () -1 ; i
-- > 0;)
397 Accidental_placement_entry
*ape
= apes
[i
];
401 d
= - skyline_meshing_distance (ape
->right_skyline_
,
402 apes
[j
]->left_skyline_
);
405 || j
+ 1 == apes
.size())
415 ape
->offset_
+= apes
[j
]->offset_
+ d
;
419 for (int i
= apes
.size(); i
--;)
421 Accidental_placement_entry
* ape
= apes
[i
];
422 for (int j
= ape
->grobs_
.size(); j
--;)
424 ape
->grobs_
[j
]->translate_axis (ape
->offset_
, X_AXIS
);
429 Interval left_extent
, right_extent
;
430 Accidental_placement_entry
*ape
= apes
[0];
432 for (int i
= ape
->extents_
.size(); i
--;)
433 left_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
436 for (int i
= ape
->extents_
.size(); i
--;)
437 right_extent
.unite (ape
->offset_
+ ape
->extents_
[i
][X_AXIS
]);
439 SCM ls
= me
->get_grob_property ("left-padding");
440 if (gh_number_p (rs
))
441 left_extent
[LEFT
] -= gh_scm2double (ls
);
444 Interval
width(left_extent
[LEFT
], right_extent
[RIGHT
]);
446 SCM scm_width
= ly_interval2scm (width
);
447 me
->set_extent (scm_width
, X_AXIS
);
449 for (int i
= apes
.size(); i
--;)
452 return SCM_UNSPECIFIED
;
455 ADD_INTERFACE(Accidental_placement
,
456 "accidental-placement-interface",
457 "Take care of complex accidental collisions.",
458 "left-padding padding right-padding accidental-grobs alignment-done")