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

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

namespace ceda
{
template<typename S, typename T>
struct TSun
{
    S s;
    T u;
    T n;
};

template<typename S, typename T>
inline bool operator==(const TSun<S,T>& sun1, const TSun<S,T>& sun2)
{
    return sun1.s == sun2.s &&
           sun1.u == sun2.u &&
           sun1.n == sun2.n;
}

template<typename S, typename T>
inline xostream& operator<<(xostream& os, const TSun<S,T>& sun) 
{ 
    os << "sun(" << sun.s << ',' << sun.u << ',' << sun.n << ')';
    return os; 
}

/*
Add (s,u,n) to an existing ordered list.

We use vector not linked list for good cache coherency and to avoid heap allocations.

Note that Add() is very efficient because it
    a)  avoids recursion using tail call optimisation
    
    b)  only erases the last element of the vector, which is very efficient and never
        results in memory copies or heap allocations
*/
        
// Let V = V @ [(s,u,n)].
template<typename S, typename T>
void Add(xvector<TSun<S,T>>& V, TSun<S,T> sun)
{
again:
    if (V.empty())
    {
        V.push_back(sun);
    }
    else
    {
        auto& last = V.back();
        if (last.s <= sun.s)
        {
            V.push_back(sun);
        }
        else if (last.u < sun.u)
        {
            // last eats (s,u,n)
            last.n += sun.n;    
        }
        else
        {
            // (s,u,n) eats last
            cxAssert(sun.u < last.u);
            sun.n += last.n;
            V.pop_back();
            goto again;
        }
    }
}

/*
Returns true if the siteids are non-decreasing 
- i.e. we take monotone increasing to mean weakly increasing. not strictly increasing
*/
template<typename S, typename T>
bool IsMonotoneIncreasingSiteId(const xvector<TSun<S,T>>& V)
{
    if (V.size() > 1)
    {
        auto i = V.begin();
        auto j = i;
        ++j;
        do
        {
            if (i->s > j->s) return false;
            ++i;
            ++j;
        } while(j != V.end());
    }
    return true;
}

} // namespace ceda