#include "operation.h"

#include <algorithm>
#include <sstream>
#include <stdexcept>

namespace
{
void require(bool condition, const std::string& message)
{
    if (!condition) throw std::runtime_error(message);
}

std::size_t asSize(Index value)
{
    require(value >= 0, "negative index");
    return static_cast<std::size_t>(value);
}

Index visibleBefore(const std::vector<Character>& characters, Index q)
{
    require(0 <= q && q <= static_cast<Index>(characters.size()), "q-position outside document");
    return static_cast<Index>(std::count_if(characters.begin(), characters.begin() + q,
        [](const Character& character) { return character.visible; }));
}

template<class Range>
auto split(std::list<Range>& ranges, typename std::list<Range>::iterator i, Index leftSize)
{
    require(0 < leftSize && leftSize < i->size(), "invalid range split");
    Range right = *i;
    right.q += leftSize;
    if constexpr (std::is_same_v<Range, Extraction>)
    {
        if (i->enabled) right.p += leftSize;
    }
    else right.p += leftSize;
    right.characters.erase(right.characters.begin(), right.characters.begin() + leftSize);
    i->characters.erase(i->characters.begin() + leftSize, i->characters.end());
    return ranges.insert(std::next(i), std::move(right));
}

void coalesce(std::list<Extraction>& ranges)
{
    for (auto i = ranges.begin(); i != ranges.end(); ++i)
    {
        auto j = std::next(i);
        while (j != ranges.end() && i->q + i->size() == j->q &&
               i->enabled == j->enabled && i->originSite == j->originSite)
        {
            i->characters.insert(i->characters.end(), j->characters.begin(), j->characters.end());
            j = ranges.erase(j);
        }
    }
}

void dualDeleteDelete(std::list<Extraction>& first, std::list<Extraction>& second)
{
    Index firstShift = 0, secondShift = 0;
    auto a = first.begin();
    auto b = second.begin();
    while (a != first.end() && b != second.end())
    {
        if (a->q + a->size() <= b->q)
        {
            a->p -= secondShift;
            if (a->enabled) firstShift += a->size();
            ++a;
        }
        else if (b->q + b->size() <= a->q)
        {
            b->p -= firstShift;
            if (b->enabled) secondShift += b->size();
            ++b;
        }
        else
        {
            if (a->q < b->q)
            {
                split(first, a, b->q - a->q);
                a->p -= secondShift;
                if (a->enabled) firstShift += a->size();
                ++a;
            }
            else if (b->q < a->q)
            {
                split(second, b, a->q - b->q);
                b->p -= firstShift;
                if (b->enabled) secondShift += b->size();
                ++b;
            }
            if (b->size() < a->size()) split(first, a, b->size());
            else if (a->size() < b->size()) split(second, b, a->size());
            b->p -= firstShift;
            a->p -= secondShift;
            const bool aEnabled = a->enabled;
            if (b->enabled) { secondShift += b->size(); a->enabled = false; }
            if (aEnabled) { firstShift += a->size(); b->enabled = false; }
            ++a; ++b;
        }
    }
    for (; b != second.end(); ++b) b->p -= firstShift;
    for (; a != first.end(); ++a) a->p -= secondShift;
    coalesce(first); coalesce(second);
}

void dualInsertDelete(std::list<Insertion>& insertions, std::list<Extraction>& extractions)
{
    Index insertionShift = 0, extractionShift = 0;
    auto i = insertions.begin();
    auto x = extractions.begin();
    while (i != insertions.end() && x != extractions.end())
    {
        const Index distance = i->q - (insertionShift + x->q);
        if (distance <= 0)
        {
            insertionShift += i->size();
            i->p -= extractionShift;
            ++i;
        }
        else
        {
            if (distance < x->size()) split(extractions, x, distance);
            x->q += insertionShift;
            x->p += insertionShift;
            if (x->enabled) extractionShift += x->size();
            ++x;
        }
    }
    for (; x != extractions.end(); ++x) { x->q += insertionShift; x->p += insertionShift; }
    for (; i != insertions.end(); ++i) i->p -= extractionShift;
}

void dualInsertInsert(std::list<Insertion>& first, std::list<Insertion>& second)
{
    Index firstShift = 0, secondShift = 0;
    auto a = first.begin();
    auto b = second.begin();
    while (a != first.end() && b != second.end())
    {
        const Index distance = (firstShift + b->q) - (secondShift + a->q);
        if (distance < 0 || (distance == 0 && b->originSite < a->originSite))
        {
            b->p += firstShift; b->q += firstShift; secondShift += b->size(); ++b;
        }
        else
        {
            a->p += secondShift; a->q += secondShift; firstShift += a->size(); ++a;
        }
    }
    for (; b != second.end(); ++b) { b->p += firstShift; b->q += firstShift; }
    for (; a != first.end(); ++a) { a->p += secondShift; a->q += secondShift; }
}

void transposeDeleteDelete(std::list<Extraction>& first, std::list<Extraction>& second)
{
    Index firstShift = 0, secondShift = 0;
    auto a = first.begin(); auto b = second.begin();
    while (a != first.end() && b != second.end())
    {
        if (a->q + a->size() <= b->q)
        { a->p -= secondShift; if (a->enabled) firstShift += a->size(); ++a; }
        else if (b->q + b->size() <= a->q)
        { b->p += firstShift; if (b->enabled) secondShift += b->size(); ++b; }
        else
        {
            if (a->q < b->q)
            { split(first,a,b->q-a->q); a->p-=secondShift; if(a->enabled)firstShift+=a->size(); ++a; }
            else if (b->q < a->q)
            { split(second,b,a->q-b->q); b->p+=firstShift; if(b->enabled)secondShift+=b->size(); ++b; }
            if (b->size() < a->size()) split(first,a,b->size());
            else if (a->size() < b->size()) split(second,b,a->size());
            a->p -= secondShift; b->p += firstShift;
            if (a->enabled) { firstShift += a->size(); b->enabled = true; }
            if (b->enabled) { secondShift += b->size(); a->enabled = false; }
            ++a; ++b;
        }
    }
    for (; b != second.end(); ++b) b->p += firstShift;
    for (; a != first.end(); ++a) a->p -= secondShift;
    coalesce(first); coalesce(second);
}

void transposeInsertInsert(std::list<Insertion>& first, std::list<Insertion>& second)
{
    Index firstShift=0, secondShift=0;
    auto a=first.begin(); auto b=second.begin();
    while(a!=first.end() && b!=second.end())
    {
        if (b->q <= secondShift + a->q)
        { b->p-=firstShift; b->q-=firstShift; secondShift+=b->size(); ++b; }
        else
        { a->p+=secondShift; a->q+=secondShift; firstShift+=a->size(); ++a; }
    }
    for(;b!=second.end();++b){b->p-=firstShift;b->q-=firstShift;}
    for(;a!=first.end();++a){a->p+=secondShift;a->q+=secondShift;}
}

void transposeInsertDelete(std::list<Insertion>& insertions, std::list<Extraction>& extractions)
{
    Index insertionShift=0, extractionShift=0;
    auto i=insertions.begin(); auto x=extractions.begin();
    while(i!=insertions.end() && x!=extractions.end())
    {
        if(i->q+i->size()<=x->q){i->p-=extractionShift;insertionShift+=i->size();++i;}
        else if(x->q+x->size()<=i->q)
        {x->p-=insertionShift;x->q-=insertionShift;if(x->enabled)extractionShift+=x->size();++x;}
        else require(false,"concurrent insertion/deletion intervals overlap");
    }
    for(;x!=extractions.end();++x){x->p-=insertionShift;x->q-=insertionShift;}
    for(;i!=insertions.end();++i)i->p-=extractionShift;
}

void transposeDeleteInsert(std::list<Extraction>& extractions, std::list<Insertion>& insertions)
{
    Index insertionShift=0, extractionShift=0;
    auto i=insertions.begin(); auto x=extractions.begin();
    while(i!=insertions.end() && x!=extractions.end())
    {
        const Index distance=i->q-(insertionShift+x->q);
        if(distance<=0){insertionShift+=i->size();i->p+=extractionShift;++i;}
        else
        {if(distance<x->size())split(extractions,x,distance);x->q+=insertionShift;x->p+=insertionShift;if(x->enabled)extractionShift+=x->size();++x;}
    }
    for(;x!=extractions.end();++x){x->q+=insertionShift;x->p+=insertionShift;}
    for(;i!=insertions.end();++i)i->p+=extractionShift;
}
}

