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