56 Merge composite string insertion operations

3-partitions of q-contiguous operations

Definition: Let operation O represent insertions on a single given text field. Let the insertion intervals be recorded in an ordered list, expressed in post-insertion coordinates (i.e. q coordinates). We say that O is q-contiguous if there are no gaps in q-space between adjacent intervals. In other words, execution of O is equivalent to the insertion of a single string into the text field.

O = [...)[.........)[.)[..............)[....)

Note that if O contains no intervals, or only a single interval then we assume O is q-contiguous.

Definition: If O is q-contiguous, let O.q denote the q position of its left most character (if any) and O.size denote the total size of its intervals (i.e. the total number of characters inserted).

Definition: Given lists L₁, L₂, let L₁ + L₂ denote the concatenation of L₁ and L₂ (i.e. L₂ appended to the end of L₁). Note that concatenation is associative but not commutative.

Claim: L₁ and L₂ are q-contiguous and L₁.q + L₁.size = L₂.q ⇔ (L₁+L₂) is q-contiguous.

Definition [x₁,…,x_n] denotes the list containing elements x₁,x₂,….,x_n in that order.

Definition: Let O be nonempty and q-contiguous. A 3-partition of O is some partition of O into three parts as follows:

O = A+[b]+C

where b is an interval in O satisfying ¬ (∃ O_x ∈ Ψ(O) such that O_x → b).

It follows that

• A and C are q-contiguous (and possibly empty)
• A.q = O.q
• b.q = A.q + A.size
• C.q = b.q + b.size.

The condition ¬ (∃ O_x ∈ Ψ(O) such that O_x → b) shows that a valid factorisation exists that extracts L-factor [b] from O (because it doesn’t break causality). Therefore we can write the factorisation into contextually serialised left and right parts as follows:

O = [b’] ⊕_>> (A+C)

The Lfactor algorithm involves decrementing the q-position of [b] as it ETs backward past A, resulting in b’.q = O.q. The RFactor algorithm doesn’t alter q positions (ie A.q and C.q are unchanged by factorisation), so we know a gap in q coordinates of b.size has appeared between A and C. Therefore the R-factor (A+C) is not q-contiguous if both A and C are non-empty.

Definition: A 3-partition is non-trivial if either A or C in the above definition is non empty.

The merge of concurrent q-contiguous operations at different positions

Let shift(O,n) represent the result of shifting all insertion intervals in O to the right by n characters.

The merge of concurrent q-contiguous operations at the same position

We are interested in defining the merge of O₁,O₂ where O₁,O₂ are each q-contiguous and satisfy O₁ || O₂, O₁ <> O₂ and O₁.q = O₂.q.

Evidently the merge O_sum = O₁ ⊕_<> O₂ will also be q-contiguous and satisfy O_sum.q = O₁.q = O₂.q, O_sum.size = O₁.size + O₂.size.

Since O₁ is q-contiguous, the q-position of each interval is determined by O₁.q and the sizes of all the intervals that come before it. Similarly for O₂ and O_sum. This suggests that the recorded q-positions are redundant.

The goal is to define a merge algorithm that completely ignores q-position values, and instead uses them only implicitly by virtue of the order in which the insertion intervals are stored.

Merging an interval into a context equivalent, concurrent, coincident, contiguous operation

Let O₁ be q-contiguous and have a 3-partition O₁ = A₁+[b₁]+C₁ and let O₂ = [b₂] where O₁ <> O₂ and O₁|| O₂. Let O₁,O₂ be coincident - meaning that O₁.q = O₂.q. To simplify the following exposition assume WLOG O₁.q = O₂.q = 0. We are interested in the merge of O₂ into O₁ using an algorithm that ignores q-position values.

Let O₁ be factorised as follows

O₁ = [b₁] ⊕_>> (A₁+C₁)

Then we know as an LFactor, b₁ satisfies b₁.q = 0.

The dual IT between O₁,O₂ first involves comparison of siteids of b₁,b₂ because they are coincident at q = 0.

Firstly assume b₁.s < b₂.s so b₂ will appear on the right of b₁ in the effects document. Under dual IT of b₁,b₂ we see that after transformation b₁.q = 0 whereas b₂.q = b₁.size. b₂ then dualITs against (A₁+C₁) which is not q-contiguous. Since b₂.q = b₁.size > 0 we see that the first interval of A₁, having q = 0 is necessarily to the left of b₂. This pushes b₂ further to the right. In fact when b₂ is compared to any subsequent intervals of A₁, b₂ will always be pushed further to the right. So eventually b₂ IT’s past all of A₁ resulting in b₂.q = b₁.size + A₁.size. Now b₂ will dualIT with C₁ which also begins at q = A₁.size + b₁.size, so b₂ and C₁ are coincident. Therefore following our idea of ignoring q-positions in the merge algorithm, we see that b₂ needs to be merged into C₁ in a recursive fashion. The conclusion is that O₁ ⊕_<> O₂ = A₁ + [b₁] + (C₁ ⊕_<> [b₂]).

