19.9 Move tracking and transpose helpers

The top-level Transpose algorithm uses the four supporting algorithms below when moves interact with deletions or other moves. They align interval boundaries before comparing character identity, preserve complete alias groups, and delay extraction relocation until active scans have finished. Track_ETxm is also used by Merge to follow an extraction backwards through an enabled move.

Supporting algorithm: track an extraction through a move

TrackETxm(x2,i1,N2) implements the rule if (i1 == x2) x2 = x1. Here x2 may be either a deletion or a move extraction. The insertion list i1 and extraction list x2 are in the same post-insertion coordinates, so their intervals may be compared directly. An overlap means that the extraction refers to characters inserted at the destination of an enabled move in O1.

Disjoint intervals simply advance the list whose interval ends first:

[11111)          [22222)          advance i1

[22222)          [11111)          advance x2

For an overlap, first align the left edges:

[1111111111111)                   split i1; continue with its right part
      [2222222)

[2222222222222)                   split x2; continue with its right part
      [1111111)

Then align the right edges:

[111111111111)                    split i1 after the common span
[222222)

[111111)                          split x2 after the common span
[222222222222)

The result is an equal span:

[111111)
[222222)

The move interval i1 must have e=0. Append the command track(x2,i1.xdoc,i1.xq) to N2, advance i1, and advance x2 past its complete alias group. Apply not perform the tracking during the scan.

template <class T>
void Track_ETxm(
    T* x2,
    MoveInterval* i1,
    std::vector<SetNewExtractionPosCommand<T> >& N2)
{
    while (i1 && x2)
    {
        if (i1->iq + i1->size() <= x2->xq)
        {
            i1 = i1->nextI;
        }
        else if (x2->xq + x2->size() <= i1->iq)
        {
            x2 = x2->nextX;
        }
        else
        {
            if (i1->iq < x2->xq)
            {
                SplitInterval(i1, x2->xq - i1->iq, true);
                i1 = i1->nextI;
            }
            else if (x2->xq < i1->iq)
            {
                x2 = SplitInterval(x2, i1->iq - x2->xq, false);
            }

            assert(x2->xq == i1->iq);
            if (x2->size() < i1->size())
                SplitInterval(i1, x2->size(), true);
            else if (i1->size() < x2->size())
                SplitInterval(x2, i1->size(), false);

            assert(i1->size() == x2->size());
            assert(i1->e == 0);
            N2.push_back(SetNewExtractionPosCommand<T>(
                x2, i1->xdoc, i1->xq));

            i1 = i1->nextI;
            int xq = x2->xq;
            do x2 = x2->nextX; while (x2 && x2->xq == xq);
        }
    }
}

Supporting algorithm: transpose competing e-coordinates

When two move alias groups compete for the same characters, regard every move interval as a single-character insertion at its e coordinate. TransposeEE(x1,x2) transposes the two increasing sequences. The groups may be at different extraction positions, so save xq1=x1.xq and xq2=x2.xq independently.

void Transpose_ee(
    MoveInterval* x1,
    MoveInterval* x2,
    MoveInterval*& nx1,
    MoveInterval*& nx2)
{
    assert(x1 && x2);
    int s1 = 0;
    int s2 = 0;
    int xq1 = x1->xq;
    int xq2 = x2->xq;

    while (1)
    {
        if (x2->e <= s2 + x1->e)
        {
            x2->e -= s1;
            ++s2;
            x2 = x2->nextX;
            if (!x2 || x2->xq != xq2)
            {
                do
                {
                    x1->e += s2;
                    x1 = x1->nextX;
                }
                while (x1 && x1->xq == xq1);
                break;
            }
        }
        else
        {
            x1->e += s2;
            ++s1;
            x1 = x1->nextX;
            if (!x1 || x1->xq != xq1)
            {
                do
                {
                    x2->e -= s1;
                    x2 = x2->nextX;
                }
                while (x2 && x2->xq == xq2);
                break;
            }
        }
    }
    nx1 = x1;
    nx2 = x2;
}

The <= comparison is significant: equality processes x2. The returned pointers are the first intervals following the two groups and must be used to resume the outer scan.

Supporting algorithm: coincident extraction groups

TransposeXX1(X1,X2,N1) handles the rule below for move extractions that refer to the same span:

if (x1 == x2) {
    if (x1.e < x2.e) --x2.e; else ++x1.e;
    if (x2.e == 0) asynchronously track x1 to i2;
}

