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--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7
   8 */
   9
  10 #include "tie-formatting-problem.hh"
  11
  12 #include "bezier.hh"
  13 #include "directional-element-interface.hh"
  14 #include "item.hh"
  15 #include "libc-extension.hh"
  16 #include "note-head.hh"
  17 #include "rhythmic-head.hh"
  18 #include "spanner.hh"
  19 #include "staff-symbol-referencer.hh"
  20 #include "stem.hh"
  21 #include "tie-configuration.hh"
  22 #include "tie.hh"
  23 #include "warn.hh"
  24
  25 /*
  26    0 at threshold,  1 at 0, with 1/x falloff.
  27  */
  28 Real peak_around (Real epsilon,  Real threshold, Real x)
  29 {
  30   if (x < 0)
  31     return 1.0;
  32   return max (- epsilon * (x - threshold) / ((x + epsilon)  * threshold), 0.0);
  33 }
  34
  35 void
  36 Tie_formatting_problem::print_ties_configuration (Ties_configuration const *ties)
  37 {
  38   for (vsize i = 0; i < ties->size (); i++)
  39     {
  40       char const *man_pos = (specifications_[i].has_manual_position_) ? "(M)" : "";
  41       char const *man_dir = (specifications_[i].has_manual_dir_) ? "(M)" : "";
  42       char const *dir = (ties->at (i).dir_ == UP) ? "up" : "dn";
  43
  44       printf ("(P%d%s, %s%s) ", ties->at (i).position_, man_pos, dir, man_dir);
  45     }
  46   printf ("\n");
  47 }
  48
  49 Interval
  50 Tie_formatting_problem::get_attachment (Real y) const
  51 {
  52   Interval attachments;
  53   Direction d = LEFT;
  54   do
  55     {
  56       attachments[d] = skyline_height (chord_outlines_[d], y, -d);
  57     }
  58   while (flip (&d) != LEFT);
  59
  60   return attachments;
  61 }
  62
  63 Tie_formatting_problem::Tie_formatting_problem()
  64 {
  65   x_refpoint_ = 0;
  66 }
  67
  68 Tie_formatting_problem::~Tie_formatting_problem ()
  69 {
  70   for (Tie_configuration_map::const_iterator i (possibilities_.begin ());
  71        i != possibilities_.end (); i++)
  72     delete (*i).second;
  73 }
  74
  75 void
  76 Tie_formatting_problem::set_chord_outline (vector<Item*> bounds,
  77                                            Direction dir)
  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           dot_positions_.insert (p);
 109           dot_x_.unite (x);
 110
 111           Interval y (dots->extent (dots, Y_AXIS));
 112           y.translate (p * staff_space * 0.5);
 113
 114           boxes.push_back (Box (x, y));
 115         }
 116     }
 117
 118   chord_outlines_[dir] = empty_skyline (-dir);
 119   if (bounds[0]->break_status_dir ())
 120     {
 121       Real x = robust_relative_extent (bounds[0],  x_refpoint_, X_AXIS)[-dir];
 122       chord_outlines_[dir].at (0).height_ = x;
 123     }
 124
 125   for (vsize i = 0; i < boxes.size (); i++)
 126     insert_extent_into_skyline (&chord_outlines_[dir]  ,
 127                                 boxes[i], Y_AXIS, -dir);
 128
 129   if (stem
 130       && !Stem::is_invisible (stem))
 131     {
 132       Interval x;
 133       x.add_point (stem->relative_coordinate (x_refpoint_, X_AXIS));
 134       x.widen (staff_space / 20); // ugh.
 135       Interval y;
 136       y.add_point (Stem::stem_end_position (stem) * staff_space * .5);
 137
 138       Direction stemdir = get_grob_direction (stem);
 139       y.add_point (Stem::head_positions (stem)[-stemdir]
 140                    * staff_space * .5);
 141
 142       insert_extent_into_skyline (&chord_outlines_[dir], Box (x,y), Y_AXIS, -dir);
 143
 144       stem_extents_[dir].unite (Box (x,y));
 145
 146       if (dir == LEFT)
 147         {
 148           Box flag_box = Stem::get_translated_flag (stem).extent_box ();
 149           flag_box.translate( Offset (x[RIGHT], X_AXIS));
 150           insert_extent_into_skyline (&chord_outlines_[dir], flag_box,
 151                                       Y_AXIS, -dir);
 152         }
 153     }
 154
 155   Direction updowndir = DOWN;
 156   do
 157     {
 158       Interval x;
 159       Interval y;
 160       if (head_boxes.size())
 161         {
 162           Box b = boundary (head_boxes, updowndir, 0);
 163           x = b[X_AXIS];
 164           x[-dir] =  b[X_AXIS].linear_combination (-dir / 2);
 165           y[-updowndir] = b[Y_AXIS][updowndir];
 166           y[updowndir] = updowndir * infinity_f;
 167         }
 168
 169       if (!x.is_empty ())
 170         insert_extent_into_skyline (&chord_outlines_[dir],
 171                                     Box (x,y),
 172                                     Y_AXIS, -dir);
 173     }
 174   while (flip (&updowndir) != DOWN);
 175
 176   head_extents_[dir].set_empty ();
 177   for (vsize i = 0; i < head_boxes.size (); i++)
 178     {
 179       head_extents_[dir].unite (head_boxes[i]);
 180     }
 181 }
 182
 183
 184 void
 185 Tie_formatting_problem::from_tie (Grob *tie)
 186 {
 187   vector<Grob*> ties;
 188   ties.push_back (tie);
 189   from_ties (ties);
 190
 191   details_.from_grob (tie);
 192 }
 193
 194 Grob *
 195 Tie_formatting_problem::common_x_refpoint () const
 196 {
 197   return x_refpoint_;
 198 }
 199
 200 void
 201 Tie_formatting_problem::from_ties (vector<Grob*> const &ties)
 202 {
 203   if (ties.empty ())
 204     return;
 205
 206   x_refpoint_ = ties[0];
 207   for (vsize i = 0; i < ties.size (); i++)
 208     {
 209       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (LEFT)->common_refpoint (x_refpoint_, X_AXIS);
 210       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (RIGHT)->common_refpoint (x_refpoint_, X_AXIS);
 211     }
 212
 213   details_.from_grob (ties[0]);
 214
 215   Direction d = LEFT;
 216   do
 217     {
 218       vector<Item*> bounds;
 219
 220       for (vsize i = 0; i < ties.size (); i++)
 221         {
 222           Item *it = dynamic_cast<Spanner*> (ties[i])->get_bound (d);
 223
 224           bounds.push_back (it);
 225         }
 226
 227       set_chord_outline (bounds, d);
 228     }
 229   while (flip (&d) != LEFT);
 230
 231
 232   for (vsize i = 0; i < ties.size (); i++)
 233     {
 234       Tie_specification spec;
 235
 236       if (scm_is_number (ties[i]->get_property_data (ly_symbol2scm ("direction"))))
 237         {
 238           spec.manual_dir_ = to_dir (ties[i]->get_property ("direction"));
 239           spec.has_manual_dir_ = true;
 240         }
 241
 242       spec.position_ = Tie::get_position (ties[i]);
 243
 244       do
 245         {
 246           spec.note_head_drul_[d] = Tie::head (ties[i], d);
 247         }
 248       while (flip (&d) != LEFT);
 249
 250       specifications_.push_back (spec);
 251     }
 252 }
 253
 254 void
 255 Tie_formatting_problem::from_semi_ties (vector<Grob*> const &lv_ties, Direction head_dir)
 256 {
 257   if (lv_ties.empty ())
 258     return;
 259
 260   details_.from_grob (lv_ties[0]);
 261   vector<Item*> heads;
 262
 263   for (vsize i = 0; i < lv_ties.size (); i++)
 264     {
 265       Tie_specification spec;
 266       Item *head = unsmob_item (lv_ties[i]->get_object ("note-head"));
 267
 268       if (!head)
 269         programming_error ("LV tie without head?!");
 270
 271       if (head)
 272         {
 273           spec.position_ = int (Staff_symbol_referencer::get_position (head));
 274         }
 275
 276       spec.note_head_drul_[head_dir] = head;
 277       heads.push_back (head);
 278       specifications_.push_back (spec);
 279     }
 280
 281   x_refpoint_ = lv_ties [0];
 282   for (vsize i = 0; i < lv_ties.size (); i++)
 283     x_refpoint_ = lv_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 284   for (vsize i = 0; i < heads.size (); i++)
 285     x_refpoint_ = heads[i]->common_refpoint (x_refpoint_, X_AXIS);
 286
 287   set_chord_outline (heads, head_dir);
 288
 289   Real extremal = head_dir * infinity_f;
 290
 291   for (vsize i = 0; i < chord_outlines_[head_dir].size (); i++)
 292     {
 293       extremal = head_dir * min (head_dir * extremal,
 294                                    head_dir * chord_outlines_[head_dir][i].height_);
 295     }
 296
 297   Skyline_entry right_entry;
 298   right_entry.width_.set_full ();
 299   right_entry.height_ = extremal - head_dir * 1.5;
 300
 301   chord_outlines_[-head_dir].push_back (right_entry);
 302 }
 303
 304
 305 Tie_specification
 306 Tie_formatting_problem::get_tie_specification (int i) const
 307 {
 308   return specifications_[i];
 309 }
 310
 311
 312 Tie_configuration*
 313 Tie_formatting_problem::get_configuration (int pos, Direction dir) const
 314 {
 315   pair<int,int> key (pos, dir);
 316   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 317
 318   if (f != possibilities_.end ())
 319     {
 320       return (*f).second;
 321     }
 322
 323
 324   Tie_configuration *conf = generate_configuration (pos, dir);
 325   ((Tie_formatting_problem*) this)->possibilities_[key] = conf;
 326   return conf;
 327 }
 328
 329 Tie_configuration*
 330 Tie_formatting_problem::generate_configuration (int pos, Direction dir) const
 331 {
 332   Tie_configuration *conf = new Tie_configuration;
 333   conf->position_ = pos;
 334   conf->dir_ = dir;
 335   Real y = conf->position_ * 0.5 * details_.staff_space_;
 336
 337
 338   bool y_tune = true;
 339   if (dot_positions_.find (pos) != dot_positions_.end ())
 340     {
 341       conf->delta_y_ += 0.25 * details_.staff_space_;
 342       y_tune = false;
 343     }
 344
 345
 346
 347   if (y_tune
 348       && max (fabs (head_extents_[LEFT][Y_AXIS][dir] - y),
 349               fabs (head_extents_[RIGHT][Y_AXIS][dir] - y)) < 0.25
 350       && !Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 351     {
 352       conf->delta_y_ =
 353         (head_extents_[LEFT][Y_AXIS][dir] - y)
 354         + dir * details_.outer_tie_vertical_gap_;
 355     }
 356
 357   if (y_tune)
 358     {
 359       conf->attachment_x_ = get_attachment (y + conf->delta_y_);
 360       Real h =  conf->height (details_);
 361
 362       /*
 363         TODO:
 364
 365         - should make sliding criterion, should flatten ties if
 366
 367         - they're just the wrong (ie. touching line at top & bottom)
 368         size.
 369
 370        */
 371       if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 372         {
 373           if (!Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos)
 374               && abs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 375             {
 376               conf->center_tie_vertically (details_);
 377             }
 378           else if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 379             {
 380               conf->delta_y_ += dir *
 381                 details_.tip_staff_line_clearance_ * 0.5 *  details_.staff_space_;
 382             }
 383         }
 384       else
 385         {
 386           Real top_y = y + conf->delta_y_ + conf->dir_ * h;
 387           Real top_pos = top_y / (0.5*details_.staff_space_);
 388           int round_pos = int (my_round (top_pos));
 389
 390           /* TODO: should use other variable? */
 391           Real clearance = details_.center_staff_line_clearance_;
 392           if (fabs (top_pos - round_pos) < clearance
 393               && Staff_symbol_referencer::on_staff_line (details_.staff_symbol_referencer_,
 394                                                          round_pos))
 395             {
 396               Real new_y = (round_pos + clearance * conf->dir_) * 0.5 * details_.staff_space_;
 397               conf->delta_y_ = (new_y - top_y);
 398             }
 399         }
 400     }
 401
 402   conf->attachment_x_ = get_attachment (y + conf->delta_y_);
 403   if (conf->height (details_) < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 404     {
 405       /*
 406         This is less sensible for long ties, since those are more
 407         horizontal.
 408       */
 409       Interval close_by = get_attachment (y
 410                                           + conf->delta_y_
 411                                           + (dir * details_.intra_space_threshold_ * 0.25
 412                                              * details_.staff_space_));
 413
 414       conf->attachment_x_.intersect (close_by);
 415     }
 416
 417   conf->attachment_x_.widen ( - details_.x_gap_);
 418
 419   Direction d = LEFT;
 420   do
 421     {
 422       Real y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 423       if (stem_extents_[d][X_AXIS].is_empty ()
 424           || !stem_extents_[d][Y_AXIS].contains (y))
 425         continue;
 426
 427       conf->attachment_x_[d] =
 428         d* min (d * conf->attachment_x_[d],
 429                 d * (stem_extents_[d][X_AXIS][-d] - d * details_.stem_gap_));
 430     }
 431   while (flip (&d) != LEFT);
 432   return conf;
 433 }
 434
 435 /**
 436    TIE_IDX and TIES_CONF are optional.
 437  */
 438 Real
 439 Tie_formatting_problem::score_aptitude (Tie_configuration *conf,
 440                                         Tie_specification const &spec,
 441                                         Ties_configuration *ties_conf, int tie_idx) const
 442 {
 443   Real penalty = 0.0;
 444   Real curve_y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 445   Real tie_y = spec.position_ * details_.staff_space_ * 0.5;
 446   if (sign (curve_y - tie_y) != conf->dir_)
 447     {
 448       Real p =  details_.wrong_direction_offset_penalty_;
 449       if (ties_conf)
 450         ties_conf->add_tie_score (p, tie_idx, "wrong dir");
 451       else
 452         penalty += p;
 453     }
 454
 455   {
 456     Real p = details_.vertical_distance_penalty_factor_ * fabs (curve_y - tie_y);
 457     if (ties_conf)
 458       ties_conf->add_tie_score (p, tie_idx, "vdist");
 459     else
 460       penalty += p;
 461   }
 462
 463   Direction d = LEFT;
 464   do
 465     {
 466       if (!spec.note_head_drul_[d])
 467         continue;
 468
 469       Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS);
 470       Real dist = head_x.distance (conf->attachment_x_[d]);
 471
 472       /*
 473         TODO: flatten with log or sqrt.
 474        */
 475       Real p = details_.horizontal_distance_penalty_factor_ * dist;
 476       if (ties_conf)
 477         ties_conf->add_tie_score (p, tie_idx,
 478                                   (d == LEFT) ? "lhdist" : "rhdist");
 479       else
 480         penalty += p;
 481     }
 482   while (flip (&d) != LEFT);
 483
 484   return penalty;
 485 }
 486
 487 void
 488 Tie_formatting_problem::score_configuration (Tie_configuration *conf) const
 489 {
 490   if (conf->scored_)
 491     {
 492       return ;
 493     }
 494
 495   Real length = conf->attachment_x_.length ();
 496
 497   conf->add_score (details_.min_length_penalty_factor_
 498                    * peak_around (0.33 * details_.min_length_, details_.min_length_, length),
 499                    "minlength");
 500
 501   Real tip_pos = conf->position_ + conf->delta_y_ / 0.5 * details_.staff_space_;
 502   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 503   Real height =  conf->height (details_);
 504
 505   Real top_y = tip_y + conf->dir_ * height;
 506   Real top_pos = 2 * top_y / details_.staff_space_;
 507   Real round_top_pos = rint (top_pos);
 508   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 509                                                 int (round_top_pos))
 510       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 511     {
 512       conf->add_score (
 513         details_.staff_line_collision_penalty_
 514         * peak_around (0.1 * details_.center_staff_line_clearance_,
 515                      details_.center_staff_line_clearance_,
 516                        fabs (top_pos - round_top_pos)),
 517         "line center");
 518     }
 519
 520   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 521                                         int (rint (tip_pos))))
 522     {
 523       conf->add_score (details_.staff_line_collision_penalty_
 524                        * peak_around (0.1 * details_.tip_staff_line_clearance_,
 525                                       details_.tip_staff_line_clearance_,
 526                                       fabs (tip_pos - rint (tip_pos))),
 527                        "tipline");
 528     }
 529
 530   if (!dot_x_.is_empty ())
 531     {
 532       /* use left edge? */
 533       Real x = dot_x_.center ();
 534
 535       Bezier b = conf->get_transformed_bezier (details_);
 536       if (b.control_point_extent (X_AXIS).contains (x))
 537         {
 538           Real y = b.get_other_coordinate (X_AXIS, x);
 539
 540           for (set<int>::const_iterator i (dot_positions_.begin ());
 541                i != dot_positions_.end (); i ++)
 542             {
 543               int dot_pos = (*i);
 544               conf->add_score (details_.dot_collision_penalty_
 545                 * peak_around (.1 * details_.dot_collision_clearance_,
 546                                details_.dot_collision_clearance_,
 547                                fabs (dot_pos * details_.staff_space_ * 0.5 - y)),
 548                                "dot collision");
 549             }
 550         }
 551     }
 552
 553   conf->scored_ = true;
 554 }
 555
 556 Tie_configuration
 557 Tie_formatting_problem::find_optimal_tie_configuration (Tie_specification const &spec) const
 558 {
 559   vector<Tie_configuration*> confs;
 560
 561   int pos = spec.position_;
 562   Direction dir = spec.manual_dir_;
 563
 564   for (int i = 0; i < details_.single_tie_region_size_; i ++)
 565     {
 566       confs.push_back (generate_configuration (pos + i * dir, dir));
 567     }
 568
 569   vector<Real> scores;
 570
 571   int best_idx = -1;
 572   Real best_score = 1e6;
 573   for (vsize i = 0; i < confs.size (); i ++)
 574     {
 575       score_configuration (confs[i]);
 576       Real score = score_aptitude (confs[i], spec, 0, 0)
 577         + confs[i]->score ();
 578
 579       if (score < best_score)
 580         {
 581           best_score = score;
 582           best_idx = i;
 583         }
 584     }
 585
 586   Tie_configuration best = *confs[best_idx];
 587   for (vsize i = 0; i < confs.size (); i++)
 588     delete confs[i];
 589
 590   return best;
 591 }
 592
 593 Tie_specification::Tie_specification ()
 594 {
 595   has_manual_position_ = false;
 596   has_manual_dir_ = false;
 597   position_ = 0;
 598   manual_position_ = 0;
 599   manual_dir_ = CENTER;
 600   note_head_drul_[LEFT] =
 601     note_head_drul_[RIGHT] = 0;
 602 }
 603
 604
 605 void
 606 Tie_formatting_problem::score_ties_aptitude (Ties_configuration *ties) const
 607 {
 608   if  (ties->size () != specifications_.size ())
 609     {
 610       programming_error ("Huh? Mismatch between sizes.");
 611       return;
 612     }
 613
 614   for (vsize i = 0; i < ties->size (); i++)
 615     score_aptitude (&ties->at (i), specifications_[i],
 616                     ties, i);
 617 }
 618
 619 void
 620 Tie_formatting_problem::score_ties (Ties_configuration *ties) const
 621 {
 622   if (ties->scored_)
 623     return;
 624
 625   score_ties_configuration (ties);
 626   score_ties_aptitude (ties);
 627   ties->scored_ = true;
 628 }
 629
 630 void
 631 Tie_formatting_problem::score_ties_configuration (Ties_configuration *ties) const
 632 {
 633   for (vsize i = 0; i < ties->size (); i++)
 634     {
 635       score_configuration (&ties->at (i));
 636       ties->add_tie_score (ties->at (i).score (), i, "conf");
 637     }
 638
 639   Real last_edge = 0.0;
 640   Real last_center = 0.0;
 641   for (vsize i = 0; i < ties->size (); i++)
 642     {
 643       Bezier b (ties->at (i).get_transformed_bezier (details_));
 644
 645       Real center = b.curve_point (0.5)[Y_AXIS];
 646       Real edge = b.curve_point (0.0)[Y_AXIS];
 647
 648       if (i)
 649         {
 650           if (edge <= last_edge)
 651             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton edge");
 652           if (center <= last_center)
 653             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton cent");
 654
 655           ties->add_score (details_.tie_tie_collision_penalty_ *
 656                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 657                                         details_.tie_tie_collision_distance_,
 658                                         fabs (center - last_center)),
 659                            "tietie center");
 660           ties->add_score (details_.tie_tie_collision_penalty_ *
 661                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 662                                         details_.tie_tie_collision_distance_,
 663                                         fabs (edge - last_edge)), "tietie edge");
 664         }
 665
 666       last_edge = edge;
 667       last_center = center;
 668     }
 669
 670   ties->add_score (details_.outer_tie_length_symmetry_penalty_factor_
 671                    * fabs (ties->at (0).attachment_x_.length () - ties->back ().attachment_x_.length ()),
 672                    "length symm");
 673
 674   ties->add_score (details_.outer_tie_vertical_distance_symmetry_penalty_factor_
 675                    * fabs (fabs (specifications_[0].position_ * 0.5 * details_.staff_space_
 676                                  - (ties->at (0).position_ * 0.5 * details_.staff_space_
 677                                     + ties->at (0).delta_y_))
 678                            -
 679                            fabs (specifications_.back ().position_ * 0.5 * details_.staff_space_
 680                                  - (ties->back ().position_ * 0.5 * details_.staff_space_
 681                                     + ties->back ().delta_y_))),
 682                    "pos symmetry");
 683 }
 684
 685 /*
 686   Generate with correct X-attachments and beziers, copying delta_y_
 687   from TIES_CONFIG if necessary.
 688 */
 689 Ties_configuration
 690 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
 691 {
 692   Ties_configuration copy;
 693   for (vsize i = 0; i < ties_config.size (); i++)
 694     {
 695       Tie_configuration * ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_);
 696       if (specifications_[i].has_manual_position_)
 697         {
 698           ptr->delta_y_
 699             = (specifications_[i].manual_position_ - ties_config[i].position_)
 700             * 0.5 * details_.staff_space_;
 701         }
 702       copy.push_back (*ptr);
 703     }
 704
 705   return copy;
 706 }
 707
 708 Ties_configuration
 709 Tie_formatting_problem::generate_base_chord_configuration ()
 710 {
 711   Ties_configuration ties_config;
 712   for (vsize i = 0;  i < specifications_.size (); i ++)
 713     {
 714       Tie_configuration conf;
 715       if (specifications_[i].has_manual_dir_)
 716         conf.dir_ = specifications_[i].manual_dir_;
 717       if (specifications_[i].has_manual_position_)
 718         {
 719           conf.position_ = (int) my_round (specifications_[i].manual_position_);
 720           conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
 721             * 0.5 * details_.staff_space_;
 722         }
 723       else
 724         {
 725           conf.position_ = specifications_[i].position_;
 726         }
 727       ties_config.push_back (conf);
 728     }
 729
 730   set_ties_config_standard_directions (&ties_config);
 731   for (vsize i = 0; i < ties_config.size (); i++)
 732     if (!specifications_[i].manual_position_)
 733       ties_config[i].position_ += ties_config[i].dir_;
 734
 735   ties_config = generate_ties_configuration (ties_config);
 736
 737   return ties_config;
 738 }
 739
 740 Ties_configuration
 741 Tie_formatting_problem::find_best_variation (Ties_configuration const &base,
 742                                              vector<Tie_configuration_variation> vars)
 743 {
 744   Ties_configuration best = base;
 745
 746   /*
 747     This simply is 1-opt: we have K substitions, and we try applying
 748     exactly every one for each.
 749   */
 750   for (vsize i = 0; i < vars.size (); i++)
 751     {
 752       Ties_configuration variant (base);
 753       variant[vars[i].index_] = *vars[i].suggestion_;
 754
 755       variant.reset_score ();
 756       score_ties (&variant);
 757
 758       if (variant.score () < best.score ())
 759         {
 760           best = variant;
 761         }
 762     }
 763
 764   return best;
 765 }
 766
 767
 768
 769 Ties_configuration
 770 Tie_formatting_problem::generate_optimal_chord_configuration ()
 771 {
 772
 773   Ties_configuration base = generate_base_chord_configuration ();
 774   vector<Tie_configuration_variation> vars = generate_collision_variations (base);
 775
 776   score_ties (&base);
 777   Ties_configuration best = find_best_variation (base, vars);
 778   vars = generate_extremal_tie_variations (best);
 779   best = find_best_variation (best, vars);
 780
 781   return best;
 782 }
 783
 784 void
 785 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
 786 {
 787   if (tie_configs->empty ())
 788     return ;
 789
 790   if (!tie_configs->at (0).dir_)
 791     tie_configs->at (0).dir_ = DOWN;
 792   if (!tie_configs->back ().dir_)
 793     tie_configs->back ().dir_ = UP;
 794
 795   /*
 796     Seconds
 797    */
 798   for (vsize i = 1; i < tie_configs->size (); i++)
 799     {
 800       Real diff = (tie_configs->at (i-1).position_
 801                    - tie_configs->at (i).position_);
 802
 803       if (fabs (diff) <= 1)
 804         {
 805           if (!tie_configs->at (i-1).dir_)
 806             tie_configs->at (i-1).dir_ = DOWN;
 807           if (!tie_configs->at (i).dir_)
 808             tie_configs->at (i).dir_ = UP;
 809         }
 810     }
 811
 812   for (vsize i = 1; i < tie_configs->size() - 1; i++)
 813     {
 814       Tie_configuration &conf = tie_configs->at (i);
 815       if (conf.dir_)
 816         continue;
 817
 818       Direction position_dir =
 819         Direction (sign (conf.position_));
 820       if (!position_dir)
 821         position_dir = DOWN;
 822
 823       conf.dir_ = position_dir;
 824     }
 825 }
 826
 827 Tie_configuration_variation::Tie_configuration_variation ()
 828 {
 829   index_ = 0;
 830   suggestion_ = 0;
 831 }
 832
 833 vector<Tie_configuration_variation>
 834 Tie_formatting_problem::generate_extremal_tie_variations (Ties_configuration const &ties) const
 835 {
 836   vector<Tie_configuration_variation> vars;
 837   Direction d = DOWN;
 838   do
 839     {
 840       if (boundary (ties, d, 0).dir_ == d
 841           && !boundary (specifications_, d, 0).has_manual_position_)
 842         for (int i = 1; i <= details_.multi_tie_region_size_; i++)
 843           {
 844             Tie_configuration_variation var;
 845             var.index_ = (d == DOWN) ? 0 : ties.size () - 1;
 846             var.suggestion_ = get_configuration (boundary (ties, d, 0).position_
 847                                                  + d * i, d);
 848             vars.push_back (var);
 849           }
 850     }
 851   while (flip (&d) !=  DOWN);
 852
 853   return vars;
 854 }
 855
 856
 857 vector<Tie_configuration_variation>
 858 Tie_formatting_problem::generate_collision_variations (Ties_configuration const &ties) const
 859 {
 860   Real center_distance_tolerance = 0.25;
 861
 862   vector<Tie_configuration_variation> vars;
 863   Real last_center = 0.0;
 864   for (vsize i = 0; i < ties.size (); i++)
 865     {
 866       Bezier b (ties[i].get_transformed_bezier (details_));
 867
 868       Real center = b.curve_point (0.5)[Y_AXIS];
 869
 870       if (i)
 871         {
 872           if (center <= last_center + center_distance_tolerance)
 873             {
 874               if (!specifications_[i].has_manual_dir_)
 875                 {
 876                   Tie_configuration_variation var;
 877                   var.index_ = i;
 878                   var.suggestion_ = get_configuration (specifications_[i].position_
 879                                                        - ties[i].dir_,
 880                                                        -ties[i].dir_);
 881
 882                   vars.push_back (var);
 883                 }
 884
 885               if (!specifications_[i-1].has_manual_dir_)
 886                 {
 887                   Tie_configuration_variation var;
 888                   var.index_ = i-1;
 889                   var.suggestion_ = get_configuration (specifications_[i-1].position_
 890                                                        - ties[i-1].dir_,
 891                                                        - ties[i-1].dir_);
 892
 893                   vars.push_back (var);
 894                 }
 895
 896               if (i == 1 && !specifications_[i-1].has_manual_position_
 897                   && ties[i-1].dir_ == DOWN)
 898                 {
 899                   Tie_configuration_variation var;
 900                   var.index_ = i-1;
 901                   var.suggestion_ = get_configuration (specifications_[i-1].position_
 902                                                        - 1, DOWN);
 903                   vars.push_back (var);
 904                 }
 905               if (i == ties.size() && !specifications_[i].has_manual_position_
 906                   && ties[i].dir_ == UP)
 907                 {
 908                   Tie_configuration_variation var;
 909                   var.index_ = i;
 910                   var.suggestion_ = get_configuration (specifications_[i].position_
 911                                                        + 1, UP);
 912                   vars.push_back (var);
 913                 }
 914             }
 915           else if (dot_positions_.find (ties[i].position_) != dot_positions_.end ()
 916                    && !specifications_[i].has_manual_position_)
 917             {
 918               Tie_configuration_variation var;
 919               var.index_ = i;
 920               var.suggestion_ = get_configuration (ties[i].position_  + ties[i].dir_,
 921                                                    ties[i].dir_);
 922               vars.push_back (var);
 923             }
 924
 925         }
 926
 927       last_center = center;
 928     }
 929
 930
 931   return vars;
 932 }
 933
 934 void
 935 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
 936 {
 937   vsize k = 0;
 938   for (SCM s = manual_configs;
 939        scm_is_pair (s) && k < specifications_.size (); s = scm_cdr (s))
 940     {
 941       SCM entry = scm_car (s);
 942       if (scm_is_pair (entry))
 943         {
 944           Tie_specification &spec = specifications_[k];
 945
 946           if (scm_is_number (scm_car (entry)))
 947             {
 948               spec.has_manual_position_ = true;
 949               spec.manual_position_ = scm_to_double (scm_car (entry));
 950             }
 951           if (scm_is_number (scm_cdr (entry)))
 952             {
 953               spec.has_manual_dir_ = true;
 954               spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry)));
 955             }
 956         }
 957       k ++;
 958     }
 959 }
 960