// TestVectorInsertions.cpp
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2021

#include "Ceda/cxOT/TVectorInsertionsAndDeletions.h"
#include "Ceda/cxOT/VectorRFactor.h"
#include "Ceda/cxOT/VectorGetDelta.h"
#include "Ceda/cxOT/VectorApplyDelta.h"
#include "Ceda/cxOT/VectorApplyOperation.h"
#include "Ceda/cxUtils/TestTimer.h"
#include "Ceda/cxUtils/Tracer.h"
#include "Ceda/cxUtils/IsaacRandom.h"

#define TRACE_TestVectorInsertions 0

using Isaac = ceda::IsaacRandomNumberGen;
using SiteId = int;
using TimeIndex = int;
using VectorIndex = int;
using Opid = ceda::TOpid<SiteId,TimeIndex>;
using VectorTime = ceda::TVectorTime<SiteId,TimeIndex>;
using VectorInsertionInterval = ceda::TVectorInsertionInterval<SiteId,TimeIndex,VectorIndex>;
using VectorDeletionInterval = ceda::TVectorDeletionInterval<SiteId,TimeIndex,VectorIndex>;
using VectorInsertions = ceda::TVectorInsertions<SiteId,TimeIndex,VectorIndex>;
using VectorDeletions = ceda::TVectorDeletions<SiteId,TimeIndex,VectorIndex>;
using VectorInsertionsAndDeletions = ceda::TVectorInsertionsAndDeletions<SiteId,TimeIndex,VectorIndex>;

namespace ceda
{
    class StringAsVectorField
    {
    public:
        StringAsVectorField(std::string& s) : s(s) {}

        void EraseRange(ssize_t p1, ssize_t p2)
        {
            s.erase(p1, p2-p1);
        }
        const octet_t* MoveFrom(ssize_t d, const octet_t* src, ssize_t count)
        {
            const octet_t* src_end = src + count;
            s.insert(d, (const char*) src, count);
            return src_end;
        }

    private:
        std::string& s;
    };

    class FilteredListUpdaterOnString
    {
    public:
        FilteredListUpdaterOnString(std::string& s) :
            s(s)
        {
            keepPos = dropPos = s.data();
        }
        ~FilteredListUpdaterOnString()
        {
            cxAssert(dropPos == s.data() + s.size());
            s.resize(keepPos - s.data());
        }

        // Drop the next n elements
        void Drop(ssize_t n)
        {
            cxAssert(n >= 0);
            cxAssert(dropPos + n <= s.data() + s.size());
            dropPos += n;
        }

        // Keep the next n elements
        void Keep(ssize_t n)
        {
            cxAssert(n >= 0);
            cxAssert(dropPos + n <= s.data() + s.size());

            std::memmove(keepPos, dropPos, n);
            keepPos += n;
            dropPos += n;
        }

    private:
        std::string& s;
        char* keepPos;
        char* dropPos;
    };

    template<typename T>
    void LinkedListFromVectorOfPointersToNodes(FrontLinkedList<T>& x, const xvector<const T*>& v)
    {
        x.Clear();
        ssize_t n = v.size();
        typename FrontLinkedList<T>::Node* prevr = nullptr;
        typename FrontLinkedList<T>::Node* r = nullptr;
        for (ssize_t i=0 ; i < n ; ++i)
        {
            r = new typename FrontLinkedList<T>::Node;
            r->m_prev = prevr;
            r->m_next = nullptr;
            if (prevr) prevr->m_next = r; else x.m_first = r;
            prevr = r;
            (T&)*r = *v[i];
        }
    }    
}

namespace vector_insertions_test
{
    struct Site
    {
        Opid opid;
        VectorTime vout;        // Summaries what operations have been applied on this site
        std::string field;
        VectorInsertionsAndDeletions vectorInsertionsAndDeletions;
    };

    ceda::xostream& operator<<(ceda::xostream& os, const Site& s)
    {
        os << "Site " << s.opid 
           << "  vout=" << s.vout 
           << "  field=" << s.field
           << "  vectorInsertions= " << s.vectorInsertionsAndDeletions;
        return os;
    }

    struct Test
    {
        Test(int numSites);
        SiteId PickSite();
        void DoLocalOp();
        void TrySendOp(SiteId s1, SiteId s2);
        void PickDifferentSites(SiteId& s1, SiteId& s2);
        void SendOp();
        void TestConvergenceOfTwoSites();
        int NumSites() const { return (int) sites.size(); }
        
        ceda::xvector<Site> sites;      // Indexed by SiteId
        Isaac isaac;
    };

