lily/tie-formatting-problem.cc

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