// VectorRFactor.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2007-2021

#pragma once
#include "TVectorInsertions.h"
#include "TVectorDeletions.h"
#include "TVectorTime.h"
#include "MonotoneIncreasingExtentsOnIntervalSet.h"
#include "Ceda/cxUtils/CedaAssert.h"

namespace ceda
{
////////////////////////////////////////////////////////////////////////////////////////////////////
// Factorise O with respect to v
// v must be a causally valid vector time with vin(O) <= v <= vout(O)
// Returns with Rf set to the RFactor of O, and O assigned to its LFactor

template<typename VectorInsertions, typename VectorTime>
void ExtractRFactor(VectorInsertions& O, const VectorTime& v, VectorInsertions& Rf)
{
    using I = typename VectorInsertions::VectorIndex;
    using Node = typename VectorInsertions::Node;
    cxAssert(O.m_u2 >= 0);
    
    // Accumulates the number of characters inserted by Rf
    I offset = 0;

    Rf.m_u2 = O.m_u2;

    // The following implementation makes use of the original intervals to avoid
    // heap deallocations and heap allocations.
    // We assign O.m_c.m_first = nullptr to orphan the list from O.  This allows us
    // to iterate through the intervals and add them either to O or Rf.
    Rf.m_c.Clear();
    Node* cn = O.m_c.m_first;
    O.m_c.m_first = nullptr;
    Node* last1 = nullptr;
    Node* last2 = nullptr;

    while(cn)
    {
        Node* next = cn->m_next;  // Record next before we overwrite it with nullptr
        cn->m_prev = nullptr;
        cn->m_next = nullptr;
        
        /*
        if (bTraceMergeOidOps)
        {
            Tracer() << "  O.m_u2 = " << O.m_u2
                     << "  cn->m_u = " << cn->m_u
                     << "  cn = " << *cn
                     << '\n';
        }
        */
        
        cxAssert(cn->m_u < O.m_u2);
        if (v.ExtentContains(cn->m_opid))
        {
            // Add cn to Lf
            cn->m_q -= offset;
            O.m_c.PushBack(last1,cn);
        }
        else
        {
            // Add cn to Rf
            offset += cn->m_n;
            Rf.m_c.PushBack(last2,cn);
        }
        cn = next;
    }
}

/*
Version which writes the dst associated with the RFactor.
*/
template <typename Insertions, typename VectorTime, typename Vector>
void ExtractRFactor(
    Insertions& O, 
    const VectorTime& v, 
    Insertions& Rf, 
    const Vector& src, 
    Vector& dst)
{
    using I = typename VectorInsertions::VectorIndex;
    using Node = typename Insertions::Node;

    dst.clear();
    dst.reserve(src.size());
    auto psrc = src.data();

    // Accumulates the number of characters inserted by Rf
    I offset = 0;

    Rf.m_u2 = O.m_u2;

    // The following implementation makes use of the original intervals to avoid
    // heap deallocations and heap allocations.
    // We assign O.m_c.m_first = nullptr to orphan the list from O.  This allows us
    // to iterate through the intervals and add them either to O or Rf.
    Rf.m_c.Clear();
    Node* cn = O.m_c.m_first;
    O.m_c.m_first = nullptr;
    Node* last1 = nullptr;
    Node* last2 = nullptr;

    while(cn)
    {
        Node* next = cn->m_next;  // Record next before we overwrite it with nullptr
        cn->m_prev = nullptr;
        cn->m_next = nullptr;

        I n = cn->size();
        
        /*
        if (bTraceMergeOidOps)
        {
            Tracer() << "  O.m_u2 = " << O.m_u2
                     << "  cn->m_u = " << cn->m_u
                     << "  cn = " << *cn
                     << '\n';
        }
        */
        
        cxAssert(cn->m_u < O.m_u2);
        if (v.ExtentContains(cn->m_opid))
        {
            // Add cn to Lf
            cn->m_q -= offset;
            O.m_c.PushBack(last1,cn);
        }
        else
        {
            // Add cn to Rf
            offset += n;
            Rf.m_c.PushBack(last2,cn);
            
            dst.append(psrc,n);
        }
        psrc += n;
        cn = next;
    }
    cxAssert(psrc == src.data() + src.size());
}

/*
A delta on a xvector<T> field is represented by a set of ordered insertion intervals I and ordered
deletion intervals D.  I,D are expressed in the same post insertion coordinates.

B represents a contiguous buffer of the elements to be inserted but not deleted by the 
delta.  Each element takes up 'elementSize' bytes.

Precondition : B.size() == (I\D).Extent() * elementSize.

v is a given causally valid vector time.  This function replaces I by RFactor(I,v).  It also
partitions B into Binside and Boutside according to whether an element in B (i.e. an element
to be inserted but not deleted by the delta) was inserted by an operation identified by (s,t) 
inside X(v) or not.

    I                   <---  Rfactor(I,v)
    
    Binside, Boutside   <---  B partitioned according to whether the insertion is inside X(v)
                              or outside X(v).
*/

// Calculates the RFactor of the composite operation (I,D,B) with respect to vector time v
// and replaces I and B with their RFactor versions.
// For an optimisation D is not updated because it happen not to be required.
template<typename VectorInsertions, typename VectorDeletions, typename FilteredListUpdater, typename VectorTime>
void TakeRFactor(VectorInsertions& I, const VectorDeletions& D, FilteredListUpdater& B, const VectorTime& v)
{
    using VectorIndex = typename VectorInsertions::VectorIndex;
    
    // Allow for measurement of extents of ([0,q) intersect D) for monotone increasing
    // values of q.
    MeasureMonotoneIncreasingExtentsOnIntervalSet<typename VectorDeletions::Range, VectorIndex> measureDExtents(MakeRangeFromBiDirectionalIterators(D));

    // Iterate through the intervals of I. For each interval we determine whether it exists 
    // in X(v). This allows us to delete intervals inside X(v) as we go, in order to convert 
    // I into an RFactor.
    VectorInsertions::Node* i = I.m_c.m_first;
    while(i)
    {
        /*
        Note that D may split interval i up into any number of parts
        
                 q1                                  q2
                 [------------------------------------)         i (an interval of I)
                     [--)     [---)           [------------)    D
                 [---)  [-----)   [-----------)                 i\D


        For each i = [q1,q2) in I we can use measureDExtents to measure 

            e1 = D.extent(q1)
            e2 = D.extent(q2)
            
        Then e2-e1 represents the extent of (i intersect D).

        That means the extent of i\D is
        
            n = (q2-q1) - (e2-e1)
            
        n represents the number of elements in B associated with the insertion interval i.
        */
        
        // Note that e1 must be calculated before e2, in order to follow the rule that
        // measureDExtents.Extent(q) is called with monotone increasing values of q.
        auto e1 = measureDExtents.Extent(i->m_q);
        auto e2 = measureDExtents.Extent(i->m_q + i->m_n);
        auto n = (i->m_n - (e2-e1));    // total extent of (i\D)
        
        VectorInsertions::Node* next = i->m_next;   // Copy i->m_next before deleting i
        if (v.ExtentContains(i->m_opid))
        {
            // i inside X(v)
            B.Drop(n);
            I.m_c.Erase(i);     // i is not part of the RFactor
        }
        else
        {
            // i outside X(V)
            B.Keep(n);
        }
        i = next;
    }
}

} // namespace ceda