19.6 Structural list operations

Splitting a creation

[------------ r1 ------------)
              split at n
[---- r1 ----)[------ r2 ----)

void SplitInterval(CreateInterval* r1, int n1)
{
    assert(r1 && n1 > 0);
    int n2 = r1->size() - n1;
    assert(n2 > 0);

    CreateInterval* r2 = new CreateInterval;
    r2->opid = r1->opid;
    r2->str.assign(r1->str.begin() + n1, r1->str.end());
    r1->str.erase(r1->str.begin() + n1, r1->str.end());
    r2->iq = r1->iq + n1;

    r2->prevI = r1;
    r2->nextI = r1->nextI;
    if (r1->nextI) r1->nextI->prevI = r2;
    r1->nextI = r2;
}

Retaining the original object as the left interval means that the list head cannot change.

Splitting an aliased deletion group

[-------)    [----------------)    [----)
[-------)                          [----)
[-------)
[-------)
[-------)
    |
    | split every alias here
    v
[--)[---)    [----------------)    [----)
[--)[---)
[--)[---)
[--)[---)
[--)[---)

If requested, follow prevX to the first interval having the same xq. Walk the complete alias group. Retain each original as a left part and allocate a right part with xq+n, the right substring and the same operation identifier. Construct the right group separately and splice it after the complete left group, preserving site order in both groups.

Splitting an aliased move group

The extraction side is split as for deletions, but every member also belongs to an insertion list. For every shared move object x1, create x2 and update both memberships:

extraction order: ... [x1-left) ...aliases... [x2-right) ...right aliases...
insertion order:  ... [x1-left)[x2-right) ...

Only after every alias has been split are the left and right extraction groups joined. Each new move object then has exactly one insertion membership and one extraction membership.

MoveInterval* SplitInterval(
    MoveInterval* r1, int n1, bool scanFirst)
{
    assert(r1 && n1 > 0 && r1->size() - n1 > 0);

    if (scanFirst)
    {
        while (r1->prevX && r1->prevX->xq == r1->xq)
            r1 = r1->prevX;
    }

    MoveInterval* firstRight = nullptr;
    MoveInterval* previousRight = nullptr;
    MoveInterval* left = r1;
    MoveInterval* right = nullptr;

    while (1)
    {
        right = new MoveInterval;
        if (!firstRight) firstRight = right;

        right->opid = left->opid;
        right->e = left->e;
        right->str.assign(left->str.begin() + n1, left->str.end());
        left->str.erase(left->str.begin() + n1, left->str.end());

        right->idoc = left->idoc;
        right->iq = left->iq + n1;
        right->prevI = left;
        right->nextI = left->nextI;
        if (left->nextI) left->nextI->prevI = right;
        left->nextI = right;

        right->xdoc = left->xdoc;
        right->xq = left->xq + n1;
        if (previousRight) previousRight->nextX = right;
        right->prevX = previousRight;
        previousRight = right;

        MoveInterval* nextLeft = left->nextX;
        if (!nextLeft || nextLeft->xq != left->xq) break;
        left = nextLeft;
    }

    firstRight->prevX = left;
    right->nextX = left->nextX;
    if (left->nextX) left->nextX->prevX = right;
    left->nextX = firstRight;
    return firstRight;
}

Relocating an extraction group

SetNewExtractionPosition(first,doc,q) requires the head of a complete alias group. Find its last member, change xdoc,xq on every member, detach the group from its old extraction list, then insert it into the unique position determined by increasing xq in the new document's extraction list. The new span must be disjoint from every existing extraction span, so equality with an existing xq is not a tie case here. The order within the relocated alias group is unchanged.

old: ... [before) [ first ... last ] [after) ...
                        |       |
                        +-------+---- detach together

new: ... [left) [ first ... last ] [right) ...

The move objects retain their insertion links throughout.

The reference implementation supplies overloads for delete and move groups. Each performs these same operations with its concrete pointer type: identify first..last, update their coordinates, detach the range, reset its boundary links, scan to the ordered destination, assert that its neighbours do not overlap, and splice the complete range. The move overload touches only prevX,nextX; its insertion membership is unchanged.

Delayed tracking

template <class T>
struct SetNewExtractionPosCommand
{
    SetNewExtractionPosCommand(T* x, DocId xdoc, int xq) :
        x(x), xdoc(xdoc), xq(xq) {}

    T* x;
    DocId xdoc;
    int xq;
};

template <class T>
void ApplyNewExtractionPosCommands(
    Operation& O,
    const std::vector<SetNewExtractionPosCommand<T> >& N)
{
    for (const auto& command : N)
    {
        O.SetNewExtractionPosition(command.x, command.xdoc, command.xq);
    }
}

A scan appends commands in discovery order. Only after every affected document has been scanned are the commands applied through SetNewExtractionPosition. Immediate relinking would invalidate active extraction pointers and document-map iterators.

Coalescing

After a major algorithm, repeatedly coalesce adjacent compatible intervals in every document until no further coalescing is possible. Two adjacent creation intervals coalesce when their operation identifiers agree and r1.iq+len(r1)=r2.iq. Append r2.str to r1.str, unlink r2 and continue testing the enlarged interval against its new successor.

Deletion coalescing operates on two adjacent alias groups, not on one pair in isolation:

[-- left group --)[------ right group ------)
[----------------)[-------------------------)
[----------------)[-------------------------)

The two groups must be contiguous, contain the same number of aliases, and have equal operation identifiers pairwise in alias order. Append every right string to its corresponding left string, delete the complete right group, and reconnect the enlarged left group to the following extraction.

Move coalescing has the same group shape. Corresponding members must have equal operation identifiers, equal e, equal insertion documents, contiguous insertion positions, equal extraction documents and contiguous extraction positions. For each pair, append the string and unlink the right move object from its insertion list before deleting it. After every pair is handled, reconnect the enlarged left extraction group to the following group.

After reaching that fixed point, remove every document-map entry whose four list heads are null. Coalescing does not change operation semantics; it reverses compatible splits and reduces later scan lengths.