lily/tie-formatting-problem.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2005--2012 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->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::note_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 ("stencil"); /* 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   Direction updowndir = DOWN;
 231   do
 232     {
 233       Interval x;
 234       Interval y;
 235       if (head_boxes.size ())
 236         {
 237           Box b = boundary (head_boxes, updowndir, 0);
 238           x = b[X_AXIS];
 239           x[-dir] = b[X_AXIS].linear_combination (-dir / 2);
 240           y[-updowndir] = b[Y_AXIS][updowndir];
 241           y[updowndir] = updowndir * infinity_f;
 242         }
 243
 244       if (!x.is_empty ())
 245         boxes.push_back (Box (x, y));
 246     }
 247   while (flip (&updowndir) != DOWN);
 248
 249   /* todo: the horizon_padding is somewhat arbitrary */
 250   chord_outlines_[key] = Skyline (boxes, details_.skyline_padding_, Y_AXIS, -dir);
 251   if (bounds[0]->break_status_dir ())
 252     {
 253       Interval iv (Axis_group_interface::staff_extent (bounds[0], x_refpoint_, X_AXIS, y_refpoint_, Y_AXIS));
 254       if (iv.is_empty ())
 255         iv.add_point (bounds[0]->relative_coordinate (x_refpoint_, X_AXIS));
 256
 257       chord_outlines_[key].set_minimum_height (iv[-dir]);
 258     }
 259   else
 260     {
 261       Interval x;
 262       for (vsize j = 0; j < head_boxes.size (); j++)
 263         {
 264           x.unite (head_boxes[j][X_AXIS]);
 265         }
 266
 267       chord_outlines_[key].set_minimum_height (x[dir]);
 268     }
 269
 270   head_extents_[key].set_empty ();
 271   for (vsize i = 0; i < head_boxes.size (); i++)
 272     {
 273       head_extents_[key].unite (head_boxes[i]);
 274     }
 275 }
 276
 277 void
 278 Tie_formatting_problem::set_chord_outline (vector<Item *> bounds,
 279                                            Direction dir)
 280
 281 {
 282   vector<int> ranks;
 283   for (vsize i = 0; i < bounds.size (); i++)
 284     ranks.push_back (bounds[i]->get_column ()->get_rank ());
 285
 286   vector_sort (ranks, less<int> ());
 287   uniq (ranks);
 288
 289   for (vsize i = 0; i < ranks.size (); i++)
 290     {
 291       vector<Item *> col_items;
 292       for (vsize j = 0; j < bounds.size (); j++)
 293         {
 294           if (bounds[j]->get_column ()->get_rank () == ranks[i])
 295             col_items.push_back (bounds[j]);
 296         }
 297
 298       set_column_chord_outline (col_items, dir, ranks[i]);
 299     }
 300 }
 301
 302 void
 303 Tie_formatting_problem::from_tie (Grob *tie)
 304 {
 305   vector<Grob *> ties;
 306   ties.push_back (tie);
 307   from_ties (ties);
 308
 309   details_.from_grob (tie);
 310 }
 311
 312 Grob *
 313 Tie_formatting_problem::common_x_refpoint () const
 314 {
 315   return x_refpoint_;
 316 }
 317
 318 void
 319 Tie_formatting_problem::from_ties (vector<Grob *> const &ties)
 320 {
 321   if (ties.empty ())
 322     return;
 323
 324   x_refpoint_ = ties[0];
 325   y_refpoint_ = ties[0];
 326   for (vsize i = 0; i < ties.size (); i++)
 327     {
 328       Spanner *tie = dynamic_cast<Spanner *> (ties[i]);
 329       Item *l = tie->get_bound (LEFT);
 330       Item *r = tie->get_bound (RIGHT);
 331
 332       x_refpoint_ = l->common_refpoint (x_refpoint_, X_AXIS);
 333       x_refpoint_ = r->common_refpoint (x_refpoint_, X_AXIS);
 334
 335       if (!l->break_status_dir ())
 336         y_refpoint_ = l->common_refpoint (y_refpoint_, Y_AXIS);
 337       if (!r->break_status_dir ())
 338         y_refpoint_ = r->common_refpoint (y_refpoint_, Y_AXIS);
 339     }
 340
 341   details_.from_grob (ties[0]);
 342
 343   Direction d = LEFT;
 344   do
 345     {
 346       vector<Item *> bounds;
 347
 348       for (vsize i = 0; i < ties.size (); i++)
 349         {
 350           Item *it = dynamic_cast<Spanner *> (ties[i])->get_bound (d);
 351           if (it->break_status_dir ())
 352             it = it->get_column ();
 353
 354           bounds.push_back (it);
 355         }
 356
 357       set_chord_outline (bounds, d);
 358     }
 359   while (flip (&d) != LEFT);
 360
 361   for (vsize i = 0; i < ties.size (); i++)
 362     {
 363       Tie_specification spec;
 364       spec.from_grob (ties[i]);
 365
 366       do
 367         {
 368           spec.note_head_drul_[d] = Tie::head (ties[i], d);
 369           spec.column_ranks_[d] = Tie::get_column_rank (ties[i], d);
 370         }
 371       while (flip (&d) != LEFT);
 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       Tie_specification spec;
 390       Item *head = unsmob_item (semi_ties[i]->get_object ("note-head"));
 391
 392       if (!head)
 393         programming_error ("LV tie without head?!");
 394
 395       if (head)
 396         {
 397           spec.position_ = int (Staff_symbol_referencer::get_position (head));
 398         }
 399
 400       spec.from_grob (semi_ties[i]);
 401
 402       spec.note_head_drul_[head_dir] = head;
 403       column_rank = Tie::get_column_rank (semi_ties[i], head_dir);
 404       spec.column_ranks_ = Drul_array<int> (column_rank, column_rank);
 405       heads.push_back (head);
 406       specifications_.push_back (spec);
 407     }
 408
 409   x_refpoint_ = semi_ties[0];
 410   y_refpoint_ = semi_ties[0];
 411
 412   for (vsize i = 0; i < semi_ties.size (); i++)
 413     {
 414       x_refpoint_ = semi_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 415       y_refpoint_ = semi_ties[i]->common_refpoint (y_refpoint_, Y_AXIS);
 416     }
 417   for (vsize i = 0; i < heads.size (); i++)
 418     {
 419       x_refpoint_ = heads[i]->common_refpoint (x_refpoint_, X_AXIS);
 420       y_refpoint_ = heads[i]->common_refpoint (y_refpoint_, Y_AXIS);
 421     }
 422
 423   set_chord_outline (heads, head_dir);
 424
 425   Tuple2<int> head_key (column_rank, head_dir);
 426   Tuple2<int> open_key (column_rank, -head_dir);
 427   Real extremal = chord_outlines_[head_key].max_height ();
 428
 429   chord_outlines_[open_key] = Skyline (head_dir);
 430   chord_outlines_[open_key].set_minimum_height (extremal - head_dir * 1.5);
 431 }
 432
 433 Tie_specification
 434 Tie_formatting_problem::get_tie_specification (int i) const
 435 {
 436   return specifications_[i];
 437 }
 438
 439 /*
 440   Return configuration, create it if necessary.
 441 */
 442 Tie_configuration *
 443 Tie_formatting_problem::get_configuration (int pos, Direction dir, Drul_array<int> columns,
 444                                            bool tune_dy) const
 445 {
 446   int key_components[]
 447   =
 448   {
 449     pos, dir, columns[LEFT], columns[RIGHT]
 450   };
 451   Tuple<int, 4> key (key_components);
 452
 453   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 454   if (f != possibilities_.end ())
 455     {
 456       return (*f).second;
 457     }
 458
 459   Tie_configuration *conf = generate_configuration (pos, dir, columns, tune_dy);
 460   ((Tie_formatting_problem *) this)->possibilities_[key] = conf;
 461   return conf;
 462 }
 463
 464 Tie_configuration *
 465 Tie_formatting_problem::generate_configuration (int pos, Direction dir,
 466                                                 Drul_array<int> columns, bool y_tune) const
 467 {
 468   Tie_configuration *conf = new Tie_configuration;
 469   conf->position_ = pos;
 470   conf->dir_ = dir;
 471
 472   conf->column_ranks_ = columns;
 473
 474   Real y = conf->position_ * 0.5 * details_.staff_space_;
 475
 476   if (dot_positions_.find (pos) != dot_positions_.end ())
 477     {
 478       conf->delta_y_ += dir * 0.25 * details_.staff_space_;
 479       y_tune = false;
 480     }
 481
 482   if (y_tune
 483       && max (fabs (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y),
 484               fabs (get_head_extent (columns[RIGHT], RIGHT, Y_AXIS)[dir] - y)) < 0.25
 485       && !Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 486     {
 487       conf->delta_y_
 488         = (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y)
 489           + dir * details_.outer_tie_vertical_gap_;
 490     }
 491
 492   if (y_tune)
 493     {
 494       conf->attachment_x_ = get_attachment (y + conf->delta_y_, conf->column_ranks_);
 495       Real h = conf->height (details_);
 496
 497       /*
 498         TODO:
 499
 500         - should make sliding criterion, should flatten ties if
 501
 502         - they're just the wrong (ie. touching line at top & bottom)
 503         size.
 504
 505        */
 506       if (head_positions_slice (columns[LEFT]).contains (pos)
 507           || head_positions_slice (columns[RIGHT]).contains (pos)
 508           || abs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 509         {
 510           if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 511             {
 512               if (!Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos)
 513                   && abs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 514                 {
 515                   conf->center_tie_vertically (details_);
 516                 }
 517               else 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             }
 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       Direction d = LEFT;
 569       do
 570         {
 571           Real y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 572           if (get_stem_extent (conf->column_ranks_[d], d, X_AXIS).is_empty ()
 573               || !get_stem_extent (conf->column_ranks_[d], d, Y_AXIS).contains (y))
 574             continue;
 575
 576           conf->attachment_x_[d]
 577             = d * min (d * conf->attachment_x_[d],
 578                        d * (get_stem_extent (conf->column_ranks_[d], d, X_AXIS)[-d] - d * details_.stem_gap_));
 579         }
 580       while (flip (&d) != LEFT);
 581     }
 582   return conf;
 583 }
 584
 585 Interval
 586 Tie_formatting_problem::get_head_extent (int col, Direction d, Axis a) const
 587 {
 588   Column_extent_map::const_iterator i = head_extents_.find (Tuple2<int> (col, int (d)));
 589   if (i != head_extents_.end ())
 590     return (*i).second[a];
 591   else
 592     return Interval ();
 593 }
 594
 595 Interval
 596 Tie_formatting_problem::get_stem_extent (int col, Direction d, Axis a) const
 597 {
 598   Column_extent_map::const_iterator i = stem_extents_.find (Tuple2<int> (col, int (d)));
 599   if (i != stem_extents_.end ())
 600     return (*i).second[a];
 601   else
 602     return Interval ();
 603 }
 604
 605 /**
 606    TIE_IDX and TIES_CONF are optional.
 607  */
 608 Real
 609 Tie_formatting_problem::score_aptitude (Tie_configuration *conf,
 610                                         Tie_specification const &spec,
 611                                         Ties_configuration *ties_conf, int tie_idx) const
 612 {
 613   Real penalty = 0.0;
 614   Real curve_y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 615   Real tie_y = spec.position_ * details_.staff_space_ * 0.5;
 616   if (sign (curve_y - tie_y) != conf->dir_)
 617     {
 618       Real p = details_.wrong_direction_offset_penalty_;
 619       if (ties_conf)
 620         ties_conf->add_tie_score (p, tie_idx, "wrong dir");
 621       else
 622         penalty += p;
 623     }
 624
 625   {
 626     Real relevant_dist = max (fabs (curve_y - tie_y) - 0.5, 0.0);
 627     Real p = details_.vertical_distance_penalty_factor_ * convex_amplifier (1.0, 0.9, relevant_dist);
 628     if (ties_conf)
 629       ties_conf->add_tie_score (p, tie_idx, "vdist");
 630     else
 631       penalty += p;
 632   }
 633
 634   Direction d = LEFT;
 635   do
 636     {
 637       if (!spec.note_head_drul_[d])
 638         continue;
 639
 640       Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS);
 641       Real dist = head_x.distance (conf->attachment_x_[d]);
 642
 643       /*
 644         TODO: flatten with log or sqrt.
 645        */
 646       Real p = details_.horizontal_distance_penalty_factor_
 647                * convex_amplifier (1.25, 1.0, dist);
 648       if (ties_conf)
 649         ties_conf->add_tie_score (p, tie_idx,
 650                                   (d == LEFT) ? "lhdist" : "rhdist");
 651       else
 652         penalty += p;
 653
 654     }
 655   while (flip (&d) != LEFT);
 656
 657   if (ties_conf
 658       && ties_conf->size () == 1)
 659     {
 660       Direction d = LEFT;
 661       Drul_array<Grob *> stems (0, 0);
 662       do
 663         {
 664           if (!spec.note_head_drul_[d])
 665             continue;
 666
 667           Grob *stem = unsmob_grob (spec.note_head_drul_[d]->get_object ("stem"));
 668           if (stem
 669               && Stem::is_normal_stem (stem))
 670             stems[d] = stem;
 671         }
 672       while (flip (&d) != LEFT);
 673
 674       bool tie_stem_dir_ok = true;
 675       bool tie_position_dir_ok = true;
 676       if (stems[LEFT] && !stems[RIGHT])
 677         tie_stem_dir_ok = conf->dir_ != get_grob_direction (stems[LEFT]);
 678       else if (!stems[LEFT] && stems[RIGHT])
 679         tie_stem_dir_ok = conf->dir_ != get_grob_direction (stems[RIGHT]);
 680       else if (stems[LEFT] && stems[RIGHT]
 681                && get_grob_direction (stems[LEFT]) == get_grob_direction (stems[RIGHT]))
 682         tie_stem_dir_ok = conf->dir_ != get_grob_direction (stems[LEFT]);
 683       else if (spec.position_)
 684         tie_position_dir_ok = conf->dir_ == sign (spec.position_);
 685
 686       if (!tie_stem_dir_ok)
 687         ties_conf->add_score (details_.same_dir_as_stem_penalty_, "tie/stem dir");
 688       if (!tie_position_dir_ok)
 689         ties_conf->add_score (details_.same_dir_as_stem_penalty_, "tie/pos dir");
 690     }
 691
 692   return penalty;
 693 }
 694
 695 Slice
 696 Tie_formatting_problem::head_positions_slice (int rank) const
 697 {
 698   Position_extent_map::const_iterator i (head_positions_.find (rank));
 699   if (i != head_positions_.end ())
 700     {
 701       return (*i).second;
 702     }
 703   Slice empty;
 704   return empty;
 705 }
 706
 707 /*
 708   Score a configuration, ie. how well these ties looks without regard
 709   to the note heads that they should connect to.
 710  */
 711 void
 712 Tie_formatting_problem::score_configuration (Tie_configuration *conf) const
 713 {
 714   if (conf->scored_)
 715     {
 716       return;
 717     }
 718
 719   Real length = conf->attachment_x_.length ();
 720
 721   Real length_penalty
 722     = peak_around (0.33 * details_.min_length_, details_.min_length_, length);
 723   conf->add_score (details_.min_length_penalty_factor_
 724                    * length_penalty, "minlength");
 725
 726   Real tip_pos = conf->position_ + conf->delta_y_ / 0.5 * details_.staff_space_;
 727   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 728   Real height = conf->height (details_);
 729
 730   Real top_y = tip_y + conf->dir_ * height;
 731   Real top_pos = 2 * top_y / details_.staff_space_;
 732   Real round_top_pos = rint (top_pos);
 733   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 734                                         int (round_top_pos))
 735       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > 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   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, rounded_tip_pos)
 746       && (head_positions_slice (conf->column_ranks_[LEFT]).contains (rounded_tip_pos)
 747           || head_positions_slice (conf->column_ranks_[RIGHT]).contains (rounded_tip_pos)
 748           || abs (rounded_tip_pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 749      )
 750     {
 751       conf->add_score (details_.staff_line_collision_penalty_
 752                        * peak_around (0.1 * details_.tip_staff_line_clearance_,
 753                                       details_.tip_staff_line_clearance_,
 754                                       fabs (tip_pos - rint (tip_pos))),
 755                        "tipline");
 756     }
 757
 758   if (!dot_x_.is_empty ())
 759     {
 760       /* use left edge? */
 761       Real x = dot_x_.center ();
 762
 763       Bezier b = conf->get_transformed_bezier (details_);
 764       if (b.control_point_extent (X_AXIS).contains (x))
 765         {
 766           Real y = b.get_other_coordinate (X_AXIS, x);
 767
 768           for (set<int>::const_iterator i (dot_positions_.begin ());
 769                i != dot_positions_.end (); i++)
 770             {
 771               int dot_pos = (*i);
 772               conf->add_score (details_.dot_collision_penalty_
 773                                * peak_around (.1 * details_.dot_collision_clearance_,
 774                                               details_.dot_collision_clearance_,
 775                                               fabs (dot_pos * details_.staff_space_ * 0.5 - y)),
 776                                "dot collision");
 777             }
 778         }
 779     }
 780
 781   conf->scored_ = true;
 782 }
 783
 784 void
 785 Tie_formatting_problem::score_ties_aptitude (Ties_configuration *ties) const
 786 {
 787   if (ties->size () != specifications_.size ())
 788     {
 789       programming_error ("Huh? Mismatch between sizes.");
 790       return;
 791     }
 792
 793   for (vsize i = 0; i < ties->size (); i++)
 794     score_aptitude (&ties->at (i), specifications_[i],
 795                     ties, i);
 796 }
 797
 798 void
 799 Tie_formatting_problem::score_ties (Ties_configuration *ties) const
 800 {
 801   if (ties->scored_)
 802     return;
 803
 804   score_ties_configuration (ties);
 805   score_ties_aptitude (ties);
 806   ties->scored_ = true;
 807 }
 808
 809 void
 810 Tie_formatting_problem::score_ties_configuration (Ties_configuration *ties) const
 811 {
 812   for (vsize i = 0; i < ties->size (); i++)
 813     {
 814       score_configuration (&ties->at (i));
 815       ties->add_tie_score (ties->at (i).score (), i, "conf");
 816     }
 817
 818   Real last_edge = 0.0;
 819   Real last_center = 0.0;
 820   for (vsize i = 0; i < ties->size (); i++)
 821     {
 822       Bezier b (ties->at (i).get_transformed_bezier (details_));
 823
 824       Real center = b.curve_point (0.5)[Y_AXIS];
 825       Real edge = b.curve_point (0.0)[Y_AXIS];
 826
 827       if (i)
 828         {
 829           if (edge <= last_edge)
 830             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton edge");
 831           if (center <= last_center)
 832             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton cent");
 833
 834           ties->add_score (details_.tie_tie_collision_penalty_ *
 835                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 836                                         details_.tie_tie_collision_distance_,
 837                                         fabs (center - last_center)),
 838                            "tietie center");
 839           ties->add_score (details_.tie_tie_collision_penalty_ *
 840                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 841                                         details_.tie_tie_collision_distance_,
 842                                         fabs (edge - last_edge)), "tietie edge");
 843         }
 844
 845       last_edge = edge;
 846       last_center = center;
 847     }
 848
 849   if (ties->size () > 1)
 850     {
 851       ties->add_score (details_.outer_tie_length_symmetry_penalty_factor_
 852                        * fabs (ties->at (0).attachment_x_.length () - ties->back ().attachment_x_.length ()),
 853                        "length symm");
 854
 855       ties->add_score (details_.outer_tie_vertical_distance_symmetry_penalty_factor_
 856                        * fabs (fabs (specifications_[0].position_ * 0.5 * details_.staff_space_
 857                                      - (ties->at (0).position_ * 0.5 * details_.staff_space_
 858                                         + ties->at (0).delta_y_))
 859                                -
 860                                fabs (specifications_.back ().position_ * 0.5 * details_.staff_space_
 861                                      - (ties->back ().position_ * 0.5 * details_.staff_space_
 862                                         + ties->back ().delta_y_))),
 863                        "pos symmetry");
 864     }
 865 }
 866
 867 /*
 868   Generate with correct X-attachments and beziers, copying delta_y_
 869   from TIES_CONFIG if necessary.
 870 */
 871 Ties_configuration
 872 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
 873 {
 874   Ties_configuration copy;
 875   for (vsize i = 0; i < ties_config.size (); i++)
 876     {
 877       Tie_configuration *ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_,
 878                                                   ties_config[i].column_ranks_,
 879                                                   !specifications_[i].has_manual_delta_y_);
 880       if (specifications_[i].has_manual_delta_y_)
 881         {
 882           ptr->delta_y_
 883             = (specifications_[i].manual_position_ - ties_config[i].position_)
 884               * 0.5 * details_.staff_space_;
 885         }
 886       copy.push_back (*ptr);
 887     }
 888
 889   return copy;
 890 }
 891
 892 Ties_configuration
 893 Tie_formatting_problem::generate_base_chord_configuration ()
 894 {
 895   Ties_configuration ties_config;
 896   for (vsize i = 0; i < specifications_.size (); i++)
 897     {
 898       Tie_configuration conf;
 899       if (specifications_[i].has_manual_dir_)
 900         conf.dir_ = specifications_[i].manual_dir_;
 901       if (specifications_[i].has_manual_position_)
 902         {
 903           conf.position_ = (int) my_round (specifications_[i].manual_position_);
 904           if (specifications_[i].has_manual_delta_y_)
 905             conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
 906                             * 0.5 * details_.staff_space_;
 907         }
 908       else
 909         {
 910           conf.position_ = specifications_[i].position_;
 911         }
 912
 913       conf.column_ranks_ = specifications_[i].column_ranks_;
 914       ties_config.push_back (conf);
 915     }
 916
 917   set_ties_config_standard_directions (&ties_config);
 918   for (vsize i = 0; i < ties_config.size (); i++)
 919     if (!specifications_[i].manual_position_)
 920       ties_config[i].position_ += ties_config[i].dir_;
 921
 922   ties_config = generate_ties_configuration (ties_config);
 923
 924   return ties_config;
 925 }
 926
 927 Ties_configuration
 928 Tie_formatting_problem::find_best_variation (Ties_configuration const &base,
 929                                              vector<Tie_configuration_variation> const &vars)
 930 {
 931   Ties_configuration best = base;
 932
 933   /*
 934     This simply is 1-opt: we have K substitions, and we try applying
 935     exactly every one for each.
 936   */
 937   for (vsize i = 0; i < vars.size (); i++)
 938     {
 939       Ties_configuration variant (base);
 940       for (vsize j = 0; j < vars[i].index_suggestion_pairs_.size (); j++)
 941         variant[vars[i].index_suggestion_pairs_[j].first] = *vars[i].index_suggestion_pairs_[j].second;
 942
 943       variant.reset_score ();
 944       score_ties (&variant);
 945
 946       if (variant.score () < best.score ())
 947         {
 948           best = variant;
 949         }
 950     }
 951
 952   return best;
 953 }
 954
 955 Ties_configuration
 956 Tie_formatting_problem::generate_optimal_configuration ()
 957 {
 958   Ties_configuration base = generate_base_chord_configuration ();
 959   score_ties (&base);
 960
 961   vector<Tie_configuration_variation> vars;
 962   if (specifications_.size () > 1)
 963     vars = generate_collision_variations (base);
 964   else
 965     vars = generate_single_tie_variations (base);
 966
 967   Ties_configuration best = find_best_variation (base, vars);
 968
 969   if (specifications_.size () > 1)
 970     {
 971       vars = generate_extremal_tie_variations (best);
 972       best = find_best_variation (best, vars);
 973     }
 974   return best;
 975 }
 976
 977 void
 978 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
 979 {
 980   if (tie_configs->empty ())
 981     return;
 982
 983   if (!tie_configs->at (0).dir_)
 984     {
 985       if (tie_configs->size () == 1)
 986         tie_configs->at (0).dir_ = Direction (sign (tie_configs->at (0).position_));
 987
 988       if (!tie_configs->at (0).dir_)
 989         tie_configs->at (0).dir_
 990           = (tie_configs->size () > 1) ? DOWN : details_.neutral_direction_;
 991     }
 992
 993   if (!tie_configs->back ().dir_)
 994     tie_configs->back ().dir_ = UP;
 995
 996   /*
 997     Seconds
 998    */
 999   for (vsize i = 1; i < tie_configs->size (); i++)
1000     {
1001       Real diff = (tie_configs->at (i).position_
1002                    - tie_configs->at (i - 1).position_);
1003
1004       Real span_diff
1005         = specifications_[i].column_span () - specifications_[i - 1].column_span ();
1006       if (span_diff && fabs (diff) <= 2)
1007         {
1008           if (span_diff > 0)
1009             tie_configs->at (i).dir_ = UP;
1010           else if (span_diff < 0)
1011             tie_configs->at (i - 1).dir_ = DOWN;
1012         }
1013       else if (fabs (diff) <= 1)
1014         {
1015           if (!tie_configs->at (i - 1).dir_)
1016             tie_configs->at (i - 1).dir_ = DOWN;
1017           if (!tie_configs->at (i).dir_)
1018             tie_configs->at (i).dir_ = UP;
1019         }
1020     }
1021
1022   for (vsize i = 1; i + 1 < tie_configs->size (); i++)
1023     {
1024       Tie_configuration &conf = tie_configs->at (i);
1025       if (conf.dir_)
1026         continue;
1027
1028       Direction position_dir
1029         = Direction (sign (conf.position_));
1030       if (!position_dir)
1031         position_dir = DOWN;
1032
1033       conf.dir_ = position_dir;
1034     }
1035 }
1036
1037 vector<Tie_configuration_variation>
1038 Tie_formatting_problem::generate_extremal_tie_variations (Ties_configuration const &ties) const
1039 {
1040   vector<Tie_configuration_variation> vars;
1041   Direction d = DOWN;
1042   for (int i = 1; i <= details_.multi_tie_region_size_; i++)
1043     {
1044       Drul_array<Tie_configuration *> configs (0, 0);
1045       do
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       while (flip (&d) != DOWN);
1061       if (configs[LEFT] && configs[RIGHT])
1062         {
1063           Tie_configuration_variation var;
1064           var.add_suggestion (0, configs[DOWN]);
1065           var.add_suggestion (ties.size () - 1, configs[UP]);
1066           vars.push_back (var);
1067         }
1068     }
1069
1070   return vars;
1071 }
1072
1073 vector<Tie_configuration_variation>
1074 Tie_formatting_problem::generate_single_tie_variations (Ties_configuration const &ties) const
1075 {
1076   vector<Tie_configuration_variation> vars;
1077
1078   int sz = details_.single_tie_region_size_;
1079   if (specifications_[0].has_manual_position_)
1080     sz = 1;
1081   for (int i = 0; i < sz; i++)
1082     {
1083       Direction d = LEFT;
1084       do
1085         {
1086           if (i == 0
1087               && ties[0].dir_ == d)
1088             continue;
1089
1090           int p = ties[0].position_ + i * d;
1091
1092           if (!specifications_[0].has_manual_dir_
1093               || d == specifications_[0].manual_dir_)
1094             {
1095               Tie_configuration_variation var;
1096               var.add_suggestion (0,
1097                                   get_configuration (p,
1098                                                      d, specifications_[0].column_ranks_,
1099                                                      !specifications_[0].has_manual_delta_y_));
1100               vars.push_back (var);
1101             }
1102         }
1103       while (flip (&d) != LEFT);
1104     }
1105   return vars;
1106 }
1107
1108 vector<Tie_configuration_variation>
1109 Tie_formatting_problem::generate_collision_variations (Ties_configuration const &ties) const
1110 {
1111   Real center_distance_tolerance = 0.25;
1112
1113   vector<Tie_configuration_variation> vars;
1114   Real last_center = 0.0;
1115   for (vsize i = 0; i < ties.size (); i++)
1116     {
1117       Bezier b (ties[i].get_transformed_bezier (details_));
1118
1119       Real center = b.curve_point (0.5)[Y_AXIS];
1120
1121       if (i)
1122         {
1123           if (center <= last_center + center_distance_tolerance)
1124             {
1125               if (!specifications_[i].has_manual_dir_)
1126                 {
1127                   Tie_configuration_variation var;
1128                   var.add_suggestion (i,
1129                                       get_configuration (specifications_[i].position_
1130                                                          - ties[i].dir_,
1131                                                          - ties[i].dir_,
1132
1133                                                          ties[i].column_ranks_,
1134                                                          !specifications_[i].has_manual_delta_y_
1135                                                         ));
1136
1137                   vars.push_back (var);
1138                 }
1139
1140               if (!specifications_[i - 1].has_manual_dir_)
1141                 {
1142                   Tie_configuration_variation var;
1143                   var.add_suggestion (i - 1,
1144                                       get_configuration (specifications_[i - 1].position_
1145                                                          - ties[i - 1].dir_,
1146                                                          - ties[i - 1].dir_,
1147                                                          specifications_[i - 1].column_ranks_,
1148                                                          !specifications_[i - 1].has_manual_delta_y_));
1149
1150                   vars.push_back (var);
1151                 }
1152
1153               if (i == 1 && !specifications_[i - 1].has_manual_position_
1154                   && ties[i - 1].dir_ == DOWN)
1155                 {
1156                   Tie_configuration_variation var;
1157                   var.add_suggestion (i - 1,
1158                                       get_configuration (specifications_[i - 1].position_ - 1, DOWN,
1159                                                          specifications_[i - 1].column_ranks_,
1160                                                          !specifications_[i - 1].has_manual_delta_y_
1161                                                         ));
1162                   vars.push_back (var);
1163                 }
1164               if (i == ties.size () && !specifications_[i].has_manual_position_
1165                   && ties[i].dir_ == UP)
1166                 {
1167                   Tie_configuration_variation var;
1168                   var.add_suggestion (i,
1169                                       get_configuration (specifications_[i].position_
1170                                                          + 1, UP,
1171                                                          specifications_[i].column_ranks_,
1172                                                          !specifications_[i].has_manual_delta_y_
1173                                                         ));
1174                   vars.push_back (var);
1175                 }
1176             }
1177           else if (dot_positions_.find (ties[i].position_) != dot_positions_.end ()
1178                    && !specifications_[i].has_manual_position_)
1179             {
1180               Tie_configuration_variation var;
1181               var.add_suggestion (i,
1182                                   get_configuration (ties[i].position_ + ties[i].dir_,
1183                                                      ties[i].dir_,
1184                                                      ties[i].column_ranks_,
1185                                                      !specifications_[i].has_manual_delta_y_
1186                                                     ));
1187               vars.push_back (var);
1188             }
1189
1190         }
1191
1192       last_center = center;
1193     }
1194
1195   return vars;
1196 }
1197
1198 void
1199 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
1200 {
1201   vsize k = 0;
1202   for (SCM s = manual_configs;
1203        scm_is_pair (s) && k < specifications_.size (); s = scm_cdr (s))
1204     {
1205       SCM entry = scm_car (s);
1206       if (scm_is_pair (entry))
1207         {
1208           Tie_specification &spec = specifications_[k];
1209
1210           if (scm_is_number (scm_car (entry)))
1211             {
1212               spec.has_manual_position_ = true;
1213               spec.manual_position_ = scm_to_double (scm_car (entry));
1214               spec.has_manual_delta_y_ = (scm_inexact_p (scm_car (entry)) == SCM_BOOL_T);
1215             }
1216
1217           if (scm_is_number (scm_cdr (entry)))
1218             {
1219               spec.has_manual_dir_ = true;
1220               spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry)));
1221             }
1222         }
1223       k++;
1224     }
1225 }
1226
1227 void
1228 Tie_formatting_problem::set_debug_scoring (Ties_configuration const &base)
1229 {
1230 #if DEBUG_TIE_SCORING
1231   if (to_boolean (x_refpoint_->layout ()
1232                   ->lookup_variable (ly_symbol2scm ("debug-tie-scoring"))))
1233     {
1234       for (vsize i = 0; i < base.size (); i++)
1235         {
1236           string card = base.complete_tie_card (i);
1237           specifications_[i].tie_grob_->set_property ("annotation",
1238                                                       ly_string2scm (card));
1239         }
1240     }
1241 #endif
1242 }