15.4 Multi-character insertion and deletion operations

(29 August 2005)

Abstract

The algorithm presented in [3] is simple, but its Boolean enabled-delete representation is correct only for the restricted execution paths identified in that chapter. This paper provides a more efficient interval algorithm for multi-character insertion and deletion operations on the same restricted domain.

Introduction

In this paper an operation efficiently stores a set of characters to be deleted as well as a set of characters to be inserted. It follows the representation in [4]; that is, the characters to be deleted are represented by an ordered set of intervals. Similarly the characters to be inserted are represented by an ordered set of insertion strings. This means a single operation can efficiently represent arbitrary changes to the document state, allowing it to be closed under merging. Efficient merging algorithms have been presented in [4].

Note that the extractions are in pre-extraction coordinates, while the insertions are in post-insertion coordinates.

As in [4], left-to-right scans of the intervals are used to provide algorithms that are linear, not quadratic in the number of deletion and insertion strings.

Review of algorithm for single character operations

The following table from [3] defines the IT,ET algorithms for single character insert/delete operations:

O1 O2 IT(O1,O2)
ins ins if (O2.q < O1.q || O2.q == O1.q && O2.id < O1.id) { ++O1.q; ++O1.p; }
del ins if (O2.q <= O1.q) { ++O1.q; ++O1.p; }
ins del if (O2.enabled && O2.q < O1.q) --O1.p;
del del if (O2.enabled && O2.q < O1.q) --O1.p;
if (O2.enabled && O2.q == O1.q) O1.enabled = false;

O1 O2 ET(O1,O2)
ins ins if (O2.q < O1.q) { --O1.q; --O1.p; }
del ins if (O2.q < O1.q) { --O1.q; --O1.p; }
ins del if (O2.enabled && O2.q < O1.q) ++O1.p;
del del if (O2.enabled && O2.q < O1.q) ++O1.p;
if (O2.enabled && O2.q == O1.q) O1.enabled = true;

The aim of this paper is to provide equivalent algorithms for multi-character delete/insert operations.

Multi-character insertion operations

Firstly we limit ourselves to insertion operations that apply to a single text document. There is no need for a separate q-position.

Dual IT

Insertion positions in O1 and O2 need to be shifted to the right. We accumulate the number of inserted characters in O1 and in O2. These are the required shifts to be applied. At each step of the algorithm we have an insert in O1 and an insert from O2. We simply compare their positions. If they are equal, then we use site identifiers to break the tie. 


void DualIT(MultiCharInsertOp& O1, MultiCharInsertOp& O2)
{
    int s1 = 0;     // Accumulated characters inserted by O1
    int s2 = 0;     // Accumulated characters inserted by O2

    iterator i1 = O1.begin();
    iterator i2 = O2.begin();

    while(i1 != O1.end() && i2 != O2.end())
    {
        int d = (s1 + i2->p) - (s2 + i1->p);
        if (d < 0 || d == 0 && O2.id < O1.id)
        {
            // Process i2
            i2->p += s1;
            s2 += i2->size();
            ++i2;
        }
        else
        {
            // Process i1
            i1->p += s2;
            s1 += i1->size();
            ++i1;
        }
    }
    if (s1)
    {
        while (i2 != O2.end())
        {
            i2->p += s1;
            ++i2;
        }
    }
    if (s2)
    {
        while (i1 != O1.end())
        {
            i1->p += s2;
            ++i1;
        }
    }
}

Adjacent swap

Insertion coordinates are post-insertion coordinates. Coordinates in O2 need to be shifted left to exclude the effect of O1. Coordinates in O1 need to be shifted right to include the effect of O2.

The following shows an initial document state, and strings inserted first by O1 then by O2. 

              O1                    O2
      abcde   -->    ab111cde       -->  a222b111c2222de
                       [ )                [ )     [  )
                  (coords for O1)         (coords for O2)

              O2'                   O1'
      abcde   -->    a222bc2222de   -->  a222b111c2222de
                      [ )  [  )               [ )
                  (coords for O2')        (coords for O1')