Document::Document(Index initialSize)
{
    require(initialSize >= 0, "negative initial size");
    for(Index i=0;i<initialSize;++i) characters_.push_back({OpId{-1,0},i,static_cast<char>('A'+i%26),true});
}

Index Document::visibleSize() const
{ return static_cast<Index>(std::count_if(characters_.begin(),characters_.end(),[](const auto& c){return c.visible;})); }
Index Document::effectsSize() const { return static_cast<Index>(characters_.size()); }

Index Document::qFromP(Index p) const
{
    require(0<=p && p<=visibleSize(),"p-position outside document");
    Index visible=0;
    for(Index q=0;q<effectsSize();++q) if(characters_[asSize(q)].visible && visible++==p)return q;
    return effectsSize();
}

const Character& Document::visibleCharacter(Index p) const
{
    require(0<=p && p<visibleSize(),"visible position outside document");
    Index visible=0;
    for(const auto& c:characters_)if(c.visible && visible++==p)return c;
    throw std::runtime_error("visible character not found");
}

void Document::insert(Index p,Index q,const std::vector<Character>& characters)
{
    require(visibleBefore(characters_,q)==p,"insertion p/q positions disagree");
    characters_.insert(characters_.begin()+q,characters.begin(),characters.end());
}

void Document::erase(Index p,Index q,const std::vector<Character>& expected)
{
    require(visibleBefore(characters_,q)==p,"extraction p/q positions disagree");
    require(q+static_cast<Index>(expected.size())<=effectsSize(),"extraction outside document");
    for(std::size_t n=0;n<expected.size();++n)
    {
        Character& actual=characters_[asSize(q)+n];
        require(actual.visible,"extraction character already hidden");
        require(actual.operation==expected[n].operation && actual.offset==expected[n].offset && actual.value==expected[n].value,
                "extraction character identity mismatch");
        actual.visible=false;
    }
}

