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           if (it->break_status_dir ())
 280             {
 281               Item *sep
 282                 = dynamic_cast<Item*> (unsmob_grob (ties[i]->get_object ("separation-item")));
 283               if (sep && sep->get_column () == it->get_column ())
 284                 it = sep;
 285             }
 286
 287           bounds.push_back (it);
 288         }
 289
 290       set_chord_outline (bounds, d);
 291     }
 292   while (flip (&d) != LEFT);
 293
 294
 295   for (vsize i = 0; i < ties.size (); i++)
 296     {
 297       Tie_specification spec;
 298
 299       spec.get_tie_manual_settings (ties[i]);
 300
 301
 302
 303       do
 304         {
 305           spec.note_head_drul_[d] = Tie::head (ties[i], d);
 306           spec.column_ranks_[d] =
 307             dynamic_cast<Spanner*> (ties[i])->get_bound (d)->get_column ()->get_rank ();
 308         }
 309       while (flip (&d) != LEFT);
 310       specifications_.push_back (spec);
 311     }
 312 }
 313
 314 void
 315 Tie_formatting_problem::from_semi_ties (vector<Grob*> const &semi_ties, Direction head_dir)
 316 {
 317   if (semi_ties.empty ())
 318     return;
 319
 320   details_.from_grob (semi_ties[0]);
 321   vector<Item*> heads;
 322
 323   int column_rank = -1;
 324   for (vsize i = 0; i < semi_ties.size (); i++)
 325     {
 326       Tie_specification spec;
 327       Item *head = unsmob_item (semi_ties[i]->get_object ("note-head"));
 328
 329       if (!head)
 330         programming_error ("LV tie without head?!");
 331
 332       if (head)
 333         {
 334           spec.position_ = int (Staff_symbol_referencer::get_position (head));
 335         }
 336
 337       spec.get_tie_manual_settings (semi_ties[i]);
 338
 339       spec.note_head_drul_[head_dir] = head;
 340       column_rank = dynamic_cast<Item*> (head)->get_column ()->get_rank ();
 341       spec.column_ranks_ = Drul_array<int> (column_rank, column_rank);
 342       heads.push_back (head);
 343       specifications_.push_back (spec);
 344     }
 345
 346   x_refpoint_ = semi_ties [0];
 347   for (vsize i = 0; i < semi_ties.size (); i++)
 348     x_refpoint_ = semi_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 349   for (vsize i = 0; i < heads.size (); i++)
 350     x_refpoint_ = heads[i]->common_refpoint (x_refpoint_, X_AXIS);
 351
 352   set_chord_outline (heads, head_dir);
 353
 354   Real extremal = head_dir * infinity_f;
 355
 356   Tuple2<int> head_key (column_rank, head_dir);
 357   Tuple2<int> open_key (column_rank, -head_dir);
 358
 359   for (vsize i = 0; i < chord_outlines_[head_key].size (); i++)
 360     {
 361       extremal = head_dir * min (head_dir * extremal,
 362                                  head_dir * chord_outlines_[head_key][i].height_);
 363     }
 364
 365   Skyline_entry right_entry;
 366   right_entry.width_.set_full ();
 367   right_entry.height_ = extremal - head_dir * 1.5;
 368
 369   chord_outlines_[open_key].push_back (right_entry);
 370 }
 371
 372
 373 Tie_specification
 374 Tie_formatting_problem::get_tie_specification (int i) const
 375 {
 376   return specifications_[i];
 377 }
 378
 379
 380 /*
 381   Return configuration, create it if necessary.
 382 */
 383 Tie_configuration*
 384 Tie_formatting_problem::get_configuration (int pos, Direction dir, Drul_array<int> columns) const
 385 {
 386   int key_components[] = {
 387     pos, dir, columns[LEFT], columns[RIGHT]
 388   };
 389   Tuple<int,4> key (key_components);
 390
 391   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 392   if (f != possibilities_.end ())
 393     {
 394       return (*f).second;
 395     }
 396
 397
 398   Tie_configuration *conf = generate_configuration (pos, dir, columns);
 399   ((Tie_formatting_problem*) this)->possibilities_[key] = conf;
 400   return conf;
 401 }
 402
 403 Tie_configuration*
 404 Tie_formatting_problem::generate_configuration (int pos, Direction dir,
 405                                                 Drul_array<int> columns) const
 406 {
 407   Tie_configuration *conf = new Tie_configuration;
 408   conf->position_ = pos;
 409   conf->dir_ = dir;
 410
 411   conf->column_ranks_ = columns;
 412
 413   Real y = conf->position_ * 0.5 * details_.staff_space_;
 414
 415   bool y_tune = true;
 416   if (dot_positions_.find (pos) != dot_positions_.end ())
 417     {
 418       conf->delta_y_ += dir * 0.25 * details_.staff_space_;
 419       y_tune = false;
 420     }
 421
 422   if (y_tune
 423       && max (fabs (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y),
 424               fabs (get_head_extent (columns[RIGHT], RIGHT, Y_AXIS)[dir] - y)) < 0.25
 425       && !Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 426     {
 427       conf->delta_y_ =
 428         (get_head_extent (columns[LEFT], LEFT, Y_AXIS)[dir] - y)
 429         + dir * details_.outer_tie_vertical_gap_;
 430     }
 431
 432   if (y_tune)
 433     {
 434       conf->attachment_x_ = get_attachment (y + conf->delta_y_, conf->column_ranks_);
 435       Real h =  conf->height (details_);
 436
 437       /*
 438         TODO:
 439
 440         - should make sliding criterion, should flatten ties if
 441
 442         - they're just the wrong (ie. touching line at top & bottom)
 443         size.
 444
 445        */
 446       if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 447         {
 448           if (!Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos)
 449               && abs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 450             {
 451               conf->center_tie_vertically (details_);
 452             }
 453           else if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 454             {
 455               conf->delta_y_ += dir *
 456                 details_.tip_staff_line_clearance_ * 0.5 *  details_.staff_space_;
 457             }
 458         }
 459       else
 460         {
 461           Real top_y = y + conf->delta_y_ + conf->dir_ * h;
 462           Real top_pos = top_y / (0.5*details_.staff_space_);
 463           int round_pos = int (my_round (top_pos));
 464
 465           /* TODO: should use other variable? */
 466           Real clearance = details_.center_staff_line_clearance_;
 467           if (fabs (top_pos - round_pos) < clearance
 468               && Staff_symbol_referencer::on_staff_line (details_.staff_symbol_referencer_,
 469                                                          round_pos))
 470             {
 471               Real new_y = (round_pos + clearance * conf->dir_) * 0.5 * details_.staff_space_;
 472               conf->delta_y_ = (new_y - top_y);
 473             }
 474         }
 475     }
 476
 477   conf->attachment_x_ = get_attachment (y + conf->delta_y_, conf->column_ranks_);
 478   if (conf->height (details_) < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 479     {
 480       /*
 481         This is less sensible for long ties, since those are more
 482         horizontal.
 483       */
 484       Interval close_by = get_attachment (y
 485                                           + conf->delta_y_
 486                                           + (dir * details_.intra_space_threshold_ * 0.25
 487                                              * details_.staff_space_),
 488                                           conf->column_ranks_);
 489
 490       conf->attachment_x_.intersect (close_by);
 491     }
 492
 493   conf->attachment_x_.widen ( - details_.x_gap_);
 494
 495   if (conf->column_span_length ())
 496     {
 497       /*
 498         avoid the stems that we attach to as well. We don't do this
 499         for semities (span length = 0)
 500
 501         It would be better to check D against HEAD-DIRECTION if
 502         applicable.
 503       */
 504       Direction d = LEFT;
 505       do
 506         {
 507           Real y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 508           if (get_stem_extent (conf->column_ranks_[d], d, X_AXIS).is_empty ()
 509               || !get_stem_extent (conf->column_ranks_[d], d, Y_AXIS).contains (y))
 510             continue;
 511
 512           conf->attachment_x_[d] =
 513             d * min (d * conf->attachment_x_[d],
 514                      d * (get_stem_extent (conf->column_ranks_[d], d, X_AXIS)[-d] - d * details_.stem_gap_));
 515         }
 516       while (flip (&d) != LEFT);
 517     }
 518   return conf;
 519 }
 520
 521 Interval
 522 Tie_formatting_problem::get_head_extent (int col, Direction d, Axis a) const
 523 {
 524   Column_extent_map::const_iterator i = head_extents_.find (Tuple2<int> (col, int (d)));
 525   if (i != head_extents_.end ())
 526     return (*i).second[a];
 527   else
 528     return Interval ();
 529 }
 530
 531 Interval
 532 Tie_formatting_problem::get_stem_extent (int col, Direction d, Axis a) const
 533 {
 534   Column_extent_map::const_iterator i = stem_extents_.find (Tuple2<int> (col, int (d)));
 535   if (i != stem_extents_.end ())
 536     return (*i).second[a];
 537   else
 538     return Interval ();
 539 }
 540
 541 /**
 542    TIE_IDX and TIES_CONF are optional.
 543  */
 544 Real
 545 Tie_formatting_problem::score_aptitude (Tie_configuration *conf,
 546                                         Tie_specification const &spec,
 547                                         Ties_configuration *ties_conf, int tie_idx) const
 548 {
 549   Real penalty = 0.0;
 550   Real curve_y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 551   Real tie_y = spec.position_ * details_.staff_space_ * 0.5;
 552   if (sign (curve_y - tie_y) != conf->dir_)
 553     {
 554       Real p =  details_.wrong_direction_offset_penalty_;
 555       if (ties_conf)
 556         ties_conf->add_tie_score (p, tie_idx, "wrong dir");
 557       else
 558         penalty += p;
 559     }
 560
 561   {
 562     Real p = details_.vertical_distance_penalty_factor_ * fabs (curve_y - tie_y);
 563     if (ties_conf)
 564       ties_conf->add_tie_score (p, tie_idx, "vdist");
 565     else
 566       penalty += p;
 567   }
 568
 569   Direction d = LEFT;
 570   do
 571     {
 572       if (!spec.note_head_drul_[d])
 573         continue;
 574
 575       Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS);
 576       Real dist = head_x.distance (conf->attachment_x_[d]);
 577
 578       /*
 579         TODO: flatten with log or sqrt.
 580        */
 581       Real p = details_.horizontal_distance_penalty_factor_ * dist;
 582       if (ties_conf)
 583         ties_conf->add_tie_score (p, tie_idx,
 584                                   (d == LEFT) ? "lhdist" : "rhdist");
 585       else
 586         penalty += p;
 587     }
 588   while (flip (&d) != LEFT);
 589
 590   return penalty;
 591 }
 592
 593 void
 594 Tie_formatting_problem::score_configuration (Tie_configuration *conf) const
 595 {
 596   if (conf->scored_)
 597     {
 598       return ;
 599     }
 600
 601   Real length = conf->attachment_x_.length ();
 602
 603   conf->add_score (details_.min_length_penalty_factor_
 604                    * peak_around (0.33 * details_.min_length_, details_.min_length_, length),
 605                    "minlength");
 606
 607   Real tip_pos = conf->position_ + conf->delta_y_ / 0.5 * details_.staff_space_;
 608   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 609   Real height =  conf->height (details_);
 610
 611   Real top_y = tip_y + conf->dir_ * height;
 612   Real top_pos = 2 * top_y / details_.staff_space_;
 613   Real round_top_pos = rint (top_pos);
 614   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 615                                                 int (round_top_pos))
 616       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 617     {
 618       conf->add_score (
 619         details_.staff_line_collision_penalty_
 620         * peak_around (0.1 * details_.center_staff_line_clearance_,
 621                      details_.center_staff_line_clearance_,
 622                        fabs (top_pos - round_top_pos)),
 623         "line center");
 624     }
 625
 626   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 627                                         int (rint (tip_pos))))
 628     {
 629       conf->add_score (details_.staff_line_collision_penalty_
 630                        * peak_around (0.1 * details_.tip_staff_line_clearance_,
 631                                       details_.tip_staff_line_clearance_,
 632                                       fabs (tip_pos - rint (tip_pos))),
 633                        "tipline");
 634     }
 635
 636   if (!dot_x_.is_empty ())
 637     {
 638       /* use left edge? */
 639       Real x = dot_x_.center ();
 640
 641       Bezier b = conf->get_transformed_bezier (details_);
 642       if (b.control_point_extent (X_AXIS).contains (x))
 643         {
 644           Real y = b.get_other_coordinate (X_AXIS, x);
 645
 646           for (set<int>::const_iterator i (dot_positions_.begin ());
 647                i != dot_positions_.end (); i ++)
 648             {
 649               int dot_pos = (*i);
 650               conf->add_score (details_.dot_collision_penalty_
 651                 * peak_around (.1 * details_.dot_collision_clearance_,
 652                                details_.dot_collision_clearance_,
 653                                fabs (dot_pos * details_.staff_space_ * 0.5 - y)),
 654                                "dot collision");
 655             }
 656         }
 657     }
 658
 659   conf->scored_ = true;
 660 }
 661
 662 Tie_configuration
 663 Tie_formatting_problem::find_optimal_tie_configuration (Tie_specification const &spec) const
 664 {
 665   vector<Tie_configuration*> confs;
 666
 667   int pos = spec.position_;
 668   Direction dir = spec.manual_dir_;
 669
 670   for (int i = 0; i < details_.single_tie_region_size_; i ++)
 671     {
 672       confs.push_back (generate_configuration (pos + i * dir, dir,
 673                                                spec.column_ranks_));
 674
 675       if (spec.has_manual_position_)
 676         {
 677           confs.back ()->delta_y_
 678             = (spec.manual_position_ - spec.position_)
 679             * 0.5 * details_.staff_space_;
 680
 681           break;
 682         }
 683     }
 684
 685   vector<Real> scores;
 686
 687   int best_idx = -1;
 688   Real best_score = 1e6;
 689   for (vsize i = 0; i < confs.size (); i ++)
 690     {
 691       score_configuration (confs[i]);
 692       Real score = score_aptitude (confs[i], spec, 0, 0)
 693         + confs[i]->score ();
 694
 695       if (score < best_score)
 696         {
 697           best_score = score;
 698           best_idx = i;
 699         }
 700     }
 701
 702   if (best_idx < 0)
 703     programming_error ("No best tie configuration found.");
 704
 705   Tie_configuration best
 706     = (best_idx >= 0) ?  *confs[best_idx] : *confs[0];
 707
 708   for (vsize i = 0; i < confs.size (); i++)
 709     delete confs[i];
 710
 711   return best;
 712 }
 713
 714 Tie_specification::Tie_specification ()
 715 {
 716   has_manual_position_ = false;
 717   has_manual_dir_ = false;
 718   position_ = 0;
 719   manual_position_ = 0;
 720   manual_dir_ = CENTER;
 721   note_head_drul_[LEFT] =
 722     note_head_drul_[RIGHT] = 0;
 723   column_ranks_[RIGHT] =
 724     column_ranks_[LEFT] = 0;
 725 }
 726
 727
 728 void
 729 Tie_specification::get_tie_manual_settings (Grob *tie)
 730 {
 731   if (scm_is_number (tie->get_property_data ("direction")))
 732     {
 733       manual_dir_ = to_dir (tie->get_property ("direction"));
 734       has_manual_dir_ = true;
 735     }
 736
 737   position_ = Tie::get_position (tie);
 738   if (scm_is_number (tie->get_property ("staff-position")))
 739     {
 740       manual_position_ = scm_to_double (tie->get_property ("staff-position"));
 741       has_manual_position_ = true;
 742       position_ = int (my_round (manual_position_));
 743     }
 744 }
 745
 746 int
 747 Tie_specification::column_span () const
 748 {
 749   return column_ranks_[RIGHT] - column_ranks_[LEFT];
 750 }
 751
 752 void
 753 Tie_formatting_problem::score_ties_aptitude (Ties_configuration *ties) const
 754 {
 755   if  (ties->size () != specifications_.size ())
 756     {
 757       programming_error ("Huh? Mismatch between sizes.");
 758       return;
 759     }
 760
 761   for (vsize i = 0; i < ties->size (); i++)
 762     score_aptitude (&ties->at (i), specifications_[i],
 763                     ties, i);
 764 }
 765
 766 void
 767 Tie_formatting_problem::score_ties (Ties_configuration *ties) const
 768 {
 769   if (ties->scored_)
 770     return;
 771
 772   score_ties_configuration (ties);
 773   score_ties_aptitude (ties);
 774   ties->scored_ = true;
 775 }
 776
 777 void
 778 Tie_formatting_problem::score_ties_configuration (Ties_configuration *ties) const
 779 {
 780   for (vsize i = 0; i < ties->size (); i++)
 781     {
 782       score_configuration (&ties->at (i));
 783       ties->add_tie_score (ties->at (i).score (), i, "conf");
 784     }
 785
 786   Real last_edge = 0.0;
 787   Real last_center = 0.0;
 788   for (vsize i = 0; i < ties->size (); i++)
 789     {
 790       Bezier b (ties->at (i).get_transformed_bezier (details_));
 791
 792       Real center = b.curve_point (0.5)[Y_AXIS];
 793       Real edge = b.curve_point (0.0)[Y_AXIS];
 794
 795       if (i)
 796         {
 797           if (edge <= last_edge)
 798             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton edge");
 799           if (center <= last_center)
 800             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton cent");
 801
 802           ties->add_score (details_.tie_tie_collision_penalty_ *
 803                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 804                                         details_.tie_tie_collision_distance_,
 805                                         fabs (center - last_center)),
 806                            "tietie center");
 807           ties->add_score (details_.tie_tie_collision_penalty_ *
 808                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 809                                         details_.tie_tie_collision_distance_,
 810                                         fabs (edge - last_edge)), "tietie edge");
 811         }
 812
 813       last_edge = edge;
 814       last_center = center;
 815     }
 816
 817   ties->add_score (details_.outer_tie_length_symmetry_penalty_factor_
 818                    * fabs (ties->at (0).attachment_x_.length () - ties->back ().attachment_x_.length ()),
 819                    "length symm");
 820
 821   ties->add_score (details_.outer_tie_vertical_distance_symmetry_penalty_factor_
 822                    * fabs (fabs (specifications_[0].position_ * 0.5 * details_.staff_space_
 823                                  - (ties->at (0).position_ * 0.5 * details_.staff_space_
 824                                     + ties->at (0).delta_y_))
 825                            -
 826                            fabs (specifications_.back ().position_ * 0.5 * details_.staff_space_
 827                                  - (ties->back ().position_ * 0.5 * details_.staff_space_
 828                                     + ties->back ().delta_y_))),
 829                    "pos symmetry");
 830 }
 831
 832 /*
 833   Generate with correct X-attachments and beziers, copying delta_y_
 834   from TIES_CONFIG if necessary.
 835 */
 836 Ties_configuration
 837 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
 838 {
 839   Ties_configuration copy;
 840   for (vsize i = 0; i < ties_config.size (); i++)
 841     {
 842       Tie_configuration * ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_,
 843                                                    ties_config[i].column_ranks_);
 844       if (specifications_[i].has_manual_position_)
 845         {
 846           ptr->delta_y_
 847             = (specifications_[i].manual_position_ - ties_config[i].position_)
 848             * 0.5 * details_.staff_space_;
 849         }
 850       copy.push_back (*ptr);
 851     }
 852
 853   return copy;
 854 }
 855
 856 Ties_configuration
 857 Tie_formatting_problem::generate_base_chord_configuration ()
 858 {
 859   Ties_configuration ties_config;
 860   for (vsize i = 0;  i < specifications_.size (); i ++)
 861     {
 862       Tie_configuration conf;
 863       if (specifications_[i].has_manual_dir_)
 864         conf.dir_ = specifications_[i].manual_dir_;
 865       if (specifications_[i].has_manual_position_)
 866         {
 867           conf.position_ = (int) my_round (specifications_[i].manual_position_);
 868           conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
 869             * 0.5 * details_.staff_space_;
 870         }
 871       else
 872         {
 873           conf.position_ = specifications_[i].position_;
 874         }
 875
 876       conf.column_ranks_ = specifications_[i].column_ranks_;
 877       ties_config.push_back (conf);
 878     }
 879
 880   set_ties_config_standard_directions (&ties_config);
 881   for (vsize i = 0; i < ties_config.size (); i++)
 882     if (!specifications_[i].manual_position_)
 883       ties_config[i].position_ += ties_config[i].dir_;
 884
 885   ties_config = generate_ties_configuration (ties_config);
 886
 887   return ties_config;
 888 }
 889
 890 Ties_configuration
 891 Tie_formatting_problem::find_best_variation (Ties_configuration const &base,
 892                                              vector<Tie_configuration_variation> vars)
 893 {
 894   Ties_configuration best = base;
 895
 896   /*
 897     This simply is 1-opt: we have K substitions, and we try applying
 898     exactly every one for each.
 899   */
 900   for (vsize i = 0; i < vars.size (); i++)
 901     {
 902       Ties_configuration variant (base);
 903       variant[vars[i].index_] = *vars[i].suggestion_;
 904
 905       variant.reset_score ();
 906       score_ties (&variant);
 907
 908       if (variant.score () < best.score ())
 909         {
 910           best = variant;
 911         }
 912     }
 913
 914   return best;
 915 }
 916
 917
 918
 919 Ties_configuration
 920 Tie_formatting_problem::generate_optimal_chord_configuration ()
 921 {
 922   Ties_configuration base = generate_base_chord_configuration ();
 923   vector<Tie_configuration_variation> vars = generate_collision_variations (base);
 924
 925   score_ties (&base);
 926   Ties_configuration best = find_best_variation (base, vars);
 927   vars = generate_extremal_tie_variations (best);
 928   best = find_best_variation (best, vars);
 929
 930   return best;
 931 }
 932
 933 void
 934 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
 935 {
 936   if (tie_configs->empty ())
 937     return ;
 938
 939   if (!tie_configs->at (0).dir_)
 940     {
 941       if (tie_configs->size () == 1)
 942         tie_configs->at (0).dir_ = Direction (sign (tie_configs->at (0).position_));
 943
 944       if (!tie_configs->at (0).dir_)
 945         tie_configs->at (0).dir_ = DOWN;
 946     }
 947
 948   if (!tie_configs->back ().dir_)
 949     tie_configs->back ().dir_ = UP;
 950
 951   /*
 952     Seconds
 953    */
 954   for (vsize i = 1; i < tie_configs->size (); i++)
 955     {
 956       Real diff = (tie_configs->at (i).position_
 957                    -tie_configs->at (i-1).position_);
 958
 959       Real span_diff
 960         = specifications_[i].column_span () - specifications_[i-1].column_span ();
 961       if (span_diff && fabs (diff) <= 2)
 962         {
 963           if  (span_diff > 0)
 964             tie_configs->at (i).dir_ = UP;
 965           else if (span_diff < 0)
 966             tie_configs->at (i-1).dir_ = DOWN;
 967         }
 968       else if (fabs (diff) <= 1)
 969         {
 970           if (!tie_configs->at (i-1).dir_)
 971             tie_configs->at (i-1).dir_ = DOWN;
 972           if (!tie_configs->at (i).dir_)
 973             tie_configs->at (i).dir_ = UP;
 974         }
 975     }
 976
 977   for (vsize i = 1; i + 1 < tie_configs->size (); i++)
 978     {
 979       Tie_configuration &conf = tie_configs->at (i);
 980       if (conf.dir_)
 981         continue;
 982
 983       Direction position_dir =
 984         Direction (sign (conf.position_));
 985       if (!position_dir)
 986         position_dir = DOWN;
 987
 988       conf.dir_ = position_dir;
 989     }
 990 }
 991
 992 Tie_configuration_variation::Tie_configuration_variation ()
 993 {
 994   index_ = 0;
 995   suggestion_ = 0;
 996 }
 997
 998 vector<Tie_configuration_variation>
 999 Tie_formatting_problem::generate_extremal_tie_variations (Ties_configuration const &ties) const
