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