lily/axis-group-interface.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2000--2012 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "axis-group-interface.hh"
  21
  22 #include <map>
  23
  24 #include "align-interface.hh"
  25 #include "directional-element-interface.hh"
  26 #include "grob-array.hh"
  27 #include "hara-kiri-group-spanner.hh"
  28 #include "international.hh"
  29 #include "interval-set.hh"
  30 #include "lookup.hh"
  31 #include "paper-column.hh"
  32 #include "paper-score.hh"
  33 #include "pointer-group-interface.hh"
  34 #include "separation-item.hh"
  35 #include "skyline-pair.hh"
  36 #include "staff-grouper-interface.hh"
  37 #include "stem.hh"
  38 #include "stencil.hh"
  39 #include "system.hh"
  40 #include "warn.hh"
  41 #include "unpure-pure-container.hh"
  42
  43 static bool
  44 pure_staff_priority_less (Grob *const &g1, Grob *const &g2);
  45
  46 Real Axis_group_interface::default_outside_staff_padding_ = 0.46;
  47
  48 Real
  49 Axis_group_interface::get_default_outside_staff_padding ()
  50 {
  51   return default_outside_staff_padding_;
  52 }
  53
  54 void
  55 Axis_group_interface::add_element (Grob *me, Grob *e)
  56 {
  57   SCM axes = me->get_property ("axes");
  58   if (!scm_is_pair (axes))
  59     programming_error ("axes should be nonempty");
  60
  61   for (SCM ax = axes; scm_is_pair (ax); ax = scm_cdr (ax))
  62     {
  63       Axis a = (Axis) scm_to_int (scm_car (ax));
  64
  65       if (!e->get_parent (a))
  66         e->set_parent (me, a);
  67
  68       e->set_object ((a == X_AXIS)
  69                      ? ly_symbol2scm ("axis-group-parent-X")
  70                      : ly_symbol2scm ("axis-group-parent-Y"),
  71                      me->self_scm ());
  72     }
  73
  74   /* must be ordered, because Align_interface also uses
  75      Axis_group_interface  */
  76   Pointer_group_interface::add_grob (me, ly_symbol2scm ("elements"), e);
  77 }
  78
  79 bool
  80 Axis_group_interface::has_axis (Grob *me, Axis a)
  81 {
  82   SCM axes = me->get_property ("axes");
  83
  84   return (SCM_BOOL_F != scm_memq (scm_from_int (a), axes));
  85 }
  86
  87 Interval
  88 Axis_group_interface::relative_group_extent (vector<Grob *> const &elts,
  89                                              Grob *common, Axis a)
  90 {
  91   return relative_maybe_bound_group_extent (elts, common, a, false);
  92 }
  93
  94 Interval
  95 Axis_group_interface::relative_maybe_bound_group_extent (vector<Grob *> const &elts,
  96                                                          Grob *common, Axis a, bool bound)
  97 {
  98   Interval r;
  99   for (vsize i = 0; i < elts.size (); i++)
 100     {
 101       Grob *se = elts[i];
 102       if (!to_boolean (se->get_property ("cross-staff")))
 103         {
 104           Interval dims = (bound && has_interface (se)
 105                            ? generic_bound_extent (se, common, a)
 106                            : se->extent (common, a));
 107           if (!dims.is_empty ())
 108             r.unite (dims);
 109         }
 110     }
 111   return r;
 112 }
 113
 114 Interval
 115 Axis_group_interface::generic_bound_extent (Grob *me, Grob *common, Axis a)
 116 {
 117   /* trigger the callback to do skyline-spacing on the children */
 118   if (a == Y_AXIS)
 119     (void) me->get_property ("vertical-skylines");
 120
 121   extract_grob_set (me, "elements", elts);
 122   vector<Grob *> new_elts;
 123
 124   SCM interfaces = me->get_property ("bound-alignment-interfaces");
 125
 126   for (vsize i = 0; i < elts.size (); i++)
 127     for (SCM l = interfaces; scm_is_pair (l); l = scm_cdr (l))
 128       if (elts[i]->internal_has_interface (scm_car (l)))
 129         new_elts.push_back (elts[i]);
 130
 131   if (!new_elts.size ())
 132     return robust_relative_extent (me, common, a);
 133
 134   if (!common)
 135     common = common_refpoint_of_array (new_elts, me, a);
 136
 137   return relative_maybe_bound_group_extent (new_elts, common, a, true);
 138 }
 139
 140 Interval
 141 Axis_group_interface::sum_partial_pure_heights (Grob *me, int start, int end)
 142 {
 143   Interval iv = begin_of_line_pure_height (me, start);
 144   iv.unite (rest_of_line_pure_height (me, start, end));
 145
 146   return iv;
 147 }
 148
 149 Interval
 150 Axis_group_interface::part_of_line_pure_height (Grob *me, bool begin, int start, int end)
 151 {
 152   Spanner *sp = dynamic_cast<Spanner *> (me);
 153   SCM cache_symbol = begin
 154                      ? ly_symbol2scm ("begin-of-line-pure-height")
 155                      : ly_symbol2scm ("rest-of-line-pure-height");
 156   SCM cached = sp->get_cached_pure_property (cache_symbol, start, end);
 157   if (scm_is_pair (cached))
 158     return robust_scm2interval (cached, Interval (0, 0));
 159
 160   SCM adjacent_pure_heights = me->get_property ("adjacent-pure-heights");
 161   Interval ret;
 162
 163   if (!scm_is_pair (adjacent_pure_heights))
 164     ret = Interval (0, 0);
 165   else
 166     {
 167       SCM these_pure_heights = begin
 168                                ? scm_car (adjacent_pure_heights)
 169                                : scm_cdr (adjacent_pure_heights);
 170
 171       if (scm_is_vector (these_pure_heights))
 172         ret = combine_pure_heights (me, these_pure_heights, start, end);
 173       else
 174         ret = Interval (0, 0);
 175     }
 176
 177   sp->cache_pure_property (cache_symbol, start, end, ly_interval2scm (ret));
 178   return ret;
 179 }
 180
 181 Interval
 182 Axis_group_interface::begin_of_line_pure_height (Grob *me, int start)
 183 {
 184   return part_of_line_pure_height (me, true, start, start + 1);
 185 }
 186
 187 Interval
 188 Axis_group_interface::rest_of_line_pure_height (Grob *me, int start, int end)
 189 {
 190   return part_of_line_pure_height (me, false, start, end);
 191 }
 192
 193 Interval
 194 Axis_group_interface::combine_pure_heights (Grob *me, SCM measure_extents, int start, int end)
 195 {
 196   Paper_score *ps = get_root_system (me)->paper_score ();
 197   vector<vsize> breaks = ps->get_break_indices ();
 198   vector<Grob *> cols = ps->get_columns ();
 199
 200   Interval ext;
 201   for (vsize i = 0; i + 1 < breaks.size (); i++)
 202     {
 203       int r = Paper_column::get_rank (cols[breaks[i]]);
 204       if (r >= end)
 205         break;
 206
 207       if (r >= start)
 208         ext.unite (ly_scm2interval (scm_c_vector_ref (measure_extents, i)));
 209     }
 210
 211   return ext;
 212 }
 213
 214 // adjacent-pure-heights is a pair of vectors, each of which has one element
 215 // for every measure in the score. The first vector stores, for each measure,
 216 // the combined height of the elements that are present only when the bar
 217 // is at the beginning of a line. The second vector stores, for each measure,
 218 // the combined height of the elements that are present only when the bar
 219 // is not at the beginning of a line.
 220 MAKE_SCHEME_CALLBACK (Axis_group_interface, adjacent_pure_heights, 1)
 221 SCM
 222 Axis_group_interface::adjacent_pure_heights (SCM smob)
 223 {
 224   Grob *me = unsmob_grob (smob);
 225
 226   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 227   extract_grob_set (me, "pure-relevant-grobs", elts);
 228
 229   Paper_score *ps = get_root_system (me)->paper_score ();
 230   vector<vsize> ranks = ps->get_break_ranks ();
 231
 232   vector<Interval> begin_line_heights;
 233   vector<Interval> mid_line_heights;
 234   vector<Interval> begin_line_staff_heights;
 235   vector<Interval> mid_line_staff_heights;
 236   begin_line_heights.resize (ranks.size () - 1);
 237   mid_line_heights.resize (ranks.size () - 1);
 238
 239   for (vsize i = 0; i < elts.size (); ++i)
 240     {
 241       Grob *g = elts[i];
 242
 243       if (to_boolean (g->get_property ("cross-staff")))
 244         continue;
 245
 246       bool outside_staff = scm_is_number (g->get_property ("outside-staff-priority"));
 247       Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), get_default_outside_staff_padding ());
 248
 249       // When we encounter the first outside-staff grob, make a copy
 250       // of the current heights to use as an estimate for the staff heights.
 251       // Note that the outside-staff approximation that we use here doesn't
 252       // consider any collisions that might occur between outside-staff grobs,
 253       // but only the fact that outside-staff grobs may need to be raised above
 254       // the staff.
 255       if (outside_staff && begin_line_staff_heights.empty ())
 256         {
 257           begin_line_staff_heights = begin_line_heights;
 258           mid_line_staff_heights = mid_line_heights;
 259         }
 260
 261       // TODO: consider a pure version of get_grob_direction?
 262       Direction d = to_dir (g->get_property_data ("direction"));
 263       d = (d == CENTER) ? UP : d;
 264
 265       Interval_t<int> rank_span = g->spanned_rank_interval ();
 266       vsize first_break = lower_bound (ranks, (vsize)rank_span[LEFT], less<vsize> ());
 267       if (first_break > 0 && ranks[first_break] >= (vsize)rank_span[LEFT])
 268         first_break--;
 269
 270       for (vsize j = first_break; j + 1 < ranks.size () && (int)ranks[j] <= rank_span[RIGHT]; ++j)
 271         {
 272           int start = ranks[j];
 273           int end = ranks[j + 1];
 274
 275           // Take grobs that are visible with respect to a slightly longer line.
 276           // Otherwise, we will never include grobs at breakpoints which aren't
 277           // end-of-line-visible.
 278           int visibility_end = j + 2 < ranks.size () ? ranks[j + 2] : end;
 279
 280           if (g->pure_is_visible (start, visibility_end))
 281             {
 282               Interval dims = g->pure_height (common, start, end);
 283               if (!dims.is_empty ())
 284                 {
 285                   if (rank_span[LEFT] <= start)
 286                     {
 287                       if (outside_staff)
 288                         begin_line_heights[j].unite (begin_line_staff_heights[j].union_disjoint (dims, padding, d));
 289                       else
 290                         begin_line_heights[j].unite (dims);
 291                     }
 292                   if (rank_span[RIGHT] > start)
 293                     {
 294                       if (outside_staff)
 295                         mid_line_heights[j].unite (mid_line_staff_heights[j].union_disjoint (dims, padding, d));
 296                       else
 297                         mid_line_heights[j].unite (dims);
 298                     }
 299                 }
 300             }
 301         }
 302     }
 303
 304   // Convert begin_line_heights and min_line_heights to SCM.
 305   SCM begin_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 306   SCM mid_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 307   for (vsize i = 0; i < begin_line_heights.size (); ++i)
 308     {
 309       scm_vector_set_x (begin_scm, scm_from_int (i), ly_interval2scm (begin_line_heights[i]));
 310       scm_vector_set_x (mid_scm, scm_from_int (i), ly_interval2scm (mid_line_heights[i]));
 311     }
 312
 313   return scm_cons (begin_scm, mid_scm);
 314 }
 315
 316 Interval
 317 Axis_group_interface::relative_pure_height (Grob *me, int start, int end)
 318 {
 319   /* It saves a _lot_ of time if we assume a VerticalAxisGroup is additive
 320      (ie. height (i, k) = max (height (i, j) height (j, k)) for all i <= j <= k).
 321      Unfortunately, it isn't always true, particularly if there is a
 322      VerticalAlignment somewhere in the descendants.
 323
 324      Usually, the only VerticalAlignment comes from Score. This makes it
 325      reasonably safe to assume that if our parent is a VerticalAlignment,
 326      we can assume additivity and cache things nicely. */
 327   Grob *p = me->get_parent (Y_AXIS);
 328   if (p && Align_interface::has_interface (p))
 329     return Axis_group_interface::sum_partial_pure_heights (me, start, end);
 330
 331   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 332   extract_grob_set (me, "pure-relevant-grobs", elts);
 333
 334   Interval r;
 335   for (vsize i = 0; i < elts.size (); i++)
 336     {
 337       Grob *g = elts[i];
 338       Interval_t<int> rank_span = g->spanned_rank_interval ();
 339       if (rank_span[LEFT] <= end && rank_span[RIGHT] >= start
 340           && g->pure_is_visible (start, end)
 341           && !(to_boolean (g->get_property ("cross-staff"))
 342                && Stem::has_interface (g)))
 343         {
 344           Interval dims = g->pure_height (common, start, end);
 345           if (!dims.is_empty ())
 346             r.unite (dims);
 347         }
 348     }
 349   return r;
 350 }
 351
 352 MAKE_SCHEME_CALLBACK (Axis_group_interface, width, 1);
 353 SCM
 354 Axis_group_interface::width (SCM smob)
 355 {
 356   Grob *me = unsmob_grob (smob);
 357   return generic_group_extent (me, X_AXIS);
 358 }
 359
 360 MAKE_SCHEME_CALLBACK (Axis_group_interface, height, 1);
 361 SCM
 362 Axis_group_interface::height (SCM smob)
 363 {
 364   Grob *me = unsmob_grob (smob);
 365   return generic_group_extent (me, Y_AXIS);
 366 }
 367
 368 MAKE_SCHEME_CALLBACK (Axis_group_interface, pure_height, 3);
 369 SCM
 370 Axis_group_interface::pure_height (SCM smob, SCM start_scm, SCM end_scm)
 371 {
 372   int start = robust_scm2int (start_scm, 0);
 373   int end = robust_scm2int (end_scm, INT_MAX);
 374   Grob *me = unsmob_grob (smob);
 375
 376   /* Maybe we are in the second pass of a two-pass spacing run. In that
 377      case, the Y-extent of a system is already given to us */
 378   System *system = dynamic_cast<System *> (me);
 379   if (system)
 380     {
 381       SCM line_break_details = system->column (start)->get_property ("line-break-system-details");
 382       SCM system_y_extent = scm_assq (ly_symbol2scm ("system-Y-extent"), line_break_details);
 383       if (scm_is_pair (system_y_extent))
 384         return scm_cdr (system_y_extent);
 385     }
 386
 387   return ly_interval2scm (pure_group_height (me, start, end));
 388 }
 389
 390 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_skylines, 1);
 391 SCM
 392 Axis_group_interface::calc_skylines (SCM smob)
 393 {
 394   Grob *me = unsmob_grob (smob);
 395   extract_grob_set (me, Grob_array::unsmob (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", elts);
 396   Skyline_pair skylines = skyline_spacing (me, elts);
 397
 398   return skylines.smobbed_copy ();
 399 }
 400
 401 /* whereas calc_skylines calculates skylines for axis-groups with a lot of
 402    visible children, combine_skylines is designed for axis-groups whose only
 403    children are other axis-groups (ie. VerticalAlignment). Rather than
 404    calculating all the skylines from scratch, we just merge the skylines
 405    of the children.
 406 */
 407 MAKE_SCHEME_CALLBACK (Axis_group_interface, combine_skylines, 1);
 408 SCM
 409 Axis_group_interface::combine_skylines (SCM smob)
 410 {
 411   Grob *me = unsmob_grob (smob);
 412   extract_grob_set (me, "elements", elements);
 413   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 414   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 415
 416   if (y_common != me)
 417     programming_error ("combining skylines that don't belong to me");
 418
 419   Skyline_pair ret;
 420   for (vsize i = 0; i < elements.size (); i++)
 421     {
 422       SCM skyline_scm = elements[i]->get_property ("vertical-skylines");
 423       if (Skyline_pair::unsmob (skyline_scm))
 424         {
 425           Real offset = elements[i]->relative_coordinate (y_common, Y_AXIS);
 426           Skyline_pair other = *Skyline_pair::unsmob (skyline_scm);
 427           other.raise (offset);
 428           other.shift (elements[i]->relative_coordinate (x_common, X_AXIS));
 429           ret.merge (other);
 430         }
 431     }
 432   return ret.smobbed_copy ();
 433 }
 434
 435 SCM
 436 Axis_group_interface::generic_group_extent (Grob *me, Axis a)
 437 {
 438   /* trigger the callback to do skyline-spacing on the children */
 439   if (a == Y_AXIS)
 440     (void) me->get_property ("vertical-skylines");
 441
 442   extract_grob_set (me, "elements", elts);
 443   Grob *common = common_refpoint_of_array (elts, me, a);
 444
 445   Real my_coord = me->relative_coordinate (common, a);
 446   Interval r (relative_group_extent (elts, common, a));
 447
 448   return ly_interval2scm (r - my_coord);
 449 }
 450
 451 /* This is like generic_group_extent, but it only counts the grobs that
 452    are children of some other axis-group. This is uncached; if it becomes
 453    commonly used, it may be necessary to cache it somehow. */
 454 Interval
 455 Axis_group_interface::staff_extent (Grob *me, Grob *refp, Axis ext_a, Grob *staff, Axis parent_a)
 456 {
 457   extract_grob_set (me, "elements", elts);
 458   vector<Grob *> new_elts;
 459
 460   for (vsize i = 0; i < elts.size (); i++)
 461     if (elts[i]->common_refpoint (staff, parent_a) == staff)
 462       new_elts.push_back (elts[i]);
 463
 464   return relative_group_extent (new_elts, refp, ext_a);
 465 }
 466
 467 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_relevant_grobs, 1);
 468 SCM
 469 Axis_group_interface::calc_pure_relevant_grobs (SCM smob)
 470 {
 471   Grob *me = unsmob_grob (smob);
 472   return internal_calc_pure_relevant_grobs (me, "elements");
 473 }
 474
 475 SCM
 476 Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, string grob_set_name)
 477 {
 478   extract_grob_set (me, grob_set_name.c_str (), elts);
 479
 480   vector<Grob *> relevant_grobs;
 481   SCM pure_relevant_p = ly_lily_module_constant ("pure-relevant?");
 482
 483   for (vsize i = 0; i < elts.size (); i++)
 484     {
 485       if (to_boolean (scm_apply_1 (pure_relevant_p, elts[i]->self_scm (), SCM_EOL)))
 486         relevant_grobs.push_back (elts[i]);
 487
 488       if (Item *it = dynamic_cast<Item *> (elts[i]))
 489         {
 490           for (LEFT_and_RIGHT (d))
 491             {
 492               Item *piece = it->find_prebroken_piece (d);
 493               if (piece && to_boolean (scm_apply_1 (pure_relevant_p, piece->self_scm (), SCM_EOL)))
 494                 relevant_grobs.push_back (piece);
 495             }
 496         }
 497     }
 498
 499   vector_sort (relevant_grobs, pure_staff_priority_less);
 500   SCM grobs_scm = Grob_array::make_array ();
 501   unsmob_grob_array (grobs_scm)->set_array (relevant_grobs);
 502
 503   return grobs_scm;
 504 }
 505
 506 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_y_common, 1);
 507 SCM
 508 Axis_group_interface::calc_pure_y_common (SCM smob)
 509 {
 510   Grob *me = unsmob_grob (smob);
 511
 512   extract_grob_set (me, "pure-relevant-grobs", elts);
 513   Grob *common = common_refpoint_of_array (elts, me, Y_AXIS);
 514   if (!common)
 515     {
 516       me->programming_error ("No common parent found in calc_pure_y_common.");
 517       return SCM_EOL;
 518     }
 519
 520   return common->self_scm ();
 521 }
 522
 523 SCM
 524 Axis_group_interface::calc_common (Grob *me, Axis axis)
 525 {
 526   extract_grob_set (me, "elements", elts);
 527   Grob *common = common_refpoint_of_array (elts, me, axis);
 528   if (!common)
 529     {
 530       me->programming_error ("No common parent found in calc_common axis.");
 531       return SCM_EOL;
 532     }
 533
 534   return common->self_scm ();
 535 }
 536
 537 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_x_common, 1);
 538 SCM
 539 Axis_group_interface::calc_x_common (SCM grob)
 540 {
 541   return calc_common (unsmob_grob (grob), X_AXIS);
 542 }
 543
 544 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_y_common, 1);
 545 SCM
 546 Axis_group_interface::calc_y_common (SCM grob)
 547 {
 548   return calc_common (unsmob_grob (grob), Y_AXIS);
 549 }
 550
 551 Interval
 552 Axis_group_interface::pure_group_height (Grob *me, int start, int end)
 553 {
 554   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 555
 556   if (!common)
 557     {
 558       programming_error ("no pure Y common refpoint");
 559       return Interval ();
 560     }
 561   Real my_coord = me->relative_coordinate (common, Y_AXIS);
 562   Interval r (relative_pure_height (me, start, end));
 563
 564   return r - my_coord;
 565 }
 566
 567 void
 568 Axis_group_interface::get_children (Grob *me, vector<Grob *> *found)
 569 {
 570   found->push_back (me);
 571
 572   if (!has_interface (me))
 573     return;
 574
 575   extract_grob_set (me, "elements", elements);
 576   for (vsize i = 0; i < elements.size (); i++)
 577     {
 578       Grob *e = elements[i];
 579       Axis_group_interface::get_children (e, found);
 580     }
 581 }
 582
 583 static bool
 584 staff_priority_less (Grob *const &g1, Grob *const &g2)
 585 {
 586   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 587   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 588
 589   if (priority_1 < priority_2)
 590     return true;
 591   else if (priority_1 > priority_2)
 592     return false;
 593
 594   /* if neither grob has an outside-staff priority, the ordering will have no
 595      effect -- we just need to choose a consistent ordering. We do this to
 596      avoid the side-effect of calculating extents. */
 597   if (isinf (priority_1))
 598     return g1 < g2;
 599
 600   /* if there is no preference in staff priority, choose the left-most one */
 601   Grob *common = g1->common_refpoint (g2, X_AXIS);
 602   Real start_1 = g1->extent (common, X_AXIS)[LEFT];
 603   Real start_2 = g2->extent (common, X_AXIS)[LEFT];
 604   return start_1 < start_2;
 605 }
 606
 607 static bool
 608 pure_staff_priority_less (Grob *const &g1, Grob *const &g2)
 609 {
 610   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 611   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 612
 613   return priority_1 < priority_2;
 614 }
 615
 616 // Raises the grob elt (whose skylines are given by h_skyline
 617 // and v_skyline) so that it doesn't intersect with staff_skyline,
 618 // or with anything in other_h_skylines and other_v_skylines.
 619 void
 620 avoid_outside_staff_collisions (Grob *elt,
 621                                 Skyline_pair *v_skyline,
 622                                 Real padding,
 623                                 Real horizon_padding,
 624                                 vector<Skyline_pair> const &other_v_skylines,
 625                                 vector<Real> const &other_padding,
 626                                 vector<Real> const &other_horizon_padding,
 627                                 Direction const dir)
 628 {
 629   assert (other_v_skylines.size () == other_padding.size ());
 630   assert (other_v_skylines.size () == other_horizon_padding.size ());
 631   vector<Interval> forbidden_intervals;
 632   for (vsize j = 0; j < other_v_skylines.size (); j++)
 633     {
 634       Skyline_pair const &v_other = other_v_skylines[j];
 635       Real pad = (padding + other_padding[j]);
 636       Real horizon_pad = (horizon_padding + other_horizon_padding[j]);
 637
 638       // We need to push elt up by at least this much to be above v_other.
 639       Real up = (*v_skyline)[DOWN].distance (v_other[UP], horizon_pad) + pad;
 640       // We need to push elt down by at least this much to be below v_other.
 641       Real down = (*v_skyline)[UP].distance (v_other[DOWN], horizon_pad) + pad;
 642
 643       forbidden_intervals.push_back (Interval (-down, up));
 644     }
 645
 646   Interval_set allowed_shifts
 647     = Interval_set::interval_union (forbidden_intervals).complement ();
 648   Real move = allowed_shifts.nearest_point (0, dir);
 649   v_skyline->raise (move);
 650   elt->translate_axis (move, Y_AXIS);
 651 }
 652
 653 SCM
 654 valid_outside_staff_placement_directive (Grob *me)
 655 {
 656   SCM directive = me->get_property ("outside-staff-placement-directive");
 657
 658   if ((directive == ly_symbol2scm ("left-to-right-greedy"))
 659       || (directive == ly_symbol2scm ("left-to-right-polite"))
 660       || (directive == ly_symbol2scm ("right-to-left-greedy"))
 661       || (directive == ly_symbol2scm ("right-to-left-polite")))
 662     return directive;
 663
 664   me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive",
 665                    robust_symbol2string (directive, "").c_str ()));
 666
 667   return ly_symbol2scm ("left-to-right-polite");
 668 }
 669
 670 // Shifts the grobs in elements to ensure that they (and any
 671 // connected riders) don't collide with the staff skylines
 672 // or anything in all_X_skylines.  Afterwards, the skylines
 673 // of the grobs in elements will be added to all_v_skylines.
 674 static void
 675 add_grobs_of_one_priority (Grob *me,
 676                            Drul_array<vector<Skyline_pair> > *all_v_skylines,
 677                            Drul_array<vector<Real> > *all_paddings,
 678                            Drul_array<vector<Real> > *all_horizon_paddings,
 679                            vector<Grob *> elements,
 680                            Grob *x_common,
 681                            Grob *y_common,
 682                            multimap<Grob *, Grob *> const &riders)
 683 {
 684
 685   SCM directive
 686     = valid_outside_staff_placement_directive (me);
 687
 688   bool l2r = ((directive == ly_symbol2scm ("left-to-right-greedy"))
 689               || (directive == ly_symbol2scm ("left-to-right-polite")));
 690
 691   bool polite = ((directive == ly_symbol2scm ("left-to-right-polite"))
 692                  || (directive == ly_symbol2scm ("right-to-left-polite")));
 693
 694   vector<Box> boxes;
 695   vector<Skyline_pair> skylines_to_merge;
 696
 697   // We want to avoid situations like this:
 698   //           still more text
 699   //      more text
 700   //   text
 701   //   -------------------
 702   //   staff
 703   //   -------------------
 704
 705   // The point is that "still more text" should be positioned under
 706   // "more text".  In order to achieve this, we place the grobs in several
 707   // passes.  We keep track of the right-most horizontal position that has been
 708   // affected by the current pass so far (actually we keep track of 2
 709   // positions, one for above the staff, one for below).
 710
 711   // In each pass, we loop through the unplaced grobs from left to right.
 712   // If the grob doesn't overlap the right-most affected position, we place it
 713   // (and then update the right-most affected position to point to the right
 714   // edge of the just-placed grob).  Otherwise, we skip it until the next pass.
 715   while (!elements.empty ())
 716     {
 717       Drul_array<Real> last_end (-infinity_f, -infinity_f);
 718       vector<Grob *> skipped_elements;
 719       for (vsize i = l2r ? 0 : elements.size ();
 720            l2r ? i < elements.size () : i--;
 721            l2r ? i++ : 0)
 722         {
 723           Grob *elt = elements[i];
 724           Real padding
 725             = robust_scm2double (elt->get_property ("outside-staff-padding"), 0.25);
 726           Real horizon_padding
 727             = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0);
 728           Interval x_extent = elt->extent (x_common, X_AXIS);
 729           x_extent.widen (horizon_padding);
 730
 731           Direction dir = get_grob_direction (elt);
 732           if (dir == CENTER)
 733             {
 734               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
 735               dir = UP;
 736             }
 737
 738           if (x_extent[LEFT] <= last_end[dir] && polite)
 739             {
 740               skipped_elements.push_back (elt);
 741               continue;
 742             }
 743           last_end[dir] = x_extent[RIGHT];
 744
 745           Skyline_pair *v_orig = Skyline_pair::unsmob (elt->get_property ("vertical-skylines"));
 746           if (v_orig->is_empty ())
 747             continue;
 748
 749           // Find the riders associated with this grob, and merge their
 750           // skylines with elt's skyline.
 751           typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator;
 752           pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt);
 753           vector<Skyline_pair> rider_v_skylines;
 754           for (GrobMapIterator j = range.first; j != range.second; j++)
 755             {
 756               Grob *rider = j->second;
 757               Skyline_pair *v_rider = Skyline_pair::unsmob (rider->get_property ("vertical-skylines"));
 758               if (v_rider)
 759                 {
 760                   Skyline_pair copy (*v_rider);
 761                   copy.shift (rider->relative_coordinate (x_common, X_AXIS));
 762                   copy.raise (rider->relative_coordinate (y_common, Y_AXIS));
 763                   rider_v_skylines.push_back (copy);
 764                 }
 765             }
 766           Skyline_pair v_skylines (*v_orig);
 767           v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS));
 768           v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS));
 769           v_skylines.merge (Skyline_pair (rider_v_skylines));
 770
 771           avoid_outside_staff_collisions (elt,
 772                                           &v_skylines,
 773                                           padding,
 774                                           horizon_padding,
 775                                           (*all_v_skylines)[dir],
 776                                           (*all_paddings)[dir],
 777                                           (*all_horizon_paddings)[dir],
 778                                           dir);
 779
 780           elt->set_property ("outside-staff-priority", SCM_BOOL_F);
 781           (*all_v_skylines)[dir].push_back (v_skylines);
 782           (*all_paddings)[dir].push_back (padding);
 783           (*all_horizon_paddings)[dir].push_back (horizon_padding);
 784         }
 785       swap (elements, skipped_elements);
 786       skipped_elements.clear ();
 787     }
 788 }
 789
 790 // If the Grob has a Y-ancestor with outside-staff-priority, return it.
 791 // Otherwise, return 0.
 792 Grob *
 793 Axis_group_interface::outside_staff_ancestor (Grob *me)
 794 {
 795   Grob *parent = me->get_parent (Y_AXIS);
 796   if (!parent)
 797     return 0;
 798
 799   if (scm_is_number (parent->get_property ("outside-staff-priority")))
 800     return parent;
 801
 802   return outside_staff_ancestor (parent);
 803 }
 804
 805 void
 806 Axis_group_interface::add_interior_skylines
 807 (Grob *me, Grob *x_common, Grob *y_common, vector<Skyline_pair> *skylines, bool pure)
 808 {
 809   if (Grob_array *elements = unsmob_grob_array (me->get_object ("elements")))
 810     {
 811       for (vsize i = 0; i < elements->size (); i++)
 812         add_interior_skylines (elements->grob (i), x_common, y_common, skylines, pure);
 813     }
 814   else if (pure ||
 815            (!scm_is_number (me->get_property ("outside-staff-priority"))
 816             && !to_boolean (me->get_property ("cross-staff"))))
 817     {
 818       Skyline_pair *maybe_pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines"));
 819       if (!maybe_pair)
 820         return;
 821       if (maybe_pair->is_empty ())
 822         return;
 823       skylines->push_back (Skyline_pair (*maybe_pair));
 824       skylines->back ().shift (me->relative_coordinate (x_common, X_AXIS));
 825       skylines->back ().raise (me->maybe_pure_coordinate (y_common, Y_AXIS, pure, 0, INT_MAX));
 826     }
 827 }
 828
 829 // It is tricky to correctly handle skyline placement of cross-staff grobs.
 830 // For example, cross-staff beams cannot be formatted until the distance between
 831 // staves is known and therefore any grobs that depend on the beam cannot be placed
 832 // until the skylines are known. On the other hand, the distance between staves should
 833 // really depend on position of the cross-staff grobs that lie between them.
 834 // Currently, we just leave cross-staff grobs out of the
 835 // skyline altogether, but this could mean that staves are placed so close together
 836 // that there is no room for the cross-staff grob. It also means, of course, that
 837 // we don't get the benefits of skyline placement for cross-staff grobs.
 838 Skyline_pair
 839 Axis_group_interface::skyline_spacing (Grob *me, vector<Grob *> elements)
 840 {
 841   for (vsize i = 0; i < elements.size (); i++)
 842     /*
 843       As a sanity check, we make sure that no grob with an outside staff priority
 844       has a Y-parent that also has an outside staff priority, which would result
 845       in two movings.
 846     */
 847     if (scm_is_number (elements[i]->get_property ("outside-staff-priority"))
 848         && outside_staff_ancestor (elements[i]))
 849       {
 850         elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent.");
 851         elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
 852       }
 853
 854   /* For grobs with an outside-staff-priority, the sorting function might
 855      call extent and cause suicide. This breaks the contract that is required
 856      for the STL sort function. To avoid this, we make sure that any suicides
 857      are triggered beforehand.
 858   */
 859   for (vsize i = 0; i < elements.size (); i++)
 860     if (scm_is_number (elements[i]->get_property ("outside-staff-priority")))
 861       elements[i]->extent (elements[i], X_AXIS);
 862
 863   vector_sort (elements, staff_priority_less);
 864   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 865   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 866
 867   assert (y_common == me);
 868
 869   // A rider is a grob that is not outside-staff, but has an outside-staff
 870   // ancestor.  In that case, the rider gets moved along with its ancestor.
 871   multimap<Grob *, Grob *> riders;
 872
 873   vsize i = 0;
 874   vector<Skyline_pair> inside_staff_skylines;
 875   for (i = 0; i < elements.size ()
 876        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
 877     {
 878       Grob *elt = elements[i];
 879       Grob *ancestor = outside_staff_ancestor (elt);
 880       if (!(to_boolean (elt->get_property ("cross-staff")) || ancestor)
 881           || elt->internal_has_interface (ly_symbol2scm ("cross-staff-stub-interface")))
 882         add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines, elt->internal_has_interface (ly_symbol2scm ("cross-staff-stub-interface")));
 883       if (ancestor)
 884         riders.insert (pair<Grob *, Grob *> (ancestor, elt));
 885     }
 886
 887   Skyline_pair skylines (inside_staff_skylines);
 888
 889   // These are the skylines of all outside-staff grobs
 890   // that have already been processed.  We keep them around in order to
 891   // check them for collisions with the currently active outside-staff grob.
 892   Drul_array<vector<Skyline_pair> > all_v_skylines;
 893   Drul_array<vector<Real> > all_paddings;
 894   Drul_array<vector<Real> > all_horizon_paddings;
 895   for (UP_and_DOWN (d))
 896     {
 897       all_v_skylines[d].push_back (skylines);
 898       all_paddings[d].push_back (0);
 899       all_horizon_paddings[d].push_back (0);
 900     }
 901
 902   for (; i < elements.size (); i++)
 903     {
 904       if (to_boolean (elements[i]->get_property ("cross-staff")))
 905         continue;
 906
 907       // Collect all the outside-staff grobs that have a particular priority.
 908       SCM priority = elements[i]->get_property ("outside-staff-priority");
 909       vector<Grob *> current_elts;
 910       current_elts.push_back (elements[i]);
 911       while (i + 1 < elements.size ()
 912              && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
 913         {
 914           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
 915             current_elts.push_back (elements[i + 1]);
 916           ++i;
 917         }
 918
 919       add_grobs_of_one_priority (me,
 920                                  &all_v_skylines,
 921                                  &all_paddings,
 922                                  &all_horizon_paddings,
 923                                  current_elts,
 924                                  x_common,
 925                                  y_common,
 926                                  riders);
 927     }
 928
 929   // Now everything in all_v_skylines has been shifted appropriately; merge
 930   // them all into skylines to get the complete outline.
 931   Skyline_pair other_skylines (all_v_skylines[UP]);
 932   other_skylines.merge (Skyline_pair (all_v_skylines[DOWN]));
 933   skylines.merge (other_skylines);
 934
 935   // We began by shifting my skyline to be relative to the common refpoint; now
 936   // shift it back.
 937   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
 938
 939   return skylines;
 940 }
 941
 942 MAKE_SCHEME_CALLBACK (Axis_group_interface, print, 1)
 943 SCM
 944 Axis_group_interface::print (SCM smob)
 945 {
 946   if (!debug_skylines)
 947     return SCM_BOOL_F;
 948
 949   Grob *me = unsmob_grob (smob);
 950   Stencil ret;
 951   if (Skyline_pair *s = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
 952     {
 953       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
 954                        .in_color (255, 0, 255));
 955       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[DOWN].to_points (X_AXIS))
 956                        .in_color (0, 255, 255));
 957     }
 958   return ret.smobbed_copy ();
 959 }
 960
 961 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
 962 SCM
 963 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
 964 {
 965   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 966                                               true,
 967                                               scm_to_int (start),
 968                                               scm_to_int (end));
 969 }
 970
 971 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
 972 SCM
 973 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
 974 {
 975   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 976                                               false,
 977                                               0,
 978                                               INT_MAX);
 979 }
 980
 981 SCM
 982 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
 983 {
 984   Grob *grouper = unsmob_grob (me->get_object ("staff-grouper"));
 985
 986   if (grouper)
 987     {
 988       bool within_group = Staff_grouper_interface::maybe_pure_within_group (grouper, me, pure, start, end);
 989       if (within_group)
 990         return grouper->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
 991       else
 992         return grouper->get_maybe_pure_property ("staffgroup-staff-spacing", pure, start, end);
 993     }
 994   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
 995 }
 996
 997 ADD_INTERFACE (Axis_group_interface,
 998                "An object that groups other layout objects.",
 999
1000                // TODO: some of these properties are specific to
1001                // VerticalAxisGroup. We should split off a
1002                // vertical-axis-group-interface.
1003                /* properties */
1004                "adjacent-pure-heights "
1005                "axes "
1006                "bound-alignment-interfaces "
1007                "default-staff-staff-spacing "
1008                "elements "
1009                "max-stretch "
1010                "no-alignment "
1011                "nonstaff-nonstaff-spacing "
1012                "nonstaff-relatedstaff-spacing "
1013                "nonstaff-unrelatedstaff-spacing "
1014                "outside-staff-placement-directive "
1015                "pure-relevant-grobs "
1016                "pure-relevant-items "
1017                "pure-relevant-spanners "
1018                "pure-Y-common "
1019                "staff-affinity "
1020                "staff-grouper "
1021                "staff-staff-spacing "
1022                "system-Y-offset "
1023                "vertical-skyline-elements "
1024                "X-common "
1025                "Y-common "
1026               );