1000 {
1001   vector<Tie_configuration_variation> vars;
1002   Direction d = DOWN;
1003   do
1004     {
1005       if (boundary (ties, d, 0).dir_ == d
1006           && !boundary (specifications_, d, 0).has_manual_position_)
1007         for (int i = 1; i <= details_.multi_tie_region_size_; i++)
1008           {
1009             Tie_configuration_variation var;
1010             var.index_ = (d == DOWN) ? 0 : ties.size () - 1;
1011             var.suggestion_ = get_configuration (boundary (ties, d, 0).position_
1012                                                  + d * i, d,
1013                                                  boundary (ties, d, 0).column_ranks_);
1014             vars.push_back (var);
1015           }
1016     }
1017   while (flip (&d) !=  DOWN);
1018
1019   return vars;
1020 }
1021
1022
1023 vector<Tie_configuration_variation>
1024 Tie_formatting_problem::generate_collision_variations (Ties_configuration const &ties) const
1025 {
1026   Real center_distance_tolerance = 0.25;
1027
1028   vector<Tie_configuration_variation> vars;
1029   Real last_center = 0.0;
1030   for (vsize i = 0; i < ties.size (); i++)
1031     {
1032       Bezier b (ties[i].get_transformed_bezier (details_));
1033
1034       Real center = b.curve_point (0.5)[Y_AXIS];
1035
1036       if (i)
1037         {
1038           if (center <= last_center + center_distance_tolerance)
1039             {
1040               if (!specifications_[i].has_manual_dir_)
1041                 {
1042                   Tie_configuration_variation var;
1043                   var.index_ = i;
1044                   var.suggestion_ = get_configuration (specifications_[i].position_
1045                                                        - ties[i].dir_,
1046                                                        - ties[i].dir_,
1047
1048                                                        ties[i].column_ranks_
1049                                                        );
1050
1051                   vars.push_back (var);
1052                 }
1053
1054               if (!specifications_[i-1].has_manual_dir_)
1055                 {
1056                   Tie_configuration_variation var;
1057                   var.index_ = i-1;
1058                   var.suggestion_ = get_configuration (specifications_[i-1].position_
1059                                                        - ties[i-1].dir_,
1060                                                        - ties[i-1].dir_,
1061                                                        specifications_[i-1].column_ranks_);
1062
1063                   vars.push_back (var);
1064                 }
1065
1066               if (i == 1 && !specifications_[i-1].has_manual_position_
1067                   && ties[i-1].dir_ == DOWN)
1068                 {
1069                   Tie_configuration_variation var;
1070                   var.index_ = i-1;
1071                   var.suggestion_ = get_configuration (specifications_[i-1].position_ - 1, DOWN,
1072                                                        specifications_[i-1].column_ranks_);
1073                   vars.push_back (var);
1074                 }
1075               if (i == ties.size() && !specifications_[i].has_manual_position_
1076                   && ties[i].dir_ == UP)
1077                 {
1078                   Tie_configuration_variation var;
1079                   var.index_ = i;
1080                   var.suggestion_ = get_configuration (specifications_[i].position_
1081                                                        + 1, UP,
1082                                                        specifications_[i].column_ranks_);
1083                   vars.push_back (var);
1084                 }
1085             }
1086           else if (dot_positions_.find (ties[i].position_) != dot_positions_.end ()
1087                    && !specifications_[i].has_manual_position_)
1088             {
1089               Tie_configuration_variation var;
1090               var.index_ = i;
1091               var.suggestion_ = get_configuration (ties[i].position_  + ties[i].dir_,
1092                                                    ties[i].dir_,
1093                                                    ties[i].column_ranks_);
1094               vars.push_back (var);
1095             }
1096
1097         }
1098
1099       last_center = center;
1100     }
1101
1102
1103   return vars;
1104 }
1105
1106 void
1107 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
1108 {
1109   vsize k = 0;
1110   for (SCM s = manual_configs;
1111        scm_is_pair (s) && k < specifications_.size (); s = scm_cdr (s))
1112     {
1113       SCM entry = scm_car (s);
1114       if (scm_is_pair (entry))
1115         {
1116           Tie_specification &spec = specifications_[k];
1117
1118           if (scm_is_number (scm_car (entry)))
1119             {
1120               spec.has_manual_position_ = true;
1121               spec.manual_position_ = scm_to_double (scm_car (entry));
1122             }
1123           if (scm_is_number (scm_cdr (entry)))
1124             {
1125               spec.has_manual_dir_ = true;
1126               spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry)));
1127             }
1128         }
1129       k ++;
1130     }
1131 }
1132