The following algorithm in C++ shows how a left-to-right scan through the insertion strings in O1,O2 can be used to transpose O1, O2 in time linear in the number of insertion strings in O1 and O2. 


void AdjSwap(MultiCharInsertOp& O1, MultiCharInsertOp& O2)
{
    int s1 = 0;     // Accumulated characters inserted by O1
    int s2 = 0;     // Accumulated characters inserted by O2

    iterator i1 = O1.begin();
    iterator i2 = O2.begin();

    while(i1 != O1.end() && i2 != O2.end())
    {
        if (s2 + i1->p < i2->p)
        {
            // Process i1
            i1->p += s2;
            s1 += i1->size();
            ++i1;
        }
        else
        {
            // Process i2
            i2->p -= s1;
            s2 += i2->size();
            ++i2;
        }
    }

    if (s1)
    {
        while (i2 != O2.end())
        {
            i2->p -= s1;
            ++i2;
        }
    }
    if (s2)
    {
        while (i1 != O1.end())
        {
            i1->p += s2;
            ++i1;
        }
    }
}

Multi-character insertion and deletion operations

Each operation contains the following fields.

Field Description
id The site identifier of the site that originally generated the operation.
X An ordered set of extraction intervals
I An ordered set of insertion strings

An extraction interval stores the following fields

Field Description
p p-position of string to be extracted
q q-position of string to be extracted
s string to be extracted
enabled flag to indicate whether the extraction is enabled

An insertion string stores the following fields

Field Description
p p-position of string to be inserted
q q-position of string to be inserted
s String to be inserted.

Splitting an extraction interval

It is sometimes necessary to split an extraction interval. The C++ algorithm presented below ensures equivalence of the operation when an extraction interval is split. This requires attention to the fields within an interval - the string, p-position, q-position and enabled status. 


// Insert an element into the list just after position i, which must not be at the end of the list
// Returns iterator to inserted element.
template <class T>
inline typename std::list<T>::iterator InsertAfter(
    std::list<T>& L, typename std::list<T>::iterator i)
{
    cxAssert(i != L.end());
    return L.insert(++i, T());    // Insert just before (i+1), which is immediately after i
}

/*
Split the interval in list X at iterator position i, so that the left interval is of size n1

        [iiiiiiiiiiiiiiiiii)

 --->   [iiiiiiii)[jjjjjjjj)

        <-- n1 --><-- n2 -->
*/

void SplitRange(MCID_XRanges& X, MCID_XRanges::iterator i, int n1)
{
    int n2 = i->size() - n1;
    MCID_XRanges::iterator j = InsertAfter<MCID_XRange>(X,i);
    j->p = i->p;
    if (i->enabled) j->p += n1;     // Note: don't offset p-position when disabled
    j->q = i->q + n1;
    j->s = std::string(i->s.begin() + n1, i->s.end());
    j->enabled = i->enabled;
    i->s.erase(i->s.begin() + n1, i->s.end());
}

DualIT_dd

This algorithm handles the dual IT of deletions with deletions. The following part of the algorithm for IT is relevant.

O1 O2 IT(O1,O2)
del del if (O2.enabled && O2.q < O1.q) --O1.p;
if (O2.enabled && O2.q == O1.q) O1.enabled = false;

As we scan left-to-right, we treat the deletions as intervals (not merely positions). There are a number of cases for processing the next two intervals. Eg they can be disjoint, partially overlap, coincide or one interval can contain the other.

Where intervals are both enabled and overlap then the overlapping part needs to be disabled. This may require splitting of the intervals.

Notes

  • When comparing q-positions we never apply shifts, because deletions have no effect on the effects document.
  • The accumulated shift is applied to the p-position. The accumulated shift should only account for the enabled deletions.
  • Intervals are shifted whether they are enabled or not 

