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

#pragma once
#include "Ceda/cxUtils/CedaAssert.h"

/*
This is the old way to calculate effective siteids.  

This transient state was recorded in the persistent intervals, and calculated before 
performing DualIT.

This code is no longer used, instead a recursive algorithm on a vector of (s,u,n) triples is
used to calculate the effective siteids.  See TSun.h
*/

namespace ceda
{
    // Calculate m_es,m_eu of each insertion interval in list.
    template <typename List>
    void CalculateEffectiveSiteIds(List& list)
    {
        typedef List::Node Node;
        
        /*
        if (bTraceMergeOidOps)
        {
            Tracer() << "\nCalculateEffectiveSiteIds on list = " << list << '\n';
        }
        */
        
        Node* r1 = list.m_first;
        
        while(r1)
        {
            /*
            if (bTraceMergeOidOps)
            {
                Tracer() << "  r1 = " << *r1 << '\n';
            }
            */
            
            r1->m_es = r1->m_opid.s;
            r1->m_eu = r1->m_u;
            
            // Process maximal q-contiguous piece that starts at r1
            Node* rp = r1;
            cxAssert(rp);
            ssize_t q = r1->m_q + r1->m_n;
            Node* rn = rp->m_next;
            while(rn && rn->m_q == q)
            {
                /*
                if (bTraceMergeOidOps)
                {
                    Tracer() << "  rp = " << *rp << '\n';
                    Tracer() << "  rn = " << *rn << '\n';
                }
                */

                // Process rn
                cxAssert(rp);
                cxAssert(rn);
                if (rp->m_es <= rn->m_opid.s)
                {
                    // Siteids are in order
                    rn->m_es = rn->m_opid.s;
                    rn->m_eu = rn->m_u;
                }
                else
                {
                    // Siteids are decreasing which is no good
                    cxAssert(rp->m_eu != rn->m_u);
                    if (rp->m_eu < rn->m_u)
                    {
                        // rp dominates rn, so rn inherits effective s,u from rp
                        rn->m_es = rp->m_es;
                        rn->m_eu = rp->m_eu;
                    }
                    else
                    {
                        // rn dominates rp, so we must scan right to left as far as
                        // needed to propagate rn's s,u to the intervals that precede 
                        // it according to q-position
                        SiteId s = rn->m_opid.s;
                        ssize_t u = rn->m_u;
                        rn->m_es = s;
                        rn->m_eu = u;
                        Node* r = rp;
                        while(1)
                        {
                            cxAssert(r);
                            if (r->m_es > s)
                            {
                                if (r->m_eu < u)
                                {
                                    // r dominates rn, so we now have to scan left to right
                                    // from r propagating the s,u from r
                                    s = r->m_es;
                                    u = r->m_eu;
                                    while(1)
                                    {
                                        r = r->m_next;
                                        cxAssert(r);
                                        r->m_es = s;
                                        r->m_eu = u;
                                        if (r == rn) break;
                                    }
                                    break;
                                }
                            }
                            else
                            {
                                break;
                            }
                            r->m_es = rn->m_opid.s;
                            r->m_eu = rn->m_u;
                            if (r == r1) break;
                            r = r->m_prev;
                        };
                    }
                }
                
                q += rn->m_n;
                rp = rn;
                rn = rn->m_next;
            }
        
            // Advance to the start of the next maximal q-contiguous piece
            cxAssert(rp);
            r1 = rp->m_next;
        }
    }
} // namespace ceda