// MultiCharDeleteThenInsertOp.cpp
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2005

#include "StdAfx.h"
#include "Ceda/Core/cxUtils/ListToOStream.h"
#include "Ceda/Core/cxUtils/PseudoRandom.h"
#include "Ceda/Core/cxUtils/CedaAssert.h"
#include "Ceda/Core/cxUtils/Tracer.h"
#include "StringDoc.h"
#include "MultiCharDeleteThenInsertOp.h"

using namespace ceda;

xchar GetCycledLowercaseChar();

///////////////////////////////////////////////////////////////////////////////////////////////////

void CoalesceRanges(MCDI_XRanges& L)
{
    for (MCDI_XRanges::iterator i = L.begin() ; i != L.end() ; ++i)
    {
        MCDI_XRanges::iterator j = i;
        ++j;
        while(j != L.end() && i->q + i->size() == j->q && i->enabled == j->enabled && i->id == j->id)
        {
            // Coalesce j into i
            i->s += j->s;
            j = L.erase(j);
        }
    }
}

void CoalesceRanges(MCDI_IRanges& L)
{
    for (MCDI_IRanges::iterator i = L.begin() ; i != L.end() ; ++i)
    {
        MCDI_IRanges::iterator j = i;
        ++j;
        while (j != L.end() && i->q + i->size() == j->q && i->id == j->id)
        {
            // Coalesce j into i
            i->s += j->s;
            j = L.erase(j);
        }
    }
}


///////////////////////////////////////////////////////////////////////////////////////////////////

// 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 typename 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(MCDI_XRanges& X, MCDI_XRanges::iterator i, ssize_t n1)
{
    cxAssert(n1 > 0);

    ssize_t n2 = i->size() - n1;
    cxAssert(n2 > 0);

    MCDI_XRanges::iterator j = InsertAfter<MCDI_XRange>(X,i);

    j->id = i->id;
    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 = xstring(i->s.begin() + n1, i->s.end());
    cxAssert(j->size() == n2);
    j->enabled = i->enabled;

    i->s.erase(i->s.begin() + n1, i->s.end());
    cxAssert(i->size() == n1);
}

void SplitRange(MCDI_IRanges& I, MCDI_IRanges::iterator i, ssize_t n1)
{
    cxAssert(n1 > 0);

    ssize_t n2 = i->size() - n1;
    cxAssert(n2 > 0);

    MCDI_IRanges::iterator j = InsertAfter<MCDI_IRange>(I,i);

    j->id = i->id;
    j->p = i->p + n1;
    j->q = i->q + n1;
    j->s = xstring(i->s.begin() + n1, i->s.end());
    cxAssert(j->size() == n2);

    i->s.erase(i->s.begin() + n1, i->s.end());
    cxAssert(i->size() == n1);
}


///////////////////////////////////////////////////////////////////////////////////////////////////
// MultiCharDeleteThenInsertOp

MultiCharDeleteThenInsertOp::MultiCharDeleteThenInsertOp() : 
    buf(0)
{
}

bool MultiCharDeleteThenInsertOp::operator==(const MultiCharDeleteThenInsertOp& rhs) const
{ 
    return m_opid == rhs.m_opid &&
           buf == rhs.buf &&
           X == rhs.X &&
           I == rhs.I;
}

void MultiCharDeleteThenInsertOp::SetRandom(RandomInitSettings ris, const OpDocSet& ds, Opid opid)
{
    cxAssert(opid.id >= 0);
    cxAssert(opid.t >= 0);
    m_opid = opid;

    ssize_t numDocs = ds.size();
    cxAlwaysAssert(numDocs > 0);

    buf = GetUniformDistInteger_ssize_t(0,numDocs);
    ssize_t numChars = ds[buf].size();

    X.clear();
    I.clear();

    ssize_t sx = 0;             // Total number of characters extracted
    ssize_t si = 0;             // Total number of characters inserted

    MCDI_XRange rx;          // Current Range being extracted
    rx.id = opid.id;

    for (ssize_t p=0 ; p <= numChars ; ++p)
    {
        ssize_t q = ds[buf].GetQ(p);
        
        if (p < numChars && ris.m_generateExtractions && GetUniformDistDouble(0,1) < ris.m_probOfExtractionPerCharacter)
        {
            if (rx.size() > 0 /*&& q - rx.q != p - rx.p*/)
            {
                // Have to start a new interval because q-position is not continuous
                X.push_back(rx);
                rx.s.clear();
            }

            // Extract pth character
            if (rx.size() == 0)
            {
                rx.p = p;
                rx.q = q;
            }
            rx.s += ds[buf][p];
            ++sx;
        }
        else
        {
            if (rx.size() > 0)
            {
                X.push_back(rx);
                rx.s.clear();
            }

            // Not deleting this character, so it is a valid insertion position
            ssize_t numCharsToInsert = GetUniformDistInteger_ssize_t(-1,3);
            if (ris.m_generateInsertions && numCharsToInsert > 0)
            {
                MCDI_IRange ri;
                ri.id = opid.id;

                for (ssize_t j=0 ; j < numCharsToInsert ; ++j)
                {
                    ri.s += GetCycledLowercaseChar();
                }
                ri.p = si + p - sx;
                ri.q = si + q;
                si += numCharsToInsert;
                I.push_back(ri);
            }
        }
    }

    CoalesceRanges(X);
}

