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