+struct Substitution_entry
+{
+ Grob *grob_;
+
+ /* Assumption: we have less than 32k paper columns. */
+ 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_substitute_grob_array (SCM sym,
+ Grob_array *grob_array)
+{
+ int len = grob_array->size ();
+
+ if (grob_array->ordered ())
+ return false;
+
+ if (len < 15)
+ return false;
+
+ /*
+ We store items on the left, spanners on the right in this vector.
+
+ FIXME: will not multithread.
+ */
+ 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);
+
+ int spanner_index = len;
+ int item_index = 0;
+
+ for (vsize i = 0; i < grob_array->size (); i++)
+ {
+ Grob *g = grob_array->grob (i);
+
+ Slice sr = grob_system_range (g);
+ sr.intersect (system_range);
+
+ int idx = 0;
+ if (dynamic_cast<Spanner *> (g))
+ idx = --spanner_index;
+ else if (dynamic_cast<Item *> (g))
+ idx = item_index++;
+
+ vec[idx].set (g, sr);
+ }
+
+ qsort (vec, item_index,
+ sizeof (Substitution_entry), &Substitution_entry::item_compare);
+
+ vector<Slice> item_indices;
+ vector<Slice> spanner_indices;
+ for (int i = 0; i <= system_range.length (); i++)
+ {
+ item_indices.push_back (Slice (len, 0));
+ spanner_indices.push_back (Slice (len, 0));
+ }
+
+ vector<Slice> *arrs[]
+ = {
+ &item_indices, &spanner_indices
+ };