void MultiCharDeleteThenInsertOp::Do(StringDocSet& ds) const
{
    // Do all the extractions
    for (MCDI_XRanges::const_reverse_iterator x = X.rbegin() ; x != X.rend() ; ++x)
    {
        if (x->enabled)
        {
            ds[buf].Remove(x->p,x->q,x->s);
        }
    }

    // Do all the insertions
    for (MCDI_IRanges::const_iterator i = I.begin() ; i != I.end() ; ++i)
    {
        ds[buf].Insert(i->p,i->q,i->s);
    }
}

void MultiCharDeleteThenInsertOp::Undo(StringDocSet& ds) const
{
    cxAlwaysAssert(0); // todo
}

xostream& operator<<(xostream& os, const MultiCharDeleteThenInsertOp& O)
{
    if (O.buf)
    {
        os << O.buf << ':';
    }
    os << "X:" << O.X
       << "I:" << O.I;
    return os;
}


///////////////////////////////////////////////////////////////////////////////////////////////////

/*
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.  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(MCDI_XRanges& X1, MCDI_XRanges& X2)
{
    ssize_t s1 = 0;     // Accumulated shift from enabled intervals of X1
    ssize_t s2 = 0;     // Accumulated shift from enabled intervals of X2

    MCDI_XRanges::iterator x1 = X1.begin();
    MCDI_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);
}

/*
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.

        Coords mentioned in O1 are already relative to this state.  Coords 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 - i.e. when there are insertions within the 
        interval
*/

void DualIT_id(MCDI_IRanges& I, MCDI_XRanges& X)
{
    ssize_t si = 0;     // Accumulated shift from I
    ssize_t sx = 0;     // Accumulated shift from X

    MCDI_XRanges::iterator x = X.begin();
    MCDI_IRanges::iterator i = I.begin();

    while(i != I.end() && x != X.end())
    {
        ssize_t d = i->q - (si + x->q);
        if (d <= 0)
        {
            //    [2222222)
            //   1
            si += i->size();
            i->p -= sx;
            ++i;
        }
        else
        {
            if (d < x->size())
            {
                // [222222)
                //     1
                SplitRange(X,x,d);
            }

            // [2222222)
            //           1
            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;
        }
    }
}


/*
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 ids to break the tie.
*/

void DualIT_ii(MCDI_IRanges& I1, MCDI_IRanges& I2)
{
    ssize_t s1 = 0;     // Accumulated shift from I1
    ssize_t s2 = 0;     // Accumulated shift from I2

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

    while(i1 != I1.end() && i2 != I2.end())
    {
        ssize_t d = (s1 + i2->q) - (s2 + i1->q);
        if (d < 0 || d == 0 && i2->id < i1->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;
        }
    }
}

/*
    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;


From the point of view of the effects document, there are no extractions.  So it's simply a problem
of transforming insertions against insertions, as done in MultiCharInsertOp.

Steps

1.  DualIT O1.X, O2.X

    This is used to 1) shift p positions of O1.X, O2.X to the left
                    2) disable extractions

2.  DualIT O1.X, O2.I

    This is used to 1) shift p,q positions of O1.X to the right
                    2) shift p positions of O2.I to the left

3.  DualIT O1.I, O2.X

    (like step 2)

4.  DualIT O1.I, O2.I

    This is used to shift p,q positions of O1.I, O2.I to the right

Notes
    
    *   Step 1 doesn't affect any X or I q-positions and therefore won't upset any subsequent 
        position comparisons.

        Shifting of p coords can be done in any order.  The only important thing is to apply the 
        p-position shifts correctly.

    *   It is appropriate that disabling a delete in step 1, has an effect in steps 2,3 (of whether
        to decrement insertion p-positions)

    *   Steps 2,3 don't adjust insertion q-positions, and therefore won't upset the insertion 
        position comparisons in step 4.

    *   Step 2,3 affect extraction q-positions,  but the extraction q-positions are not compared
        after than point.
*/