Scan X1 and X2 by extraction position. Use exactly the four overlap pictures shown for TrackETxm to split partial overlaps until the two current spans are equal. At that point x1.e must be greater than zero: if it had been enabled, x2 would already have tracked to its destination and could not still alias it. Call TransposeEE(x1,x2). Test x2.e after that call; if it is zero, append track(x1,x2.idoc,x2.iq) to N1. Resume from the two next-group pointers returned by TransposeEE.

void TransposeConcurrent_xx_1(
    MoveInterval* x1,
    MoveInterval* x2,
    std::vector<SetNewExtractionPosCommand<MoveInterval> >& N1)
{
    while (x1 && x2)
    {
        if (x1->xq + x1->size() <= x2->xq)
        {
            x1 = x1->nextX;
        }
        else if (x2->xq + x2->size() <= x1->xq)
        {
            x2 = x2->nextX;
        }
        else
        {
            if (x1->xq < x2->xq)
                x1 = SplitInterval(x1, x2->xq - x1->xq, false);
            else if (x2->xq < x1->xq)
                x2 = SplitInterval(x2, x1->xq - x2->xq, false);

            assert(x2->xq == x1->xq);
            if (x2->size() < x1->size())
                SplitInterval(x1, x2->size(), false);
            else if (x1->size() < x2->size())
                SplitInterval(x2, x1->size(), false);

            assert(x1->size() == x2->size());
            assert(x1->e > 0);

            MoveInterval* nx1;
            MoveInterval* nx2;
            Transpose_ee(x1, x2, nx1, nx2);
            if (x2->e == 0)
                N1.push_back(SetNewExtractionPosCommand<MoveInterval>(
                    x1, x2->idoc, x2->iq));
            x1 = nx1;
            x2 = nx2;
        }
    }
}

Supporting algorithm: an extraction at a move destination

TransposeXX2(I1,X2,N1,N2) handles the second way in which the moves can conflict:

if (i1 == x2) {
    asynchronously track x2 back to x1;
    if (i1.e < x2.e) --x2.e; else ++i1.e;
    if (x2.e == 0) asynchronously track x1 to i2;
}

Scan insertion positions from I1 against extraction positions from X2. Use the same four overlap cases, comparing i1.iq with x2.xq. When splitting i1, set scanFirst=true because splitting one move must split its complete extraction alias group as well. Once the spans are equal, require i1.e=0 and append track(x2,i1.xdoc,i1.xq) to N2.

Follow the shared move object i1 into its extraction list and walk backward through prevX to the head of its alias group. Call that head x1. Invoke TransposeEE(x1,x2). If the resulting x2.e=0, append track(i1,x2.idoc,x2.iq) to N1. Resume X2 from the next-group pointer returned by TransposeEE, and advance i1 through nextI. This traversal through both sets of links is why the insertion and extraction lists must contain the same move objects.

void TransposeConcurrent_xx_2(
    MoveInterval* i1,
    MoveInterval* x2,
    std::vector<SetNewExtractionPosCommand<MoveInterval> >& N1,
    std::vector<SetNewExtractionPosCommand<MoveInterval> >& N2)
{
    while (i1 && x2)
    {
        if (i1->iq + i1->size() <= x2->xq)
        {
            i1 = i1->nextI;
        }
        else if (x2->xq + x2->size() <= i1->iq)
        {
            x2 = x2->nextX;
        }
        else
        {
            if (i1->iq < x2->xq)
            {
                SplitInterval(i1, x2->xq - i1->iq, true);
                i1 = i1->nextI;
            }
            else if (x2->xq < i1->iq)
            {
                x2 = SplitInterval(x2, i1->iq - x2->xq, false);
            }

            assert(x2->xq == i1->iq);
            if (x2->size() < i1->size())
                SplitInterval(i1, x2->size(), true);
            else if (i1->size() < x2->size())
                SplitInterval(x2, i1->size(), false);

            assert(i1->size() == x2->size());
            assert(i1->e == 0);
            N2.push_back(SetNewExtractionPosCommand<MoveInterval>(
                x2, i1->xdoc, i1->xq));

            MoveInterval* x1 = i1;
            int xq = x1->xq;
            while (x1->prevX && x1->prevX->xq == xq)
                x1 = x1->prevX;

            MoveInterval* nx1;
            MoveInterval* nx2;
            Transpose_ee(x1, x2, nx1, nx2);

            assert(x2->e >= 0);
            if (x2->e == 0)
                N1.push_back(SetNewExtractionPosCommand<MoveInterval>(
                    i1, x2->idoc, x2->iq));

            x2 = nx2;
            i1 = i1->nextI;
        }
    }
}