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