57 Merge composite string operations

State

The following relates to a single text field. Information about the insertions and deletions which have been applied to a text field are recorded using InsertionsAndDeletions. The text characters that were inserted or deleted are not recorded.

// Identifies operation op(s,t)
struct Opid
{
    SiteId s;
    int t;
};

// Insertion of n characters at position q with temporal index u by operation op(s,t)
struct InsertionInterval
{
    Opid opid;
    int q, n, u;
};

// Deletion of n characters at position q by operation op(s,t)
struct DeletionInterval
{
    Opid opid;
    int q,n;
};

// The insertions and deletions which have been applied to a text field
struct InsertionsAndDeletions
{
    int next_u;
    vector<InsertionInterval> I;
    vector<DeletionInterval> D;
};

I,D,B representation

Locally we store a linked list of insertion intervals and a separate linked list of deletion intervals. These are relative to a purported initial state of the field associated with the base vector time - so in that sense they represent a delta which we call the "local delta". Both lists are ordered by q-position.

Local delta : Delta1 = [I1 D1]

In the remote delta (which is already an RFactor based on an underestimate of the local hv) we store a linked list of insertion intervals and a separate linked list of deletion intervals.

Remote delta : Delta2 = [I2 D2]

In the remote delta we also record the characters to be inserted in a single string buffer B2. This buffer only stores characters associated with I2\D2.

Note that the interval set code contains an algorithm to compute a set difference using left to right scans.

It is useful to assert that sizeof(B2) = sizeof(I2\D2).

In both the local and remote delta, the deletion intervals are recorded in post insertion q-coords. In other words, conceptually the deletes are applied after the inserts.

q-coordinates of both insertions and deletions are unaffected by taking an RFactor - because both are expressed in post insertion coords.

Both inserts and deletes are shifted to the right as they IT past inserts. Neither inserts nor deletes are shifted as they IT past deletes.

        +------+------+
        |      |      |
    D1  |      |      |
        |      |      |
        +------+------+
        |      |      |
    I1  |      |      |
 -->Rf1 |      |      |
        +------+------+

          I2      D2
       -->Rf2

Steps to merge remote delta

There is no need to factorise deletion operations w.r.t. v. Our strategy is simply to apply the appropriate positive shifts to deletion intervals (in both D1 and D2) so that every deletion interval is expressed in the same coordinate system (i.e. merged q-position coordinates).

The following are the steps to perform Delta1 += Delta2. i.e. [I1 D1 B1] += [I2 D2 B2]

v = (Delta1.vout ↓ Delta2.vout) (i.e. what's common to both sites)
Factorise I2,B2 with respect to v. See Factorisation of composite insertions and deletions on a text field and take RFactor
B2 ← field_RFactor(B2,I2\D2,v)
Rf2 = insertion_Rfactor(I2,v)
Factorise I1 into Lf1+Rf1 with respect to v.
Lf1 = insertion_Lfactor(I1,v)
Rf1 = insertion_Rfactor(I1,v)
DualIT Rf1,Rf2 (dualIT context equivalent)
Rf1 ← IT(Rf1,Rf2)
Rf2 ← IT(Rf2,Rf1)
This involves the calculation of effective siteids of maximal q-contiguous pieces
D1 ← IT(D1, Rf2)
D2 ← IT(D2, Rf1)
At this point Rf1, Rf2, D1, D2 are all expressed in the same coord system - i.e. the coord system that arises after all insertions from both deltas but no deletions from either delta have been performed. Note:
Rf1 ⋂ Rf2 = {}
Rf1 ⋂ RFactor(D2,v) = {}
Rf2 ⋂ RFactor(D1,v) = {}
Apply insertions/deletions to the field
This involves a left-to-right scan through both the intervals of Rf2 and D2 (which are expressed in the same merged q-coord), where at each step we process an interval in one of the following:
1. [q1,q2) in Rf2\D2
  These correspond to elements of B2 that need to be inserted into the field. The insertion p-position corresponding to this interval [q1,q2) corresponds to p where
  
  p = (D1+D2).getp(q1)
  
  [Reason: to the left of q1 we have already applied all insertions and deletions to the field - i.e. it corresponds to the state for Delta1+Delta2. Therefore D1+D2 represents the tombstones to the left of q1 and hence gives the relationship between p and q coords]
2. [q1,q2) in D2\Rf2
  These correspond to elements of the field that need to be deleted (if not already deleted according to D1).
  
  The contiguous range of p coords to be deleted [p1,p2) is determined using
  
  p1 = q1 - ([0,q1) intersect (D1+D2)).extent()
  p2 = p1 + ( [q1,q2) \ D1 ).extent() = p1 + D1.getp(q2) - D1.getp(q1)
  
  [ Reason : to the left of q1 we have already applied all insertions and deletions to the field - i.e. it corresponds to the state for Delta1+Delta2. Therefore D1+D2 represents the tombstones to the left of q1 and hence gives the relationship between p and q coords. To the right of q1 we haven't yet applied either the insertions or deletions of Delta2. In particular this is relevant to [q1,q2) which is to the right of q1. Since this is an interval in D2\Rf2 (i.e. not in Rf2) we can ignore the insertions by Delta2. What matters is that within this interval we have applied D1 but not D2. Therefore only D1 is relevant to the relationship between p and q coordinates. ]
  
  Note that p1=p2 is possible - which would suggest that the interval had already been deleted by D1.
3. [q1,q2) in Rf2 intersect D2
  Do nothing. Delta2 had performed an insertion then a deletion of the same elements, so no change to the field is required.
Note that we are stepping a q-position from left to right and asking for the calculation of ([0,q) intersect(D1+D2)).extent(). This can be achieved efficiently using an iterator that keeps track of where we are up to so far.
D1 ← D1 + D2 (merge context equivalent deletions)
Rf1 ← Rf1 + Rf2 (merge context convergent insertions)
I1 ← Lf1 + Rf1 (merge context serialised)

Notes

There is a concept of merged q-position coordinates corresponding to the merge Delta1 + Delta2. This corresponds to the post insertion coordinates in which all insertions from all sites in both Delta1 and Delta2 have been performed and no deletions from any site have been performed.
In step 7, it would be preferable to perform p coord calculations without needing to expplicitly calculate D1+D2. Note that in b) and c) we are processing all intervals in D2. Consider that for each [q1,q2) in D2 we look at what's happening in D1. On this basis we accumulate (D1+D2).extent() and D1.extent(). as we go. In more detail: For each [q1,q2) in D2 we calculate extent of D1 since the last q2 and up to this q1. This represents stuff in D1\D2. This is added to D1.extent but not (D1+D2).extent. Then for [q1,q2) we add q2-q1 to both D1+D2.extent and scan forwards to q2 in order to update D1.extent Building block: Write a class whose purpose is to measure extents from left to right.

Questions

Do we actually need to calculate v? Can't we factorise I2,D2,B2 w.r.t. Delta1.vout, and I1 w.r.t. Delta2.vout?

Previous56 Merge composite string insertion operations Next58 Merging coincident string insertions