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