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