lily/tie-formatting-problem.cc

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