// Operation.cpp
//

#include "StdAfx.h"
#include "Ceda/Core/cxUtils/PseudoRandom.h"
#include "Ceda/Core/cxUtils/Tracer.h"
#include "Ceda/Core/cxUtils/ListToOStream.h"
#include "Operation.h"

using namespace ceda;

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

// Calculate a random set of extractions to be performed on the given string
void CreateRandomExtractions(Ranges& X, const xstring& str, double probOfExtractionPerCharacter)
{
    X.clear();
    Range r;        // Current Range being extracted
    for (ssize_t i=0 ; i < str.size() ; ++i)
    {
        if (GetUniformDistDouble(0,1) < probOfExtractionPerCharacter)
        {
            // Extract ith character
            r.s += str[i];
        }
        else
        {
            if (r.size() > 0)
            {
                X.push_back(r);
            }

            r.p = i+1;
            r.s.clear();
        }
    }

    if (r.size() > 0)
    {
        X.push_back(r);
    }
}

// Create a random set of insertions to be performed on the string of given size
void CreateRandomInsertions(Ranges& I, ssize_t size, int& ch, int ch1, int ch2)
{
    // At each position we inserted between 0 and n characters.  

    I.clear();
    ssize_t shift = 0;  // Accumulate the number of inserted characters
    for (ssize_t i=0 ; i <= size ; ++i)
    {
        ssize_t n = GetUniformDistInteger(-1,3);
        if (n > 0)
        {
            Range r;
            for (ssize_t j=0 ; j < n ; ++j)
            {
                r.s += ch;
                if (++ch == ch2) ch = ch1;
            }
            r.p = shift + i;
            shift += n;
            I.push_back(r);
        }
    }
}


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

void DoInsertions(xstring& s, const Ranges& I)
{
    for (Ranges::const_iterator i = I.begin() ; i != I.end() ; ++i)
    {
        s.insert(s.begin() + i->p, i->s.begin(), i->s.end());
    }
}

void DoExtractions(xstring& s, const Ranges& X)
{
    for (Ranges::const_reverse_iterator x = X.rbegin() ; x != X.rend() ; ++x)
    {
        xstring t( s.begin() + x->p, s.begin() + x->p + x->size() );
        cxAssert(t == x->s);

        s.erase(s.begin() + x->p, s.begin() + x->p + x->size());
    }
}


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

void ValidateRanges(const Ranges& L, const xstring& str)
{
    for (Ranges::const_iterator i = L.begin() ; i != L.end() ; ++i)
    {
        xstring s(str.begin() + i->p, str.begin() + i->p + i->size());
        cxAssert(s == i->s);

        Ranges::const_iterator j = i;
        ++j;
        if (j != L.end())
        {
            cxAssert(i->p + i->size() < j->p);
        }
    }    
}


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

