lily/tie-formatting-problem.cc

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