]> git.donarmstrong.com Git - lilypond.git/blob - lily/accidental-placement.cc
offsets <-> scm conversion routines
[lilypond.git] / lily / accidental-placement.cc
1 /*
2   accidental-placement.cc -- implement Accidental_placement
3
4   source file of the GNU LilyPond music typesetter
5
6   (c) 2002--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
7 */
8
9
10 #include "accidental-placement.hh"
11
12 #include "item.hh"
13 #include "rhythmic-head.hh"
14 #include "accidental-interface.hh"
15 #include "music.hh"
16 #include "note-collision.hh"
17 #include "note-column.hh"
18 #include "pointer-group-interface.hh"
19 #include "skyline.hh"
20 #include "stream-event.hh"
21 #include "warn.hh"
22
23
24 void
25 Accidental_placement::add_accidental (Grob *me, Grob *a)
26 {
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");
30
31   Stream_event *mcause = unsmob_stream_event (cause);
32   if (!mcause)
33     {
34       programming_error ("note head has no event cause");
35       return;
36     }
37
38   Pitch *p = unsmob_pitch (mcause->get_property ("pitch"));
39
40   int n = p->get_notename ();
41
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)
46     entry = SCM_EOL;
47   else
48     entry = scm_cdr (entry);
49
50   entry = scm_cons (a->self_scm (), entry);
51
52   accs = scm_assq_set_x (accs, key, entry);
53
54   me->set_object ("accidental-grobs", accs);
55 }
56
57 /*
58   Split into break reminders.
59 */
60 void
61 Accidental_placement::split_accidentals (Grob *accs,
62                                          vector<Grob*> *break_reminder,
63                                          vector<Grob*> *real_acc)
64 {
65   for (SCM acs = accs->get_object ("accidental-grobs"); scm_is_pair (acs);
66        acs = scm_cdr (acs))
67     for (SCM s = scm_cdar (acs); scm_is_pair (s); s = scm_cdr (s))
68       {
69         Grob *a = unsmob_grob (scm_car (s));
70
71         if (unsmob_grob (a->get_object ("tie")))
72           break_reminder->push_back (a);
73         else
74           real_acc->push_back (a);
75       }
76 }
77
78 /*
79   Accidentals are special, because they appear and disappear after
80   ties at will.
81 */
82 Interval
83 Accidental_placement::get_relevant_accidental_extent (Grob *me,
84                                                       Item *item_col,
85                                                       Grob *left_object)
86 {
87   vector<Grob*> br, ra;
88   vector<Grob*> *which = 0;
89
90   Accidental_placement::split_accidentals (me, &br, &ra);
91   concat (br, ra);
92
93   if (dynamic_cast<Item *> (left_object)->break_status_dir () == RIGHT)
94     which = &br;
95   else
96     which = &ra;
97
98   Interval extent;
99   for (vsize i = 0; i < which->size (); i++)
100     extent.unite (which->at (i)->extent (item_col, X_AXIS));
101
102   if (!extent.is_empty ())
103     {
104       Real p = robust_scm2double (me->get_property ("left-padding"), 0.2);
105       extent[LEFT] -= p;
106     }
107
108   return extent;
109 }
110
111 struct Accidental_placement_entry
112 {
113   Skyline left_skyline_;
114   Skyline right_skyline_;
115   Interval vertical_extent_;
116   vector<Box> extents_;
117   vector<Grob*> grobs_;
118   Real offset_;
119   int notename_;
120   Accidental_placement_entry ()
121   {
122     offset_ = 0.0;
123     notename_ = -1;
124   }
125 };
126
127 static Interval all_accidental_vertical_extent;
128 Real ape_priority (Accidental_placement_entry const *a)
129 {
130   return a->vertical_extent_[UP];
131 }
132
133 int ape_compare (Accidental_placement_entry *const &a,
134                  Accidental_placement_entry *const &b)
135 {
136   return sign (ape_priority (a) - ape_priority (b));
137 }
138
139 bool ape_less (Accidental_placement_entry *const &a,
140                Accidental_placement_entry *const &b)
141 {
142   return ape_priority (a) < ape_priority (b);
143 }
144
145 int ape_rcompare (Accidental_placement_entry *const &a,
146                   Accidental_placement_entry *const &b)
147 {
148   return -sign (ape_priority (a) - ape_priority (b));
149 }
150
151 /*
152   TODO: should favor
153
154   b
155   b
156
157   placement
158 */
159 void
160 stagger_apes (vector<Accidental_placement_entry*> *apes)
161 {
162   vector<Accidental_placement_entry*> asc = *apes;
163
164   vector_sort (asc, &ape_less);
165
166   apes->clear ();
167
168   int parity = 1;
169   for (vsize i = 0; i < asc.size ();)
170     {
171       Accidental_placement_entry *a = 0;
172       if (parity)
173         {
174           a = asc.back ();
175           asc.pop_back ();
176         }
177       else
178         a = asc[i++];
179
180       apes->push_back (a);
181       parity = !parity;
182     }
183
184   reverse (*apes);
185 }
186
187 /*
188   This routine computes placements of accidentals. During
189   add_accidental (), accidentals are already grouped by note, so that
190   octaves are placed above each other; they form columns. Then the
191   columns are sorted: the biggest columns go closest to the note.
192   Then the columns are spaced as closely as possible (using skyline
193   spacing).
194
195
196   TODO: more advanced placement. Typically, the accs should be placed
197   to form a C shape, like this
198
199
200   ##
201   b b
202   # #
203   b
204   b b
205
206   The naturals should be left of the C as well; they should
207   be separate accs.
208
209   Note that this placement problem looks NP hard, so we just use a
210   simple strategy, not an optimal choice.
211 */
212
213 /*
214   TODO: there should be more space in the following situation
215
216
217   Natural + downstem
218
219   *
220   *  |_
221   *  | |    X
222   *  |_|   |
223   *    |   |
224   *
225
226 */
227
228 MAKE_SCHEME_CALLBACK(Accidental_placement, calc_positioning_done, 1);
229 SCM
230 Accidental_placement::calc_positioning_done (SCM smob)
231 {
232   Grob *me = unsmob_grob (smob);
233   if (!me->is_live ())
234     return SCM_BOOL_T;
235
236   SCM accs = me->get_object ("accidental-grobs");
237   if (!scm_is_pair (accs))
238     return SCM_BOOL_T;
239
240   /*
241     TODO: there is a bug in this code. If two accs are on the same
242     Y-position, they share an Ape, and will be printed in overstrike.
243   */
244   vector<Accidental_placement_entry*> apes;
245   for (SCM s = accs; scm_is_pair (s); s = scm_cdr (s))
246     {
247       Accidental_placement_entry *ape = new Accidental_placement_entry;
248       ape->notename_ = scm_to_int (scm_caar (s));
249
250       for (SCM t = scm_cdar (s); scm_is_pair (t); t = scm_cdr (t))
251         ape->grobs_.push_back (unsmob_grob (scm_car (t)));
252
253       apes.push_back (ape);
254     }
255
256   Grob *common[] = {me, 0};
257
258   /*
259     First we must extract *all* pointers. We can only determine
260     extents if we're sure that we've found the right common refpoint
261   */
262   vector<Grob*> note_cols, heads;
263   for (vsize i = apes.size (); i--;)
264     {
265       Accidental_placement_entry *ape = apes[i];
266       for (vsize j = ape->grobs_.size (); j--;)
267         {
268           Grob *a = ape->grobs_[j];
269
270           if (common[Y_AXIS])
271             common[Y_AXIS] = common[Y_AXIS]->common_refpoint (a, Y_AXIS);
272           else
273             common[Y_AXIS] = a;
274
275           Grob *head = a->get_parent (Y_AXIS);
276
277           Grob *col = head->get_parent (X_AXIS);
278           if (Note_column::has_interface (col))
279             note_cols.push_back (col);
280           else
281             heads.push_back (head);
282         }
283     }
284
285   /*
286     This is a little kludgy: to get all notes, we look if there are
287     collisions as well.
288   */
289   for (vsize i = note_cols.size (); i--;)
290     {
291       Grob *c = note_cols[i]->get_parent (X_AXIS);
292       if (Note_collision_interface::has_interface (c))
293         {
294           extract_grob_set (c, "elements", gs);
295
296           concat (note_cols, gs);
297         }
298     }
299
300   for (vsize i = note_cols.size (); i--;)
301     concat (heads, extract_grob_array (note_cols[i], "note-heads"));
302
303   vector_sort (heads, less<Grob*> ());
304   uniq (heads);
305   common[Y_AXIS] = common_refpoint_of_array (heads, common[Y_AXIS], Y_AXIS);
306
307   for (vsize i = apes.size (); i--;)
308     {
309       Accidental_placement_entry *ape = apes[i];
310
311       for (vsize j = apes[i]->grobs_.size (); j--;)
312         {
313           Grob *a = apes[i]->grobs_[j];
314           vector<Box> boxes = Accidental_interface::accurate_boxes (a, common);
315
316           ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ());
317         }
318       ape->left_skyline_ = Skyline (ape->extents_, Y_AXIS, LEFT);
319       ape->right_skyline_ = Skyline (ape->extents_, Y_AXIS, RIGHT);
320     }
321
322   Interval total;
323   for (vsize i = apes.size (); i--;)
324     {
325       Interval y;
326
327       for (vsize j = apes[i]->extents_.size (); j--;)
328         y.unite (apes[i]->extents_[j][Y_AXIS]);
329       apes[i]->vertical_extent_ = y;
330       total.unite (y);
331     }
332   all_accidental_vertical_extent = total;
333   stagger_apes (&apes);
334
335   Accidental_placement_entry *head_ape = new Accidental_placement_entry;
336   common[X_AXIS] = common_refpoint_of_array (heads, common[X_AXIS], X_AXIS);
337   
338   vector<Box> head_extents;
339   for (vsize i = heads.size (); i--;)
340     head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS),
341                                  heads[i]->extent (common[Y_AXIS], Y_AXIS)));
342
343   vector<Grob *> stems;
344   for (vsize i = 0; i < heads.size  (); i++)
345     {
346       if (Grob *s = Rhythmic_head::get_stem (heads[i]))
347         stems.push_back (s);
348     }
349   
350   vector_sort (stems, less<Grob*> ());
351   uniq (stems);
352   for (vsize i = 0; i < stems.size (); i ++)
353     {
354       int very_large = INT_MAX;
355       
356       head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS),
357                                    heads[i]->pure_height (common[Y_AXIS], 0, very_large)));
358     }
359
360   head_ape->left_skyline_ = Skyline (head_extents, Y_AXIS, LEFT);
361   head_ape->offset_ = 0.0;
362
363   Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
364
365   Skyline left_skyline = head_ape->left_skyline_;
366   left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0))
367 ;
368   /*
369     Add accs entries right-to-left.
370   */
371   for (vsize i = apes.size (); i-- > 0;)
372     {
373       Real offset = -apes[i]->right_skyline_.distance (left_skyline);
374       if (isinf (offset))
375         offset = (i < apes.size () - 1) ? apes[i + 1]->offset_ : 0.0;
376       else
377         offset -= padding;
378
379       apes[i]->offset_ = offset;
380
381       Skyline new_left_skyline = apes[i]->left_skyline_;
382       new_left_skyline.raise (apes[i]->offset_);
383       new_left_skyline.merge (left_skyline);
384       left_skyline = new_left_skyline;
385     }
386
387   for (vsize i = apes.size (); i--;)
388     {
389       Accidental_placement_entry *ape = apes[i];
390       for (vsize j = ape->grobs_.size (); j--;)
391         ape->grobs_[j]->translate_axis (ape->offset_, X_AXIS);
392     }
393
394   Interval left_extent, right_extent;
395   Accidental_placement_entry *ape = apes[0];
396
397   for (vsize i = ape->extents_.size (); i--;)
398     left_extent.unite (ape->offset_ + ape->extents_[i][X_AXIS]);
399
400   ape = apes.back ();
401   for (vsize i = ape->extents_.size (); i--;)
402     right_extent.unite (ape->offset_ + ape->extents_[i][X_AXIS]);
403
404   left_extent[LEFT] -= robust_scm2double (me->get_property ("left-padding"), 0);
405   Interval width (left_extent[LEFT], right_extent[RIGHT]);
406
407   SCM scm_width = ly_interval2scm (width);
408   me->flush_extent_cache (X_AXIS);
409   me->set_property ("X-extent", scm_width);
410
411   for (vsize i = apes.size (); i--;)
412     delete apes[i];
413
414   return SCM_BOOL_T;
415 }
416
417 ADD_INTERFACE (Accidental_placement,
418                "Resolve accidental collisions.",
419
420                /* properties */
421                "accidental-grobs "
422                "left-padding "
423                "padding "
424                "positioning-done "
425                "right-padding "
426                "script-priority "
427                )