19.11 Merge
Contract
Given context-serialised operations [O1,O2], Merge(O1,O2) changes
O1 in place to the information-preserving composite O1 ⊕ O2 and
empties the interval content of O2. The enclosing O2.opid is retained. The
result has the same effect as the sequence and must satisfy MP1–MP4.
Processing starts at the bottom right and ends by merging the diagonal lists. The progress diagrams
use the symbols defined in
Dual inclusion transformation, oriented with
O1 proceeding upwards and O2 proceeding from right to left.
Move-only overview
Before considering every cell of the matrix, suppress creations and deletions and follow only the move insertion and extraction lists. The serial pair initially has the form:
[O1 O2] = [ I1 X1 I2 X2 ]
The move part of Merge can then be read as the following derivation. A prime denotes a list whose coordinates or extraction location have been transformed; it does not denote a copied list.
[O1 O2] =
[ I1 X1 I2 X2 ]
→ [ I1 I2 X1' X2 ] X1' = IT(X1,I2)
shift X1 for the insertions in I2
→ [ I2 X1' X2 ] I1' = IT2(I1,I2)
I1' I1' and I2 share post-I1,I2 coordinates
→ [ I2 X1' ] if X2 extracts at I1', track it back to X1'
I1' X2'
→ [ I X ] I = merge(I1',I2)
X = merge(X1',X2')
Thus both insertion lists and both extraction lists first acquire the coordinate system produced by
all move insertions. Only then can a chained move be recognised by comparing X2 with
I1'. It tracks to X1', not the old X1, because the tracked
position must include the shift caused by I2. The final two list merges do not discard
either move identity; coincident extractions become an alias group ordered by e.
The complete algorithm below adds creations and deletions and performs these transformations in an order that keeps every required pair of lists in compatible coordinates.
Merging insertion lists with shifts
Mergeii(I1,I2) assumes I1 >> I2.
I1
abcdefgh --------> abc1111de111fg1111111h
[ ) [ ) [ )
I2
--------> abc1111d22e111fg11122221122211h
[) [ ) [ )
template <class T>
void Mergeii(T*& fi1, T*& fi2)
{
T* i1 = fi1;
T* i2 = fi2;
if (i1)
{
int s = 0;
T* previ1 = nullptr;
while (i1 && i2)
{
int d = i2->iq - (s + i1->iq);
if (d <= 0)
{
T* nexti2 = i2->nextI;
if (previ1) previ1->nextI = i2;
else fi1 = i2;
i2->prevI = previ1;
i2->nextI = i1;
i1->prevI = i2;
previ1 = i2;
s += i2->size();
i2 = nexti2;
}
else
{
if (d < i1->size()) SplitInterval(i1, d);
i1->iq += s;
previ1 = i1;
i1 = i1->nextI;
}
}
if (i2)
{
previ1->nextI = i2;
i2->prevI = previ1;
}
else
{
while (i1)
{
i1->iq += s;
i1 = i1->nextI;
}
}
}
else
{
fi1 = i2;
}
fi2 = nullptr;
}
Mergeii_noshift performs the same stable relinking and splitting but does not accumulate
or apply a position shift; it is used after I1 has already been transformed past
I2 and both use their common post-insertion coordinates.
Merging deletion extraction lists
Mergedd(D1,D2) compares extraction positions directly. Disjoint intervals are linked
in position order. For an overlap, split the four geometrical cases until the spans are equal:
[1111111111111) [2222222222222) [111111111111) [111111)
[2222222) [1111111) [222222) [222222222222)
Merge complete equal-span alias groups in non-decreasing site order, as in merge sort. Then advance
past the complete merged group. Append any remaining D2 list and clear its head.
Merging move extraction lists
Mergexx(X1,X2) uses the same position alignment. For an equal span, merge the two
increasing e sequences. Existing X1 values must shift to account for members
inserted from X2:
int xq = x1->xq;
int s = 0;
while (1)
{
if (x2->e <= s + x1->e)
{
++s;
MoveInterval* nextx2 = x2->nextX;
InsertExtractionJustAfter(fx1, prevx1, x2);
prevx1 = x2;
x2 = nextx2;
if (!x2 || x2->xq != xq)
{
do
{
x1->e += s;
prevx1 = x1;
x1 = x1->nextX;
}
while (x1 && x1->xq == xq);
break;
}
}
else
{
x1->e += s;
prevx1 = x1;
x1 = x1->nextX;
if (!x1 || x1->xq != xq)
{
prevx1->nextX = x2;
x2->prevX = prevx1;
MoveInterval* lastx2;
do
{
lastx2 = x2;
x2 = x2->nextX;
}
while (x2 && x2->xq == xq);
prevx1 = lastx2;
lastx2->nextX = x1;
if (x1) x1->prevX = lastx2;
break;
}
}
}Equality processes X2; this is the serial merge order.
The mutable Merge function
The following five subsections form the body of the mutable overload. It consumes O2
while building the composite in O1. The opening listing validates both inputs; the
listing after step 5 clears O2, compacts and validates the result, and closes the
function.
void Merge(Operation& O1, Operation& O2)
{
O1.AssertValid();
O2.AssertValid();Step 1: merge creations
{
for (auto& [doc, di2] : O2.documents)
{
if (di2.c)
{
DocIntervals& di1 = O1.documents[doc];
IT_xi(di1.x, di2.c); // x1 = IT(x1,c2)
Transposeii(di1.i, di2.c);
IT_xi(di1.d, di2.c); // d1 = IT(d1,c2)
Mergeii(di1.c, di2.c); // assumes c1 >> c2
}
}
}Step 2: track D2 through moves of O1
At this point D2 and I1 are expressed in exactly the same coordinates:
post-C1,I1,C2. A direct overlap test is therefore meaningful. An overlap says that
D2 is deleting characters that O1 moved. The deletion must consequently
track from the move destination I1 back to the corresponding source
X1:
if (I1 == D2) D2 = X1
Track_ETxm(D2,I1,N2) discovers those cases but does not relink the extraction list
during its traversal. It appends commands to N2. Only after every document has been
scanned does ApplyNewExtractionPosCommands move the complete deletion alias groups in
O2. This delay prevents tracking from invalidating the active list and map iterators.
{
std::vector<SetNewExtractionPosCommand<DeleteInterval> > N2;
for (auto& [doc, di2] : O2.documents)
{
if (di2.d)
{
DocIntervals& di1 = O1.documents[doc];
Track_ETxm(di2.d, di1.i, N2);
}
}
ApplyNewExtractionPosCommands(O2, N2);
}How steps 3–5 fit together
The next three steps implement one continuous argument. Let O=[O1 O2] be the merged
operation. Both O.I and O.X must be expressed in post-O.I
coordinates, where O.I is the combined insertion effect of I1 and
I2. Step 3 therefore transforms I1 and X1 past
I2, placing I1,X1,I2,X2 in one common coordinate system.
In that coordinate system there are exactly two forms of move conflict:
1. X2 = I1 a chained move 2. X2 = X1 competing moves of the same characters
Step 4 resolves the first form by tracking X2 back to X1. Once that rule
has been fully applied, every conflict has the second form. Step 5 can therefore find all competing
moves simply by comparing X2 with X1. It merges their e
coordinates like insertion positions, preserving the ordering that chooses the enabled move.
Step 3: common post-I1,I2 coordinates
|
v
Step 4: X2 = I1 becomes X2 = X1
|
v
Step 5: merge coincident X1 and X2, including e coordinates
Step 3: merge deletions and prepare moves
The tracking rule from step 2 has made D2 and I1 mutually exclusive, so
ET_xi may remove the positional effect of I1 from D2.
D1 and D2 are then in the same coordinate system, allowing
Mergedd to take their union. Coincident deletions are retained as aliases rather than
discarded.
The merged operation O=[O1 O2] must express both its move insertions and move
extractions in post-O.I coordinates, where O.I is the combined effect of
I1 and I2. The last two calls therefore inclusion-transform X1
and I1 past I2. Afterwards I1,X1,I2,X2 all use the common
post-I1,I2 coordinate system.
{
for (auto& [doc, di2] : O2.documents)
{
DocIntervals& di1 = O1.documents[doc];
ET_xi(di2.d, di1.i);
Mergedd(di1.d, di2.d);
IT_xi(di1.x, di2.i);
IT2_ii(di1.i, di2.i);
}
}Step 4: unchain moves
There are two ways in which a move from O2 can conflict with a move from
O1: X2=I1, which is a chained move, and X2=X1, which means
that both moves extract the same working characters. Both comparisons are now meaningful because
all four move lists use the common post-I1,I2 coordinates established by step 3.
Resolve the chained case first by applying the tracking rule
if (X2 == I1) X2 = X1. Thus a move from A to B followed by a move from B to C is
represented by two extractions that alias A; the composite operation contains no internal A-to-B,
B-to-C chain. As in step 2, Track_ETxm records every relocation in N2, and
the commands are applied only after all documents have been scanned.
{
std::vector<SetNewExtractionPosCommand<MoveInterval> > N2;
for (auto& [doc, di2] : O2.documents)
{
if (di2.x)
{
DocIntervals& di1 = O1.documents[doc];
Track_ETxm(di2.x, di1.i, N2);
}
}
ApplyNewExtractionPosCommands(O2, N2);
}Step 5: merge moves
After unchaining, every remaining move conflict has the simple form X2=X1.
Mergeii_noshift merges the insertion lists without further position shifts because
step 3 already put them in their common coordinate system. Mergexx then merges the
extraction lists. For an aliased span it merges the two increasing e sequences in the
same way that Mergeii merges insertion positions: members retained from X1
are shifted by the number of preceding members inserted from X2. This preserves a unique
ordering of all competing moves and hence a unique enabled extraction.
for (auto& [doc, di2] : O2.documents)
{
DocIntervals& di1 = O1.documents[doc];
Mergeii_noshift(di1.i, di2.i);
Mergexx(di1.x, di2.x);
}Deletion and move extraction merging is deliberately delayed until after every tracking operation that could relocate those groups.
O2.documents.clear();
O1.CoalesceAdjacentIntervals();
O1.AssertValid();
O2.AssertValid();
}The const Merge overload
The public overload preserves its second argument by copying it and invoking the consuming overload. The deep-copy rules preserve the shared move objects described under Operations.
void Merge(Operation& O1, const Operation& O2)
{
Operation copyO2 = O2;
Merge(O1, copyO2);
}