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