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