    ceda::xostream& operator<<(ceda::xostream& os, const Test& v)
    {
        for (SiteId i=0 ; i < v.sites.size() ; ++i)
        {
            os << v.sites[i] << '\n';
        }
        return os;
    }

    Test::Test(int numSites) :
        sites(numSites)
    {
        for (SiteId i=0 ; i < numSites ; ++i)
        {
            sites[i].opid.s = i;
            sites[i].opid.t = 0;
        }
    }

    SiteId Test::PickSite()
    {
        return isaac.GetUniformDistInteger(0, NumSites());
    }

    static char nextChar = 'a';

    char GetNextChar()
    {
        char c = nextChar;
        if (++nextChar == 'z'+1) nextChar = 'a';
        return c;    
    }

    VectorIndex GetRandomString(Isaac& isaac, char* str, VectorIndex minSize, VectorIndex maxSize)
    {
        VectorIndex numChars = isaac.GetUniformDistInteger(minSize, maxSize+1);
        for (VectorIndex c = 0 ; c < numChars ; ++c)
        {
            str[c] = GetNextChar(); //isaac.GetUniformDistInteger('a','z'+1);
        }
        str[numChars] = '\0';
        return numChars;
    }

    void Test::DoLocalOp()
    {
        SiteId si = PickSite();
        Site& site = sites[si];

        VectorIndex n = (VectorIndex) site.field.size();
        if (n == 0 || isaac.GetUniformDistInteger(0,2) != 0)
        {
            // Generate random insertion

            const VectorIndex MIN_STR_SIZE = 1;
            const VectorIndex MAX_STR_SIZE = 2;
            char str[MAX_STR_SIZE+1];
            VectorIndex count = GetRandomString(isaac, str, MIN_STR_SIZE, MAX_STR_SIZE);

            VectorIndex pos = isaac.GetUniformDistInteger<VectorIndex>(0,n+1);

            // Record insertion interval for local operation
            site.vectorInsertionsAndDeletions.LocalInsertInterval_p(site.opid, pos, count);

            // Do the actual insertion on the field
            site.field.insert(pos, str, count);

            #if TRACE_TestVectorInsertions
                Tracer() << "Generated op : site S" << site.opid.s << " insert '" << str << "' at pos " << pos << " -> " << site.field << '\n';
            #endif
        }
        else
        {
            // Generate random deletion
            VectorIndex pos = isaac.GetUniformDistInteger<VectorIndex>(0,n);
            VectorIndex availToDelete = n-pos;
            cxAlwaysAssert(availToDelete >= 1);
            VectorIndex count = isaac.GetUniformDistInteger<VectorIndex>(1,availToDelete+1);

            // Record insertion interval for local operation
            site.vectorInsertionsAndDeletions.LocalDeleteInterval_p(site.opid, pos, count);

            // Do the actual insertion on the field
            site.field.erase(pos, count);

            #if TRACE_TestVectorInsertions
                Tracer() << "Generated op : site S" << site.opid.s << " delete " << count << " characters at pos " << pos << " -> " << site.field << '\n';
            #endif
        }

        // Update local vout and opid
        cxAlwaysAssert(site.vout(site.opid.s) == site.opid.t);
        ++site.opid.t;
        site.vout.Add(site.opid.s,site.opid.t);

    }

