lily/tie-formatting-problem.cc

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