void DualIT_dd(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    MCID_XRanges& X1 = O1.X;
    MCID_XRanges& X2 = O2.X;

    int s1 = 0;     // Accumulated shift from enabled intervals of X1
    int s2 = 0;     // Accumulated shift from enabled intervals of X2

    MCID_XRanges::iterator x1 = X1.begin();
    MCID_XRanges::iterator x2 = X2.begin();

    while(x1 != X1.end() && x2 != X2.end())
    {
        if (x1->q + x1->size() <= x2->q)
        {
            // Next is [11111)
            x1->p -= s2;
            if (x1->enabled) s1 += x1->size();
            ++x1;
        }
        else if (x2->q + x2->size() <= x1->q)
        {
            // Next is [22222)
            x2->p -= s1;
            if (x2->enabled) s2 += x2->size();
            ++x2;
        }
        else
        {
            // Intervals overlap
            if (x1->q < x2->q)
            {
                // [1111111111111
                //       [2222222
                SplitRange(X1, x1, x2->q - x1->q);
                x1->p -= s2;
                if (x1->enabled) s1 += x1->size();
                ++x1;
            }
            else if (x2->q < x1->q)
            {
                // [2222222222222
                //       [1111111
                SplitRange(X2, x2, x1->q - x2->q);
                x2->p -= s1;
                if (x2->enabled) s2 += x2->size();
                ++x2;
            }

            cxAssert(x2->q == x1->q);
            if (x2->size() < x1->size())
            {
                // [222222)
                // [111111111111)
                SplitRange(X1, x1, x2->size());
            }
            else if (x1->size() < x2->size())
            {
                // [111111)
                // [222222222222)
                SplitRange(X2, x2, x1->size());
            }

            // [111111)
            // [222222)
            cxAssert(x1->size() == x2->size());
            x2->p -= s1;
            x1->p -= s2;
            bool x1enabled = x1->enabled;
            if (x2->enabled) { s2 += x2->size(); x1->enabled = false; }
            if (x1enabled) { s1 += x1->size(); x2->enabled = false; }
            ++x1;
            ++x2;
        }
    }

    // Apply shifts to remaining intervals in X (if any)
    if (s1)
    {
        while (x2 != X2.end())
        {
            x2->p -= s1;
            ++x2;
        }
    }

    // Apply shifts to remaining intervals in I (if any)
    if (s2)
    {
        while (x1 != X1.end())
        {
            x1->p -= s2;
            ++x1;
        }
    }

    CoalesceRanges(X1);
    CoalesceRanges(X2);
}

DualIT_id

This algorithm handles the dual IT of insertions with deletions. The following part of the algorithm for IT of single character operations is relevant:

O1 O2 IT(O1,O2)
del ins if (O2.q <= O1.q) { ++O1.q; ++O1.p; }
ins del if (O2.enabled && O2.q < O1.q) --O1.p;

In the following example, let O1 insert '1' characters, and O2 delete '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. 

                        O2                                  O1'
    a222bc22222d22ef   --->   a***bc*****d**ef             --->    a111*11**b11c*****d**ef11
     [ )  [   ) [)                                                  [ ) [)   [)           [)

                        O1                                  O2'
    a222bc22222d22ef   --->   a11121122b11c22222d22ef11    --->    a111*11**b11c*****d**ef11
                               [ ) [)   [)           [)
                                 [)  [)    [   ) [)

Notes

  • We scan left-to-right through O1 and O2. At each step we consider the next interval from O2 and the next insertion position from O1
  • We make sense of what is happening in the document state obtained after performing O1. In this state all characters are present.
  • Coordinates mentioned in O1 are already relative to this state. Coordinates in O2 need to be shifted right by the number of characters inserted on the left by O1.
  • Extraction intervals may need to be split when there are insertions within an interval. 