[todo: this is sloppy – we need to more formally bring in the idea that we have developed an algorithm that ignores q positions]

Otherwise assume b₂.s < b₁.s so b₂ will appear on the left of b₁ in the effects document. When b₂ IT’s past b₁ we end up with b₂.q = 0. Therefore b₂ will dualIT with (A₁+C₁) at the same q position. In fact we can do better than that because we know that b₂ will appear to the left of b₁ so it is sufficient to dual IT b₂ with A₁ only.

This suggests the following result:

Given 3-partition of O₁ = A₁+[b₁]+C₁ and O₂ = [b₂] where O₁ <> O₂ and O₁ || O₂ then

O₁ ⊕_<> O₂ = (b₁.s < b₂.s) ? (A₁+[b₁]+ (C₁ ⊕_<> [b₂])) : ((A₁ ⊕_<> [b₂]) +[b₁]+C₁)

As the algorithm proceeds there is a range of intervals that narrows over time until we have found the proper insertion position.

The approach is similar to binary search in the way at each step we have a range of potential insertion positions, and using a comparison to some point within the range we narrow the search down to either the left or the right "half". However, binary search normally allows us to compare to a point midway in the range, but we have no such luck. Instead we must make comparisons to intervals in an order compatible with the partial ordering defined by the precedes relation. Therefore there is the potential to only eat away at the range one interval at a time.

Presumably on average this algorithm is O(n log n), and in the worst case is O(n²) where n is the number of intervals in O₁. Maybe it doesn’t matter anyway because it’s not common to have many concurrent insertions in the same field at exactly the same position. [Actually what it we merge the work of two independent groups of users that have typed in thousands of characters into an initially empty document?]

Merge algorithm

Consider that (i₁,i₂) represents an open range of intervals in O₁. In other words the range is exclusive of positions i₁,i₂ and i₁ and i₂ are respectively one before and one after sentinels. If the range is empty (i.e. next(i₁) = i₂) then we stop and insert at the position between i₁ and i₂. Otherwise we scan the intervals in (i₁,i₂) for the interval with the minimum temporal index u. This yields an interval j satisfying i₁ < j < i₂. Depending on the siteid comparison we either assign i₁=j or else i₂ = j. Note therefore that the range must get smaller at each iteration which guarantees that the loop will eventually terminate.

// Merge coincident interval x into contiguous range of intervals
// in (i1,i2)
void MergeCoincidentIntervalIntoContiguousRange(i1,i2,x)
{
    while(next(i1) != i2)
    {
        scan j in (i1,i2) for smallest u
        if (x.s < j.s) i2 = j; else i1 = j;
    }
    insert(i1,x);  // insert x immediately after i1.
}

Example:

Let (s,u) denote an insertion interval with siteid s and temporal index u.

In the following we depict the insertion intervals ordered left to right by q position. Let s₁ < s₂ < s₃ < s₄ and u₁ < u₂ < u₃

O₁ intervals: (s₁,u₂) (s₂,u₃) (s₄,u₁)

O₂ intervals: (s₃,u₁)

Consider that we pick the first (and only) interval from O₂ which is (s₃,u₁). Our job is to find its insertion position amongst the intervals of O₁. Initially there are 3 intervals and hence 4 possible insertion positions.

First we compare (s₃,u₁) with (s₄,u₁). Comparing siteids we deduce that (s₃,u₁) is to the left of (s₄,u₁). This narrows the potential insertion positions according to the intervals to the left of (s₄,u₁). I.e. (s₁,u₂) and (s₂,u₃). So now there are only 3 potential insertion positions.

Next we compare (s₃,u₁) with (s₁,u₂) and find that (s₃,u₁) must be to the right of (s₁,u₂). This leave us with only (s₂,u₃) in the range, and we deduce that (s₃,u₁) must be inserted between (s₂,u₃) and (s₄,u₁).

Assigning the temporal index as we merge operations

As we merge operations into a history buffer there should be no need to change the temporal index values of the existing intervals. In fact the basic idea is for the HB to record the next u, and as intervals are added to the HB we assign u values to these new intervals as required. This can be regarded as analogous to thinking of the HB in its conventional form of a growing linear list of operations ordered by u.

Merging of two 3-partitions

Let O₁, O₂ be q-contiguous and satisfy O₁ <> O₂ and O₁ || O₂. Let O₁.q = O₂.q = 0.

Our approach to merge O₁,O₂ is to merge one interval at a time from O₂ into O₁, until all intervals from O₂ have been merged into O₁. We process the intervals of O₂ in temporal order. We expect that each time we merge an interval from O₂ into O₁, O₁ will remain q-contiguous.

Let there be a 3-partition of O₂ = A₂+[b₂ ]+C₂. If we L-factorise b₂ we get:

O₂ = [b₂] + (A₂+C₂)

In this form b₂.q = A₂.q = 0. A gap in q coordinates of b₂.size has appeared between A₂ and C₂.

The merge of [b₂] into O₁ is straightforward (see section ?) and yields O₁' containing b₂ somewhere. However for the purposes of merging in the remaining intervals from O₂, it is actually important to L-factorise [b₂] from O₁', which means a gap may well appear in the remaining RFactor of O₁'.

After removal of b₂ from O₂ we are left with the following R-factor:

O₂ := (A₂ + C₂)

Now we want to take the next 'b₂' interval (in temporal order) from O₂ as an LFactor. There are two cases. If it lies in A₂ then in similar fashion the interval b₂ to be extracted will satisfy b₂.q = 0. However, if b₂ is inside C₂ then as an LFactor it will have b₂.q > 0. In either case this LFactor of O₂ is suitable for merging into the RFactor of O₁' that doesn't contain the intervals that have already been added from O₂.

Claim: When a b₂ is L-factored out of O₂, as it ETs backward through earlier intervals of O₂, the gaps from missing intervals on its left are in effect summed in order to determine its resultant q position as an LFactor of O₂. Then when it is merged with the relevant RFactor of O₁, the gaps caused by the very same O₂ intervals that have previously been added cause a neat book keeping effect such that the merge will in fact be applied to a q-contiguous section bounded below and above by the relevant b₂ 's appearing now on O₁ according to their original q-position order in O₂.

Upshot: We can implement an algorithm that is based around the idea that an interval is merged into a coincident, concurrent, contiguous range of intervals. To merge O₂ into O₁ we simply iterate through intervals of O₂ in temporal order, and merge them into a range within O₁ that is bounded by the intervals that have already been inserted so as to ensure we maintain the existing q-position order in O₂.

Note that we should merge O₂ into O₁ if O₂ has fewer intervals. Otherwise it is better to instead merge intervals from O₁ into O₂.

Merge algorithm

The interesting aspect here is how to efficiently keep track of the locations of the intervals from O₂ that have been inserted so far into O₁, so that when we insert the next interval from O₂ we can quickly find the q-contiguous range of intervals from O₁ into which it should be merged.

Assuming double linked lists in order of q-position, for a given interval from O₂, we can quickly find the previous and next intervals in O₂. However they may not have been inserted into O₁ yet. So that doesn't really help us.

Consider that we separately record an array of pointers to the intervals from O₂ that have already been inserted into O₁. Then when we want to insert the next interval from O₂ we can perform a binary search to find the insertion position with respect to the intervals from O₂ that have already been inserted into O₁. More to the point this gives us the intervals below and above. Now since these intervals have already been inserted into O₁ they form part of the double linked list ordered by q-position. The upshot is that we have found a pair of iterators that bound the range in which the next insertion must be made.

In the following let X and Y be arrays of pointers to intervals.

// Merge O2 = (j1,j2) into O1 = (i1,i2) where O1,O2 are q-contiguous,
// concurrent and coincident.
void MergeCoincidentRanges(
    Interval* i1,Interval* i2,
    Interval* j1,Interval* j2)
{
    Copy pointers to intervals in (j1,j2) to an array X;
    Sort pointers to intervals in X by their u values;
    Y = [];
    for each j in X  (in order of increasing u)
    {
        // Y is ordered by q-position.   Insert j into Y using binary
        // search according to q-position
        // Returns pointers to intervals y1,y2 that straddle interval j.
        // May return y1=NULL or y2=NULL (or both)
        (y1,y2) = Y.insert(j);   // insert j in Y
        if (!y1) y1 = i1;
        if (!y2) y2 = i2;

        // Merge j into open range (y1,y2)
        MergeCoincidentIntervalIntoContiguousRange(y1,y2,j);
    }
}

Recursive formulation of the algorithm

Lemma: Let O₁ = A₁+C₁, O₂ = A₂+C₂, where A₁,A₂,C₁, C₂ are each q-contiguous. Let A₁,A₂ be q-coincident. Let there be a gap of x>0 characters between the end of A₁ and the start of C₁. Let there be the same sized gap x between A₂ and C₂. Then

(A₁+C₁) ⊕ (A₂+C₂) = (A₁ ⊕ A₂) + (C₁ ⊕ C₂)

Let there be a 3-partition of O₂ as A₂+[b₂ ]+C₂. As an L-Factor we know that b₂.q = 0. Therefore b₂ is coincident with O₁ and by section ? we have an algorithm to find the insertion position of b₂ within O₁. Let is write this as

O₁ = A₁ + [b₂] + C₁.

i.e. the interval b₂ we inserted into O₁ can be written as a 3-partition of O₁. This leaves us with O₂ = A₂+C₂.

Claim: O₁ ⊕ O₂ = (A₁ ⊕ A₂) + [b₂] + (C₁ ⊕ C₂)