]> git.donarmstrong.com Git - lilypond.git/blob - lily/tie-formatting-problem.cc
restore regression tests for time-signature styles; issue 4176
[lilypond.git] / lily / tie-formatting-problem.cc
1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3
4   Copyright (C) 2005--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
5
6
7   LilyPond is free software: you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation, either version 3 of the License, or
10   (at your option) any later version.
11
12   LilyPond is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include <cstdio>
22 #include "tie-formatting-problem.hh"
23
24 #include "axis-group-interface.hh"
25 #include "paper-column.hh"
26 #include "bezier.hh"
27 #include "directional-element-interface.hh"
28 #include "libc-extension.hh"
29 #include "misc.hh"
30 #include "note-head.hh"
31 #include "rhythmic-head.hh"
32 #include "spanner.hh"
33 #include "staff-symbol-referencer.hh"
34 #include "stem.hh"
35 #include "tie-configuration.hh"
36 #include "tie.hh"
37 #include "warn.hh"
38 #include "pointer-group-interface.hh"
39 #include "output-def.hh"
40
41 void
42 Tie_formatting_problem::print_ties_configuration (Ties_configuration const *ties)
43 {
44   for (vsize i = 0; i < ties->size (); i++)
45     {
46       char const *man_pos = (specifications_[i].has_manual_position_) ? "(M)" : "";
47       char const *man_dir = (specifications_[i].has_manual_dir_) ? "(M)" : "";
48       char const *dir = (ties->at (i).dir_ == UP) ? "up" : "dn";
49
50       printf ("(P%d%s, %s%s) ", ties->at (i).position_, man_pos, dir, man_dir);
51     }
52   printf ("\n");
53 }
54
55 Interval
56 Tie_formatting_problem::get_attachment (Real y, Drul_array<int> columns) const
57 {
58   Interval attachments (0, 0);
59
60   for (LEFT_and_RIGHT (d))
61     {
62       Tuple2<int> key (columns[d], int (d));
63       Chord_outline_map::const_iterator i (chord_outlines_.find (key));
64       if (i == chord_outlines_.end ())
65         programming_error ("Cannot find chord outline");
66       else
67         attachments[d] = i->second.height (y);
68     }
69
70   return attachments;
71 }
72
73 Tie_formatting_problem::Tie_formatting_problem ()
74 {
75   x_refpoint_ = 0;
76   y_refpoint_ = 0;
77   use_horizontal_spacing_ = true;
78 }
79
80 Tie_formatting_problem::~Tie_formatting_problem ()
81 {
82   for (Tie_configuration_map::const_iterator i (possibilities_.begin ());
83        i != possibilities_.end (); i++)
84     delete (*i).second;
85 }
86
87 void
88 Tie_formatting_problem::set_column_chord_outline (vector<Item *> bounds,
89                                                   Direction dir,
90                                                   int column_rank)
91 {
92   Real staff_space = Staff_symbol_referencer::staff_space (bounds[0]);
93
94   vector<Box> boxes;
95   vector<Box> head_boxes;
96
97   Grob *stem = 0;
98   for (vsize i = 0; i < bounds.size (); i++)
99     {
100       Grob *head = bounds[i];
101       if (!Note_head::has_interface (head))
102         continue;
103
104       if (!stem)
105         stem = Grob::unsmob (head->get_object ("stem"));
106
107       Real p = Staff_symbol_referencer::get_position (head);
108       Interval y ((p - 1) * 0.5 * staff_space,
109                   (p + 1) * 0.5 * staff_space);
110
111       Interval x = head->extent (x_refpoint_, X_AXIS);
112       head_boxes.push_back (Box (x, y));
113       boxes.push_back (Box (x, y));
114
115       Grob *dots = Rhythmic_head::get_dots (head);
116       if (dir == LEFT && dots)
117         {
118           Interval x = dots->extent (x_refpoint_, X_AXIS);
119           int p = int (Staff_symbol_referencer::get_position (dots));
120
121           /*
122             TODO: shouldn't this use column-rank dependent key?
123           */
124           dot_positions_.insert (p);
125           dot_x_.unite (x);
126
127           Interval y (dots->extent (dots, Y_AXIS));
128           y.translate (p * staff_space * 0.5);
129
130           boxes.push_back (Box (x, y));
131         }
132     }
133
134   Tuple2<int> key (column_rank, int (dir));
135
136   if (stem)
137     {
138       if (Stem::is_normal_stem (stem))
139         {
140           Interval x;
141           x.add_point (stem->relative_coordinate (x_refpoint_, X_AXIS));
142           x.widen (staff_space / 20); // ugh.
143           Interval y;
144
145           Real stem_end_position = 0.0;
146           if (Stem::is_cross_staff (stem))
147             stem_end_position = get_grob_direction (stem) * infinity_f;
148           else
149             {
150               if (use_horizontal_spacing_ || !Stem::get_beam (stem))
151                 stem_end_position = stem->extent (stem, Y_AXIS)[get_grob_direction (stem)];
152               else
153                 // May want to change this to the stem's pure height...
154                 stem_end_position = Stem::head_positions (stem)[get_grob_direction (stem)]
155                                     * staff_space * .5;
156             }
157
158           y.add_point (stem_end_position);
159
160           Direction stemdir = get_grob_direction (stem);
161           y.add_point (Stem::head_positions (stem)[-stemdir]
162                        * staff_space * .5);
163
164           /*
165             add extents of stem.
166           */
167           boxes.push_back (Box (x, y));
168
169           stem_extents_[key].unite (Box (x, y));
170
171           if (dir == LEFT)
172             {
173               Grob *flag = Stem::flag (stem);
174               if (flag)
175                 {
176                   Grob *commony = stem->common_refpoint (flag, Y_AXIS);
177                   boxes.push_back (Box (flag->extent (x_refpoint_, X_AXIS),
178                                         flag->extent (commony, Y_AXIS)));
179                 }
180             }
181         }
182       else
183         {
184           Grob *head = Stem::support_head (stem);
185
186           /*
187             In case of invisible stem, don't pass x-center of heads.
188           */
189           Real x_center = head->extent (x_refpoint_, X_AXIS).center ();
190           Interval x_ext;
191           x_ext[-dir] = x_center;
192           x_ext[dir] = infinity_f * dir;
193           Interval y_ext;
194           for (vsize j = 0; j < head_boxes.size (); j++)
195             y_ext.unite (head_boxes[j][Y_AXIS]);
196
197           boxes.push_back (Box (x_ext, y_ext));
198         }
199
200       extract_grob_set (stem, "note-heads", heads);
201       for (vsize i = 0; i < heads.size (); i++)
202         {
203           if (find (bounds.begin (), bounds.end (), dynamic_cast<Item *> (heads[i])) == bounds.end ())
204             {
205               /*
206                 other untied notes in the same chord.
207               */
208
209               Interval y = Staff_symbol_referencer::extent_in_staff (heads[i]);
210               Interval x = heads[i]->extent (x_refpoint_, X_AXIS);
211               boxes.push_back (Box (x, y));
212             }
213
214           Grob *acc = Grob::unsmob (heads[i]->get_object ("accidental-grob"));
215           if (acc)
216             acc->get_property ("after-line-breaking"); /* trigger tie-related suicide */
217
218           if (acc && acc->is_live () && dir == RIGHT)
219             {
220               boxes.push_back (Box (acc->extent (x_refpoint_, X_AXIS),
221                                     Staff_symbol_referencer::extent_in_staff (acc)));
222             }
223
224           head_positions_[column_rank].add_point (int (Staff_symbol_referencer::get_position (heads[i])));
225         }
226
227     }
228
229   for (DOWN_and_UP (updowndir))
230     {
231       Interval x;
232       Interval y;
233       if (head_boxes.size ())
234         {
235           Box b = boundary (head_boxes, updowndir, 0);
236           x = b[X_AXIS];
237           x[-dir] = b[X_AXIS].linear_combination (-dir / 2);
238           y[-updowndir] = b[Y_AXIS][updowndir];
239           y[updowndir] = updowndir * infinity_f;
240         }
241
242       if (!x.is_empty ())
243         boxes.push_back (Box (x, y));
244     }
245
246   chord_outlines_[key] = Skyline (boxes, Y_AXIS, -dir).padded (details_.skyline_padding_);
247   if (bounds[0]->break_status_dir ())
248     {
249       Interval iv (Axis_group_interface::staff_extent (bounds[0], x_refpoint_, X_AXIS, y_refpoint_, Y_AXIS));
250       if (iv.is_empty ())
251         iv.add_point (bounds[0]->relative_coordinate (x_refpoint_, X_AXIS));
252
253       chord_outlines_[key].set_minimum_height (iv[-dir]);
254     }
255   else
256     {
257       Interval x;
258       for (vsize j = 0; j < head_boxes.size (); j++)
259         {
260           x.unite (head_boxes[j][X_AXIS]);
261         }
262
263       chord_outlines_[key].set_minimum_height (x[dir]);
264     }
265
266   head_extents_[key].set_empty ();
267   for (vsize i = 0; i < head_boxes.size (); i++)
268     {
269       head_extents_[key].unite (head_boxes[i]);
270     }
271 }
272
273 void
274 Tie_formatting_problem::set_chord_outline (vector<Item *> bounds,
275                                            Direction dir)
276
277 {
278   vector<int> ranks;
279   for (vsize i = 0; i < bounds.size (); i++)
280     ranks.push_back (bounds[i]->get_column ()->get_rank ());
281
282   vector_sort (ranks, less<int> ());
283   uniq (ranks);
284
285   for (vsize i = 0; i < ranks.size (); i++)
286     {
287       vector<Item *> col_items;
288       for (vsize j = 0; j < bounds.size (); j++)
289         {
290           if (bounds[j]->get_column ()->get_rank () == ranks[i])
291             col_items.push_back (bounds[j]);
292         }
293
294       set_column_chord_outline (col_items, dir, ranks[i]);
295     }
296 }
297
298 void
299 Tie_formatting_problem::from_tie (Grob *tie)
300 {
301   vector<Grob *> ties;
302   ties.push_back (tie);
303   from_ties (ties);
304
305   details_.from_grob (tie);
306 }
307
308 Grob *
309 Tie_formatting_problem::common_x_refpoint () const
310 {
311   return x_refpoint_;
312 }
313
314 void
315 Tie_formatting_problem::from_ties (vector<Grob *> const &ties)
316 {
317   if (ties.empty ())
318     return;
319
320   x_refpoint_ = ties[0];
321   y_refpoint_ = ties[0];
322   for (vsize i = 0; i < ties.size (); i++)
323     {
324       Spanner *tie = dynamic_cast<Spanner *> (ties[i]);
325       Item *l = tie->get_bound (LEFT);
326       Item *r = tie->get_bound (RIGHT);
327
328       x_refpoint_ = l->common_refpoint (x_refpoint_, X_AXIS);
329       x_refpoint_ = r->common_refpoint (x_refpoint_, X_AXIS);
330
331       if (!l->break_status_dir ())
332         y_refpoint_ = l->common_refpoint (y_refpoint_, Y_AXIS);
333       if (!r->break_status_dir ())
334         y_refpoint_ = r->common_refpoint (y_refpoint_, Y_AXIS);
335     }
336
337   details_.from_grob (ties[0]);
338
339   for (LEFT_and_RIGHT (d))
340     {
341       vector<Item *> bounds;
342
343       for (vsize i = 0; i < ties.size (); i++)
344         {
345           Item *it = dynamic_cast<Spanner *> (ties[i])->get_bound (d);
346           if (it->break_status_dir ())
347             it = it->get_column ();
348
349           bounds.push_back (it);
350         }
351
352       set_chord_outline (bounds, d);
353     }
354
355   for (vsize i = 0; i < ties.size (); i++)
356     {
357       Tie_specification spec;
358       spec.from_grob (ties[i]);
359
360       for (LEFT_and_RIGHT (d))
361         {
362           spec.note_head_drul_[d] = Tie::head (ties[i], d);
363           spec.column_ranks_[d] = Tie::get_column_rank (ties[i], d);
364         }
365       specifications_.push_back (spec);
366     }
367 }
368
369 void
370 Tie_formatting_problem::from_semi_ties (vector<Grob *> const &semi_ties, Direction head_dir)
371 {
372   if (semi_ties.empty ())
373     return;
374
375   use_horizontal_spacing_ = false;
376   details_.from_grob (semi_ties[0]);
377   vector<Item *> heads;
378
379   int column_rank = -1;
380   for (vsize i = 0; i < semi_ties.size (); i++)
381     {
382       Tie_specification spec;
383       Item *head = Item::unsmob (semi_ties[i]->get_object ("note-head"));
384
385       if (!head)
386         programming_error ("LV tie without head?!");
387
388       if (head)
389         {
390           spec.position_ = int (Staff_symbol_referencer::get_position (head));
391         }
392
393       spec.from_grob (semi_ties[i]);
394
395       spec.note_head_drul_[head_dir] = head;
396       column_rank = Tie::get_column_rank (semi_ties[i], head_dir);
397       spec.column_ranks_ = Drul_array<int> (column_rank, column_rank);
398       heads.push_back (head);
399       specifications_.push_back (spec);
400     }
401
402   x_refpoint_ = semi_ties[0];
403   y_refpoint_ = semi_ties[0];
404
405   for (vsize i = 0; i < semi_ties.size (); i++)
406     {
407       x_refpoint_ = semi_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
408       y_refpoint_ = semi_ties[i]->common_refpoint (y_refpoint_, Y_AXIS);
409     }
410   for (vsize i = 0; i < heads.size (); i++)
411     {
412       x_refpoint_ = heads[i]->common_refpoint (x_refpoint_, X_AXIS);
413       y_refpoint_ = heads[i]->common_refpoint (y_refpoint_, Y_AXIS);
414     }
415
416   set_chord_outline (heads, head_dir);
417
418   Tuple2<int> head_key (column_rank, head_dir);
419   Tuple2<int> open_key (column_rank, -head_dir);
420   Real extremal = chord_outlines_[head_key].max_height ();
421
422   chord_outlines_[open_key] = Skyline (head_dir);
423   chord_outlines_[open_key].set_minimum_height (extremal - head_dir * 1.5);
424 }
425
426 Tie_specification
427 Tie_formatting_problem::get_tie_specification (int i) const
428 {
429   return specifications_[i];
430 }
431
432 /*
433   Return configuration, create it if necessary.
434 */
435 Tie_configuration *
436 Tie_formatting_problem::get_configuration (int pos, Direction dir, Drul_array<int> columns,
437                                            bool tune_dy) const
438 {
439   int key_components[]
440   =
441   {
442     pos, dir, columns[LEFT], columns[RIGHT]
443   };
444   Tuple<int, 4> key (key_components);
445
446   Tie_configuration_map::const_iterator f = possibilities_.find (key);
447   if (f != possibilities_.end ())
448     {
449       return (*f).second;
450     }
451
452   Tie_configuration *conf = generate_configuration (pos, dir, columns, tune_dy);
453   ((Tie_formatting_problem *) this)->possibilities_[key] = conf;
454   return conf;
455 }
456
457 Tie_configuration *
458 Tie_formatting_problem::generate_configuration (int pos, Direction dir,
459                                                 Drul_array<int> columns, bool y_tune) const
460 {
461   Tie_configuration *conf = new Tie_configuration;
462   conf->position_ = pos;
463   conf->dir_ = dir;
464
465   conf->column_ranks_ = columns;
466
467   Real y = conf->position_ * 0.5 * details_.staff_space_;
468
469   if (dot_positions_.find (pos) != dot_positions_.end ())
470     {
471       conf->delta_y_ += dir * 0.25 * details_.staff_space_;
472       y_tune = false;
473     }
474
475   if (y_tune
476       && max (fabs (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y),
477               fabs (get_head_extent (columns[RIGHT], RIGHT, Y_AXIS)[dir] - y)) < 0.25
478       && !Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
479     {
480       conf->delta_y_
481         = (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y)
482           + dir * details_.outer_tie_vertical_gap_;
483     }
484
485   if (y_tune)
486     {
487       conf->attachment_x_ = get_attachment (y + conf->delta_y_, conf->column_ranks_);
488       Real h = conf->height (details_);
489
490       /*
491         TODO:
492
493         - should make sliding criterion, should flatten ties if
494
495         - they're just the wrong (ie. touching line at top & bottom)
496         size.
497
498        */
499       Interval staff_span
500         = Staff_symbol_referencer::staff_span (details_.staff_symbol_referencer_);
501       staff_span.widen (-1);
502       bool const within_staff = staff_span.contains (pos);
503       if (head_positions_slice (columns[LEFT]).contains (pos)
504           || head_positions_slice (columns[RIGHT]).contains (pos)
505           || within_staff)
506         {
507           if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
508             {
509               if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
510                 {
511                   conf->delta_y_ += dir *
512                                     details_.tip_staff_line_clearance_ * 0.5 * details_.staff_space_;
513                 }
514               else if (within_staff)
515                 {
516                   conf->center_tie_vertically (details_);
517                 }
518             }
519           else
520             {
521               Real top_y = y + conf->delta_y_ + conf->dir_ * h;
522               Real top_pos = top_y / (0.5 * details_.staff_space_);
523               int round_pos = int (my_round (top_pos));
524
525               /* TODO: should use other variable? */
526               Real clearance = details_.center_staff_line_clearance_;
527               if (fabs (top_pos - round_pos) < clearance
528                   && Staff_symbol_referencer::on_staff_line (details_.staff_symbol_referencer_,
529                                                              round_pos))
530                 {
531                   Real new_y = (round_pos + clearance * conf->dir_) * 0.5 * details_.staff_space_;
532                   conf->delta_y_ = (new_y - top_y);
533                 }
534             }
535         }
536     }
537   conf->attachment_x_ = get_attachment (y + conf->delta_y_, conf->column_ranks_);
538   if (conf->height (details_) < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
539     {
540       /*
541         This is less sensible for long ties, since those are more
542         horizontal.
543       */
544       Interval close_by = get_attachment (y
545                                           + conf->delta_y_
546                                           + (dir * details_.intra_space_threshold_ * 0.25
547                                              * details_.staff_space_),
548                                           conf->column_ranks_);
549
550       conf->attachment_x_.intersect (close_by);
551     }
552
553   conf->attachment_x_.widen ( - details_.x_gap_);
554
555   if (conf->column_span_length ())
556     {
557       /*
558         avoid the stems that we attach to as well. We don't do this
559         for semities (span length = 0)
560
561         It would be better to check D against HEAD-DIRECTION if
562         applicable.
563       */
564       for (LEFT_and_RIGHT (d))
565         {
566           Real y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
567           if (get_stem_extent (conf->column_ranks_[d], d, X_AXIS).is_empty ()
568               || !get_stem_extent (conf->column_ranks_[d], d, Y_AXIS).contains (y))
569             continue;
570
571           conf->attachment_x_[d]
572             = d * min (d * conf->attachment_x_[d],
573                        d * (get_stem_extent (conf->column_ranks_[d], d, X_AXIS)[-d] - d * details_.stem_gap_));
574         }
575     }
576   return conf;
577 }
578
579 Interval
580 Tie_formatting_problem::get_head_extent (int col, Direction d, Axis a) const
581 {
582   Column_extent_map::const_iterator i = head_extents_.find (Tuple2<int> (col, int (d)));
583   if (i != head_extents_.end ())
584     return (*i).second[a];
585   else
586     return Interval ();
587 }
588
589 Interval
590 Tie_formatting_problem::get_stem_extent (int col, Direction d, Axis a) const
591 {
592   Column_extent_map::const_iterator i = stem_extents_.find (Tuple2<int> (col, int (d)));
593   if (i != stem_extents_.end ())
594     return (*i).second[a];
595   else
596     return Interval ();
597 }
598
599 /**
600    TIE_IDX and TIES_CONF are optional.
601  */
602 Real
603 Tie_formatting_problem::score_aptitude (Tie_configuration *conf,
604                                         Tie_specification const &spec,
605                                         Ties_configuration *ties_conf, int tie_idx) const
606 {
607   Real penalty = 0.0;
608   Real curve_y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
609   Real tie_y = spec.position_ * details_.staff_space_ * 0.5;
610   if (sign (curve_y - tie_y) != conf->dir_)
611     {
612       Real p = details_.wrong_direction_offset_penalty_;
613       if (ties_conf)
614         ties_conf->add_tie_score (p, tie_idx, "wrong dir");
615       else
616         penalty += p;
617     }
618
619   {
620     Real relevant_dist = max (fabs (curve_y - tie_y) - 0.5, 0.0);
621     Real p = details_.vertical_distance_penalty_factor_ * convex_amplifier (1.0, 0.9, relevant_dist);
622     if (ties_conf)
623       ties_conf->add_tie_score (p, tie_idx, "vdist");
624     else
625       penalty += p;
626   }
627
628   for (LEFT_and_RIGHT (d))
629     {
630       if (!spec.note_head_drul_[d])
631         continue;
632
633       Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS);
634       Real dist = head_x.distance (conf->attachment_x_[d]);
635
636       /*
637         TODO: flatten with log or sqrt.
638        */
639       Real p = details_.horizontal_distance_penalty_factor_
640                * convex_amplifier (1.25, 1.0, dist);
641       if (ties_conf)
642         ties_conf->add_tie_score (p, tie_idx,
643                                   (d == LEFT) ? "lhdist" : "rhdist");
644       else
645         penalty += p;
646
647     }
648
649   if (ties_conf
650       && ties_conf->size () == 1)
651     {
652       Drul_array<Grob *> stems (0, 0);
653       for (LEFT_and_RIGHT (d))
654         {
655           if (!spec.note_head_drul_[d])
656             continue;
657
658           Grob *stem = Grob::unsmob (spec.note_head_drul_[d]->get_object ("stem"));
659           if (stem
660               && Stem::is_normal_stem (stem))
661             stems[d] = stem;
662         }
663
664       bool tie_stem_dir_ok = true;
665       bool tie_position_dir_ok = true;
666       if (stems[LEFT] && !stems[RIGHT])
667         tie_stem_dir_ok = conf->dir_ != get_grob_direction (stems[LEFT]);
668       else if (!stems[LEFT] && stems[RIGHT])
669         tie_stem_dir_ok = conf->dir_ != get_grob_direction (stems[RIGHT]);
670       else if (stems[LEFT] && stems[RIGHT]
671                && get_grob_direction (stems[LEFT]) == get_grob_direction (stems[RIGHT]))
672         tie_stem_dir_ok = conf->dir_ != get_grob_direction (stems[LEFT]);
673       else if (spec.position_)
674         tie_position_dir_ok = conf->dir_ == sign (spec.position_);
675
676       if (!tie_stem_dir_ok)
677         ties_conf->add_score (details_.same_dir_as_stem_penalty_, "tie/stem dir");
678       if (!tie_position_dir_ok)
679         ties_conf->add_score (details_.same_dir_as_stem_penalty_, "tie/pos dir");
680     }
681
682   return penalty;
683 }
684
685 Slice
686 Tie_formatting_problem::head_positions_slice (int rank) const
687 {
688   Position_extent_map::const_iterator i (head_positions_.find (rank));
689   if (i != head_positions_.end ())
690     {
691       return (*i).second;
692     }
693   Slice empty;
694   return empty;
695 }
696
697 /*
698   Score a configuration, ie. how well these ties looks without regard
699   to the note heads that they should connect to.
700  */
701 void
702 Tie_formatting_problem::score_configuration (Tie_configuration *conf) const
703 {
704   if (conf->scored_)
705     {
706       return;
707     }
708
709   Real length = conf->attachment_x_.length ();
710
711   Real length_penalty
712     = peak_around (0.33 * details_.min_length_, details_.min_length_, length);
713   conf->add_score (details_.min_length_penalty_factor_
714                    * length_penalty, "minlength");
715
716   Real tip_pos = conf->position_ + conf->delta_y_ / 0.5 * details_.staff_space_;
717   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
718   Real height = conf->height (details_);
719
720   Real top_y = tip_y + conf->dir_ * height;
721   Real top_pos = 2 * top_y / details_.staff_space_;
722   Real round_top_pos = rint (top_pos);
723   Interval staff_span
724     = Staff_symbol_referencer::staff_span (details_.staff_symbol_referencer_);
725   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
726                                         int (round_top_pos))
727       && staff_span[UP] * 0.5 > top_y)
728     {
729       conf->add_score (details_.staff_line_collision_penalty_
730                        * peak_around (0.1 * details_.center_staff_line_clearance_,
731                                       details_.center_staff_line_clearance_,
732                                       fabs (top_pos - round_top_pos)),
733                        "line center");
734     }
735
736   int rounded_tip_pos = int (rint (tip_pos));
737   staff_span.widen (-1);
738   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, rounded_tip_pos)
739       && (head_positions_slice (conf->column_ranks_[LEFT]).contains (rounded_tip_pos)
740           || head_positions_slice (conf->column_ranks_[RIGHT]).contains (rounded_tip_pos)
741           || staff_span.contains (rounded_tip_pos))
742      )
743     {
744       conf->add_score (details_.staff_line_collision_penalty_
745                        * peak_around (0.1 * details_.tip_staff_line_clearance_,
746                                       details_.tip_staff_line_clearance_,
747                                       fabs (tip_pos - rint (tip_pos))),
748                        "tipline");
749     }
750
751   if (!dot_x_.is_empty ())
752     {
753       /* use left edge? */
754       Real x = dot_x_.center ();
755
756       Bezier b = conf->get_transformed_bezier (details_);
757       if (b.control_point_extent (X_AXIS).contains (x))
758         {
759           Real y = b.get_other_coordinate (X_AXIS, x);
760
761           for (set<int>::const_iterator i (dot_positions_.begin ());
762                i != dot_positions_.end (); i++)
763             {
764               int dot_pos = (*i);
765               conf->add_score (details_.dot_collision_penalty_
766                                * peak_around (.1 * details_.dot_collision_clearance_,
767                                               details_.dot_collision_clearance_,
768                                               fabs (dot_pos * details_.staff_space_ * 0.5 - y)),
769                                "dot collision");
770             }
771         }
772     }
773
774   conf->scored_ = true;
775 }
776
777 void
778 Tie_formatting_problem::score_ties_aptitude (Ties_configuration *ties) const
779 {
780   if (ties->size () != specifications_.size ())
781     {
782       programming_error ("Huh? Mismatch between sizes.");
783       return;
784     }
785
786   for (vsize i = 0; i < ties->size (); i++)
787     score_aptitude (&ties->at (i), specifications_[i],
788                     ties, i);
789 }
790
791 void
792 Tie_formatting_problem::score_ties (Ties_configuration *ties) const
793 {
794   if (ties->scored_)
795     return;
796
797   score_ties_configuration (ties);
798   score_ties_aptitude (ties);
799   ties->scored_ = true;
800 }
801
802 void
803 Tie_formatting_problem::score_ties_configuration (Ties_configuration *ties) const
804 {
805   for (vsize i = 0; i < ties->size (); i++)
806     {
807       score_configuration (&ties->at (i));
808       ties->add_tie_score (ties->at (i).score (), i, "conf");
809     }
810
811   Real last_edge = 0.0;
812   Real last_center = 0.0;
813   for (vsize i = 0; i < ties->size (); i++)
814     {
815       Bezier b (ties->at (i).get_transformed_bezier (details_));
816
817       Real center = b.curve_point (0.5)[Y_AXIS];
818       Real edge = b.curve_point (0.0)[Y_AXIS];
819
820       if (i)
821         {
822           if (edge <= last_edge)
823             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton edge");
824           if (center <= last_center)
825             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton cent");
826
827           ties->add_score (details_.tie_tie_collision_penalty_ *
828                            peak_around (0.1 * details_.tie_tie_collision_distance_,
829                                         details_.tie_tie_collision_distance_,
830                                         fabs (center - last_center)),
831                            "tietie center");
832           ties->add_score (details_.tie_tie_collision_penalty_ *
833                            peak_around (0.1 * details_.tie_tie_collision_distance_,
834                                         details_.tie_tie_collision_distance_,
835                                         fabs (edge - last_edge)), "tietie edge");
836         }
837
838       last_edge = edge;
839       last_center = center;
840     }
841
842   if (ties->size () > 1)
843     {
844       ties->add_score (details_.outer_tie_length_symmetry_penalty_factor_
845                        * fabs (ties->at (0).attachment_x_.length () - ties->back ().attachment_x_.length ()),
846                        "length symm");
847
848       ties->add_score (details_.outer_tie_vertical_distance_symmetry_penalty_factor_
849                        * fabs (fabs (specifications_[0].position_ * 0.5 * details_.staff_space_
850                                      - (ties->at (0).position_ * 0.5 * details_.staff_space_
851                                         + ties->at (0).delta_y_))
852                                -
853                                fabs (specifications_.back ().position_ * 0.5 * details_.staff_space_
854                                      - (ties->back ().position_ * 0.5 * details_.staff_space_
855                                         + ties->back ().delta_y_))),
856                        "pos symmetry");
857     }
858 }
859
860 /*
861   Generate with correct X-attachments and beziers, copying delta_y_
862   from TIES_CONFIG if necessary.
863 */
864 Ties_configuration
865 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
866 {
867   Ties_configuration copy;
868   for (vsize i = 0; i < ties_config.size (); i++)
869     {
870       Tie_configuration *ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_,
871                                                   ties_config[i].column_ranks_,
872                                                   !specifications_[i].has_manual_delta_y_);
873       if (specifications_[i].has_manual_delta_y_)
874         {
875           ptr->delta_y_
876             = (specifications_[i].manual_position_ - ties_config[i].position_)
877               * 0.5 * details_.staff_space_;
878         }
879       copy.push_back (*ptr);
880     }
881
882   return copy;
883 }
884
885 Ties_configuration
886 Tie_formatting_problem::generate_base_chord_configuration ()
887 {
888   Ties_configuration ties_config;
889   for (vsize i = 0; i < specifications_.size (); i++)
890     {
891       Tie_configuration conf;
892       if (specifications_[i].has_manual_dir_)
893         conf.dir_ = specifications_[i].manual_dir_;
894       if (specifications_[i].has_manual_position_)
895         {
896           conf.position_ = (int) my_round (specifications_[i].manual_position_);
897           if (specifications_[i].has_manual_delta_y_)
898             conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
899                             * 0.5 * details_.staff_space_;
900         }
901       else
902         {
903           conf.position_ = specifications_[i].position_;
904         }
905
906       conf.column_ranks_ = specifications_[i].column_ranks_;
907       ties_config.push_back (conf);
908     }
909
910   set_ties_config_standard_directions (&ties_config);
911   for (vsize i = 0; i < ties_config.size (); i++)
912     if (!specifications_[i].manual_position_)
913       ties_config[i].position_ += ties_config[i].dir_;
914
915   ties_config = generate_ties_configuration (ties_config);
916
917   return ties_config;
918 }
919
920 Ties_configuration
921 Tie_formatting_problem::find_best_variation (Ties_configuration const &base,
922                                              vector<Tie_configuration_variation> const &vars)
923 {
924   Ties_configuration best = base;
925
926   /*
927     This simply is 1-opt: we have K substitions, and we try applying
928     exactly every one for each.
929   */
930   for (vsize i = 0; i < vars.size (); i++)
931     {
932       Ties_configuration variant (base);
933       for (vsize j = 0; j < vars[i].index_suggestion_pairs_.size (); j++)
934         variant[vars[i].index_suggestion_pairs_[j].first] = *vars[i].index_suggestion_pairs_[j].second;
935
936       variant.reset_score ();
937       score_ties (&variant);
938
939       if (variant.score () < best.score ())
940         {
941           best = variant;
942         }
943     }
944
945   return best;
946 }
947
948 Ties_configuration
949 Tie_formatting_problem::generate_optimal_configuration ()
950 {
951   Ties_configuration base = generate_base_chord_configuration ();
952   score_ties (&base);
953
954   vector<Tie_configuration_variation> vars;
955   if (specifications_.size () > 1)
956     vars = generate_collision_variations (base);
957   else
958     vars = generate_single_tie_variations (base);
959
960   Ties_configuration best = find_best_variation (base, vars);
961
962   if (specifications_.size () > 1)
963     {
964       vars = generate_extremal_tie_variations (best);
965       best = find_best_variation (best, vars);
966     }
967   return best;
968 }
969
970 void
971 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
972 {
973   if (tie_configs->empty ())
974     return;
975
976   if (!tie_configs->at (0).dir_)
977     {
978       if (tie_configs->size () == 1)
979         tie_configs->at (0).dir_ = Direction (sign (tie_configs->at (0).position_));
980
981       if (!tie_configs->at (0).dir_)
982         tie_configs->at (0).dir_
983           = (tie_configs->size () > 1) ? DOWN : details_.neutral_direction_;
984     }
985
986   if (!tie_configs->back ().dir_)
987     tie_configs->back ().dir_ = UP;
988
989   /*
990     Seconds
991    */
992   for (vsize i = 1; i < tie_configs->size (); i++)
993     {
994       Real diff = (tie_configs->at (i).position_
995                    - tie_configs->at (i - 1).position_);
996
997       Real span_diff
998         = specifications_[i].column_span () - specifications_[i - 1].column_span ();
999       if (span_diff && fabs (diff) <= 2)
1000         {
1001           if (span_diff > 0)
1002             tie_configs->at (i).dir_ = UP;
1003           else if (span_diff < 0)
1004             tie_configs->at (i - 1).dir_ = DOWN;
1005         }
1006       else if (fabs (diff) <= 1)
1007         {
1008           if (!tie_configs->at (i - 1).dir_)
1009             tie_configs->at (i - 1).dir_ = DOWN;
1010           if (!tie_configs->at (i).dir_)
1011             tie_configs->at (i).dir_ = UP;
1012         }
1013     }
1014
1015   for (vsize i = 1; i + 1 < tie_configs->size (); i++)
1016     {
1017       Tie_configuration &conf = tie_configs->at (i);
1018       if (conf.dir_)
1019         continue;
1020
1021       Direction position_dir
1022         = Direction (sign (conf.position_));
1023       if (!position_dir)
1024         position_dir = DOWN;
1025
1026       conf.dir_ = position_dir;
1027     }
1028 }
1029
1030 vector<Tie_configuration_variation>
1031 Tie_formatting_problem::generate_extremal_tie_variations (Ties_configuration const &ties) const
1032 {
1033   vector<Tie_configuration_variation> vars;
1034   for (int i = 1; i <= details_.multi_tie_region_size_; i++)
1035     {
1036       Drul_array<Tie_configuration *> configs (0, 0);
1037       for (DOWN_and_UP (d))
1038         {
1039           const Tie_configuration &config = boundary (ties, d, 0);
1040           if (config.dir_ == d
1041               && !boundary (specifications_, d, 0).has_manual_position_)
1042             {
1043               Tie_configuration_variation var;
1044               configs[d] = get_configuration (config.position_ + d * i, d,
1045                                               config.column_ranks_,
1046                                               true);
1047               var.add_suggestion ((d == DOWN) ? 0 : ties.size () - 1,
1048                                   configs[d]);
1049               vars.push_back (var);
1050             }
1051         }
1052       if (configs[LEFT] && configs[RIGHT])
1053         {
1054           Tie_configuration_variation var;
1055           var.add_suggestion (0, configs[DOWN]);
1056           var.add_suggestion (ties.size () - 1, configs[UP]);
1057           vars.push_back (var);
1058         }
1059     }
1060
1061   return vars;
1062 }
1063
1064 vector<Tie_configuration_variation>
1065 Tie_formatting_problem::generate_single_tie_variations (Ties_configuration const &ties) const
1066 {
1067   vector<Tie_configuration_variation> vars;
1068
1069   int sz = details_.single_tie_region_size_;
1070   if (specifications_[0].has_manual_position_)
1071     sz = 1;
1072   for (int i = 0; i < sz; i++)
1073     {
1074       for (LEFT_and_RIGHT (d))
1075         {
1076           if (i == 0
1077               && ties[0].dir_ == d)
1078             continue;
1079
1080           int p = ties[0].position_ + i * d;
1081
1082           if (!specifications_[0].has_manual_dir_
1083               || d == specifications_[0].manual_dir_)
1084             {
1085               Tie_configuration_variation var;
1086               var.add_suggestion (0,
1087                                   get_configuration (p,
1088                                                      d, specifications_[0].column_ranks_,
1089                                                      !specifications_[0].has_manual_delta_y_));
1090               vars.push_back (var);
1091             }
1092         }
1093     }
1094   return vars;
1095 }
1096
1097 vector<Tie_configuration_variation>
1098 Tie_formatting_problem::generate_collision_variations (Ties_configuration const &ties) const
1099 {
1100   Real center_distance_tolerance = 0.25;
1101
1102   vector<Tie_configuration_variation> vars;
1103   Real last_center = 0.0;
1104   for (vsize i = 0; i < ties.size (); i++)
1105     {
1106       Bezier b (ties[i].get_transformed_bezier (details_));
1107
1108       Real center = b.curve_point (0.5)[Y_AXIS];
1109
1110       if (i)
1111         {
1112           if (center <= last_center + center_distance_tolerance)
1113             {
1114               if (!specifications_[i].has_manual_dir_)
1115                 {
1116                   Tie_configuration_variation var;
1117                   var.add_suggestion (i,
1118                                       get_configuration (specifications_[i].position_
1119                                                          - ties[i].dir_,
1120                                                          - ties[i].dir_,
1121
1122                                                          ties[i].column_ranks_,
1123                                                          !specifications_[i].has_manual_delta_y_
1124                                                         ));
1125
1126                   vars.push_back (var);
1127                 }
1128
1129               if (!specifications_[i - 1].has_manual_dir_)
1130                 {
1131                   Tie_configuration_variation var;
1132                   var.add_suggestion (i - 1,
1133                                       get_configuration (specifications_[i - 1].position_
1134                                                          - ties[i - 1].dir_,
1135                                                          - ties[i - 1].dir_,
1136                                                          specifications_[i - 1].column_ranks_,
1137                                                          !specifications_[i - 1].has_manual_delta_y_));
1138
1139                   vars.push_back (var);
1140                 }
1141
1142               if (i == 1 && !specifications_[i - 1].has_manual_position_
1143                   && ties[i - 1].dir_ == DOWN)
1144                 {
1145                   Tie_configuration_variation var;
1146                   var.add_suggestion (i - 1,
1147                                       get_configuration (specifications_[i - 1].position_ - 1, DOWN,
1148                                                          specifications_[i - 1].column_ranks_,
1149                                                          !specifications_[i - 1].has_manual_delta_y_
1150                                                         ));
1151                   vars.push_back (var);
1152                 }
1153               if (i == ties.size () && !specifications_[i].has_manual_position_
1154                   && ties[i].dir_ == UP)
1155                 {
1156                   Tie_configuration_variation var;
1157                   var.add_suggestion (i,
1158                                       get_configuration (specifications_[i].position_
1159                                                          + 1, UP,
1160                                                          specifications_[i].column_ranks_,
1161                                                          !specifications_[i].has_manual_delta_y_
1162                                                         ));
1163                   vars.push_back (var);
1164                 }
1165             }
1166           else if (dot_positions_.find (ties[i].position_) != dot_positions_.end ()
1167                    && !specifications_[i].has_manual_position_)
1168             {
1169               Tie_configuration_variation var;
1170               var.add_suggestion (i,
1171                                   get_configuration (ties[i].position_ + ties[i].dir_,
1172                                                      ties[i].dir_,
1173                                                      ties[i].column_ranks_,
1174                                                      !specifications_[i].has_manual_delta_y_
1175                                                     ));
1176               vars.push_back (var);
1177             }
1178
1179         }
1180
1181       last_center = center;
1182     }
1183
1184   return vars;
1185 }
1186
1187 void
1188 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
1189 {
1190   vsize k = 0;
1191   for (SCM s = manual_configs;
1192        scm_is_pair (s) && k < specifications_.size (); s = scm_cdr (s))
1193     {
1194       SCM entry = scm_car (s);
1195       if (scm_is_pair (entry))
1196         {
1197           Tie_specification &spec = specifications_[k];
1198
1199           if (scm_is_number (scm_car (entry)))
1200             {
1201               spec.has_manual_position_ = true;
1202               spec.manual_position_ = scm_to_double (scm_car (entry));
1203               spec.has_manual_delta_y_ = (scm_inexact_p (scm_car (entry)) == SCM_BOOL_T);
1204             }
1205
1206           if (scm_is_number (scm_cdr (entry)))
1207             {
1208               spec.has_manual_dir_ = true;
1209               spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry)));
1210             }
1211         }
1212       k++;
1213     }
1214 }
1215
1216 void
1217 Tie_formatting_problem::set_debug_scoring (Ties_configuration const &base)
1218 {
1219 #if DEBUG_TIE_SCORING
1220   if (to_boolean (x_refpoint_->layout ()
1221                   ->lookup_variable (ly_symbol2scm ("debug-tie-scoring"))))
1222     {
1223       for (vsize i = 0; i < base.size (); i++)
1224         {
1225           string card = base.complete_tie_card (i);
1226           specifications_[i].tie_grob_->set_property ("annotation",
1227                                                       ly_string2scm (card));
1228         }
1229     }
1230 #endif
1231 }