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       if (!g->is_live ())
 247         continue;
 248
 249       bool outside_staff = scm_is_number (g->get_property ("outside-staff-priority"));
 250       Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), get_default_outside_staff_padding ());
 251
 252       // When we encounter the first outside-staff grob, make a copy
 253       // of the current heights to use as an estimate for the staff heights.
 254       // Note that the outside-staff approximation that we use here doesn't
 255       // consider any collisions that might occur between outside-staff grobs,
 256       // but only the fact that outside-staff grobs may need to be raised above
 257       // the staff.
 258       if (outside_staff && begin_line_staff_heights.empty ())
 259         {
 260           begin_line_staff_heights = begin_line_heights;
 261           mid_line_staff_heights = mid_line_heights;
 262         }
 263
 264       // TODO: consider a pure version of get_grob_direction?
 265       Direction d = to_dir (g->get_property_data ("direction"));
 266       d = (d == CENTER) ? UP : d;
 267
 268       Interval_t<int> rank_span = g->spanned_rank_interval ();
 269       vsize first_break = lower_bound (ranks, (vsize)rank_span[LEFT], less<vsize> ());
 270       if (first_break > 0 && ranks[first_break] >= (vsize)rank_span[LEFT])
 271         first_break--;
 272
 273       for (vsize j = first_break; j + 1 < ranks.size () && (int)ranks[j] <= rank_span[RIGHT]; ++j)
 274         {
 275           int start = ranks[j];
 276           int end = ranks[j + 1];
 277
 278           // Take grobs that are visible with respect to a slightly longer line.
 279           // Otherwise, we will never include grobs at breakpoints which aren't
 280           // end-of-line-visible.
 281           int visibility_end = j + 2 < ranks.size () ? ranks[j + 2] : end;
 282
 283           if (g->pure_is_visible (start, visibility_end))
 284             {
 285               Interval dims = g->pure_height (common, start, end);
 286               if (!dims.is_empty ())
 287                 {
 288                   if (rank_span[LEFT] <= start)
 289                     {
 290                       if (outside_staff)
 291                         begin_line_heights[j].unite (begin_line_staff_heights[j].union_disjoint (dims, padding, d));
 292                       else
 293                         begin_line_heights[j].unite (dims);
 294                     }
 295                   if (rank_span[RIGHT] > start)
 296                     {
 297                       if (outside_staff)
 298                         mid_line_heights[j].unite (mid_line_staff_heights[j].union_disjoint (dims, padding, d));
 299                       else
 300                         mid_line_heights[j].unite (dims);
 301                     }
 302                 }
 303             }
 304         }
 305     }
 306
 307   // Convert begin_line_heights and min_line_heights to SCM.
 308   SCM begin_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 309   SCM mid_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 310   for (vsize i = 0; i < begin_line_heights.size (); ++i)
 311     {
 312       scm_vector_set_x (begin_scm, scm_from_int (i), ly_interval2scm (begin_line_heights[i]));
 313       scm_vector_set_x (mid_scm, scm_from_int (i), ly_interval2scm (mid_line_heights[i]));
 314     }
 315
 316   return scm_cons (begin_scm, mid_scm);
 317 }
 318
 319 Interval
 320 Axis_group_interface::relative_pure_height (Grob *me, int start, int end)
 321 {
 322   /* It saves a _lot_ of time if we assume a VerticalAxisGroup is additive
 323      (ie. height (i, k) = max (height (i, j) height (j, k)) for all i <= j <= k).
 324      Unfortunately, it isn't always true, particularly if there is a
 325      VerticalAlignment somewhere in the descendants.
 326
 327      Usually, the only VerticalAlignment comes from Score. This makes it
 328      reasonably safe to assume that if our parent is a VerticalAlignment,
 329      we can assume additivity and cache things nicely. */
 330   Grob *p = me->get_parent (Y_AXIS);
 331   if (p && Align_interface::has_interface (p))
 332     return Axis_group_interface::sum_partial_pure_heights (me, start, end);
 333
 334   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 335   extract_grob_set (me, "pure-relevant-grobs", elts);
 336
 337   Interval r;
 338   for (vsize i = 0; i < elts.size (); i++)
 339     {
 340       Grob *g = elts[i];
 341       Interval_t<int> rank_span = g->spanned_rank_interval ();
 342       if (rank_span[LEFT] <= end && rank_span[RIGHT] >= start
 343           && g->pure_is_visible (start, end)
 344           && !(to_boolean (g->get_property ("cross-staff"))
 345                && Stem::has_interface (g)))
 346         {
 347           Interval dims = g->pure_height (common, start, end);
 348           if (!dims.is_empty ())
 349             r.unite (dims);
 350         }
 351     }
 352   return r;
 353 }
 354
 355 MAKE_SCHEME_CALLBACK (Axis_group_interface, width, 1);
 356 SCM
 357 Axis_group_interface::width (SCM smob)
 358 {
 359   Grob *me = unsmob_grob (smob);
 360   return generic_group_extent (me, X_AXIS);
 361 }
 362
 363 MAKE_SCHEME_CALLBACK (Axis_group_interface, height, 1);
 364 SCM
 365 Axis_group_interface::height (SCM smob)
 366 {
 367   Grob *me = unsmob_grob (smob);
 368   return generic_group_extent (me, Y_AXIS);
 369 }
 370
 371 MAKE_SCHEME_CALLBACK (Axis_group_interface, pure_height, 3);
 372 SCM
 373 Axis_group_interface::pure_height (SCM smob, SCM start_scm, SCM end_scm)
 374 {
 375   int start = robust_scm2int (start_scm, 0);
 376   int end = robust_scm2int (end_scm, INT_MAX);
 377   Grob *me = unsmob_grob (smob);
 378
 379   /* Maybe we are in the second pass of a two-pass spacing run. In that
 380      case, the Y-extent of a system is already given to us */
 381   System *system = dynamic_cast<System *> (me);
 382   if (system)
 383     {
 384       SCM line_break_details = system->column (start)->get_property ("line-break-system-details");
 385       SCM system_y_extent = scm_assq (ly_symbol2scm ("system-Y-extent"), line_break_details);
 386       if (scm_is_pair (system_y_extent))
 387         return scm_cdr (system_y_extent);
 388     }
 389
 390   return ly_interval2scm (pure_group_height (me, start, end));
 391 }
 392
 393 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_skylines, 1);
 394 SCM
 395 Axis_group_interface::calc_skylines (SCM smob)
 396 {
 397   Grob *me = unsmob_grob (smob);
 398   Skyline_pair skylines = skyline_spacing (me);
 399   return skylines.smobbed_copy ();
 400 }
 401
 402 /* whereas calc_skylines calculates skylines for axis-groups with a lot of
 403    visible children, combine_skylines is designed for axis-groups whose only
 404    children are other axis-groups (ie. VerticalAlignment). Rather than
 405    calculating all the skylines from scratch, we just merge the skylines
 406    of the children.
 407 */
 408 MAKE_SCHEME_CALLBACK (Axis_group_interface, combine_skylines, 1);
 409 SCM
 410 Axis_group_interface::combine_skylines (SCM smob)
 411 {
 412   Grob *me = unsmob_grob (smob);
 413   extract_grob_set (me, "elements", elements);
 414   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 415   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 416
 417   if (y_common != me)
 418     programming_error ("combining skylines that don't belong to me");
 419
 420   Skyline_pair ret;
 421   for (vsize i = 0; i < elements.size (); i++)
 422     {
 423       SCM skyline_scm = elements[i]->get_property ("vertical-skylines");
 424       if (Skyline_pair::unsmob (skyline_scm))
 425         {
 426           Real offset = elements[i]->relative_coordinate (y_common, Y_AXIS);
 427           Skyline_pair other = *Skyline_pair::unsmob (skyline_scm);
 428           other.raise (offset);
 429           other.shift (elements[i]->relative_coordinate (x_common, X_AXIS));
 430           ret.merge (other);
 431         }
 432     }
 433   return ret.smobbed_copy ();
 434 }
 435
 436 SCM
 437 Axis_group_interface::generic_group_extent (Grob *me, Axis a)
 438 {
 439   extract_grob_set (me, "elements", elts);
 440
 441   /* trigger the callback to do skyline-spacing on the children */
 442   if (a == Y_AXIS)
 443     for (vsize i = 0; i < elts.size (); i++)
 444       if (!(Stem::has_interface (elts[i])
 445             && to_boolean (elts[i]->get_property ("cross-staff"))))
 446         (void) elts[i]->get_property ("vertical-skylines");
 447
 448   Grob *common = common_refpoint_of_array (elts, me, a);
 449
 450   Real my_coord = me->relative_coordinate (common, a);
 451   Interval r (relative_group_extent (elts, common, a));
 452
 453   return ly_interval2scm (r - my_coord);
 454 }
 455
 456 /* This is like generic_group_extent, but it only counts the grobs that
 457    are children of some other axis-group. This is uncached; if it becomes
 458    commonly used, it may be necessary to cache it somehow. */
 459 Interval
 460 Axis_group_interface::staff_extent (Grob *me, Grob *refp, Axis ext_a, Grob *staff, Axis parent_a)
 461 {
 462   extract_grob_set (me, "elements", elts);
 463   vector<Grob *> new_elts;
 464
 465   for (vsize i = 0; i < elts.size (); i++)
 466     if (elts[i]->common_refpoint (staff, parent_a) == staff)
 467       new_elts.push_back (elts[i]);
 468
 469   return relative_group_extent (new_elts, refp, ext_a);
 470 }
 471
 472 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_relevant_grobs, 1);
 473 SCM
 474 Axis_group_interface::calc_pure_relevant_grobs (SCM smob)
 475 {
 476   Grob *me = unsmob_grob (smob);
 477   return internal_calc_pure_relevant_grobs (me, "elements");
 478 }
 479
 480 SCM
 481 Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, string grob_set_name)
 482 {
 483   extract_grob_set (me, grob_set_name.c_str (), elts);
 484
 485   vector<Grob *> relevant_grobs;
 486
 487   for (vsize i = 0; i < elts.size (); i++)
 488     {
 489       if (elts[i] && elts[i]->is_live ())
 490         {
 491           relevant_grobs.push_back (elts[i]);
 492           if (Item *it = dynamic_cast<Item *> (elts[i]))
 493             {
 494               for (LEFT_and_RIGHT (d))
 495                 {
 496                   Item *piece = it->find_prebroken_piece (d);
 497                   if (piece && piece->is_live ())
 498                     relevant_grobs.push_back (piece);
 499                 }
 500             }
 501         }
 502     }
 503
 504   vector_sort (relevant_grobs, pure_staff_priority_less);
 505   SCM grobs_scm = Grob_array::make_array ();
 506   unsmob_grob_array (grobs_scm)->set_array (relevant_grobs);
 507
 508   return grobs_scm;
 509 }
 510
 511 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_y_common, 1);
 512 SCM
 513 Axis_group_interface::calc_pure_y_common (SCM smob)
 514 {
 515   Grob *me = unsmob_grob (smob);
 516
 517   extract_grob_set (me, "pure-relevant-grobs", elts);
 518   Grob *common = common_refpoint_of_array (elts, me, Y_AXIS);
 519   if (!common)
 520     {
 521       me->programming_error ("No common parent found in calc_pure_y_common.");
 522       return SCM_EOL;
 523     }
 524
 525   return common->self_scm ();
 526 }
 527
 528 SCM
 529 Axis_group_interface::calc_common (Grob *me, Axis axis)
 530 {
 531   extract_grob_set (me, "elements", elts);
 532   Grob *common = common_refpoint_of_array (elts, me, axis);
 533   if (!common)
 534     {
 535       me->programming_error ("No common parent found in calc_common axis.");
 536       return SCM_EOL;
 537     }
 538
 539   return common->self_scm ();
 540 }
 541
 542 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_x_common, 1);
 543 SCM
 544 Axis_group_interface::calc_x_common (SCM grob)
 545 {
 546   return calc_common (unsmob_grob (grob), X_AXIS);
 547 }
 548
 549 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_y_common, 1);
 550 SCM
 551 Axis_group_interface::calc_y_common (SCM grob)
 552 {
 553   return calc_common (unsmob_grob (grob), Y_AXIS);
 554 }
 555
 556 Interval
 557 Axis_group_interface::pure_group_height (Grob *me, int start, int end)
 558 {
 559   Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
 560
 561   if (!common)
 562     {
 563       programming_error ("no pure Y common refpoint");
 564       return Interval ();
 565     }
 566   Real my_coord = me->pure_relative_y_coordinate (common, start, end);
 567   Interval r (relative_pure_height (me, start, end));
 568
 569   return r - my_coord;
 570 }
 571
 572 void
 573 Axis_group_interface::get_children (Grob *me, vector<Grob *> *found)
 574 {
 575   found->push_back (me);
 576
 577   if (!has_interface (me))
 578     return;
 579
 580   extract_grob_set (me, "elements", elements);
 581   for (vsize i = 0; i < elements.size (); i++)
 582     {
 583       Grob *e = elements[i];
 584       Axis_group_interface::get_children (e, found);
 585     }
 586 }
 587
 588 static bool
 589 staff_priority_less (Grob *const &g1, Grob *const &g2)
 590 {
 591   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 592   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 593
 594   if (priority_1 < priority_2)
 595     return true;
 596   else if (priority_1 > priority_2)
 597     return false;
 598
 599   /* if neither grob has an outside-staff priority, the ordering will have no
 600      effect -- we just need to choose a consistent ordering. We do this to
 601      avoid the side-effect of calculating extents. */
 602   if (isinf (priority_1))
 603     return g1 < g2;
 604
 605   /* if there is no preference in staff priority, choose the left-most one */
 606   Grob *common = g1->common_refpoint (g2, X_AXIS);
 607   Real start_1 = g1->extent (common, X_AXIS)[LEFT];
 608   Real start_2 = g2->extent (common, X_AXIS)[LEFT];
 609   return start_1 < start_2;
 610 }
 611
 612 static bool
 613 pure_staff_priority_less (Grob *const &g1, Grob *const &g2)
 614 {
 615   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 616   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 617
 618   return priority_1 < priority_2;
 619 }
 620
 621 static void
 622 add_interior_skylines (Grob *me, Grob *x_common, Grob *y_common, vector<Skyline_pair> *skylines)
 623 {
 624   if (Grob_array *elements = unsmob_grob_array (me->get_object ("elements")))
 625     {
 626       for (vsize i = 0; i < elements->size (); i++)
 627         add_interior_skylines (elements->grob (i), x_common, y_common, skylines);
 628     }
 629   else if (!scm_is_number (me->get_property ("outside-staff-priority"))
 630            && !to_boolean (me->get_property ("cross-staff")))
 631     {
 632       Skyline_pair *maybe_pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines"));
 633       if (!maybe_pair)
 634         return;
 635       if (maybe_pair->is_empty ())
 636         return;
 637       skylines->push_back (Skyline_pair (*maybe_pair));
 638       skylines->back ().shift (me->relative_coordinate (x_common, X_AXIS));
 639       skylines->back ().raise (me->relative_coordinate (y_common, Y_AXIS));
 640     }
 641 }
 642
 643 // Raises the grob elt (whose skylines are given by h_skyline
 644 // and v_skyline) so that it doesn't intersect with staff_skyline,
 645 // or with anything in other_h_skylines and other_v_skylines.
 646 void
 647 avoid_outside_staff_collisions (Grob *elt,
 648                                 Skyline_pair *v_skyline,
 649                                 Real padding,
 650                                 Real horizon_padding,
 651                                 vector<Skyline_pair> const &other_v_skylines,
 652                                 vector<Real> const &other_padding,
 653                                 vector<Real> const &other_horizon_padding,
 654                                 Direction const dir)
 655 {
 656   assert (other_v_skylines.size () == other_padding.size ());
 657   assert (other_v_skylines.size () == other_horizon_padding.size ());
 658   vector<Interval> forbidden_intervals;
 659   for (vsize j = 0; j < other_v_skylines.size (); j++)
 660     {
 661       Skyline_pair const &v_other = other_v_skylines[j];
 662       Real pad = (padding + other_padding[j]);
 663       Real horizon_pad = (horizon_padding + other_horizon_padding[j]);
 664
 665       // We need to push elt up by at least this much to be above v_other.
 666       Real up = (*v_skyline)[DOWN].distance (v_other[UP], horizon_pad) + pad;
 667       // We need to push elt down by at least this much to be below v_other.
 668       Real down = (*v_skyline)[UP].distance (v_other[DOWN], horizon_pad) + pad;
 669
 670       forbidden_intervals.push_back (Interval (-down, up));
 671     }
 672
 673   Interval_set allowed_shifts
 674     = Interval_set::interval_union (forbidden_intervals).complement ();
 675   Real move = allowed_shifts.nearest_point (0, dir);
 676   v_skyline->raise (move);
 677   elt->translate_axis (move, Y_AXIS);
 678 }
 679
 680 SCM
 681 valid_outside_staff_placement_directive (Grob *me)
 682 {
 683   SCM directive = me->get_property ("outside-staff-placement-directive");
 684
 685   if ((directive == ly_symbol2scm ("left-to-right-greedy"))
 686       || (directive == ly_symbol2scm ("left-to-right-polite"))
 687       || (directive == ly_symbol2scm ("right-to-left-greedy"))
 688       || (directive == ly_symbol2scm ("right-to-left-polite")))
 689     return directive;
 690
 691   me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive",
 692                    robust_symbol2string (directive, "").c_str ()));
 693
 694   return ly_symbol2scm ("left-to-right-polite");
 695 }
 696
 697 // Shifts the grobs in elements to ensure that they (and any
 698 // connected riders) don't collide with the staff skylines
 699 // or anything in all_X_skylines.  Afterwards, the skylines
 700 // of the grobs in elements will be added to all_v_skylines.
 701 static void
 702 add_grobs_of_one_priority (Grob *me,
 703                            Drul_array<vector<Skyline_pair> > *all_v_skylines,
 704                            Drul_array<vector<Real> > *all_paddings,
 705                            Drul_array<vector<Real> > *all_horizon_paddings,
 706                            vector<Grob *> elements,
 707                            Grob *x_common,
 708                            Grob *y_common,
 709                            multimap<Grob *, Grob *> const &riders)
 710 {
 711
 712   SCM directive
 713     = valid_outside_staff_placement_directive (me);
 714
 715   bool l2r = ((directive == ly_symbol2scm ("left-to-right-greedy"))
 716               || (directive == ly_symbol2scm ("left-to-right-polite")));
 717
 718   bool polite = ((directive == ly_symbol2scm ("left-to-right-polite"))
 719                  || (directive == ly_symbol2scm ("right-to-left-polite")));
 720
 721   vector<Box> boxes;
 722   vector<Skyline_pair> skylines_to_merge;
 723
 724   // We want to avoid situations like this:
 725   //           still more text
 726   //      more text
 727   //   text
 728   //   -------------------
 729   //   staff
 730   //   -------------------
 731
 732   // The point is that "still more text" should be positioned under
 733   // "more text".  In order to achieve this, we place the grobs in several
 734   // passes.  We keep track of the right-most horizontal position that has been
 735   // affected by the current pass so far (actually we keep track of 2
 736   // positions, one for above the staff, one for below).
 737
 738   // In each pass, we loop through the unplaced grobs from left to right.
 739   // If the grob doesn't overlap the right-most affected position, we place it
 740   // (and then update the right-most affected position to point to the right
 741   // edge of the just-placed grob).  Otherwise, we skip it until the next pass.
 742   while (!elements.empty ())
 743     {
 744       Drul_array<Real> last_end (-infinity_f, -infinity_f);
 745       vector<Grob *> skipped_elements;
 746       for (vsize i = l2r ? 0 : elements.size ();
 747            l2r ? i < elements.size () : i--;
 748            l2r ? i++ : 0)
 749         {
 750           Grob *elt = elements[i];
 751           Real padding
 752             = robust_scm2double (elt->get_property ("outside-staff-padding"), 0.25);
 753           Real horizon_padding
 754             = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0);
 755           Interval x_extent = elt->extent (x_common, X_AXIS);
 756           x_extent.widen (horizon_padding);
 757
 758           Direction dir = get_grob_direction (elt);
 759           if (dir == CENTER)
 760             {
 761               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
 762               dir = UP;
 763             }
 764
 765           if (x_extent[LEFT] <= last_end[dir] && polite)
 766             {
 767               skipped_elements.push_back (elt);
 768               continue;
 769             }
 770           last_end[dir] = x_extent[RIGHT];
 771
 772           Skyline_pair *v_orig = Skyline_pair::unsmob (elt->get_property ("vertical-skylines"));
 773           if (v_orig->is_empty ())
 774             continue;
 775
 776           // Find the riders associated with this grob, and merge their
 777           // skylines with elt's skyline.
 778           typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator;
 779           pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt);
 780           vector<Skyline_pair> rider_v_skylines;
 781           for (GrobMapIterator j = range.first; j != range.second; j++)
 782             {
 783               Grob *rider = j->second;
 784               Skyline_pair *v_rider = Skyline_pair::unsmob (rider->get_property ("vertical-skylines"));
 785               if (v_rider)
 786                 {
 787                   Skyline_pair copy (*v_rider);
 788                   copy.shift (rider->relative_coordinate (x_common, X_AXIS));
 789                   copy.raise (rider->relative_coordinate (y_common, Y_AXIS));
 790                   rider_v_skylines.push_back (copy);
 791                 }
 792             }
 793           Skyline_pair v_skylines (*v_orig);
 794           v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS));
 795           v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS));
 796           v_skylines.merge (Skyline_pair (rider_v_skylines));
 797
 798           avoid_outside_staff_collisions (elt,
 799                                           &v_skylines,
 800                                           padding,
 801                                           horizon_padding,
 802                                           (*all_v_skylines)[dir],
 803                                           (*all_paddings)[dir],
 804                                           (*all_horizon_paddings)[dir],
 805                                           dir);
 806
 807           elt->set_property ("outside-staff-priority", SCM_BOOL_F);
 808           (*all_v_skylines)[dir].push_back (v_skylines);
 809           (*all_paddings)[dir].push_back (padding);
 810           (*all_horizon_paddings)[dir].push_back (horizon_padding);
 811         }
 812       swap (elements, skipped_elements);
 813       skipped_elements.clear ();
 814     }
 815 }
 816
 817 // If the Grob has a Y-ancestor with outside-staff-priority, return it.
 818 // Otherwise, return 0.
 819 Grob *
 820 Axis_group_interface::outside_staff_ancestor (Grob *me)
 821 {
 822   Grob *parent = me->get_parent (Y_AXIS);
 823   if (!parent)
 824     return 0;
 825
 826   if (scm_is_number (parent->get_property ("outside-staff-priority")))
 827     return parent;
 828
 829   return outside_staff_ancestor (parent);
 830 }
 831
 832 // It is tricky to correctly handle skyline placement of cross-staff grobs.
 833 // For example, cross-staff beams cannot be formatted until the distance between
 834 // staves is known and therefore any grobs that depend on the beam cannot be placed
 835 // until the skylines are known. On the other hand, the distance between staves should
 836 // really depend on position of the cross-staff grobs that lie between them.
 837 // Currently, we just leave cross-staff grobs out of the
 838 // skyline altogether, but this could mean that staves are placed so close together
 839 // that there is no room for the cross-staff grob. It also means, of course, that
 840 // we don't get the benefits of skyline placement for cross-staff grobs.
 841 Skyline_pair
 842 Axis_group_interface::skyline_spacing (Grob *me)
 843 {
 844   extract_grob_set (me, Grob_array::unsmob (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", fakeelements);
 845   vector<Grob *> elements (fakeelements);
 846   for (vsize i = 0; i < elements.size (); i++)
 847     /*
 848       As a sanity check, we make sure that no grob with an outside staff priority
 849       has a Y-parent that also has an outside staff priority, which would result
 850       in two movings.
 851     */
 852     if (scm_is_number (elements[i]->get_property ("outside-staff-priority"))
 853         && outside_staff_ancestor (elements[i]))
 854       {
 855         elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent.");
 856         elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
 857       }
 858
 859   /* For grobs with an outside-staff-priority, the sorting function might
 860      call extent and cause suicide. This breaks the contract that is required
 861      for the STL sort function. To avoid this, we make sure that any suicides
 862      are triggered beforehand.
 863   */
 864   for (vsize i = 0; i < elements.size (); i++)
 865     if (scm_is_number (elements[i]->get_property ("outside-staff-priority")))
 866       elements[i]->extent (elements[i], X_AXIS);
 867
 868   vector_sort (elements, staff_priority_less);
 869   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 870   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 871
 872   assert (y_common == me);
 873
 874   // A rider is a grob that is not outside-staff, but has an outside-staff
 875   // ancestor.  In that case, the rider gets moved along with its ancestor.
 876   multimap<Grob *, Grob *> riders;
 877
 878   vsize i = 0;
 879   vector<Skyline_pair> inside_staff_skylines;
 880
 881   for (i = 0; i < elements.size ()
 882        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
 883     {
 884       Grob *elt = elements[i];
 885       Grob *ancestor = outside_staff_ancestor (elt);
 886       if (!(to_boolean (elt->get_property ("cross-staff")) || ancestor))
 887         add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines);
 888       if (ancestor)
 889         riders.insert (pair<Grob *, Grob *> (ancestor, elt));
 890     }
 891
 892   Skyline_pair skylines (inside_staff_skylines);
 893
 894   // These are the skylines of all outside-staff grobs
 895   // that have already been processed.  We keep them around in order to
 896   // check them for collisions with the currently active outside-staff grob.
 897   Drul_array<vector<Skyline_pair> > all_v_skylines;
 898   Drul_array<vector<Real> > all_paddings;
 899   Drul_array<vector<Real> > all_horizon_paddings;
 900   for (UP_and_DOWN (d))
 901     {
 902       all_v_skylines[d].push_back (skylines);
 903       all_paddings[d].push_back (0);
 904       all_horizon_paddings[d].push_back (0);
 905     }
 906
 907   for (; i < elements.size (); i++)
 908     {
 909       if (to_boolean (elements[i]->get_property ("cross-staff")))
 910         continue;
 911
 912       // Collect all the outside-staff grobs that have a particular priority.
 913       SCM priority = elements[i]->get_property ("outside-staff-priority");
 914       vector<Grob *> current_elts;
 915       current_elts.push_back (elements[i]);
 916       while (i + 1 < elements.size ()
 917              && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
 918         {
 919           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
 920             current_elts.push_back (elements[i + 1]);
 921           ++i;
 922         }
 923
 924       add_grobs_of_one_priority (me,
 925                                  &all_v_skylines,
 926                                  &all_paddings,
 927                                  &all_horizon_paddings,
 928                                  current_elts,
 929                                  x_common,
 930                                  y_common,
 931                                  riders);
 932     }
 933
 934   // Now everything in all_v_skylines has been shifted appropriately; merge
 935   // them all into skylines to get the complete outline.
 936   Skyline_pair other_skylines (all_v_skylines[UP]);
 937   other_skylines.merge (Skyline_pair (all_v_skylines[DOWN]));
 938   skylines.merge (other_skylines);
 939
 940   // We began by shifting my skyline to be relative to the common refpoint; now
 941   // shift it back.
 942   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
 943
 944   return skylines;
 945 }
 946
 947 MAKE_SCHEME_CALLBACK (Axis_group_interface, print, 1)
 948 SCM
 949 Axis_group_interface::print (SCM smob)
 950 {
 951   if (!debug_skylines)
 952     return SCM_BOOL_F;
 953
 954   Grob *me = unsmob_grob (smob);
 955   Stencil ret;
 956   if (Skyline_pair *s = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
 957     {
 958       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
 959                        .in_color (255, 0, 255));
 960       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[DOWN].to_points (X_AXIS))
 961                        .in_color (0, 255, 255));
 962     }
 963   return ret.smobbed_copy ();
 964 }
 965
 966 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
 967 SCM
 968 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
 969 {
 970   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 971                                               true,
 972                                               scm_to_int (start),
 973                                               scm_to_int (end));
 974 }
 975
 976 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
 977 SCM
 978 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
 979 {
 980   return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
 981                                               false,
 982                                               0,
 983                                               INT_MAX);
 984 }
 985
 986 SCM
 987 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
 988 {
 989   Grob *grouper = unsmob_grob (me->get_object ("staff-grouper"));
 990
 991   if (grouper)
 992     {
 993       bool within_group = Staff_grouper_interface::maybe_pure_within_group (grouper, me, pure, start, end);
 994       if (within_group)
 995         return grouper->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
 996       else
 997         return grouper->get_maybe_pure_property ("staffgroup-staff-spacing", pure, start, end);
 998     }
 999   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
1000 }
1001
1002 ADD_INTERFACE (Axis_group_interface,
1003                "An object that groups other layout objects.",
1004
1005                // TODO: some of these properties are specific to
1006                // VerticalAxisGroup. We should split off a
1007                // vertical-axis-group-interface.
1008                /* properties */
1009                "adjacent-pure-heights "
1010                "axes "
1011                "bound-alignment-interfaces "
1012                "default-staff-staff-spacing "
1013                "elements "
1014                "max-stretch "
1015                "no-alignment "
1016                "nonstaff-nonstaff-spacing "
1017                "nonstaff-relatedstaff-spacing "
1018                "nonstaff-unrelatedstaff-spacing "
1019                "outside-staff-placement-directive "
1020                "pure-relevant-grobs "
1021                "pure-relevant-items "
1022                "pure-relevant-spanners "
1023                "pure-Y-common "
1024                "staff-affinity "
1025                "staff-grouper "
1026                "staff-staff-spacing "
1027                "system-Y-offset "
1028                "vertical-skyline-elements "
1029                "X-common "
1030                "Y-common "
1031               );