void CoalesceRanges(Ranges& L)
{
    for (Ranges::iterator i = L.begin() ; i != L.end() ; ++i)
    {
        Ranges::iterator j = i;
        ++j;
        while (j != L.end() && i->p + i->size() == j->p)
        {
            // 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 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(Ranges& L, Ranges::iterator i, ssize_t n1)
{
    cxAssert(n1 > 0);

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

    Ranges::iterator j = InsertAfter<Range>(L,i);

    j->p = i->p + 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);
}



/*
    HB = [I  X ]
    -->  [X' I']

X is ET'd backward past I.  I is IT'd forwards past X'.


    S  ------>  S' -------> S''
          I           X

Note that I uses post-insertion coords and X uses pre-extraction coords.  So both sets of 
coordinates are defined with respect to the intermediate state S'.  Therefore they can be directly 
compared.

According to the analysis by Du Li in the SDTO algorithm,  there is no need for the ER relation
and there are no ambiguities

Example
                  
                    I
    abcdxxxefgh    -->    abciiiidxxxeiiifgiixxxiiixxiih
                             [  )     [ )  [          )        I
                                  [ )        [ )   [)          X

                    X
                   -->    abciiiideiiifgiiiiiiih



                    X'
    abcdxxxefgh    -->    abcdefgh
        [ )                      

                    I'
                   -->    abciiiideiiifgiiiiiiih
                             [  )  [ )  [     )


We scan left to right for next extraction interval [xxxx) or insertion interval [iiii).

    [iiii)               --->  i->p -= sx
                               si += i->size()

    [xxxx)               --->  x->p -= si
                               sx += x->size()

    [iiixxxxiiiixxiii)   --->  Discard overlapping sections.
                               Remove corresponding characters from insertion string ---> [iiiiiiiiii)
                               i->p -= sx
                               si += i->size()

    [iiii)    [ii)       --->  Deal with [iiii) as above
         [xxxx)                Deal with [xxxx) as above
                               See that next [ii) now touches previous insertion interval, so merge
                               with previous [iiii)

    [iiiiiiii)           --->  Treat this as  [iiii)[iii)  
         [xxxxxxx)                                  [xxx)[xxxx)
                               The overlapping part is discarded from both the insertions and the
                               extractions.

Note that this function is not information preserving.  In fact it can be used to help compress the
log.
*/

void Transposeix(Ranges& I, Ranges& X)
{
    ssize_t si = 0;     // Accumulated shift from I
    ssize_t sx = 0;     // Accumulated shift from X

    Ranges::iterator i = I.begin();
    Ranges::iterator x = X.begin();
    
    while(i != I.end() && x != X.end())
    {
        if (i->p + i->size() <= x->p)
        {
            // Next is [iiiii)
            i->p -= sx;
            si += i->size();
            ++i;
        }
        else if (x->p + x->size() <= i->p)
        {
            // Next is [xxxxx)
            x->p -= si;
            sx += x->size();
            ++x;
        }
        else
        {
            // Intervals overlap
            if (i->p < x->p)
            {
                //    [iiiiiiiii
                //         [xxxx
                SplitRange(I,i,x->p - i->p);
                i->p -= sx;
                si += i->size();
                ++i;
            }
            else if (x->p < i->p)
            {
                // [xxxxxxxxxxxxx
                //       [iiiiiii
                SplitRange(X,x,i->p - x->p);
                x->p -= si;
                sx += x->size();
                ++x;
            }

            cxAssert(x->p == i->p);
            if (x->size() < i->size())
            {
                // [xxxxxx)
                // [iiiiiiiiiiii)
                SplitRange(I,i,x->size());
            }
            else if (i->size() < x->size())
            {
                // [iiiiii)
                // [xxxxxxxxxxxx)
                SplitRange(X,x,i->size());
            }

            cxAssert(i->size() == x->size());
            // [iiiiii)
            // [xxxxxx)
            // Discard both intervals
            sx += x->size();
            si += i->size();
            i = I.erase(i);
            x = X.erase(x);
        }
    }

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

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

    CoalesceRanges(I);
    CoalesceRanges(X);
}

/*
Given HB = [X1 X2] we want to merge X2 into X1

It is impossible for X1, X2 to delete the same characters, because they are contextually 
serialised.

                                      X1
    a11bc111211122de222fg222211      --->     abc222de222fg2222
     [)  [ ) [ )             [)                  [ )  [ )  [  )
                                      X2
                                     --->     abcdefg


We want to merge X1, X2 like this...

                                     X1+X2
    a11bc111211122de222fg222211      --->     abcdefg
     [)  [       )  [ )  [    )


Note that the intervals of X1 don't need to be shifted.  The intervals of X2 need to be shifted 
to the right by the accumulated count of characters extracted by X1.
*/

void Mergexx(Ranges& X1, const Ranges& X2)
{
    ssize_t shift = 0;
       
    Ranges::iterator x1 = X1.begin();
    Ranges::const_iterator x2 = X2.begin();

    while(x2 != X2.end())
    {
        //      [11...)
        //        [22..)
        //
        // Skip over all [11..) that are strictly to the left of the next [22..) in its shifted
        // position.  These [11..) don't require adjustment.  However we need to accumulate the 
        // shift.
        // These intervals don't actually overlap because the effect of [11..) is to shift the 
        // next [22..) further to the right, past the end of the [11..)
        while(x1 != X1.end() && x1->p < shift + x2->p)
        {
            shift += x1->size();
            ++x1;
        }

        /*
        Now process all [11..) that coalesce with the next [22..).  The effect is to split the next
        [22..) into pieces that are shifted by different amounts.
        
        Initially we position the [22..) according to the initial shift.  In the following 
        example it aligns on the left with the next [11..).

        As we process each [11..) we have to split the next [22..) into a left portion that is 
        appended to r using the current shift,  and a right portion that is shifted further to the 
        right and requires further processing.
        
                   22222222222222222222
                   111     111111       1111
        
            --->      22222222222222222222
                   111     111111       1111
        
            --->      22222      222222222222222
                   111     111111       1111
        
            --->      22222      2222222    22222222
                   111     111111       1111

        
        So     r = 111222221111112222222111122222222 is the coalesced string to be extracted
        
        [t1,t2) represents the next substring from [22..) to be appended to r
        */

        Range r;
        r.p = shift + x2->p;
        xstring::const_iterator t1 = x2->s.begin();
        while(x1 != X1.end() && x1->p <= shift + x2->p + x2->size())
        {
            // Append next substring from [22..) to end of r
            xstring::const_iterator t2 = x2->s.begin() + x1->p - (shift + x2->p);
            r.s.append(t1,t2);
            t1 = t2;

            // Append next [11..) to end of r
            r.s += x1->s;
            
            // Accumulate shift from [11..), and erase [11..) because its effect is built into r
            shift += x1->size();
            x1 = X1.erase(x1);
        }
        r.s.append( t1, x2->s.end() );  // Append remainder of [22..) to end of r
        X1.insert(x1, r);
        
        ++x2;
    }
}

/*
Given HB = [I1 I2] we want to merge I2 into I1

Example:

              I1
    abcdefgh  -->  abc1111de111fg1111111h
                      [  )  [ )  [     )
                      
              I2
              -->  abc1111d22e111fg11122221122211h
                           [)         [  )  [ )


If 2's touch any 1's (either on left, middle or on the right) then we should accumulate the 2's 
into the existing 1's - i.e. we form a bigger string to be inserted.

I1 positions need to be shifted to the right to account for the accumulated shift from all the 
insertions by I2.   I2 positions do not require adjustment.

We use an STL list so that insertions or deletions in the middle of the list are efficient.
Also insertions or deletions don't invalidate existing iterators.


    abc     -->   a111bc
                   [ )

            -->   a2222111bc
                   [  )


    abc           abc11111

                  a22222b22222c11111
*/

void Mergeii(Ranges& I1, const Ranges& I2)
{
    ssize_t shift = 0;     // Accumulated shift from I2

    Ranges::iterator i1 = I1.begin();
    Ranges::const_iterator i2 = I2.begin();
    
    while(i1 != I1.end())
    {
        while (i2 != I2.end() && i2->p < shift + i1->p)
        {
            // [222) comes next.  Insert immediately before position i1
            I1.insert(i1, *i2);
            shift += i2->size();
            ++i2;
        }

        if (i2 == I2.end())
        {
            do 
            {
                i1->p += shift;
                ++i1;    
            } while(i1 != I1.end());
            return;
        }

        cxAssert(shift + i1->p <= i2->p);

        i1->p += shift;
        
        while (i2 != I2.end() && i2->p <= i1->p + i1->size())
        {
            // We have one of the following
            //
            //      2222111   // 2's on the left of the 1's
            //      1222211   // 2's in the middle of the 1's
            //      1112222   // 2's on the right of the 1's
            //
            // Accumulate 2's into 1's

            i1->s.insert(i1->s.begin() + i2->p - i1->p, i2->s.begin(), i2->s.end());
            shift += i2->size();
            ++i2;
        } 

        ++i1;
    }

    cxAssert(i1 == I1.end());
    while(i2 != I2.end())
    {
        I1.insert(I1.end(), *i2);
        ++i2;
    }
}


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

void TestTransposeix()
{
    for (ssize_t i=0 ; i < 100000 ; ++i)
    {
        xstring s1 = "abcdefghijk";
        xstring s2 = "abcdefghijk";

        Tracer() << "\ns1 = " << s1 << '\n';

        Ranges I;
        int ch = 'A';
        CreateRandomInsertions(I, s1.size(), ch, 'A', 'Z'+1);
        Tracer() << "I = " << I << '\n';

        DoInsertions(s1,I);
        Tracer() << "After I s1 = " << s1 << '\n';

        Ranges X;
        CreateRandomExtractions(X, s1, 0.5);
        Tracer() << "X = " << X << '\n';

        DoExtractions(s1,X);
        Tracer() << "After X s1 = " << s1 << '\n';

        Transposeix(I, X);

        Tracer() << "X' = " << X << '\n';
        Tracer() << "I' = " << I << '\n';

        ValidateRanges(X, s2);
        DoExtractions(s2,X);
        Tracer() << "After X' s2 = " << s2 << '\n';

        DoInsertions(s2,I);
        ValidateRanges(I, s2);
        Tracer() << "After I' s2 = " << s2 << '\n';

        cxAssert(s1 == s2);
    }
}

void TestMergexx()
{
    for (ssize_t i=0 ; i < 100000 ; ++i)
    {
        xstring s1 = "abcdefghijk";
        xstring s2 = "abcdefghijk";

        Tracer() << "\ns1 = " << s1 << '\n';

        Ranges X1;
        CreateRandomExtractions(X1, s1, 0.5);
        Tracer() << "X1 = " << X1 << '\n';
        ValidateRanges(X1, s1);
        DoExtractions(s1,X1);
        Tracer() << "After X1 s1 = " << s1 << '\n';

        Ranges X2;
        CreateRandomExtractions(X2, s1, 0.5);
        Tracer() << "X2 = " << X2 << '\n';
        ValidateRanges(X2, s1);
        DoExtractions(s1,X2);
        Tracer() << "After X2 s1 = " << s1 << '\n';

        Mergexx(X1, X2);

        Tracer() << "X1+X2 = " << X1 << '\n';

        ValidateRanges(X1, s2);
        DoExtractions(s2,X1);
        Tracer() << "After X1+x2 s2 = " << s2 << '\n';

        cxAssert(s1 == s2);
    }
}

void TestMergeii()
{
    for (ssize_t i=0 ; i < 100000 ; ++i)
    {
        xstring s1 = "abcdefghijk";
        xstring s2 = "abcdefghijk";

        Tracer() << "\ns1 = " << s1 << '\n';

        Ranges I1;
        int ch = 'A';
        CreateRandomInsertions(I1, s1.size(), ch, 'A', 'Z'+1);
        Tracer() << "I1 = " << I1 << '\n';
        DoInsertions(s1,I1);
        Tracer() << "After I1 s1 = " << s1 << '\n';
        ValidateRanges(I1, s1);

        Ranges I2;
        CreateRandomInsertions(I2, s1.size(), ch, 'A', 'Z'+1);
        Tracer() << "I2 = " << I2 << '\n';
        DoInsertions(s1,I2);
        Tracer() << "After I2 s1 = " << s1 << '\n';
        ValidateRanges(I2, s1);

        Mergeii(I1, I2);
        Tracer() << "I1+I2 = " << I1 << '\n';

        DoInsertions(s2,I1);
        Tracer() << "After I1+I2 s2 = " << s2 << '\n';
        ValidateRanges(I1, s2);

        cxAssert(s1 == s2);
    }
}

void TestMergeOps(ssize_t count, bool debug)
{
    for (ssize_t i=0 ; i < count ; ++i)
    {
        xstring s1 = "abcdefghijk";
        xstring s2 = "abcdefghijk";

        if (debug) Tracer() << "\ns1 = " << s1 << '\n';

        // Apply [-X1 +I1 -X2 +I2] to s1
        Ranges X1;
        CreateRandomExtractions(X1, s1, 0.5);
        if (debug) Tracer() << "X1 = " << X1 << '\n';
        ValidateRanges(X1, s1);
        DoExtractions(s1,X1);
        if (debug) Tracer() << "After X1 s1 = " << s1 << '\n';

        Ranges I1;
        int ch = 'A';
        CreateRandomInsertions(I1, s1.size(), ch, 'A', 'Z'+1);
        if (debug) Tracer() << "I1 = " << I1 << '\n';
        DoInsertions(s1,I1);
        ValidateRanges(I1, s1);
        if (debug) Tracer() << "After I1 s1 = " << s1 << '\n';

        Ranges X2;
        CreateRandomExtractions(X2, s1, 0.5);
        if (debug) Tracer() << "X2 = " << X2 << '\n';
        ValidateRanges(X2, s1);
        DoExtractions(s1,X2);
        if (debug) Tracer() << "After X2 s1 = " << s1 << '\n';

        Ranges I2;
        CreateRandomInsertions(I2, s1.size(), ch, 'A', 'Z'+1);
        if (debug) Tracer() << "I2 = " << I2 << '\n';
        DoInsertions(s1,I2);
        ValidateRanges(I2, s1);
        if (debug) Tracer() << "After I2 s1 = " << s1 << '\n';

        // Merge [-X2 +I2] into [-X1 +I1]
        Transposeix(I1, X2);
        Mergexx(X1, X2);
        Mergeii(I1, I2);
        
        if (debug) Tracer() << "X = " << X1 << '\n';
        if (debug) Tracer() << "I = " << I1 << '\n';

        ValidateRanges(X1, s2);
        DoExtractions(s2,X1);
        DoInsertions(s2,I1);
        ValidateRanges(I1, s2);
        if (debug) Tracer() << "After X,I s2 = " << s2 << '\n';

        cxAssert(s1 == s2);
    }
}


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

void MergeX(Operation& O1, const Ranges& X)
{
    Ranges cX = X;
    Transposeix(O1.I, cX);
    Mergexx(O1.X, cX);
}

void MergeI(Operation& O1, const Ranges& I)
{
    Mergeii(O1.I, I);
}

/*
O1 += O2

We *must* use an in-place algorithm.  Consider that O1 represents 6 months work, and we want to 
merge in O2 which is comparitively small.  Clearly we can save a lot of unnecessary copying of data
if we use an in-place algorithm.  This suggests linked lists.
*/

void Merge(Operation& O1, const Operation& O2)
{
    MergeX(O1, O2.X);
    MergeI(O1, O2.I);
}


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

void Testx()
{
    //TestTransposeix()
    //TestMergexx();
    //TestMergeii();

    bool debug = false;
    ssize_t count = 100000;
    TestMergeOps(count, debug);
}