lily/axis-group-interface.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2000--2014 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 = Grob::unsmob (smob);
 225
 226   Grob *common = Grob::unsmob (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 = Grob::unsmob (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 = Grob::unsmob (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 = Grob::unsmob (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 = Grob::unsmob (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 = Grob::unsmob (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 = Grob::unsmob (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 = Grob::unsmob (smob);
 477   /* TODO: Filter out elements that belong to a different Axis_group,
 478      such as the tie in
 479      << \new Staff=A { c'1~ \change Staff=B c'}
 480         \new Staff=B { \clef bass R1 R } >>
 481     because thier location relative to this Axis_group is not known before
 482     page layout.  For now, we need to trap this case in calc_pure_y_common.
 483   */
 484   return internal_calc_pure_relevant_grobs (me, "elements");
 485 }
 486
 487 SCM
 488 Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, const string &grob_set_name)
 489 {
 490   extract_grob_set (me, grob_set_name.c_str (), elts);
 491
 492   vector<Grob *> relevant_grobs;
 493
 494   for (vsize i = 0; i < elts.size (); i++)
 495     {
 496       if (elts[i] && elts[i]->is_live ())
 497         relevant_grobs.push_back (elts[i]);
 498       /*
 499         TODO (mikesol): it is probably bad that we're reading prebroken
 500         pieces from potentially suicided elements.  This behavior
 501         has been in current master since at least 2.16.
 502
 503         We need to fully suicide all Items, meaning that their
 504         prebroken pieces should not be accessible, which means that
 505         Item::handle_prebroken_dependencies should only be called
 506         AFTER this list is composed.  The list composition function
 507         should probably not check for suicided items or NULL pointers
 508         but leave that to the various methods that use it.
 509       */
 510       if (Item *it = dynamic_cast<Item *> (elts[i]))
 511         {
 512           for (LEFT_and_RIGHT (d))
 513             {
 514               Item *piece = it->find_prebroken_piece (d);
 515               if (piece && piece->is_live ())
 516                 relevant_grobs.push_back (piece);
 517             }
 518         }
 519     }
 520
 521   vector_sort (relevant_grobs, pure_staff_priority_less);
 522   SCM grobs_scm = Grob_array::make_array ();
 523   Grob_array::unsmob (grobs_scm)->set_array (relevant_grobs);
 524
 525   return grobs_scm;
 526 }
 527
 528 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_y_common, 1);
 529 SCM
 530 Axis_group_interface::calc_pure_y_common (SCM smob)
 531 {
 532   Grob *me = Grob::unsmob (smob);
 533
 534   extract_grob_set (me, "pure-relevant-grobs", elts);
 535   Grob *common = common_refpoint_of_array (elts, me, Y_AXIS);
 536   if (common != me && Align_interface::has_interface (common))
 537     {
 538       me->programming_error("My pure_y_common is a VerticalAlignment,"
 539                             " which might contain several staves.");
 540       common = me;
 541     }
 542   if (!common)
 543     {
 544       me->programming_error ("No common parent found in calc_pure_y_common.");
 545       return SCM_EOL;
 546     }
 547
 548   return common->self_scm ();
 549 }
 550
 551 SCM
 552 Axis_group_interface::calc_common (Grob *me, Axis axis)
 553 {
 554   extract_grob_set (me, "elements", elts);
 555   Grob *common = common_refpoint_of_array (elts, me, axis);
 556   if (!common)
 557     {
 558       me->programming_error ("No common parent found in calc_common axis.");
 559       return SCM_EOL;
 560     }
 561
 562   return common->self_scm ();
 563 }
 564
 565 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_x_common, 1);
 566 SCM
 567 Axis_group_interface::calc_x_common (SCM grob)
 568 {
 569   return calc_common (Grob::unsmob (grob), X_AXIS);
 570 }
 571
 572 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_y_common, 1);
 573 SCM
 574 Axis_group_interface::calc_y_common (SCM grob)
 575 {
 576   return calc_common (Grob::unsmob (grob), Y_AXIS);
 577 }
 578
 579 Interval
 580 Axis_group_interface::pure_group_height (Grob *me, int start, int end)
 581 {
 582   Grob *common = Grob::unsmob (me->get_object ("pure-Y-common"));
 583
 584   if (!common)
 585     {
 586       programming_error ("no pure Y common refpoint");
 587       return Interval ();
 588     }
 589   Real my_coord = me->pure_relative_y_coordinate (common, start, end);
 590   Interval r (relative_pure_height (me, start, end));
 591
 592   return r - my_coord;
 593 }
 594
 595 void
 596 Axis_group_interface::get_children (Grob *me, vector<Grob *> *found)
 597 {
 598   found->push_back (me);
 599
 600   if (!has_interface (me))
 601     return;
 602
 603   extract_grob_set (me, "elements", elements);
 604   for (vsize i = 0; i < elements.size (); i++)
 605     {
 606       Grob *e = elements[i];
 607       Axis_group_interface::get_children (e, found);
 608     }
 609 }
 610
 611 static bool
 612 staff_priority_less (Grob *const &g1, Grob *const &g2)
 613 {
 614   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 615   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 616
 617   if (priority_1 < priority_2)
 618     return true;
 619   else if (priority_1 > priority_2)
 620     return false;
 621
 622   /* if neither grob has an outside-staff priority, the ordering will have no
 623      effect -- we just need to choose a consistent ordering. We do this to
 624      avoid the side-effect of calculating extents. */
 625   if (isinf (priority_1))
 626     return g1 < g2;
 627
 628   /* if there is no preference in staff priority, choose the left-most one */
 629   Grob *common = g1->common_refpoint (g2, X_AXIS);
 630   Real start_1 = g1->extent (common, X_AXIS)[LEFT];
 631   Real start_2 = g2->extent (common, X_AXIS)[LEFT];
 632   return start_1 < start_2;
 633 }
 634
 635 static bool
 636 pure_staff_priority_less (Grob *const &g1, Grob *const &g2)
 637 {
 638   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 639   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 640
 641   return priority_1 < priority_2;
 642 }
 643
 644 static void
 645 add_interior_skylines (Grob *me, Grob *x_common, Grob *y_common, vector<Skyline_pair> *skylines)
 646 {
 647   if (Grob_array *elements = Grob_array::unsmob (me->get_object ("elements")))
 648     {
 649       for (vsize i = 0; i < elements->size (); i++)
 650         add_interior_skylines (elements->grob (i), x_common, y_common, skylines);
 651     }
 652   else if (!scm_is_number (me->get_property ("outside-staff-priority"))
 653            && !to_boolean (me->get_property ("cross-staff")))
 654     {
 655       Skyline_pair *maybe_pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines"));
 656       if (!maybe_pair)
 657         return;
 658       if (maybe_pair->is_empty ())
 659         return;
 660       skylines->push_back (Skyline_pair (*maybe_pair));
 661       skylines->back ().shift (me->relative_coordinate (x_common, X_AXIS));
 662       skylines->back ().raise (me->relative_coordinate (y_common, Y_AXIS));
 663     }
 664 }
 665
 666 // Raises the grob elt (whose skylines are given by h_skyline
 667 // and v_skyline) so that it doesn't intersect with staff_skyline,
 668 // or with anything in other_h_skylines and other_v_skylines.
 669 void
 670 avoid_outside_staff_collisions (Grob *elt,
 671                                 Skyline_pair *v_skyline,
 672                                 Real padding,
 673                                 Real horizon_padding,
 674                                 vector<Skyline_pair> const &other_v_skylines,
 675                                 vector<Real> const &other_padding,
 676                                 vector<Real> const &other_horizon_padding,
 677                                 Direction const dir)
 678 {
 679   assert (other_v_skylines.size () == other_padding.size ());
 680   assert (other_v_skylines.size () == other_horizon_padding.size ());
 681   vector<Interval> forbidden_intervals;
 682   for (vsize j = 0; j < other_v_skylines.size (); j++)
 683     {
 684       Skyline_pair const &v_other = other_v_skylines[j];
 685       Real pad = max (padding, other_padding[j]);
 686       Real horizon_pad = max (horizon_padding, other_horizon_padding[j]);
 687
 688       // We need to push elt up by at least this much to be above v_other.
 689       Real up = (*v_skyline)[DOWN].distance (v_other[UP], horizon_pad) + pad;
 690       // We need to push elt down by at least this much to be below v_other.
 691       Real down = (*v_skyline)[UP].distance (v_other[DOWN], horizon_pad) + pad;
 692
 693       forbidden_intervals.push_back (Interval (-down, up));
 694     }
 695
 696   Interval_set allowed_shifts
 697     = Interval_set::interval_union (forbidden_intervals).complement ();
 698   Real move = allowed_shifts.nearest_point (0, dir);
 699   v_skyline->raise (move);
 700   elt->translate_axis (move, Y_AXIS);
 701 }
 702
 703 SCM
 704 valid_outside_staff_placement_directive (Grob *me)
 705 {
 706   SCM directive = me->get_property ("outside-staff-placement-directive");
 707
 708   if ((directive == ly_symbol2scm ("left-to-right-greedy"))
 709       || (directive == ly_symbol2scm ("left-to-right-polite"))
 710       || (directive == ly_symbol2scm ("right-to-left-greedy"))
 711       || (directive == ly_symbol2scm ("right-to-left-polite")))
 712     return directive;
 713
 714   me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive",
 715                    robust_symbol2string (directive, "").c_str ()));
 716
 717   return ly_symbol2scm ("left-to-right-polite");
 718 }
 719
 720 // Shifts the grobs in elements to ensure that they (and any
 721 // connected riders) don't collide with the staff skylines
 722 // or anything in all_X_skylines.  Afterwards, the skylines
 723 // of the grobs in elements will be added to all_v_skylines.
 724 static void
 725 add_grobs_of_one_priority (Grob *me,
 726                            Drul_array<vector<Skyline_pair> > *all_v_skylines,
 727                            Drul_array<vector<Real> > *all_paddings,
 728                            Drul_array<vector<Real> > *all_horizon_paddings,
 729                            vector<Grob *> elements,
 730                            Grob *x_common,
 731                            Grob *y_common,
 732                            multimap<Grob *, Grob *> const &riders)
 733 {
 734
 735   SCM directive
 736     = valid_outside_staff_placement_directive (me);
 737
 738   bool l2r = ((directive == ly_symbol2scm ("left-to-right-greedy"))
 739               || (directive == ly_symbol2scm ("left-to-right-polite")));
 740
 741   bool polite = ((directive == ly_symbol2scm ("left-to-right-polite"))
 742                  || (directive == ly_symbol2scm ("right-to-left-polite")));
 743
 744   vector<Box> boxes;
 745   vector<Skyline_pair> skylines_to_merge;
 746
 747   // We want to avoid situations like this:
 748   //           still more text
 749   //      more text
 750   //   text
 751   //   -------------------
 752   //   staff
 753   //   -------------------
 754
 755   // The point is that "still more text" should be positioned under
 756   // "more text".  In order to achieve this, we place the grobs in several
 757   // passes.  We keep track of the right-most horizontal position that has been
 758   // affected by the current pass so far (actually we keep track of 2
 759   // positions, one for above the staff, one for below).
 760
 761   // In each pass, we loop through the unplaced grobs from left to right.
 762   // If the grob doesn't overlap the right-most affected position, we place it
 763   // (and then update the right-most affected position to point to the right
 764   // edge of the just-placed grob).  Otherwise, we skip it until the next pass.
 765   while (!elements.empty ())
 766     {
 767       Drul_array<Real> last_end (-infinity_f, -infinity_f);
 768       vector<Grob *> skipped_elements;
 769       for (vsize i = l2r ? 0 : elements.size ();
 770            l2r ? i < elements.size () : i--;
 771            l2r ? i++ : 0)
 772         {
 773           Grob *elt = elements[i];
 774           Real padding
 775             = robust_scm2double (elt->get_property ("outside-staff-padding"),
 776                                  Axis_group_interface
 777                                  ::get_default_outside_staff_padding ());
 778           Real horizon_padding
 779             = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0);
 780           Interval x_extent = elt->extent (x_common, X_AXIS);
 781           x_extent.widen (horizon_padding);
 782
 783           Direction dir = get_grob_direction (elt);
 784           if (dir == CENTER)
 785             {
 786               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
 787               dir = UP;
 788             }
 789
 790           if (x_extent[LEFT] <= last_end[dir] && polite)
 791             {
 792               skipped_elements.push_back (elt);
 793               continue;
 794             }
 795           last_end[dir] = x_extent[RIGHT];
 796
 797           Skyline_pair *v_orig = Skyline_pair::unsmob (elt->get_property ("vertical-skylines"));
 798           if (v_orig->is_empty ())
 799             continue;
 800
 801           // Find the riders associated with this grob, and merge their
 802           // skylines with elt's skyline.
 803           typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator;
 804           pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt);
 805           vector<Skyline_pair> rider_v_skylines;
 806           for (GrobMapIterator j = range.first; j != range.second; j++)
 807             {
 808               Grob *rider = j->second;
 809               Skyline_pair *v_rider = Skyline_pair::unsmob (rider->get_property ("vertical-skylines"));
 810               if (v_rider)
 811                 {
 812                   Skyline_pair copy (*v_rider);
 813                   copy.shift (rider->relative_coordinate (x_common, X_AXIS));
 814                   copy.raise (rider->relative_coordinate (y_common, Y_AXIS));
 815                   rider_v_skylines.push_back (copy);
 816                 }
 817             }
 818           Skyline_pair v_skylines (*v_orig);
 819           v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS));
 820           v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS));
 821           v_skylines.merge (Skyline_pair (rider_v_skylines));
 822
 823           avoid_outside_staff_collisions (elt,
 824                                           &v_skylines,
 825                                           padding,
 826                                           horizon_padding,
 827                                           (*all_v_skylines)[dir],
 828                                           (*all_paddings)[dir],
 829                                           (*all_horizon_paddings)[dir],
 830                                           dir);
 831
 832           elt->set_property ("outside-staff-priority", SCM_BOOL_F);
 833           (*all_v_skylines)[dir].push_back (v_skylines);
 834           (*all_paddings)[dir].push_back (padding);
 835           (*all_horizon_paddings)[dir].push_back (horizon_padding);
 836         }
 837       swap (elements, skipped_elements);
 838       skipped_elements.clear ();
 839     }
 840 }
 841
 842 // If the Grob has a Y-ancestor with outside-staff-priority, return it.
 843 // Otherwise, return 0.
 844 Grob *
 845 Axis_group_interface::outside_staff_ancestor (Grob *me)
 846 {
 847   Grob *parent = me->get_parent (Y_AXIS);
 848   if (!parent)
 849     return 0;
 850
 851   if (scm_is_number (parent->get_property ("outside-staff-priority")))
 852     return parent;
 853
 854   return outside_staff_ancestor (parent);
 855 }
 856
 857 // It is tricky to correctly handle skyline placement of cross-staff grobs.
 858 // For example, cross-staff beams cannot be formatted until the distance between
 859 // staves is known and therefore any grobs that depend on the beam cannot be placed
 860 // until the skylines are known. On the other hand, the distance between staves should
 861 // really depend on position of the cross-staff grobs that lie between them.
 862 // Currently, we just leave cross-staff grobs out of the
 863 // skyline altogether, but this could mean that staves are placed so close together
 864 // that there is no room for the cross-staff grob. It also means, of course, that
 865 // we don't get the benefits of skyline placement for cross-staff grobs.
 866 Skyline_pair
 867 Axis_group_interface::skyline_spacing (Grob *me)
 868 {
 869   extract_grob_set (me, Grob_array::unsmob (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", fakeelements);
 870   vector<Grob *> elements (fakeelements);
 871   for (vsize i = 0; i < elements.size (); i++)
 872     /*
 873       As a sanity check, we make sure that no grob with an outside staff priority
 874       has a Y-parent that also has an outside staff priority, which would result
 875       in two movings.
 876     */
 877     if (scm_is_number (elements[i]->get_property ("outside-staff-priority"))
 878         && outside_staff_ancestor (elements[i]))
 879       {
 880         elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent.");
 881         elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
 882       }
 883
 884   /* For grobs with an outside-staff-priority, the sorting function might
 885      call extent and cause suicide. This breaks the contract that is required
 886      for the STL sort function. To avoid this, we make sure that any suicides
 887      are triggered beforehand.
 888   */
 889   for (vsize i = 0; i < elements.size (); i++)
 890     if (scm_is_number (elements[i]->get_property ("outside-staff-priority")))
 891       elements[i]->extent (elements[i], X_AXIS);
 892
 893   vector_sort (elements, staff_priority_less);
 894   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 895   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 896
 897   if (y_common != me)
 898     {
 899       me->programming_error("Some of my vertical-skyline-elements"
 900                             " are outside my VerticalAxisGroup.");
 901       y_common = me;
 902     }
 903
 904   // A rider is a grob that is not outside-staff, but has an outside-staff
 905   // ancestor.  In that case, the rider gets moved along with its ancestor.
 906   multimap<Grob *, Grob *> riders;
 907
 908   vsize i = 0;
 909   vector<Skyline_pair> inside_staff_skylines;
 910
 911   for (i = 0; i < elements.size ()
 912        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
 913     {
 914       Grob *elt = elements[i];
 915       Grob *ancestor = outside_staff_ancestor (elt);
 916       if (!(to_boolean (elt->get_property ("cross-staff")) || ancestor))
 917         add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines);
 918       if (ancestor)
 919         riders.insert (pair<Grob *, Grob *> (ancestor, elt));
 920     }
 921
 922   Skyline_pair skylines (inside_staff_skylines);
 923
 924   // These are the skylines of all outside-staff grobs
 925   // that have already been processed.  We keep them around in order to
 926   // check them for collisions with the currently active outside-staff grob.
 927   Drul_array<vector<Skyline_pair> > all_v_skylines;
 928   Drul_array<vector<Real> > all_paddings;
 929   Drul_array<vector<Real> > all_horizon_paddings;
 930   for (UP_and_DOWN (d))
 931     {
 932       all_v_skylines[d].push_back (skylines);
 933       all_paddings[d].push_back (0);
 934       all_horizon_paddings[d].push_back (0);
 935     }
 936
 937   for (; i < elements.size (); i++)
 938     {
 939       if (to_boolean (elements[i]->get_property ("cross-staff")))
 940         continue;
 941
 942       // Collect all the outside-staff grobs that have a particular priority.
 943       SCM priority = elements[i]->get_property ("outside-staff-priority");
 944       vector<Grob *> current_elts;
 945       current_elts.push_back (elements[i]);
 946       while (i + 1 < elements.size ()
 947              && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
 948         {
 949           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
 950             current_elts.push_back (elements[i + 1]);
 951           ++i;
 952         }
 953
 954       add_grobs_of_one_priority (me,
 955                                  &all_v_skylines,
 956                                  &all_paddings,
 957                                  &all_horizon_paddings,
 958                                  current_elts,
 959                                  x_common,
 960                                  y_common,
 961                                  riders);
 962     }
 963
 964   // Now everything in all_v_skylines has been shifted appropriately; merge
 965   // them all into skylines to get the complete outline.
 966   Skyline_pair other_skylines (all_v_skylines[UP]);
 967   other_skylines.merge (Skyline_pair (all_v_skylines[DOWN]));
 968   skylines.merge (other_skylines);
 969
 970   // We began by shifting my skyline to be relative to the common refpoint; now
 971   // shift it back.
 972   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
 973
 974   return skylines;
 975 }
 976
 977 MAKE_SCHEME_CALLBACK (Axis_group_interface, print, 1)
 978 SCM
 979 Axis_group_interface::print (SCM smob)
 980 {
 981   if (!debug_skylines)
 982     return SCM_BOOL_F;
 983
 984   Grob *me = Grob::unsmob (smob);
 985   Stencil ret;
 986   if (Skyline_pair *s = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
 987     {
 988       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
 989                        .in_color (255, 0, 255));
 990       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[DOWN].to_points (X_AXIS))
 991                        .in_color (0, 255, 255));
 992     }
 993   return ret.smobbed_copy ();
 994 }
 995
 996 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
 997 SCM
 998 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
 999 {
1000   return calc_maybe_pure_staff_staff_spacing (Grob::unsmob (smob),
1001                                               true,
1002                                               scm_to_int (start),
1003                                               scm_to_int (end));
1004 }
1005
1006 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
1007 SCM
1008 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
1009 {
1010   return calc_maybe_pure_staff_staff_spacing (Grob::unsmob (smob),
1011                                               false,
1012                                               0,
1013                                               INT_MAX);
1014 }
1015
1016 SCM
1017 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
1018 {
1019   Grob *grouper = Grob::unsmob (me->get_object ("staff-grouper"));
1020
1021   if (grouper)
1022     {
1023       bool within_group = Staff_grouper_interface::maybe_pure_within_group (grouper, me, pure, start, end);
1024       if (within_group)
1025         return grouper->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
1026       else
1027         return grouper->get_maybe_pure_property ("staffgroup-staff-spacing", pure, start, end);
1028     }
1029   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
1030 }
1031
1032 ADD_INTERFACE (Axis_group_interface,
1033                "An object that groups other layout objects.",
1034
1035                // TODO: some of these properties are specific to
1036                // VerticalAxisGroup. We should split off a
1037                // vertical-axis-group-interface.
1038                /* properties */
1039                "adjacent-pure-heights "
1040                "axes "
1041                "bound-alignment-interfaces "
1042                "default-staff-staff-spacing "
1043                "elements "
1044                "max-stretch "
1045                "no-alignment "
1046                "nonstaff-nonstaff-spacing "
1047                "nonstaff-relatedstaff-spacing "
1048                "nonstaff-unrelatedstaff-spacing "
1049                "pure-relevant-grobs "
1050                "pure-relevant-items "
1051                "pure-relevant-spanners "
1052                "pure-Y-common "
1053                "staff-affinity "
1054                "staff-grouper "
1055                "staff-staff-spacing "
1056                "system-Y-offset "
1057                "X-common "
1058                "Y-common "
1059               );