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