    void Test::TrySendOp(SiteId s1, SiteId s2)
    {
        Site& site1 = sites[s1];    // receiver = site1
        Site& site2 = sites[s2];    // sender = site2

        VectorTime vCommon;
        vCommon = Intersection(site1.vout, site2.vout);

        // Get RFactor on the sender

        VectorTime rhv = site1.vout;

        const VectorInsertions& src_insertions = site2.vectorInsertionsAndDeletions.m_insertions;
        const VectorDeletions& src_deletions = site2.vectorInsertionsAndDeletions.m_deletions;

        ceda::xvector<const VectorInsertionInterval*> dst_insertions;
        GetRFactorInsertions(dst_insertions, src_insertions, rhv);
        //Tracer() << "dst_insertions = " << dst_insertions << '\n';

        ceda::xvector<const VectorDeletionInterval*> dst_deletions;
        GetRFactorDeletions(dst_deletions, src_deletions, rhv);
        //Tracer() << "dst_deletions = " << dst_deletions << '\n';
                    
        if (!dst_insertions.empty() || !dst_deletions.empty())
        {
            ceda::RecordPCoordIntervals<VectorIndex> ri;
            GetIntervalsPresent(ri, dst_insertions, src_deletions);

            // Build RFactor string using the intervals in ri
            std::string B2;
            for (auto& i : ri.m_intervals)
            {
                B2.append( site2.field.data() + i.p, i.n );
            }
            //Tracer() << "B2 = " << B2 << '\n';

            VectorInsertions I2;
            ceda::LinkedListFromVectorOfPointersToNodes(I2.m_c, dst_insertions);
            I2.m_u2 = src_insertions.m_u2;
            //Tracer() << "I2 = " << I2 << '\n';

            VectorDeletions D2;
            ceda::LinkedListFromVectorOfPointersToNodes(D2, dst_deletions);
            //Tracer() << "D2 = " << D2 << '\n';

            {
                ceda::FilteredListUpdaterOnString filterB2(B2);
                TakeRFactor(I2, D2, filterB2, vCommon);
            }
                
            if (!I2.empty() || !D2.empty())
            {
                VectorInsertionsAndDeletions& vid = site1.vectorInsertionsAndDeletions; 
                VectorInsertions& I1 = vid.m_insertions;
                VectorDeletions& D1 = vid.m_deletions;

                ceda::StringAsVectorField vf(site1.field);
                ceda::xvector<ceda::octet_t> vB2;
                vB2.resize(B2.size());
                memcpy(vB2.data(), B2.data(), B2.size());

                ApplyDelta(vf, I1, D1, I2, D2, vB2, vCommon);

                #if TRACE_TestVectorInsertions
                    Tracer() << "Sent operation from S" << s2 << " : " << site2.field << " to S" << s1 << " -> " << site1.field << '\n';
                    //ceda::TraceIndenter indent(4);
                    //Tracer() << *this;
                #endif
            }
        }

        // site1 = merge(site1, site2)
        site1.vout.UnionWith(site2.vout);
    }

    void Test::PickDifferentSites(SiteId& s1, SiteId& s2)
    {
        do
        {
            s1 = PickSite();    // sender
            s2 = PickSite();    // receiver
        } while (s1 == s2);
    }

    void Test::SendOp()
    {
        SiteId s1,s2;
        PickDifferentSites(s1,s2);
        TrySendOp(s1,s2);
    }

    void Test::TestConvergenceOfTwoSites()
    {
        SiteId s1,s2;
        PickDifferentSites(s1,s2);
    
        #if TRACE_TestVectorInsertions
            Tracer() << "\nVerifying sites S" << s1 << " and S" << s2 << " converge\n";
            ceda::TraceIndenter indent(4);
        #endif
        TrySendOp(s1,s2);
        TrySendOp(s2,s1);
    
        #if TRACE_TestVectorInsertions
            Tracer() << "sites[s1].vout = " << sites[s1].vout << '\n';
            Tracer() << "sites[s2].vout = " << sites[s2].vout << '\n';
        #endif
        cxAlwaysAssert(sites[s1].vout == sites[s2].vout);
        cxAlwaysAssert(sites[s1].field == sites[s2].field);

        #if TRACE_TestVectorInsertions
            Tracer() << "Sites S" << s1 << " and S" << s2 << " converged to " << sites[s1].field << '\n';
        #endif
    }

    void RunTest(int numSites, int count2, double timeForTestInSecs)
    {
        // Need to be able to pick two different sites!
        cxAlwaysAssert(numSites >= 2);
    
        Isaac isaac;
        int numLocalOps = 0;
        int numSendOp = 0;
        int numCheckCgce = 0;

        ceda::HPTimer timeTaken;
        while(timeTaken.GetElapsedTimeInSeconds() < timeForTestInSecs)
        {
            Test test(numSites);
        
            #if TRACE_TestAssignment
                Tracer() << "\n------------------------------------------------------\n" << test << '\n';
            #endif
        
            for (int c2=0 ; c2 < count2 ; ++c2)
            {
                int c = isaac.GetUniformDistInteger(0,10);
            
                if (c < 5)
                {
                    test.DoLocalOp();
                    ++numLocalOps;
                }
                else if (c < 9)
                {
                    test.SendOp();
                    ++numSendOp;
                }
                else
                {
                    test.TestConvergenceOfTwoSites();
                    ++numCheckCgce;
                }
            }
        }
        Tracer() << "time=" << timeTaken.GetElapsedTimeInSeconds() << "s"
                    << "  sites=" << numSites 
                    << "  localops=" << numLocalOps 
                    << "  sendops=" << numSendOp 
                    << "  checkcgce=" << numCheckCgce 
                    << '\n';
    }
} // namespace vector_insertions_test

void UnitTestVectorInsertions(double timeForTestInSecs)
{
    Tracer() << "Unit test vector insertions\n";
    ceda::TraceIndenter indent(4);

    for (int numSites=2 ; numSites < 10 ; ++numSites)
    {
        vector_insertions_test::RunTest(numSites,200,timeForTestInSecs);
    }
}