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   Column_extent_map::const_iterator i = head_extents_.find (Tuple2<int> (col, int (d)));
 518   if (i != head_extents_.end ())
 519     return (*i).second[a];
 520   else
 521     return Interval ();
 522 }
 523
 524 Interval
 525 Tie_formatting_problem::get_stem_extent (int col, Direction d, Axis a) const
 526 {
 527   Column_extent_map::const_iterator i = stem_extents_.find (Tuple2<int> (col, int (d)));
 528   if (i != stem_extents_.end ())
 529     return (*i).second[a];
 530   else
 531     return Interval ();
 532 }
 533
 534 /**
 535    TIE_IDX and TIES_CONF are optional.
 536  */
 537 Real
 538 Tie_formatting_problem::score_aptitude (Tie_configuration *conf,
 539                                         Tie_specification const &spec,
 540                                         Ties_configuration *ties_conf, int tie_idx) const
 541 {
 542   Real penalty = 0.0;
 543   Real curve_y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 544   Real tie_y = spec.position_ * details_.staff_space_ * 0.5;
 545   if (sign (curve_y - tie_y) != conf->dir_)
 546     {
 547       Real p =  details_.wrong_direction_offset_penalty_;
 548       if (ties_conf)
 549         ties_conf->add_tie_score (p, tie_idx, "wrong dir");
 550       else
 551         penalty += p;
 552     }
 553
 554   {
 555     Real p = details_.vertical_distance_penalty_factor_ * fabs (curve_y - tie_y);
 556     if (ties_conf)
 557       ties_conf->add_tie_score (p, tie_idx, "vdist");
 558     else
 559       penalty += p;
 560   }
 561
 562   Direction d = LEFT;
 563   do
 564     {
 565       if (!spec.note_head_drul_[d])
 566         continue;
 567
 568       Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS);
 569       Real dist = head_x.distance (conf->attachment_x_[d]);
 570
 571       /*
 572         TODO: flatten with log or sqrt.
 573        */
 574       Real p = details_.horizontal_distance_penalty_factor_ * dist;
 575       if (ties_conf)
 576         ties_conf->add_tie_score (p, tie_idx,
 577                                   (d == LEFT) ? "lhdist" : "rhdist");
 578       else
 579         penalty += p;
 580     }
 581   while (flip (&d) != LEFT);
 582
 583   return penalty;
 584 }
 585
 586 void
 587 Tie_formatting_problem::score_configuration (Tie_configuration *conf) const
 588 {
 589   if (conf->scored_)
 590     {
 591       return ;
 592     }
 593
 594   Real length = conf->attachment_x_.length ();
 595
 596   conf->add_score (details_.min_length_penalty_factor_
 597                    * peak_around (0.33 * details_.min_length_, details_.min_length_, length),
 598                    "minlength");
 599
 600   Real tip_pos = conf->position_ + conf->delta_y_ / 0.5 * details_.staff_space_;
 601   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 602   Real height =  conf->height (details_);
 603
 604   Real top_y = tip_y + conf->dir_ * height;
 605   Real top_pos = 2 * top_y / details_.staff_space_;
 606   Real round_top_pos = rint (top_pos);
 607   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 608                                                 int (round_top_pos))
 609       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 610     {
 611       conf->add_score (
 612         details_.staff_line_collision_penalty_
 613         * peak_around (0.1 * details_.center_staff_line_clearance_,
 614                      details_.center_staff_line_clearance_,
 615                        fabs (top_pos - round_top_pos)),
 616         "line center");
 617     }
 618
 619   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 620                                         int (rint (tip_pos))))
 621     {
 622       conf->add_score (details_.staff_line_collision_penalty_
 623                        * peak_around (0.1 * details_.tip_staff_line_clearance_,
 624                                       details_.tip_staff_line_clearance_,
 625                                       fabs (tip_pos - rint (tip_pos))),
 626                        "tipline");
 627     }
 628
 629   if (!dot_x_.is_empty ())
 630     {
 631       /* use left edge? */
 632       Real x = dot_x_.center ();
 633
 634       Bezier b = conf->get_transformed_bezier (details_);
 635       if (b.control_point_extent (X_AXIS).contains (x))
 636         {
 637           Real y = b.get_other_coordinate (X_AXIS, x);
 638
 639           for (set<int>::const_iterator i (dot_positions_.begin ());
 640                i != dot_positions_.end (); i ++)
 641             {
 642               int dot_pos = (*i);
 643               conf->add_score (details_.dot_collision_penalty_
 644                 * peak_around (.1 * details_.dot_collision_clearance_,
 645                                details_.dot_collision_clearance_,
 646                                fabs (dot_pos * details_.staff_space_ * 0.5 - y)),
 647                                "dot collision");
 648             }
 649         }
 650     }
 651
 652   conf->scored_ = true;
 653 }
 654
 655 Tie_configuration
 656 Tie_formatting_problem::find_optimal_tie_configuration (Tie_specification const &spec) const
 657 {
 658   vector<Tie_configuration*> confs;
 659
 660   int pos = spec.position_;
 661   Direction dir = spec.manual_dir_;
 662
 663   for (int i = 0; i < details_.single_tie_region_size_; i ++)
 664     {
 665       confs.push_back (generate_configuration (pos + i * dir, dir,
 666                                                spec.column_ranks_));
 667
 668       if (spec.has_manual_position_)
 669         {
 670           confs.back ()->delta_y_
 671             = (spec.manual_position_ - spec.position_)
 672             * 0.5 * details_.staff_space_;
 673
 674           break;
 675         }
 676     }
 677
 678   vector<Real> scores;
 679
 680   int best_idx = -1;
 681   Real best_score = 1e6;
 682   for (vsize i = 0; i < confs.size (); i ++)
 683     {
 684       score_configuration (confs[i]);
 685       Real score = score_aptitude (confs[i], spec, 0, 0)
 686         + confs[i]->score ();
 687
 688       if (score < best_score)
 689         {
 690           best_score = score;
 691           best_idx = i;
 692         }
 693     }
 694
 695   if (best_idx < 0)
 696     programming_error ("No best tie configuration found.");
 697
 698   Tie_configuration best
 699     = (best_idx >= 0) ?  *confs[best_idx] : *confs[0];
 700
 701   for (vsize i = 0; i < confs.size (); i++)
 702     delete confs[i];
 703
 704   return best;
 705 }
 706
 707 Tie_specification::Tie_specification ()
 708 {
 709   has_manual_position_ = false;
 710   has_manual_dir_ = false;
 711   position_ = 0;
 712   manual_position_ = 0;
 713   manual_dir_ = CENTER;
 714   note_head_drul_[LEFT] =
 715     note_head_drul_[RIGHT] = 0;
 716   column_ranks_[RIGHT] =
 717     column_ranks_[LEFT] = 0;
 718 }
 719
 720
 721 void
 722 Tie_specification::get_tie_manual_settings (Grob *tie)
 723 {
 724   if (scm_is_number (tie->get_property_data ("direction")))
 725     {
 726       manual_dir_ = to_dir (tie->get_property ("direction"));
 727       has_manual_dir_ = true;
 728     }
 729
 730   position_ = Tie::get_position (tie);
 731   if (scm_is_number (tie->get_property ("staff-position")))
 732     {
 733       manual_position_ = scm_to_double (tie->get_property ("staff-position"));
 734       has_manual_position_ = true;
 735       position_ = int (my_round (manual_position_));
 736     }
 737 }
 738
 739 int
 740 Tie_specification::column_span () const
 741 {
 742   return column_ranks_[RIGHT] - column_ranks_[LEFT];
 743 }
 744
 745 void
 746 Tie_formatting_problem::score_ties_aptitude (Ties_configuration *ties) const
 747 {
 748   if  (ties->size () != specifications_.size ())
 749     {
 750       programming_error ("Huh? Mismatch between sizes.");
 751       return;
 752     }
 753
 754   for (vsize i = 0; i < ties->size (); i++)
 755     score_aptitude (&ties->at (i), specifications_[i],
 756                     ties, i);
 757 }
 758
 759 void
 760 Tie_formatting_problem::score_ties (Ties_configuration *ties) const
 761 {
 762   if (ties->scored_)
 763     return;
 764
 765   score_ties_configuration (ties);
 766   score_ties_aptitude (ties);
 767   ties->scored_ = true;
 768 }
 769
 770 void
 771 Tie_formatting_problem::score_ties_configuration (Ties_configuration *ties) const
 772 {
 773   for (vsize i = 0; i < ties->size (); i++)
 774     {
 775       score_configuration (&ties->at (i));
 776       ties->add_tie_score (ties->at (i).score (), i, "conf");
 777     }
 778
 779   Real last_edge = 0.0;
 780   Real last_center = 0.0;
 781   for (vsize i = 0; i < ties->size (); i++)
 782     {
 783       Bezier b (ties->at (i).get_transformed_bezier (details_));
 784
 785       Real center = b.curve_point (0.5)[Y_AXIS];
 786       Real edge = b.curve_point (0.0)[Y_AXIS];
 787
 788       if (i)
 789         {
 790           if (edge <= last_edge)
 791             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton edge");
 792           if (center <= last_center)
 793             ties->add_score (details_.tie_column_monotonicity_penalty_, "monoton cent");
 794
 795           ties->add_score (details_.tie_tie_collision_penalty_ *
 796                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 797                                         details_.tie_tie_collision_distance_,
 798                                         fabs (center - last_center)),
 799                            "tietie center");
 800           ties->add_score (details_.tie_tie_collision_penalty_ *
 801                            peak_around (0.1 * details_.tie_tie_collision_distance_,
 802                                         details_.tie_tie_collision_distance_,
 803                                         fabs (edge - last_edge)), "tietie edge");
 804         }
 805
 806       last_edge = edge;
 807       last_center = center;
 808     }
 809
 810   ties->add_score (details_.outer_tie_length_symmetry_penalty_factor_
 811                    * fabs (ties->at (0).attachment_x_.length () - ties->back ().attachment_x_.length ()),
 812                    "length symm");
 813
 814   ties->add_score (details_.outer_tie_vertical_distance_symmetry_penalty_factor_
 815                    * fabs (fabs (specifications_[0].position_ * 0.5 * details_.staff_space_
 816                                  - (ties->at (0).position_ * 0.5 * details_.staff_space_
 817                                     + ties->at (0).delta_y_))
 818                            -
 819                            fabs (specifications_.back ().position_ * 0.5 * details_.staff_space_
 820                                  - (ties->back ().position_ * 0.5 * details_.staff_space_
 821                                     + ties->back ().delta_y_))),
 822                    "pos symmetry");
 823 }
 824
 825 /*
 826   Generate with correct X-attachments and beziers, copying delta_y_
 827   from TIES_CONFIG if necessary.
 828 */
 829 Ties_configuration
 830 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
 831 {
 832   Ties_configuration copy;
 833   for (vsize i = 0; i < ties_config.size (); i++)
 834     {
 835       Tie_configuration * ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_,
 836                                                    ties_config[i].column_ranks_);
 837       if (specifications_[i].has_manual_position_)
 838         {
 839           ptr->delta_y_
 840             = (specifications_[i].manual_position_ - ties_config[i].position_)
 841             * 0.5 * details_.staff_space_;
 842         }
 843       copy.push_back (*ptr);
 844     }
 845
 846   return copy;
 847 }
 848
 849 Ties_configuration
 850 Tie_formatting_problem::generate_base_chord_configuration ()
 851 {
 852   Ties_configuration ties_config;
 853   for (vsize i = 0;  i < specifications_.size (); i ++)
 854     {
 855       Tie_configuration conf;
 856       if (specifications_[i].has_manual_dir_)
 857         conf.dir_ = specifications_[i].manual_dir_;
 858       if (specifications_[i].has_manual_position_)
 859         {
 860           conf.position_ = (int) my_round (specifications_[i].manual_position_);
 861           conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
 862             * 0.5 * details_.staff_space_;
 863         }
 864       else
 865         {
 866           conf.position_ = specifications_[i].position_;
 867         }
 868
 869       conf.column_ranks_ = specifications_[i].column_ranks_;
 870       ties_config.push_back (conf);
 871     }
 872
 873   set_ties_config_standard_directions (&ties_config);
 874   for (vsize i = 0; i < ties_config.size (); i++)
 875     if (!specifications_[i].manual_position_)
 876       ties_config[i].position_ += ties_config[i].dir_;
 877
 878   ties_config = generate_ties_configuration (ties_config);
 879
 880   return ties_config;
 881 }
 882
 883 Ties_configuration
 884 Tie_formatting_problem::find_best_variation (Ties_configuration const &base,
 885                                              vector<Tie_configuration_variation> vars)
 886 {
 887   Ties_configuration best = base;
 888
 889   /*
 890     This simply is 1-opt: we have K substitions, and we try applying
 891     exactly every one for each.
 892   */
 893   for (vsize i = 0; i < vars.size (); i++)
 894     {
 895       Ties_configuration variant (base);
 896       variant[vars[i].index_] = *vars[i].suggestion_;
 897
 898       variant.reset_score ();
 899       score_ties (&variant);
 900
 901       if (variant.score () < best.score ())
 902         {
 903           best = variant;
 904         }
 905     }
 906
 907   return best;
 908 }
 909
 910
 911
 912 Ties_configuration
 913 Tie_formatting_problem::generate_optimal_chord_configuration ()
 914 {
 915   Ties_configuration base = generate_base_chord_configuration ();
 916   vector<Tie_configuration_variation> vars = generate_collision_variations (base);
 917
 918   score_ties (&base);
 919   Ties_configuration best = find_best_variation (base, vars);
 920   vars = generate_extremal_tie_variations (best);
 921   best = find_best_variation (best, vars);
 922
 923   return best;
 924 }
 925
 926 void
 927 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
 928 {
 929   if (tie_configs->empty ())
 930     return ;
 931
 932   if (!tie_configs->at (0).dir_)
 933     {
 934       if (tie_configs->size () == 1)
 935         tie_configs->at (0).dir_ = Direction (sign (tie_configs->at (0).position_));
 936
 937       if (!tie_configs->at (0).dir_)
 938         tie_configs->at (0).dir_ = DOWN;
 939     }
 940
 941   if (!tie_configs->back ().dir_)
 942     tie_configs->back ().dir_ = UP;
 943
 944   /*
 945     Seconds
 946    */
 947   for (vsize i = 1; i < tie_configs->size (); i++)
 948     {
 949       Real diff = (tie_configs->at (i).position_
 950                    -tie_configs->at (i-1).position_);
 951
 952       Real span_diff
 953         = specifications_[i].column_span () - specifications_[i-1].column_span ();
 954       if (span_diff && fabs (diff) <= 2)
 955         {
 956           if  (span_diff > 0)
 957             tie_configs->at (i).dir_ = UP;
 958           else if (span_diff < 0)
 959             tie_configs->at (i-1).dir_ = DOWN;
 960         }
 961       else if (fabs (diff) <= 1)
 962         {
 963           if (!tie_configs->at (i-1).dir_)
 964             tie_configs->at (i-1).dir_ = DOWN;
 965           if (!tie_configs->at (i).dir_)
 966             tie_configs->at (i).dir_ = UP;
 967         }
 968     }
 969
 970   for (vsize i = 1; i < tie_configs->size() - 1; i++)
 971     {
 972       Tie_configuration &conf = tie_configs->at (i);
 973       if (conf.dir_)
 974         continue;
 975
 976       Direction position_dir =
 977         Direction (sign (conf.position_));
 978       if (!position_dir)
 979         position_dir = DOWN;
 980
 981       conf.dir_ = position_dir;
 982     }
 983 }
 984
 985 Tie_configuration_variation::Tie_configuration_variation ()
 986 {
 987   index_ = 0;
 988   suggestion_ = 0;
 989 }
 990
 991 vector<Tie_configuration_variation>
 992 Tie_formatting_problem::generate_extremal_tie_variations (Ties_configuration const &ties) const
 993 {
 994   vector<Tie_configuration_variation> vars;
 995   Direction d = DOWN;
 996   do
 997     {
 998       if (boundary (ties, d, 0).dir_ == d
 999           && !boundary (specifications_, d, 0).has_manual_position_)
1000         for (int i = 1; i <= details_.multi_tie_region_size_; i++)
1001           {
1002             Tie_configuration_variation var;
1003             var.index_ = (d == DOWN) ? 0 : ties.size () - 1;
1004             var.suggestion_ = get_configuration (boundary (ties, d, 0).position_
1005                                                  + d * i, d,
1006                                                  boundary (ties, d, 0).column_ranks_);
1007             vars.push_back (var);
1008           }
1009     }
1010   while (flip (&d) !=  DOWN);
1011
1012   return vars;
1013 }
1014
1015
1016 vector<Tie_configuration_variation>
1017 Tie_formatting_problem::generate_collision_variations (Ties_configuration const &ties) const
1018 {
1019   Real center_distance_tolerance = 0.25;
1020
1021   vector<Tie_configuration_variation> vars;
1022   Real last_center = 0.0;
1023   for (vsize i = 0; i < ties.size (); i++)
1024     {
1025       Bezier b (ties[i].get_transformed_bezier (details_));
1026
1027       Real center = b.curve_point (0.5)[Y_AXIS];
1028
1029       if (i)
1030         {
1031           if (center <= last_center + center_distance_tolerance)
1032             {
1033               if (!specifications_[i].has_manual_dir_)
1034                 {
1035                   Tie_configuration_variation var;
1036                   var.index_ = i;
1037                   var.suggestion_ = get_configuration (specifications_[i].position_
1038                                                        - ties[i].dir_,
1039                                                        - ties[i].dir_,
1040
1041                                                        ties[i].column_ranks_
1042                                                        );
1043
1044                   vars.push_back (var);
1045                 }
1046
1047               if (!specifications_[i-1].has_manual_dir_)
1048                 {
1049                   Tie_configuration_variation var;
1050                   var.index_ = i-1;
1051                   var.suggestion_ = get_configuration (specifications_[i-1].position_
1052                                                        - ties[i-1].dir_,
1053                                                        - ties[i-1].dir_,
1054                                                        specifications_[i-1].column_ranks_);
1055
1056                   vars.push_back (var);
1057                 }
1058
1059               if (i == 1 && !specifications_[i-1].has_manual_position_
1060                   && ties[i-1].dir_ == DOWN)
1061                 {
1062                   Tie_configuration_variation var;
1063                   var.index_ = i-1;
1064                   var.suggestion_ = get_configuration (specifications_[i-1].position_ - 1, DOWN,
1065                                                        specifications_[i-1].column_ranks_);
1066                   vars.push_back (var);
1067                 }
1068               if (i == ties.size() && !specifications_[i].has_manual_position_
1069                   && ties[i].dir_ == UP)
1070                 {
1071                   Tie_configuration_variation var;
1072                   var.index_ = i;
1073                   var.suggestion_ = get_configuration (specifications_[i].position_
1074                                                        + 1, UP,
1075                                                        specifications_[i].column_ranks_);
1076                   vars.push_back (var);
1077                 }
1078             }
1079           else if (dot_positions_.find (ties[i].position_) != dot_positions_.end ()
1080                    && !specifications_[i].has_manual_position_)
1081             {
1082               Tie_configuration_variation var;
1083               var.index_ = i;
1084               var.suggestion_ = get_configuration (ties[i].position_  + ties[i].dir_,
1085                                                    ties[i].dir_,
1086                                                    ties[i].column_ranks_);
1087               vars.push_back (var);
1088             }
1089
1090         }
1091
1092       last_center = center;
1093     }
1094
1095
1096   return vars;
1097 }
1098
1099 void
1100 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
1101 {
1102   vsize k = 0;
1103   for (SCM s = manual_configs;
1104        scm_is_pair (s) && k < specifications_.size (); s = scm_cdr (s))
1105     {
1106       SCM entry = scm_car (s);
1107       if (scm_is_pair (entry))
1108         {
1109           Tie_specification &spec = specifications_[k];
1110
1111           if (scm_is_number (scm_car (entry)))
1112             {
1113               spec.has_manual_position_ = true;
1114               spec.manual_position_ = scm_to_double (scm_car (entry));
1115             }
1116           if (scm_is_number (scm_cdr (entry)))
1117             {
1118               spec.has_manual_dir_ = true;
1119               spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry)));
1120             }
1121         }
1122       k ++;
1123     }
1124 }
1125