/*
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(MultiCharDeleteThenInsertOp& O1, MultiCharDeleteThenInsertOp& O2)
{
    if (O1.buf == O2.buf)
    {
        /*
               +-----+-----+
               |     |     |
            I1 |     |     |
               |     |     |
               +-----+-----+
               |     |     |
            X1 |     |     |
               |     |     |
               +-----+-----+
                 X2     I2
        */

        DualIT_dd(O1.X, O2.X);   // Deletions against deletions
        DualIT_id(O1.I, O2.X);   // Insertions against deletions
        DualIT_id(O2.I, O1.X);   // Deletions against insertions
        DualIT_ii(O1.I, O2.I);   // Insertions against insertions
    }
}


///////////////////////////////////////////////////////////////////////////////////////////////////
/*
The transpose 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 TransposeConcurrent_dd(MCDI_XRanges& X1, MCDI_XRanges& X2)
{
    ssize_t s1 = 0;     // Accumulated shift from enabled intervals of X1
    ssize_t s2 = 0;     // Accumulated shift from enabled intervals of X2

    MCDI_XRanges::iterator x1 = X1.begin();
    MCDI_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);
}

///////////////////////////////////////////////////////////////////////////////////////////////////
/*
The transpose 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.  For the purposed of comparison
q-positions of O2 don't require adjustment.  However q-positions of O2 need to the shifted to the 
right.
*/

void TransposeConcurrent_ii(MCDI_IRanges& I1, MCDI_IRanges& I2)
{
    ssize_t s1 = 0;     // Accumulated shift from I1
    ssize_t s2 = 0;     // Accumulated shift from I2

    MCDI_IRanges::iterator i1 = I1.begin();
    MCDI_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;
        }
    }
}


///////////////////////////////////////////////////////////////////////////////////////////////////
/*
The transpose 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.

It is assume that O1 || O2, so therefore 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 TransposeConcurrent_id(MCDI_IRanges& I, MCDI_XRanges& X)
{
    ssize_t si = 0;     // Accumulated shift from I
    ssize_t sx = 0;     // Accumulated shift from X

    MCDI_XRanges::iterator x = X.begin();
    MCDI_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 shouldn't overlap assuming O1 || O2
            cxAssert(0);
        }
    }

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

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


///////////////////////////////////////////////////////////////////////////////////////////////////
/*
The transpose 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 TransposeConcurrent_di(MCDI_XRanges& X, MCDI_IRanges& I)
{
    ssize_t si = 0;     // Accumulated shift from I
    ssize_t sx = 0;     // Accumulated shift from X

    MCDI_XRanges::iterator x = X.begin();
    MCDI_IRanges::iterator i = I.begin();

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

            // [111111)
            //          2
            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;
        }
    }
}


///////////////////////////////////////////////////////////////////////////////////////////////////
/*
The transpose 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 Transpose().
*/

void Transpose(MultiCharDeleteThenInsertOp& O1, MultiCharDeleteThenInsertOp& O2)
{
    if (O1.buf == O2.buf)
    {
        /*
               +-----+-----+
               |     |     |
               |     |     | I2
               |     |     |
               +-----+-----+
               |     |     |
               |     |     | X2
               |     |     |
               +-----+-----+
                 X1     I1
        */

        TransposeConcurrent_id(O1.I, O2.X);
        TransposeConcurrent_dd(O1.X, O2.X);
        TransposeConcurrent_ii(O1.I, O2.I);
        TransposeConcurrent_di(O1.X, O2.I);
    }
}


///////////////////////////////////////////////////////////////////////////////////////////////////

void IT(MultiCharDeleteThenInsertOp& O1, const MultiCharDeleteThenInsertOp& O2)
{
    MultiCharDeleteThenInsertOp copyO2 = O2;
    DualIT(O1, copyO2);
}

void ET(MultiCharDeleteThenInsertOp& O1, const MultiCharDeleteThenInsertOp& O2)
{
    MultiCharDeleteThenInsertOp copyO2 = O2;
    Transpose(copyO2, O1);
}



///////////////////////////////////////////////////////////////////////////////////////////////////
// Merging

void Merge(MultiCharDeleteThenInsertOp& O1, const MultiCharDeleteThenInsertOp& O2)
{
    // Delete then insert operations don't support merging because the operation can't represent
    // characters that are inserted then deleted again.
    cxAssert(0);
}