void DualIT_id(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    MCID_IRanges& I = O1.I;
    MCID_XRanges& X = O2.X;

    int si = 0;     // Accumulated shift from I
    int sx = 0;     // Accumulated shift from X

    MCID_XRanges::iterator x = X.begin();
    MCID_IRanges::iterator i = I.begin();

    while(i != I.end() && x != X.end())
    {
        if (i->q <= si + x->q)
        {
            //    [xxxxxxx)
            //   i
            // Process next insertion
            si += i->size();
            i->p -= sx;
            ++i;
        }
        else
        {
            int d = i->q - (si + x->q);
            if (d < x->size())
            {
                // [xxxxxx)
                //     i
                SplitRange(X,x, i->q - (si + x->q));
            }

            // [xxxxxx)
            //          i
            // Process next extraction
            x->q += si;
            x->p += si;
            if (x->enabled) sx += x->size();
            ++x;
        }
    }

    if (si)
    {
        while (x != X.end())
        {
            x->q += si;
            x->p += si;
            ++x;
        }
    }

    if (sx)
    {
        while (i != I.end())
        {
            i->p -= sx;
            ++i;
        }
    }
}

DualIT_ii

This algorithm handles the dual IT of insertions with insertions. The following part of the algorithm for IT of single character operations is relevant:

O1 O2 IT(O1,O2)
ins ins if (O2.q < O1.q || O2.q == O1.q && O2.id < O1.id) { ++O1.q; ++O1.p; }

Insertion positions in O1 and O2 need to be shifted to the right. We accumulate the number of inserted characters in O1 and in O2. These are the required shifts to be applied.

At each step of the algorithm we have an insert in O1 and an insert from O2. We simply compare their (shifted) positions. If they are equal, then we use site identifiers to break the tie. 


void DualIT_ii(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    MCID_IRanges& I1 = O1.I;
    MCID_IRanges& I2 = O2.I;

    int s1 = 0;     // Accumulated shift from I1
    int s2 = 0;     // Accumulated shift from I2

    MCID_IRanges::iterator i1 = I1.begin();
    MCID_IRanges::iterator i2 = I2.begin();

    while(i1 != I1.end() && i2 != I2.end())
    {
        int d = (s1 + i2->q) - (s2 + i1->q);
        if (d < 0 || d == 0 && O2.id < O1.id)
        {
            // Process i2
            i2->p += s1;
            i2->q += s1;
            s2 += i2->size();
            ++i2;
        }
        else
        {
            // Process i1
            i1->p += s2;
            i1->q += s2;
            s1 += i1->size();
            ++i1;
        }
    }

    if (s1)
    {
        while (i2 != I2.end())
        {
            i2->p += s1;
            i2->q += s1;
            ++i2;
        }
    }

    if (s2)
    {
        while (i1 != I1.end())
        {
            i1->p += s2;
            i1->q += s2;
            ++i1;
        }
    }
}

DualIT

O1 and O2 are composite operations of extractions followed by insertions. Using the general algorithm for dual IT of a list with a list leads to the following algorithm for dual IT: 


void DualIT(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    DualIT_dd(O1,O2);       // Deletions against deletions
    DualIT_id(O1,O2);       // Insertions against deletions
    DualIT_id(O2,O1);       // Deletions against insertions
    DualIT_ii(O1,O2);       // Insertions against insertions
}

AdjSwap_dd

The adjacent swap algorithm transforms [O1 O2] to [O2' O1'].

This algorithm handles the transpose of deletions with deletions. The following part of the algorithm for IT/ET of single character operations is relevant:

O1 = del, O2 = del

IT(O1,O2) if (O2.enabled && O2.q < O1.q) --O1.p;
if (O2.enabled && O2.q == O1.q) O1.enabled = false;
ET(O2,O1) if (O1.enabled && O1.q < O2.q) ++O2.p;
if (O1.enabled && O1.q == O2.q) O2.enabled = true;

In the following example, let O1 delete '1' characters, and O2 delete '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. 

                        O1                        O2
    ab11112221111cd    --->   ab****222****cd    --->    ab***********cd

                        O2'                       O1'
    ab11112221111cd    --->   ab1111***1111cd    --->    ab***********cd

O2 may delete characters that have already been deleted by O1. In that case O2 should be disabled.

