+/*
+ We don't do
+
+ forall b in broken-childs:
+ forall p in properties:
+ forall g in p (if grob-list):
+ g := substitute (g)
+
+ for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
+ O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
+
+ This is problematic: with large (long) scores, the costs can be
+ significant; especially all-elements in System, can become huge. For
+ a typical 50 page score, it requires running through a 100k list 50
+ times.
+
+ Instead:
+
+ forall p in properties:
+ (if grob list)
+
+ put grob list in array,
+
+ reorder array so spanners are separate -- O (grobcount)
+
+ find first and last indexes of grobs on a specific system
+
+ for items this is O (itemcount)
+
+ for spanners this is O (sum-of spanner-system-ranges)
+
+ perform the substitution O (sum-of spanner-system-ranges)
+
+
+ The complexity is harder to determine, but should be subquadratic;
+
+ For the situation above, we run through the entire 100k list once,
+ and also (more or less) once through the item part of the 100k (say
+ 98k elements) of the list.
+
+
+These timings were measured without -O2.
+
+ lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
+
+ coriolan, before 2:30, after: 1:59. Increase of 20%.
+
+ moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
+
+
+*/
+
+
+Slice
+spanner_system_range (Spanner* sp)
+{
+ Slice rv;
+
+ if (System*st = sp->get_system ())
+ {
+ rv = Slice (st->rank_, st->rank_);
+ }
+ else
+ {
+ if (sp->broken_intos_.size ())
+ rv = Slice (sp->broken_intos_[0]->get_system ()->rank_,
+ sp->broken_intos_.top ()->get_system ()->rank_);
+ }
+ return rv;
+}
+
+Slice
+item_system_range (Item* it)
+{
+ if (System*st= it->get_system ())
+ return Slice (st->rank_, st->rank_);
+
+ Slice sr;
+ Direction d = LEFT;
+ do
+ {
+ Item *bi = it->find_prebroken_piece (d);
+ if (bi && bi->get_system ())
+ sr.add_point (bi->get_system ()->rank_);
+ }
+ while (flip (&d)!=LEFT);
+
+ return sr;
+}
+
+Slice
+grob_system_range (Grob *g)
+{
+ if (Spanner*s = dynamic_cast<Spanner*>(g))
+ return spanner_system_range (s);
+ else if (Item* it = dynamic_cast<Item*> (g))
+ return item_system_range (it);
+ else
+ return Slice ();
+}
+
+
+
+struct Substitution_entry
+{
+ Grob * grob_;
+ short left_;
+ short right_;
+
+ void set (Grob*g, Slice sr)
+ {
+ grob_ = g;
+ /*
+ duh, don't support scores with more than 32000 systems.
+ */
+ if (sr.is_empty ())
+ {
+ /*
+ overflow if we don't treat this specially.
+ */
+ left_ = 1;
+ right_ = -1;
+ }
+ else
+ {
+ left_ = sr[LEFT];
+ right_ = sr[RIGHT];
+ }
+ }
+ Substitution_entry ()
+ {
+ grob_ =0;
+ left_ = right_ = -2;
+ }
+
+ int length () { return right_ - left_ ; }
+ static int
+ item_compare (void const * a , void const * b)
+ {
+ return ((Substitution_entry*)a)->left_ -
+ ((Substitution_entry*)b)->left_;
+ }
+
+ static int
+ spanner_compare (void const * a , void const * b)
+ {
+ return ((Substitution_entry*)a)->length () -
+ ((Substitution_entry*)b)->length ();
+ }
+};
+
+
+
+bool
+Spanner::fast_fubstitute_grob_list (SCM sym,
+ SCM grob_list)
+{
+ int len = scm_ilength (grob_list);
+
+ /*
+ Only do this complicated thing for large lists. This has the added
+ advantage that we won't screw up the ordering for elements in
+ alignments (which typically don't have more than 10 grobs.)
+ */
+
+ if (len < 300)
+ return false;
+
+
+ /*
+ TODO : should not free it some time?
+ */
+ static Substitution_entry * vec;
+ static int vec_room;
+
+ if (vec_room < len)
+ {
+ vec = (Substitution_entry*) realloc (vec, sizeof (Substitution_entry) * len);
+ vec_room = len;
+ }
+
+ Slice system_range = spanner_system_range (this);
+
+ Array<Slice> it_indices;
+ Array<Slice> sp_indices;
+ for (int i = 0; i <= system_range.length (); i++)
+ {
+ it_indices.push (Slice (len, 0));
+ sp_indices.push (Slice (len, 0));
+ }
+
+
+ int sp_index = len;
+ int it_index = 0;
+ for (SCM s = grob_list; ly_c_pair_p (s); s = ly_cdr (s))
+ {
+ Grob * g = unsmob_grob (ly_car (s));
+
+ Slice sr = grob_system_range (g);
+ sr.intersect (system_range);
+
+ int idx = 0;
+ if (dynamic_cast<Spanner*>(g))
+ {
+ idx =--sp_index;
+ }
+ else if (dynamic_cast<Item*> (g))
+ {
+ idx = it_index++;
+ }
+
+ vec[idx].set (g, sr);
+ }
+
+ qsort (vec, it_index,
+ sizeof (Substitution_entry), &Substitution_entry::item_compare);
+
+ Array<Slice> *arrs[] = {
+ &it_indices, &sp_indices
+ };
+
+ for (int i = 0; i < it_index ;i++)
+ {
+ for (int j = vec[i].left_; j <= vec[i].right_; j++)
+ {
+ it_indices[j - system_range[LEFT]].add_point (i);
+ }
+ }
+
+ /*
+ sorting vec[sp_index.. len]
+ is a waste of time -- the staff-spanners screw up the
+ ordering, since they go across the entire score.
+ */
+ for (int i = sp_indices.size (); i--;)
+ sp_indices[i]= Slice (sp_index, len-1);
+
+
+ assert (it_index <= sp_index);
+
+ assert (broken_intos_.size () == system_range.length () + 1);
+ for (int i = 0; i < broken_intos_.size (); i++)
+ {
+ Grob * sc = broken_intos_[i];
+ System * l = sc->get_system ();
+ set_break_subsititution (l ? l->self_scm (): SCM_UNDEFINED);
+
+ SCM newval = SCM_EOL;
+ SCM * tail = &newval;
+
+ for (int k = 0; k < 2;k++)
+ for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
+ {
+ SCM subs =substitute_grob (vec[j].grob_);
+ if (subs!= SCM_UNDEFINED)
+ {
+ *tail = scm_cons (subs, SCM_EOL);
+
+ tail = SCM_CDRLOC (*tail);
+ }
+
+ }
+
+#ifdef PARANOIA
+
+ printf ("%d (%d), sp %d (%d)\n",
+ it_indices [i].length (), it_index,
+ sp_indices[i].length () , len -sp_index);
+
+ {
+ SCM l1 =substitute_grob_list (grob_list);
+ assert (scm_ilength (l1) == scm_ilength (newval));
+ }
+#endif
+
+ /*
+ see below.
+ */
+ if (sym == ly_symbol2scm ("all-elements"))
+ sc->mutable_property_alist_
+ = scm_assq_remove_x (sc->mutable_property_alist_,
+ ly_symbol2scm ("all-elements"));
+
+ sc->mutable_property_alist_ = scm_acons (sym, newval,
+ sc->mutable_property_alist_);
+ }
+
+ return true;
+}