Span.h

#pragma once


#include <libutl/MemStream.h>


UTL_NS_BEGIN;


enum span_op_t
{
    span_overlaps,    
    span_contains,    
    span_contained_in 
};

// Span ////////////////////////////////////////////////////////////////////////////////////////////


template <class T, class D = T>
class Span : public Object, protected FlagsMI
{
    UTL_CLASS_DECL_TPL2(Span, T, D, Object);

public:
    Span(const T& begin, const T& end, bool relaxed = false);

    virtual int compare(const Object& rhs) const;

    virtual void copy(const Object& rhs);

    virtual void serialize(Stream& stream, uint_t io, uint_t mode = ser_default);

    virtual String toString() const;



    const T&
    begin() const
    {
        return _begin;
    }

    void
    setBegin(const T& begin)
    {
        _begin = begin;
    }

    const T&
    end() const
    {
        return _end;
    }

    void
    setEnd(const T& end)
    {
        _end = end;
    }

    void
    set(const T& begin, const T& end)
    {
        _begin = begin;
        _end = end;
    }

    bool
    isNil() const
    {
        return _begin >= _end;
    }

    void
    setNil()
    {
        _begin = _end = T();
    }

    bool
    isRelaxed() const
    {
        return getFlag(flg_relaxed);
    }

    void
    setRelaxed(bool relaxed)
    {
        setFlag(flg_relaxed, relaxed);
    }

    D
    size() const
    {
        return _end - _begin;
    }

    Span<T, D>& clip(const Span<T, D>& span);

    Span<T, D>&
    clipBegin(const T& t)
    {
        if (t > _begin) _begin = t;
        return *this;
    }

    Span<T, D>&
    clipEnd(const T& t)
    {
        if (t < _end) _end = t;
        return *this;
    }

    bool
    contains(const Span<T, D>& span) const
    {
        return (_begin <= span._begin) && (_end >= span._end);
    }

    bool
    contains(const T& v) const
    {
        return ((v >= _begin) && (v < _end));
    }

    bool
    isContainedBy(const Span<T, D>& span) const
    {
        return span.contains(*this);
    }

    void
    merge(const Span<T, D>& span)
    {
        _begin = min(_begin, span.begin());
        _end = max(_end, span.end());
    }

    Span<T, D> overlap(const Span<T, D>& span) const;

    bool
    overlaps(const Span<T, D>& span) const
    {
        return !overlap(span).isNil();
    }

    D overlapSize(const Span<T, D>& span) const;

    Span<T, D> remove(const Span<T, D>& span);

    Span<T, D> operator+(const Span<T, D>& rhs)
    {
        Span<T, D> res(*this);
        res.merge(rhs);
        return res;
    }

    const Span<T, D>& operator+=(const Span<T, D>& rhs)
    {
        merge(rhs);
        return *this;
    }

protected:
    T _begin;
    T _end;

private:
    enum flg_t
    {
        flg_relaxed
    };

private:
    void
    init(bool relaxed = false)
    {
        _begin = _end = T();
        setRelaxed(relaxed);
    }
    void
    deInit()
    {
    }
};

// SpanSizeOrdering ////////////////////////////////////////////////////////////////////////////////


template <class T, class D = T>
class SpanSizeOrdering : public Ordering
{
    UTL_CLASS_DECL_TPL2(SpanSizeOrdering, T, D, Ordering);
    UTL_CLASS_DEFID;

public:
    virtual int cmp(const Object* lhs, const Object* rhs) const;
};

// ObjectSpan //////////////////////////////////////////////////////////////////////////////////////


template <class T, class D = T>
class ObjectSpan : public Span<T, D>
{
    UTL_CLASS_DECL_TPL2_TPL2(ObjectSpan, T, D, Span, T, D);
    UTL_CLASS_DEFID;

public:
    ObjectSpan(Span<T, D> span)
        : Span<T, D>(span)
    {
    }

    virtual void serialize(Stream& stream, uint_t io, uint_t mode = ser_default);

    virtual String
    toString() const
    {
        return "[" + this->_begin.toString() + "," + this->_end.toString() + ")";
    }
};

// Span ////////////////////////////////////////////////////////////////////////////////////////////

template <class T, class D>
Span<T, D>::Span(const T& begin, const T& end, bool relaxed)
    : _begin(begin)
    , _end(end)
{
    setRelaxed(relaxed);
}