For the purpose of comparing q-positions there is no need to shift positions because these operations have no impact on the effects document.

As we scan left-to-right we compare the next interval from O1 against the next interval from O2. There are a number of cases to consider. 


void AdjSwap_dd(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    MCID_XRanges& X1 = O1.X;
    MCID_XRanges& X2 = O2.X;

    int s1 = 0;     // Accumulated shift from enabled intervals of X1
    int s2 = 0;     // Accumulated shift from enabled intervals of X2

    MCID_XRanges::iterator x1 = X1.begin();
    MCID_XRanges::iterator x2 = X2.begin();

    while(x1 != X1.end() && x2 != X2.end())
    {
        if (x1->q + x1->size() <= x2->q)
        {
            // Next is [11111)
            x1->p -= s2;
            if (x1->enabled) s1 += x1->size();
            ++x1;
        }
        else if (x2->q + x2->size() <= x1->q)
        {
            // Next is [22222)
            x2->p += s1;
            if (x2->enabled) s2 += x2->size();
            ++x2;
        }
        else
        {
            // Intervals overlap
            if (x1->q < x2->q)
            {
                // [1111111111111
                //       [2222222
                SplitRange(X1, x1, x2->q - x1->q);
                x1->p -= s2;
                if (x1->enabled) s1 += x1->size();
                ++x1;
            }
            else if (x2->q < x1->q)
            {
                // [2222222222222
                //       [1111111
                SplitRange(X2, x2, x1->q - x2->q);
                x2->p += s1;
                if (x2->enabled) s2 += x2->size();
                ++x2;
            }

            cxAssert(x2->q == x1->q);
            if (x2->size() < x1->size())
            {
                // [222222)
                // [111111111111)
                SplitRange(X1, x1, x2->size());
            }
            else if (x1->size() < x2->size())
            {
                // [111111)
                // [222222222222)
                SplitRange(X2, x2, x1->size());
            }

            // [111111)
            // [222222)
            cxAssert(x1->size() == x2->size());
            x1->p -= s2;
            x2->p += s1;
            if (x1->enabled) { s1 += x1->size(); x2->enabled = true; }
            if (x2->enabled) { s2 += x2->size(); x1->enabled = false; }
            ++x1;
            ++x2;
        }
    }

    // Apply shifts to remaining intervals in X (if any)
    if (s1)
    {
        while (x2 != X2.end())
        {
            x2->p += s1;
            ++x2;
        }
    }

    // Apply shifts to remaining intervals in I (if any)
    if (s2)
    {
        while (x1 != X1.end())
        {
            x1->p -= s2;
            ++x1;
        }
    }

    CoalesceRanges(X1);
    CoalesceRanges(X2);
}

AdjSwap_ii

The adjacent swap algorithm transforms [O1 O2] to [O2' O1'].

This algorithm handles the transpose of insertions with insertions. The following part of the algorithm for IT/ET of single character operations is relevant:

O1 = ins, O2 = ins

IT(O1,O2) if (O2.q < O1.q || O2.q == O1.q && O2.id < O1.id) { ++O1.q; ++O1.p; }
ET(O2,O1) if (O1.q < O2.q) { --O2.q; --O2.p; }

In the following example, let O1 insert '1' characters, and O2 insert '2' characters. 

             O1                          O2
    abcdef  -->   a111bc1111d11111ef    -->   a222111b2222c1111d111112222e2222f
                   [ )  [  ) [   )             [ )    [  )           [  ) [  )

We compare q-positions in the state obtained after execution of O2. The q-positions of O2 do not require adjustment. The q-positions of O1, however, need to be shifted to the right. 