std::string Document::describe() const
{
    std::ostringstream out; out<<'[';
    for(const auto& c:characters_)out<<(c.visible?c.value:'*')<<'@'<<c.operation.site<<':'<<c.operation.time<<':'<<c.offset<<' ';
    return out.str()+']';
}

void Operation::apply(Document& document) const
{
    for(auto x=extractions.rbegin();x!=extractions.rend();++x)if(x->enabled)document.erase(x->p,x->q,x->characters);
    for(const auto& i:insertions)document.insert(i.p,i.q,i.characters);
}

void dualInclusionTransform(Operation& first,Operation& second)
{
    dualDeleteDelete(first.extractions,second.extractions);
    dualInsertDelete(first.insertions,second.extractions);
    dualInsertDelete(second.insertions,first.extractions);
    dualInsertInsert(first.insertions,second.insertions);
}

void inclusionTransform(Operation& first,const Operation& second)
{ Operation copy=second; dualInclusionTransform(first,copy); }

void transpose(Operation& first,Operation& second)
{
    transposeInsertDelete(first.insertions,second.extractions);
    transposeDeleteDelete(first.extractions,second.extractions);
    transposeInsertInsert(first.insertions,second.insertions);
    transposeDeleteInsert(first.extractions,second.insertions);
}

void exclusionTransform(Operation& first,const Operation& second)
{ Operation copy=second; transpose(copy,first); }

std::string describe(const Operation& operation)
{
    std::ostringstream out; out<<"@("<<operation.id.site<<','<<operation.id.time<<") X{";
    for(const auto& x:operation.extractions)out<<(x.enabled?"":"*")<<x.q<<'|'<<x.p<<'+'<<x.size()<<' ';
    out<<"} I{"; for(const auto& i:operation.insertions)out<<i.q<<'|'<<i.p<<'+'<<i.size()<<' '; return out.str()+"}";
}