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

#include "StdAfx.h"
#include "Ceda/Core/cxUtils/PseudoRandom.h"
#include "Ceda/Core/cxUtils/CedaAssert.h"
#include "Ceda/Core/cxUtils/Tracer.h"
#include "AssignOp.h"


/*
We need to uniquely define the winner amongst a set of operations that all assign to the same
variable.  This can't simply be resolved by site ids because we need to respect causality.  
Unfortunately that puts a spanner in the works because we get cycles in the dominance relation.

Example
-------

Consider the following example where O1, O2, O3 are assignments on the same field

    There are three sites

    Let G = Generate, R = Receive.  

        Site 1:            R: O3   G: O1
        Site 2:   G: O2       
        Site 3:   G: O3                    R: O2   R: O1
                ----------------------------------------------------> time

    So O3 --> O1, O2 || O1 and O2 || O3.

    Then we build the following HB for site 3.

       HB =  [O3 O2' O1']  =  [ O3   IT(O2,O3)   IT(O1,IT(O2,O3)) ]
    
    Then we transpose the last two operations in this HB and check for convergence


It turns out that there is a problem with the whole idea of using a disable count to pick a unique 
winner when operations fight over a character!   More specifically, we get a cycle in the 
"dominance relation",  totally at odds with picking a unique winner. The fly in the ointment is 
the causal relation O3 --> O1 from which we expect O1 to always dominate O3 even though site ids 
suggest otherwise.  The problem is quite tricky because somehow when O1 IT's past O2' it should not
be disabled despite its smaller site id.  It needs to account for the fact that it dominates O3 by 
causality, and O3 dominates O2 by site ids.


Solution
--------

It seems very difficult to solve this problem!  All sites need to somehow agree on a total ordering
on all the assignments that have ever been performed.  That way, all sites can agree (at 
quiescence) on the unique winner that dominates all other assignments.  This way of thinking leads 
directly to the solution : employ a hypothetical effects document that holds every value that has 
ever been "assigned" (or actually inserted into the effects document).  The winner is simply the 
left most element in the effects document (i.e. at index position 0).  Convergence is guaranteed.  

Therefore a workable solution simply involves introduction of a q-position in the assignment 
operation to represent the insertion position in the effects document. This is initialised to 0 
when the operation is first generated so it dominates all previous assignments that have been 
performed on that document state.  The q-position is transformed as for insertion operations into a
string.  When an assignment operation is performed it is regarded as enabled if and only if its 
q-position is 0.

It would be possible to define the right most character in the effects document to be the winner.
However, it would be more difficult to generate an operation.  It would probably require storage of
the q-size in each assignable field.
*/

using namespace ceda;
extern bool gp_debug;

ssize_t GetRandomAssignValue()
{
    return GetUniformDistInteger_ssize_t(100, 200);
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// AssignDoc

void AssignDoc::SetRandom(RandomInitSettings ris)
{
    Set(GetRandomAssignValue());
}

void AssignDoc::Set(ssize_t value)
{
    m_value = value;
}

void AssignDoc::Write(xostream& os) const
{
    os << m_value;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// AssignDocSet

void AssignDocSet::InitRandomDocs(RandomInitSettings ris)
{
    for (iterator i = begin() ; i != end() ; ++i)
    {
        i->SetRandom(ris);
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// AssignOp

AssignOp::AssignOp() : 
    doc(-1),
    ov(-1),
    nv(-1),
    q(-1)
{
}

bool AssignOp::operator==(const AssignOp& rhs) const
{ 
    return m_opid == rhs.m_opid &&
           doc == rhs.doc &&
           ov == rhs.ov &&
           nv == rhs.nv &&
           q == rhs.q;
}

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

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

    doc = GetUniformDistInteger_ssize_t(0,numDocs);
    ov = ds[doc].Get();
    nv = GetRandomAssignValue();
    q = 0;
}

void AssignOp::Do(AssignDocSet& ds)
{
    AssignDoc& d = ds[doc];
    cxAlwaysAssert(d.Get() == ov);
    if (q == 0) d.Set(nv);
}

void AssignOp::Undo(AssignDocSet& ds)
{
    AssignDoc& d = ds[doc];
    cxAlwaysAssert(d.Get() == nv);
    if (q == 0) d.Set(ov);
}

xostream& operator<<(xostream& os, const AssignOp& O)
{
    if (O.doc)
    {
        os << O.doc << ':';
    }
    if (O.q)
    {
        os << O.q << ';';
    }
    os << O.ov << "->" << O.nv;
    return os;
}

void IT(AssignOp& O1, const AssignOp& O2)
{
    cxAlwaysAssert(O1.GetId() != O2.GetId());

    if (O1.doc == O2.doc)
    {
        // As far as the effects document is concerned assignment is an insertion at its position q
        if (O2.q < O1.q || O2.q == O1.q && O2.GetId() < O1.GetId())
        {
            ++O1.q;
        }

        if (O2.q == 0)
        {
            O1.ov = O2.nv;
        }
    }
}

// [O2 O1]
void ET(AssignOp& O1, const AssignOp& O2)
{
    cxAlwaysAssert(O1.GetId() != O2.GetId());

    if (O1.doc == O2.doc)
    {
        // As far as the effects document is concerned assignment is an insertion at its position q
        if (O2.q < O1.q)
        {
            cxAlwaysAssert(O1.q > 0);
            --O1.q;
        }

        if (O2.q == 0)
        {
            O1.ov = O2.ov;
        }
    }
}

void DualIT(AssignOp& O1, AssignOp& O2)
{
    AssignOp copyO1 = O1;
    IT(O1,O2);
    IT(O2,copyO1);    
}

void Transpose(AssignOp& O1, AssignOp& O2)
{
    ET(O2,O1);
    IT(O1,O2);
}

void Merge(AssignOp& O1, const AssignOp& O2)
{
    cxAssert(0);
}