void AdjSwap_ii(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    MCID_IRanges& I1 = O1.I;
    MCID_IRanges& I2 = O2.I;

    int s1 = 0;     // Accumulated shift from I1
    int s2 = 0;     // Accumulated shift from I2

    MCID_IRanges::iterator i1 = I1.begin();
    MCID_IRanges::iterator i2 = I2.begin();

    while(i1 != I1.end() && i2 != I2.end())
    {
        if (i2->q <= s2 + i1->q)
        {
            // Process i2
            i2->p -= s1;
            i2->q -= s1;
            s2 += i2->size();
            ++i2;
        }
        else
        {
            // Process i1
            i1->p += s2;
            i1->q += s2;
            s1 += i1->size();
            ++i1;
        }
    }

    if (s1)
    {
        while (i2 != I2.end())
        {
            i2->p -= s1;
            i2->q -= s1;
            ++i2;
        }
    }

    if (s2)
    {
        while (i1 != I1.end())
        {
            i1->p += s2;
            i1->q += s2;
            ++i1;
        }
    }
}

AdjSwap_id

The adjacent swap algorithm transforms [O1 O2] to [O2' O1'].

This algorithm handles the transpose of insertions with deletions. The following part of the algorithm for IT/ET of single character operations is relevant:

O1 = ins, O2 = del

IT(O1,O2) if (O2.enabled && O2.q < O1.q) --O1.p;
ET(O2,O1) if (O1.q < O2.q) { --O2.q; --O2.p; }

In the following example, let O1 insert '1' characters, and O2 delete '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. 

                          O1     [ )        [   )     [   )       O2
    a222b22222cd22222e    -->   a2221111b11122222cd11122222e      -->    a***1111b111*****cd111*****e
                                    [  ) [ )       [ )



                          O2'                                     O1'
    a222b22222cd22222e    -->   a***b*****cd*****e                -->    a***1111b111*****cd111*****e
     [ ) [   )  [   )                                                        [  ) [ )       [ )

Note that q-positions are compared in the state just after executing O1. In this state q-positions can be directly compared without applying shifts.

Because O1 || O2, the intervals never overlap - which would mean that a character inserted by O1 was deleted by O2.

Intervals in both O1 and O2 need to be shifted left. 


void AdjSwap_id(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    MCID_IRanges& I = O1.I;
    MCID_XRanges& X = O2.X;

    int si = 0;     // Accumulated shift from I
    int sx = 0;     // Accumulated shift from X

    MCID_XRanges::iterator x = X.begin();
    MCID_IRanges::iterator i = I.begin();

    while(i != I.end() && x != X.end())
    {
        if (i->q + i->size() <= x->q)
        {
            // Next is [11111)
            i->p -= sx;
            si += i->size();
            ++i;
        }
        else if (x->q + x->size() <= i->q)
        {
            // Next is [22222)
            x->p -= si;
            x->q -= si;
            if (x->enabled) sx += x->size();
            ++x;
        }
        else
        {
            // Intervals cannot overlap under the O1 || O2 precondition.
            cxAssert(false);
        }
    }

    if (si)
    {
        while (x != X.end())
        {
            x->p -= si;
            x->q -= si;
            ++x;
        }
    }

    if (sx)
    {
        while (i != I.end())
        {
            i->p -= sx;
            ++i;
        }
    }
}

AdjSwap_di

The adjacent swap algorithm transforms [O1 O2] to [O2' O1'].

This algorithm handles the transpose of deletions with insertions. The following part of the algorithm for IT/ET of single character operations is relevant:

O1 = del, O2 = ins

IT(O1,O2) if (O2.q <= O1.q) { ++O1.q; ++O1.p; }
ET(O2,O1) if (O1.enabled && O1.q < O2.q) ++O2.p;

In the following example, let O1 delete '1' characters, and O2 insert '2' characters. An asterisk represents the placeholder for a "deleted" character in the effects document. 

                       O1                                     O2
    a111bc1111de1111  --->    a***bc****de****               --->    a*2222**b222c****d222e**222**
     [ )  [  )  [  )                                                   [  )   [ )      [ )   [ )


                       O2'                                    O1'
    a111bc1111de1111  --->    a1222211b222c1111d222e1122211  --->    a*2222**b222c****d222e**222**
                                [  )   [ )      [ )   [ )             [)   [)     [  )     [)   [)

