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