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