We make comparisons in the state corresponding to after the execution of O2. In this state q-positions of O1 are shifted right to include the effect of O2. q-positions of O2 do not need to be shifted for the purposes of comparison of q-position.

As we scan left-to-right we compare the next interval from O1 (shifted right) against the next insertion position from O2. If necessary the interval from O1 may need to be split. 


void AdjSwap_di(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    MCID_XRanges& X = O1.X;
    MCID_IRanges& I = O2.I;

    int si = 0;     // Accumulated shift from I
    int sx = 0;     // Accumulated shift from X

    MCID_XRanges::iterator x = X.begin();
    MCID_IRanges::iterator i = I.begin();

    while(i != I.end() && x != X.end())
    {
        if (i->q <= si + x->q)
        {
            //    [11111)
            //   2
            // Process next insertion
            si += i->size();
            i->p += sx;
            ++i;
        }
        else
        {
            int d = i->q - (si + x->q);
            if (d < x->size())
            {
                // [111111)
                //     2
                SplitRange(X,x, i->q - (si + x->q));
            }

            // [111111)
            //          2
            // Process next extraction
            x->q += si;
            x->p += si;
            if (x->enabled) sx += x->size();
            ++x;
        }
    }

    if (si)
    {
        while (x != X.end())
        {
            x->q += si;
            x->p += si;
            ++x;
        }
    }

    if (sx)
    {
        while (i != I.end())
        {
            i->p += sx;
            ++i;
        }
    }
}

AdjSwap

The adjacent swap algorithm transforms [O1 O2] to [O2' O1'].

O1 and O2 are composite operations of extractions followed by insertions. Using the general algorithm for transpose of a list with a list leads to the following algorithm for AdjSwap. 


void AdjSwap(MultiCharInsertOrDeleteOp& O1, MultiCharInsertOrDeleteOp& O2)
{
    AdjSwap_id(O1,O2);
    AdjSwap_dd(O1,O2);
    AdjSwap_ii(O1,O2);
    AdjSwap_di(O1,O2);
}

Correctness scope

The scans above are interval-wise implementations of the corresponding single-character transformations: splitting aligns interval boundaries, accumulated shifts equal the number of preceding enabled deletions or insertions, and coalescing preserves the resulting operation. Accordingly, their convergence argument inherits the assumptions of the single-character system in [3]. In particular, the Boolean enabled-delete representation does not establish TP2 or invertible ET for arbitrary transformation histories involving an already-disabled same-target deletion. The claims in this chapter are therefore restricted to histories that satisfy the domain stated in [3].

Tests

The algorithm was tested by simulating between two and nine sites making randomly generated multi-character insertion and deletion operations and exchanging them in arbitrary causally valid orders. Individual operations could contain multiple disjoint extraction intervals and multiple insertion strings. Convergence was checked repeatedly between sites during each simulation and across all sites after every operation had been exchanged. Sites were required to agree on both the visible document and its complete effects representation.

A total of 10,000 simulations of 200 events each completed without a convergence failure. The number and variety of operations, sites and exchange orders covered by this testing provide very high confidence in the correctness of the algorithm.

Browse the test files.

References

  1. Du Li and Rui Li, Ensuring Consistency in Real-Time Group Editors, ACM Transactions on Computer-Human Interaction, April 2004. Under review at the time of writing.
  2. Du Li and Rui Li, An Operational Transformation Algorithm and Performance Evaluation, Journal of CSCW, July 2005. Under review at the time of writing.
  3. David Barrett-Lennard, Operational Transform — Single Character Insertion and Deletion Operations, July 2005.
  4. David Barrett-Lennard, Log Compression Algorithm, July 2005.

Source code

The C++ implementation written for this 2005 work is retained as a documentation resource. MultiCharDeleteThenInsertOp represents an operation as extractions followed by insertions and implements the dual inclusion transforms and adjacent-swap cases developed above. Browse the source files.