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