template <class T, class D>
int
Span<T, D>::compare(const Object& rhs) const
{
    int res;
    if (rhs.isA2(Span, T, D))
    {
        auto& span = utl::cast<Span<T, D>>(rhs);
        // If "relaxed" comparison, the spans are equal if they overlap,
        // Else they must be exactly the same.
        if ((isRelaxed() || span.isRelaxed()) && overlaps(span))
        {
            res = 0;
        }
        else
        {
            res = utl::compare(_begin, span._begin);
            if (res != 0) return res;
            res = utl::compare(_end, span._end);
        }
    }
    else
    {
        res = super::compare(rhs);
    }
    return res;
}


template <class T, class D>
void
Span<T, D>::copy(const Object& rhs)
{
    auto& span = utl::cast<Span<T, D>>(rhs);
    FlagsMI::copyFlags(span);
    _begin = span._begin;
    _end = span._end;
}


template <class T, class D>
void
Span<T, D>::serialize(Stream& stream, uint_t io, uint_t mode)
{
    utl::serialize(_begin, stream, io, mode);
    utl::serialize(_end, stream, io, mode);
}


template <class T, class D>
String
Span<T, D>::toString() const
{
    MemStream ms(64);
    ms << "[" << _begin << "," << _end << ")" << '\0';
    return String(ms.takeString(), true, false);
}


template <class T, class D>
Span<T, D>&
Span<T, D>::clip(const Span<T, D>& span)
{
    // ensure begin >= span.begin
    // ensure end <= span.end
    if (_begin < span._begin) _begin = span._begin;
    if (_end > span._end) _end = span._end;
    return *this;
}


template <class T, class D>
Span<T, D>
Span<T, D>::overlap(const Span<T, D>& span) const
{
    T beg = max(_begin, span._begin);
    T end = min(_end, span._end);
    return Span<T, D>(beg, end);
}


template <class T, class D>
D
Span<T, D>::overlapSize(const Span<T, D>& span) const
{
    return utl::min(_end, span._end) - utl::max(_begin, span._begin);
}


template <class T, class D>
Span<T, D>
Span<T, D>::remove(const Span<T, D>& span)
{
    T t = T();
    Span<T, D> res(t, t);

    // if span contains* this, removing span makes* this NIL
    if (span.contains(*this))
    {
        setNil();
        return res;
    }

    // get the overlapping time span
    Span<T, D> overlap = span.overlap(*this);

    if (overlap.isNil())
    {
        return res;
    }

    // if begin == beginning of overlap, begin = end of overlap
    if (_begin == overlap.begin())
    {
        setBegin(overlap.end());
    }
    // if end == end of overlap, end = beginning of overlap
    else if (_end == overlap.end())
    {
        setEnd(overlap.begin());
    }
    // else we are being bi-sected
    else
    {
        // the result is the second section [overlap.end, end)
        res.setBegin(overlap.end());
        res.setEnd(end());
        // this becomes the first section [begin, overlap.begin)
        setEnd(overlap.begin());
    }

    return res;
}

// SpanSizeOrdering ////////////////////////////////////////////////////////////////////////////////

template <class T, class D>
int
SpanSizeOrdering<T, D>::cmp(const Object* lhs, const Object* rhs) const
{
    const Object& lhsKey = lhs->getKey();
    const Object& rhsKey = rhs->getKey();
    if (!lhsKey.isA2(Span, T, D) || !rhsKey.isA2(Span, T, D))
    {
        return lhs->compare(*rhs);
    }

    const Span<T, D>& lhsSpan = (const Span<T, D>&)lhsKey;
    const Span<T, D>& rhsSpan = (const Span<T, D>&)rhsKey;
    int res = lhsSpan.size() - rhsSpan.size();
    if (res == 0)
    {
        res = lhsSpan.compare(rhsSpan);
    }
    return res;
}

// ObjectSpan //////////////////////////////////////////////////////////////////////////////////////

template <class T, class D>
void
ObjectSpan<T, D>::serialize(Stream& stream, uint_t io, uint_t mode)
{
    this->_begin.serialize(stream, io, mode);
    this->_end.serialize(stream, io, mode);
}


UTL_NS_END;


UTL_CLASS_IMPL_TPL2(utl::Span, T, D);
UTL_CLASS_IMPL_TPL2(utl::SpanSizeOrdering, T, D);
UTL_CLASS_IMPL_TPL2(utl::ObjectSpan, T, D);