lily/tie-formatting-problem.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2005--2011 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   Direction d = LEFT;
  60   do
  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   while (flip (&d) != LEFT);
  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 (!Note_head::has_interface (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::stem_end_position (stem) * staff_space * .5;
 153               else
 154                 stem_end_position = Stem::note_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 = unsmob_grob (heads[i]->get_object ("accidental-grob"));
 215           if (acc)
 216             acc->get_property ("stencil"); /* 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   Direction updowndir = DOWN;
 230   do
 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   while (flip (&updowndir) != DOWN);
 247
 248   /* todo: the horizon_padding is somewhat arbitrary */
 249   chord_outlines_[key] = Skyline (boxes, details_.skyline_padding_, Y_AXIS, -dir);
 250   if (bounds[0]->break_status_dir ())
 251     {
 252       Interval iv (Axis_group_interface::staff_extent (bounds[0], x_refpoint_, X_AXIS, y_refpoint_, Y_AXIS));
 253       if (iv.is_empty ())
 254         iv.add_point (bounds[0]->relative_coordinate (x_refpoint_, X_AXIS));
 255
 256       chord_outlines_[key].set_minimum_height (iv[-dir]);
 257     }
 258   else
 259     {
 260       Interval x;
 261       for (vsize j = 0; j < head_boxes.size (); j++)
 262         {
 263           x.unite (head_boxes[j][X_AXIS]);
 264         }
 265
 266       chord_outlines_[key].set_minimum_height (x[dir]);
 267     }
 268
 269   head_extents_[key].set_empty ();
 270   for (vsize i = 0; i < head_boxes.size (); i++)
 271     {
 272       head_extents_[key].unite (head_boxes[i]);
 273     }
 274 }
 275
 276 void
 277 Tie_formatting_problem::set_chord_outline (vector<Item *> bounds,
 278                                            Direction dir)
 279
 280 {
 281   vector<int> ranks;
 282   for (vsize i = 0; i < bounds.size (); i++)
 283     ranks.push_back (bounds[i]->get_column ()->get_rank ());
 284
 285   vector_sort (ranks, less<int> ());
 286   uniq (ranks);
 287
 288   for (vsize i = 0; i < ranks.size (); i++)
 289     {
 290       vector<Item *> col_items;
 291       for (vsize j = 0; j < bounds.size (); j++)
 292         {
 293           if (bounds[j]->get_column ()->get_rank () == ranks[i])
 294             col_items.push_back (bounds[j]);
 295         }
 296
 297       set_column_chord_outline (col_items, dir, ranks[i]);
 298     }
 299 }
 300
 301 void
 302 Tie_formatting_problem::from_tie (Grob *tie)
 303 {
 304   vector<Grob *> ties;
 305   ties.push_back (tie);
 306   from_ties (ties);
 307
 308   details_.from_grob (tie);
 309 }
 310
 311 Grob *
 312 Tie_formatting_problem::common_x_refpoint () const
 313 {
 314   return x_refpoint_;
 315 }
 316
 317 void
 318 Tie_formatting_problem::from_ties (vector<Grob *> const &ties)
 319 {
 320   if (ties.empty ())
 321     return;
 322
 323   x_refpoint_ = ties[0];
 324   y_refpoint_ = ties[0];
 325   for (vsize i = 0; i < ties.size (); i++)
 326     {
 327       Spanner *tie = dynamic_cast<Spanner *> (ties[i]);
 328       Item *l = tie->get_bound (LEFT);
 329       Item *r = tie->get_bound (RIGHT);
 330
 331       x_refpoint_ = l->common_refpoint (x_refpoint_, X_AXIS);
 332       x_refpoint_ = r->common_refpoint (x_refpoint_, X_AXIS);
 333
 334       if (!l->break_status_dir ())
 335         y_refpoint_ = l->common_refpoint (y_refpoint_, Y_AXIS);
 336       if (!r->break_status_dir ())
 337         y_refpoint_ = r->common_refpoint (y_refpoint_, Y_AXIS);
 338     }
 339
 340   details_.from_grob (ties[0]);
 341
 342   Direction d = LEFT;
 343   do
 344     {
 345       vector<Item *> bounds;
 346
 347       for (vsize i = 0; i < ties.size (); i++)
 348         {
 349           Item *it = dynamic_cast<Spanner *> (ties[i])->get_bound (d);
 350           if (it->break_status_dir ())
 351             it = it->get_column ();
 352
 353           bounds.push_back (it);
 354         }
 355
 356       set_chord_outline (bounds, d);
 357     }
 358   while (flip (&d) != LEFT);
 359
 360   for (vsize i = 0; i < ties.size (); i++)
 361     {
 362       Tie_specification spec;
 363       spec.from_grob (ties[i]);
 364
 365       do
 366         {
 367           spec.note_head_drul_[d] = Tie::head (ties[i], d);
 368           spec.column_ranks_[d] = Tie::get_column_rank (ties[i], d);
 369         }
 370       while (flip (&d) != LEFT);
 371       specifications_.push_back (spec);
 372     }
 373 }
 374
 375 void
 376 Tie_formatting_problem::from_semi_ties (vector<Grob *> const &semi_ties, Direction head_dir)
 377 {
 378   if (semi_ties.empty ())
 379     return;
 380
 381   use_horizontal_spacing_ = false;
 382   details_.from_grob (semi_ties[0]);
 383   vector<Item *> heads;
 384
 385   int column_rank = -1;
 386   for (vsize i = 0; i < semi_ties.size (); i++)
 387     {
 388       Tie_specification spec;
 389       Item *head = unsmob_item (semi_ties[i]->get_object ("note-head"));
 390
 391       if (!head)
 392         programming_error ("LV tie without head?!");
 393
 394       if (head)
 395         {
 396           spec.position_ = int (Staff_symbol_referencer::get_position (head));
 397         }
 398
 399       spec.from_grob (semi_ties[i]);
 400
 401       spec.note_head_drul_[head_dir] = head;
 402       column_rank = Tie::get_column_rank (semi_ties[i], head_dir);
 403       spec.column_ranks_ = Drul_array<int> (column_rank, column_rank);
 404       heads.push_back (head);
 405       specifications_.push_back (spec);
 406     }
 407
 408   x_refpoint_ = semi_ties[0];
 409   y_refpoint_ = semi_ties[0];
 410
 411   for (vsize i = 0; i < semi_ties.size (); i++)
 412     {
 413       x_refpoint_ = semi_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 414       y_refpoint_ = semi_ties[i]->common_refpoint (y_refpoint_, Y_AXIS);
 415     }
 416   for (vsize i = 0; i < heads.size (); i++)
 417     {
 418       x_refpoint_ = heads[i]->common_refpoint (x_refpoint_, X_AXIS);
 419       y_refpoint_ = heads[i]->common_refpoint (y_refpoint_, Y_AXIS);
 420     }
 421
 422   set_chord_outline (heads, head_dir);
 423
 424   Tuple2<int> head_key (column_rank, head_dir);
 425   Tuple2<int> open_key (column_rank, -head_dir);
 426   Real extremal = chord_outlines_[head_key].max_height ();
 427
 428   chord_outlines_[open_key] = Skyline (head_dir);
 429   chord_outlines_[open_key].set_minimum_height (extremal - head_dir * 1.5);
 430 }
 431
 432 Tie_specification
 433 Tie_formatting_problem::get_tie_specification (int i) const
 434 {
 435   return specifications_[i];
 436 }
 437
 438 /*
 439   Return configuration, create it if necessary.
 440 */
 441 Tie_configuration *
 442 Tie_formatting_problem::get_configuration (int pos, Direction dir, Drul_array<int> columns,
 443                                            bool tune_dy) const
 444 {
 445   int key_components[] =
 446   {
 447     pos, dir, columns[LEFT], columns[RIGHT]
 448   };
 449   Tuple<int, 4> key (key_components);
 450
 451   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 452   if (f != possibilities_.end ())
 453     {
 454       return (*f).second;
 455     }
 456
 457   Tie_configuration *conf = generate_configuration (pos, dir, columns, tune_dy);
 458   ((Tie_formatting_problem *) this)->possibilities_[key] = conf;
 459   return conf;
 460 }
 461
 462 Tie_configuration *
 463 Tie_formatting_problem::generate_configuration (int pos, Direction dir,
 464                                                 Drul_array<int> columns, bool y_tune) const
 465 {
 466   Tie_configuration *conf = new Tie_configuration;
 467   conf->position_ = pos;
 468   conf->dir_ = dir;
 469
 470   conf->column_ranks_ = columns;
 471
 472   Real y = conf->position_ * 0.5 * details_.staff_space_;
 473
 474   if (dot_positions_.find (pos) != dot_positions_.end ())
 475     {
 476       conf->delta_y_ += dir * 0.25 * details_.staff_space_;
 477       y_tune = false;
 478     }
 479
 480   if (y_tune
 481       && max (fabs (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y),
 482               fabs (get_head_extent (columns[RIGHT], RIGHT, Y_AXIS)[dir] - y)) < 0.25
 483       && !Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 484     {
 485       conf->delta_y_
 486         = (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y)
 487           + dir * details_.outer_tie_vertical_gap_;
 488     }
 489
 490   if (y_tune)
 491     {
 492       conf->attachment_x_ = get_attachment (y + conf->delta_y_, conf->column_ranks_);
 493       Real h = conf->height (details_);
 494
 495       /*
 496         TODO:
 497
 498         - should make sliding criterion, should flatten ties if
 499
 500         - they're just the wrong (ie. touching line at top & bottom)
 501         size.
 502
 503        */
 504       if (head_positions_slice (columns[LEFT]).contains (pos)
 505           || head_positions_slice (columns[RIGHT]).contains (pos)
 506           || abs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 507         {
 508           if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 509             {
 510               if (!Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos)
 511                   && abs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 512                 {
 513                   conf->center_tie_vertically (details_);
 514                 }
 515               else if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 516                 {
 517                   conf->delta_y_ += dir *
 518                                     details_.tip_staff_line_clearance_ * 0.5 * details_.staff_space_;
 519                 }
 520             }
 521           else
 522             {
 523               Real top_y = y + conf->delta_y_ + conf->dir_ * h;
 524               Real top_pos = top_y / (0.5 * details_.staff_space_);
 525               int round_pos = int (my_round (top_pos));
 526
 527               /* TODO: should use other variable? */
 528               Real clearance = details_.center_staff_line_clearance_;
 529               if (fabs (top_pos - round_pos) < clearance
 530                   && Staff_symbol_referencer::on_staff_line (details_.staff_symbol_referencer_,
 531                                                              round_pos))
 532                 {
 533                   Real new_y = (round_pos + clearance * conf->dir_) * 0.5 * details_.staff_space_;
 534                   conf->delta_y_ = (new_y - top_y);
 535                 }
 536             }
 537         }
 538     }
 539   conf->attachment_x_ = get_attachment (y + conf->delta_y_, conf->column_ranks_);
 540   if (conf->height (details_) < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 541     {
 542       /*
 543         This is less sensible for long ties, since those are more
 544         horizontal.
 545       */
 546       Interval close_by = get_attachment (y
 547                                           + conf->delta_y_
 548                                           + (dir * details_.intra_space_threshold_ * 0.25
 549                                              * details_.staff_space_),
 550                                           conf->column_ranks_);
 551
 552       conf->attachment_x_.intersect (close_by);
 553     }
 554
 555   conf->attachment_x_.widen ( - details_.x_gap_);
 556
 557   if (conf->column_span_length ())
 558     {
 559       /*
 560         avoid the stems that we attach to as well. We don't do this
 561         for semities (span length = 0)
 562
 563         It would be better to check D against HEAD-DIRECTION if
 564         applicable.
 565       */
 566       Direction d = LEFT;
 567       do
 568         {
 569           Real y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 570           if (get_stem_extent (conf->column_ranks_[d], d, X_AXIS).is_empty ()
 571               || !get_stem_extent (conf->column_ranks_[d], d, Y_AXIS).contains (y))
 572             continue;
 573
 574           conf->attachment_x_[d]
 575             = d * min (d * conf->attachment_x_[d],
 576                        d * (get_stem_extent (conf->column_ranks_[d], d, X_AXIS)[-d] - d * details_.stem_gap_));
 577         }
 578       while (flip (&d) != LEFT);
 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   Direction d = LEFT;
 633   do
 634     {
 635       if (!spec.note_head_drul_[d])
 636         continue;
 637
 638       Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS);
 639       Real dist = head_x.distance (conf->attachment_x_[d]);
 640
 641       /*
 642         TODO: flatten with log or sqrt.
 643        */
 644       Real p = details_.horizontal_distance_penalty_factor_
 645                * convex_amplifier (1.25, 1.0, dist);
 646       if (ties_conf)
 647         ties_conf->add_tie_score (p, tie_idx,
 648                                   (d == LEFT) ? "lhdist" : "rhdist");
 649       else
 650         penalty += p;
 651
 652     }
 653   while (flip (&d) != LEFT);
 654
 655   if (ties_conf
 656       && ties_conf->size () == 1)
 657     {
 658       Direction d = LEFT;
 659       Drul_array<Grob *> stems (0, 0);
 660       do
 661         {
 662           if (!spec.note_head_drul_[d])
 663             continue;
 664
 665           Grob *stem = unsmob_grob (spec.note_head_drul_[d]->get_object ("stem"));
 666           if (stem
 667               && Stem::is_normal_stem (stem))
 668             stems[d] = stem;
 669         }
 670       while (flip (&d) != LEFT);
 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   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 732                                         int (round_top_pos))
 733       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 734     {
 735       conf->add_score (details_.staff_line_collision_penalty_
 736                        * peak_around (0.1 * details_.center_staff_line_clearance_,
 737                                       details_.center_staff_line_clearance_,
 738                                       fabs (top_pos - round_top_pos)),
 739                        "line center");
 740     }
 741
 742   int rounded_tip_pos = int (rint (tip_pos));
 743   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, rounded_tip_pos)
 744       && (head_positions_slice (conf->column_ranks_[LEFT]).contains (rounded_tip_pos)
 745           || head_positions_slice (conf->column_ranks_[RIGHT]).contains (rounded_tip_pos)
 746           || abs (rounded_tip_pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 747      )
 748     {
 749       conf->add_score (details_.staff_line_collision_penalty_
 750                        * peak_around (0.1 * details_.tip_staff_line_clearance_,
 751                                       details_.tip_staff_line_clearance_,
 752                                       fabs (tip_pos - rint (tip_pos))),
 753                        "tipline");
 754     }
 755
 756   if (!dot_x_.is_empty ())
 757     {
 758       /* use left edge? */
 759       Real x = dot_x_.center ();
 760
 761       Bezier b = conf->get_transformed_bezier (details_);
 762       if (b.control_point_extent (X_AXIS).contains (x))
 763         {
 764           Real y = b.get_other_coordinate (X_AXIS, x);
 765
 766           for (set<int>::const_iterator i (dot_positions_.begin ());
 767                i != dot_positions_.end (); i++)
 768             {
 769               int dot_pos = (*i);
 770               conf->add_score (details_.dot_collision_penalty_
 771                                * peak_around (.1 * details_.dot_collision_clearance_,
 772                                               details_.dot_collision_clearance_,
 773                                               fabs (dot_pos * details_.staff_space_ * 0.5 - y)),
 774                                "dot collision");
 775             }
 776         }
 777     }
 778
 779   conf->scored_ = true;
 780 }
 781
 782 void
 783 Tie_formatting_problem::score_ties_aptitude (Ties_configuration *ties) const
 784 {
 785   if (ties->size () != specifications_.size ())
 786     {
 787       programming_error ("Huh? Mismatch between sizes.");
 788       return;
 789     }
 790
 791   for (vsize i = 0; i < ties->size (); i++)
 792     score_aptitude (&ties->at (i), specifications_[i],
 793                     ties, i);
 794 }
 795
 796 void
 797 Tie_formatting_problem::score_ties (Ties_configuration *ties) const
 798 {
 799   if (ties->scored_)
 800     return;
 801
 802   score_ties_configuration (ties);
 803   score_ties_aptitude (ties);
 804   ties->scored_ = true;
 805 }
 806
 807 void
 808 Tie_formatting_problem::score_ties_configuration (Ties_configuration *ties) const
 809 {
 810   for (vsize i = 0; i < ties->size (); i++)
 811     {
 812       score_configuration (&ties->at (i));
 813       ties->add_tie_score (ties->at (i).score (), i, "conf");
 814     }
 815
 816   Real last_edge = 0.0;
 817   Real last_center = 0.0;
 818   for (vsize i = 0; i < ties->size (); i++)
 819     {
 820       Bezier b (ties->at (i).get_transformed_bezier (details_));
 821
 822       Real center = b.curve_point (0.5)[Y_AXIS];
 823       Real edge = b.curve_point (0.0)[Y_AXIS];
 824
 825       if (i)
 826         {
 827           if (edge <= last_edge)
 828             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton edge");
 829           if (center <= last_center)
 830             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton cent");
 831
 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 (center - last_center)),
 836                            "tietie center");
 837           ties->add_score (details_.tie_tie_collision_penalty_ *
 838                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 839                                         details_.tie_tie_collision_distance_,
 840                                         fabs (edge - last_edge)), "tietie edge");
 841         }
 842
 843       last_edge = edge;
 844       last_center = center;
 845     }
 846
 847   if (ties->size () > 1)
 848     {
 849       ties->add_score (details_.outer_tie_length_symmetry_penalty_factor_
 850                        * fabs (ties->at (0).attachment_x_.length () - ties->back ().attachment_x_.length ()),
 851                        "length symm");
 852
 853       ties->add_score (details_.outer_tie_vertical_distance_symmetry_penalty_factor_
 854                        * fabs (fabs (specifications_[0].position_ * 0.5 * details_.staff_space_
 855                                      - (ties->at (0).position_ * 0.5 * details_.staff_space_
 856                                         + ties->at (0).delta_y_))
 857                                -
 858                                fabs (specifications_.back ().position_ * 0.5 * details_.staff_space_
 859                                      - (ties->back ().position_ * 0.5 * details_.staff_space_
 860                                         + ties->back ().delta_y_))),
 861                        "pos symmetry");
 862     }
 863 }
 864
 865 /*
 866   Generate with correct X-attachments and beziers, copying delta_y_
 867   from TIES_CONFIG if necessary.
 868 */
 869 Ties_configuration
 870 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
 871 {
 872   Ties_configuration copy;
 873   for (vsize i = 0; i < ties_config.size (); i++)
 874     {
 875       Tie_configuration *ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_,
 876                                                   ties_config[i].column_ranks_,
 877                                                   !specifications_[i].has_manual_delta_y_);
 878       if (specifications_[i].has_manual_delta_y_)
 879         {
 880           ptr->delta_y_
 881             = (specifications_[i].manual_position_ - ties_config[i].position_)
 882               * 0.5 * details_.staff_space_;
 883         }
 884       copy.push_back (*ptr);
 885     }
 886
 887   return copy;
 888 }
 889
 890 Ties_configuration
 891 Tie_formatting_problem::generate_base_chord_configuration ()
 892 {
 893   Ties_configuration ties_config;
 894   for (vsize i = 0; i < specifications_.size (); i++)
 895     {
 896       Tie_configuration conf;
 897       if (specifications_[i].has_manual_dir_)
 898         conf.dir_ = specifications_[i].manual_dir_;
 899       if (specifications_[i].has_manual_position_)
 900         {
 901           conf.position_ = (int) my_round (specifications_[i].manual_position_);
 902           if (specifications_[i].has_manual_delta_y_)
 903             conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
 904                             * 0.5 * details_.staff_space_;
 905         }
 906       else
 907         {
 908           conf.position_ = specifications_[i].position_;
 909         }
 910
 911       conf.column_ranks_ = specifications_[i].column_ranks_;
 912       ties_config.push_back (conf);
 913     }
 914
 915   set_ties_config_standard_directions (&ties_config);
 916   for (vsize i = 0; i < ties_config.size (); i++)
 917     if (!specifications_[i].manual_position_)
 918       ties_config[i].position_ += ties_config[i].dir_;
 919
 920   ties_config = generate_ties_configuration (ties_config);
 921
 922   return ties_config;
 923 }
 924
 925 Ties_configuration
 926 Tie_formatting_problem::find_best_variation (Ties_configuration const &base,
 927                                              vector<Tie_configuration_variation> const &vars)
 928 {
 929   Ties_configuration best = base;
 930
 931   /*
 932     This simply is 1-opt: we have K substitions, and we try applying
 933     exactly every one for each.
 934   */
 935   for (vsize i = 0; i < vars.size (); i++)
 936     {
 937       Ties_configuration variant (base);
 938       for (vsize j = 0; j < vars[i].index_suggestion_pairs_.size (); j++)
 939         variant[vars[i].index_suggestion_pairs_[j].first] = *vars[i].index_suggestion_pairs_[j].second;
 940
 941       variant.reset_score ();
 942       score_ties (&variant);
 943
 944       if (variant.score () < best.score ())
 945         {
 946           best = variant;
 947         }
 948     }
 949
 950   return best;
 951 }
 952
 953 Ties_configuration
 954 Tie_formatting_problem::generate_optimal_configuration ()
 955 {
 956   Ties_configuration base = generate_base_chord_configuration ();
 957   score_ties (&base);
 958
 959   vector<Tie_configuration_variation> vars;
 960   if (specifications_.size () > 1)
 961     vars = generate_collision_variations (base);
 962   else
 963     vars = generate_single_tie_variations (base);
 964
 965   Ties_configuration best = find_best_variation (base, vars);
 966
 967   if (specifications_.size () > 1)
 968     {
 969       vars = generate_extremal_tie_variations (best);
 970       best = find_best_variation (best, vars);
 971     }
 972   return best;
 973 }
 974
 975 void
 976 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
 977 {
 978   if (tie_configs->empty ())
 979     return;
 980
 981   if (!tie_configs->at (0).dir_)
 982     {
 983       if (tie_configs->size () == 1)
 984         tie_configs->at (0).dir_ = Direction (sign (tie_configs->at (0).position_));
 985
 986       if (!tie_configs->at (0).dir_)
 987         tie_configs->at (0).dir_
 988           = (tie_configs->size () > 1) ? DOWN : details_.neutral_direction_;
 989     }
 990
 991   if (!tie_configs->back ().dir_)
 992     tie_configs->back ().dir_ = UP;
 993
 994   /*
 995     Seconds
 996    */
 997   for (vsize i = 1; i < tie_configs->size (); i++)
 998     {
 999       Real diff = (tie_configs->at (i).position_
1000                    - tie_configs->at (i - 1).position_);
1001
1002       Real span_diff
1003         = specifications_[i].column_span () - specifications_[i - 1].column_span ();
1004       if (span_diff && fabs (diff) <= 2)
1005         {
1006           if (span_diff > 0)
1007             tie_configs->at (i).dir_ = UP;
1008           else if (span_diff < 0)
1009             tie_configs->at (i - 1).dir_ = DOWN;
1010         }
1011       else if (fabs (diff) <= 1)
1012         {
1013           if (!tie_configs->at (i - 1).dir_)
1014             tie_configs->at (i - 1).dir_ = DOWN;
1015           if (!tie_configs->at (i).dir_)
1016             tie_configs->at (i).dir_ = UP;
1017         }
1018     }
1019
1020   for (vsize i = 1; i + 1 < tie_configs->size (); i++)
1021     {
1022       Tie_configuration &conf = tie_configs->at (i);
1023       if (conf.dir_)
1024         continue;
1025
1026       Direction position_dir
1027         = Direction (sign (conf.position_));
1028       if (!position_dir)
1029         position_dir = DOWN;
1030
1031       conf.dir_ = position_dir;
1032     }
1033 }
1034
1035 vector<Tie_configuration_variation>
1036 Tie_formatting_problem::generate_extremal_tie_variations (Ties_configuration const &ties) const
1037 {
1038   vector<Tie_configuration_variation> vars;
1039   Direction d = DOWN;
1040   for (int i = 1; i <= details_.multi_tie_region_size_; i++)
1041     {
1042       Drul_array<Tie_configuration *> configs (0, 0);
1043       do
1044         {
1045           const Tie_configuration &config = boundary (ties, d, 0);
1046           if (config.dir_ == d
1047               && !boundary (specifications_, d, 0).has_manual_position_)
1048             {
1049               Tie_configuration_variation var;
1050               configs[d] = get_configuration (config.position_ + d * i, d,
1051                                               config.column_ranks_,
1052                                               true);
1053               var.add_suggestion ((d == DOWN) ? 0 : ties.size () - 1,
1054                                   configs[d]);
1055               vars.push_back (var);
1056             }
1057         }
1058       while (flip (&d) != DOWN);
1059       if (configs[LEFT] && configs[RIGHT])
1060         {
1061           Tie_configuration_variation var;
1062           var.add_suggestion (0, configs[DOWN]);
1063           var.add_suggestion (ties.size () - 1, configs[UP]);
1064           vars.push_back (var);
1065         }
1066     }
1067
1068   return vars;
1069 }
1070
1071 vector<Tie_configuration_variation>
1072 Tie_formatting_problem::generate_single_tie_variations (Ties_configuration const &ties) const
1073 {
1074   vector<Tie_configuration_variation> vars;
1075
1076   int sz = details_.single_tie_region_size_;
1077   if (specifications_[0].has_manual_position_)
1078     sz = 1;
1079   for (int i = 0; i < sz; i++)
1080     {
1081       Direction d = LEFT;
1082       do
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       while (flip (&d) != LEFT);
1102     }
1103   return vars;
1104 }
1105
1106 vector<Tie_configuration_variation>
1107 Tie_formatting_problem::generate_collision_variations (Ties_configuration const &ties) const
1108 {
1109   Real center_distance_tolerance = 0.25;
1110
1111   vector<Tie_configuration_variation> vars;
1112   Real last_center = 0.0;
1113   for (vsize i = 0; i < ties.size (); i++)
1114     {
1115       Bezier b (ties[i].get_transformed_bezier (details_));
1116
1117       Real center = b.curve_point (0.5)[Y_AXIS];
1118
1119       if (i)
1120         {
1121           if (center <= last_center + center_distance_tolerance)
1122             {
1123               if (!specifications_[i].has_manual_dir_)
1124                 {
1125                   Tie_configuration_variation var;
1126                   var.add_suggestion (i,
1127                                       get_configuration (specifications_[i].position_
1128                                                          - ties[i].dir_,
1129                                                          - ties[i].dir_,
1130
1131                                                          ties[i].column_ranks_,
1132                                                          !specifications_[i].has_manual_delta_y_
1133                                                         ));
1134
1135                   vars.push_back (var);
1136                 }
1137
1138               if (!specifications_[i - 1].has_manual_dir_)
1139                 {
1140                   Tie_configuration_variation var;
1141                   var.add_suggestion (i - 1,
1142                                       get_configuration (specifications_[i - 1].position_
1143                                                          - ties[i - 1].dir_,
1144                                                          - ties[i - 1].dir_,
1145                                                          specifications_[i - 1].column_ranks_,
1146                                                          !specifications_[i - 1].has_manual_delta_y_));
1147
1148                   vars.push_back (var);
1149                 }
1150
1151               if (i == 1 && !specifications_[i - 1].has_manual_position_
1152                   && ties[i - 1].dir_ == DOWN)
1153                 {
1154                   Tie_configuration_variation var;
1155                   var.add_suggestion (i - 1,
1156                                       get_configuration (specifications_[i - 1].position_ - 1, DOWN,
1157                                                          specifications_[i - 1].column_ranks_,
1158                                                          !specifications_[i - 1].has_manual_delta_y_
1159                                                         ));
1160                   vars.push_back (var);
1161                 }
1162               if (i == ties.size () && !specifications_[i].has_manual_position_
1163                   && ties[i].dir_ == UP)
1164                 {
1165                   Tie_configuration_variation var;
1166                   var.add_suggestion (i,
1167                                       get_configuration (specifications_[i].position_
1168                                                          + 1, UP,
1169                                                          specifications_[i].column_ranks_,
1170                                                          !specifications_[i].has_manual_delta_y_
1171                                                         ));
1172                   vars.push_back (var);
1173                 }
1174             }
1175           else if (dot_positions_.find (ties[i].position_) != dot_positions_.end ()
1176                    && !specifications_[i].has_manual_position_)
1177             {
1178               Tie_configuration_variation var;
1179               var.add_suggestion (i,
1180                                   get_configuration (ties[i].position_ + ties[i].dir_,
1181                                                      ties[i].dir_,
1182                                                      ties[i].column_ranks_,
1183                                                      !specifications_[i].has_manual_delta_y_
1184                                                     ));
1185               vars.push_back (var);
1186             }
1187
1188         }
1189
1190       last_center = center;
1191     }
1192
1193   return vars;
1194 }
1195
1196 void
1197 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
1198 {
1199   vsize k = 0;
1200   for (SCM s = manual_configs;
1201        scm_is_pair (s) && k < specifications_.size (); s = scm_cdr (s))
1202     {
1203       SCM entry = scm_car (s);
1204       if (scm_is_pair (entry))
1205         {
1206           Tie_specification &spec = specifications_[k];
1207
1208           if (scm_is_number (scm_car (entry)))
1209             {
1210               spec.has_manual_position_ = true;
1211               spec.manual_position_ = scm_to_double (scm_car (entry));
1212               spec.has_manual_delta_y_ = (scm_inexact_p (scm_car (entry)) == SCM_BOOL_T);
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 }