19.10 Transpose

The supporting move-tracking algorithms used below are specified in Move tracking and transpose helpers. This subchapter specifies the complete Transpose(Operation&,Operation&) function that orders and combines them with the elementary interval transformations.

Contract

Given the context-serialised sequence [O1,O2], Transpose(O1,O2) changes both operations in place to [O2',O1'] with the same effect. The operation identifiers must differ. Both input operations must satisfy all representation invariants; both output operations must satisfy them as well.

Write each operation as its four families of intervals:

O1 = [ C1 D1 I1 X1 ]
O2 = [ C2 D2 I2 X2 ]

The complete transpose consists of the sixteen pairwise interactions in this matrix. The axes use the coordinate order C,D,I,X: a cell ab is the interaction between the column family a from O1 and the row family b from O2. Processing begins at the bottom right and progresses towards the top left. The order is significant because completed cells establish the compatible coordinates required at the moving frontier; the phase diagrams therefore describe the dependency structure of the algorithm as well as its progress.

Four by four Transpose interaction matrix for the C, D, I and X families of O1 and O2

The phase diagrams use the symbols defined in Dual inclusion transformation, oriented for this matrix: O1 proceeds upwards and O2 proceeds from right to left. A combined symbol therefore has two arrows emanating from the bottom-right corner of its cell. The calls shown beneath each diagram are normative.

The `Transpose` function

The following seven subsections are consecutive parts of this function body. The opening listing gives the function signature and validates its inputs; the closing listing after step 7 gives the common epilogue and closes the function.

void Transpose(Operation& O1, Operation& O2)
{
    assert(O1.GetId() != O2.GetId());
    O1.AssertValid();
    O2.AssertValid();

Step 1: transpose creations from O2

Transpose progress matrix after processing the creations of O2

For every document occurring in both operations, in this exact order:

    {
        for (auto& [doc, di2] : O2.documents)
        {
            auto m1 = O1.documents.find(doc);
            if (m1 != O1.documents.end())
            {
                DocIntervals& di1 = m1->second;
                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)
                Transposeii(di1.c, di2.c);
            }
        }
    }

This moves C2 to the left of every family in O1. The extraction transforms split intervals when a creation falls inside them; the insertion transposes use their accumulated left and right shifts.

Step 2: track deletions from O2 back through moves of O1

Transpose progress matrix after D2 tracks the move of O1

After step 1, D2 and I1 are both in post-C1,I1,C2 coordinates. An overlap therefore means that D2 deletes characters moved by O1. For every common document call TrackETxm(D2,I1,N2). Only after all documents have been scanned, apply every command in N2 to O2.

    {
        std::vector<SetNewExtractionPosCommand<DeleteInterval> > N2;
        for (auto& [doc, di2] : O2.documents)
        {
            auto m1 = O1.documents.find(doc);
            if (m1 != O1.documents.end())
            {
                DocIntervals& di1 = m1->second;
                Track_ETxm(di2.d, di1.i, N2);
            }
        }
        ApplyNewExtractionPosCommands(O2, N2);
    }

Step 3: process D2 and transform I1 and X1 past I2

Transpose progress matrix after processing D2, I1 and X1 against I2

    {
        for (auto& [doc, di2] : O2.documents)
        {
            auto m1 = O1.documents.find(doc);
            if (m1 != O1.documents.end())
            {
                DocIntervals& di1 = m1->second;
                ET_xi(di2.d, di1.i);
                ET_xi(di2.d, di1.c);
                IT_xi(di1.x, di2.i);
                IT2_ii(di1.i, di2.i);
            }
        }
    }

The tracking in step 2 made D2 and I1 mutually exclusive, satisfying the first call's precondition. Concurrency makes D2 and C1 mutually exclusive. After the final two calls, I1,X1,I2,X2 all use the context containing both sets of move insertions; the move conflicts can now be compared directly.

Step 4: transpose competing moves

Transpose progress matrix after transposing competing moves

Create empty command lists N1 and N2. For every common document call TransposeXX1(X1,X2,N1), followed by TransposeXX2(I1,X2,N1,N2). After every document has been scanned, apply N1 to O1 and N2 to O2. No extraction list may be relocated before both scans have finished.

    {
        std::vector<SetNewExtractionPosCommand<MoveInterval> > N1;
        std::vector<SetNewExtractionPosCommand<MoveInterval> > N2;
        for (auto& [doc, di2] : O2.documents)
        {
            auto m1 = O1.documents.find(doc);
            if (m1 != O1.documents.end())
            {
                DocIntervals& di1 = m1->second;
                TransposeConcurrent_xx_1(di1.x, di2.x, N1);
                TransposeConcurrent_xx_2(di1.i, di2.x, N1, N2);
            }
        }
        ApplyNewExtractionPosCommands(O1, N1);
        ApplyNewExtractionPosCommands(O2, N2);
    }

Step 5: exclusion-transform I2 and X2 past I1

Transpose progress matrix after exclusion-transforming I2 and X2 past I1

    {
        for (auto& [doc, di2] : O2.documents)
        {
            auto m1 = O1.documents.find(doc);
            if (m1 != O1.documents.end())
            {
                DocIntervals& di1 = m1->second;
                ET_xi(di2.x, di1.i);
                ET2_ii(di2.i, di1.i);
                IT_xi(di1.d, di2.i);
            }
        }
    }

Step 4 made X2 and I1 mutually exclusive. The first two calls remove the effect of I1 from both parts of the moves in O2. The third begins transforming the deletions of O1 through the moves of O2 by first accounting for their insertions.

Step 6: track D1 through enabled moves of O2

Transpose progress matrix after D1 tracks the enabled move of O2

For every common document run ITdx(D1,X2,ND1). It aligns overlapping spans by splitting. When an X2 alias group begins with e=0, append a command to move the complete overlapping D1 alias group to (X2.idoc,X2.iq). Apply ND1 to O1 only after all documents have been scanned.

    {
        std::vector<SetNewExtractionPosCommand<DeleteInterval> > ND1;
        for (auto& [doc, di2] : O2.documents)
        {
            auto m1 = O1.documents.find(doc);
            if (m1 != O1.documents.end())
            {
                DocIntervals& di1 = m1->second;
                IT_dx(di1.d, di2.x, ND1);
            }
        }
        ApplyNewExtractionPosCommands(O1, ND1);
    }

Step 7: finish C1 against the moves of O2

Transpose progress matrix after completing the remaining position changes

    {
        for (auto& [doc, di2] : O2.documents)
        {
            auto m1 = O1.documents.find(doc);
            if (m1 != O1.documents.end())
            {
                DocIntervals& di1 = m1->second;
                Transposeii(di1.c, di2.i);
                ET_xi(di2.x, di1.c);
            }
        }
    }

Concurrency guarantees that X2 and C1 are mutually exclusive. These calls complete the remaining position changes. Finally coalesce adjacent compatible intervals in both operations and check every invariant.

    O1.CoalesceAdjacentIntervals();
    O2.CoalesceAdjacentIntervals();
    O1.AssertValid();
    O2.AssertValid();
}

Implementation correspondence

The seven steps above occur in the same order as Transpose(Operation&,Operation&). The preceding helper subchapter specifies Track_ETxm, Transpose_ee, TransposeConcurrent_xx_1 and TransposeConcurrent_xx_2. Together, the two subchapters correspond directly to Transpose.cpp.

Previous19.9 Move tracking and transpose helpers Next19.11 Merge