Range.h

// Range.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2021

#pragma once
#ifndef Ceda_cxUtils_Range_H
#define Ceda_cxUtils_Range_H

#include "Archive.h"
#include "MakeIterator.h"
#include "xvector.h"
#include <iterator>
#include <cstddef>
#include <algorithm>

/*
Proposal: Using abstract iterators
----------------------------------

To generate efficient algorithms easily consider that we made heavy use of abstract iterators.

So given a pair of iterators [w1,w2) we have a sequence of half open intervals.  To make 
the algorithms as generic as possible they should tend to work on a pair of abstract iterators 
rather than an IntervalList<T>!  In addition the way to read the start and end position of 
the interval should be abstracted as well.  That makes the algorithms fully decouple from
implementation.

Rather than iterator consider that we use the range concept.

    Range r;
    
    if (r)      // is range empty
    *r          // points to start of range which must be nonempty
    ++r         // Step into range
    
For range of intervals

    r->begin()  // start of interval
    r->end()    // end of the interval    

Example:

// r1, r2 represent ranges for ordered lists of intervals.  Write the intersection of the
// two interval sets to out
template <typename Range1, typename Range2, typename Out>
void Intersect(Range1 r1, Range2 r2, Out& out)
{
    if (!r1 || !r2) return;  // Intersection is empty
    for(;;)
    {
        if (r1->end() <= r2->begin())
        {
            // r1 before r2
            ++r1;
            if (!r1) return;
        }
        else if (r2->end() <= r1->begin())
        {
            // r2 before r1
            ++r2;
            if (!r2) return;
        }
        else
        {
            // Intervals w1 and w2 intersect.  Write their nonempty intersection
            out << Intersect(*r1,*r2);

            // Step r1 or r2 depending on which interval is lagging behind
            if (r1->end() < r2->end()) { ++r1; if (!r1) return; }
            else                       { ++r2; if (!r2) return; }
        }
    }
}

Given interval h and iterators [w1,w2) we would like to *generate* the iterator that allows
us to step through h \ [w1,w2).   Is this possible?  Actually it seems better to be passed
an output iterator which we can use to write the output.
*/

namespace ceda
{

///////////////////////////////////////////////////////////////////////////////////////////////////
// Defines a range in terms of a pair of iterators i1,i2.  

template <typename It>
class RangeFromIterators
{
public:
    typedef typename std::iterator_traits<It>::value_type value_type;

    RangeFromIterators(It i1, It i2) : m_i1(i1), m_i2(i2) {}

    explicit operator bool() const { return m_i1 != m_i2; }

    ssize_t size() const { return m_i2 - m_i1; }
    bool empty() const { return m_i2 == m_i1; }

    value_type operator[](ssize_t i) const { return m_i1[i]; }

    const value_type& operator*() const { return *m_i1; }
    const value_type* operator->() const { return &*m_i1; }

    typedef It const_iterator;
    const_iterator begin() const { return m_i1; }
    const_iterator end() const { return m_i2; }

    void setbegin(It i1) { m_i1 = i1; }
    void setend(It i2) { m_i2 = i2; }

    RangeFromIterators& operator+=(ssize_t i) { m_i1 += i; cxAssert(m_i1 <= m_i2); return *this; }
    RangeFromIterators& operator-=(ssize_t i) { m_i1 -= i; return *this; }

    RangeFromIterators& operator++() { cxAssert(m_i1 < m_i2); ++m_i1; return *this; }
    const RangeFromIterators operator++(int) { RangeFromIterators s = *this; ++(*this); return s; }
    RangeFromIterators& operator--() { --m_i1; return *this; }
    const RangeFromIterators operator--(int) { RangeFromIterators s = *this; --(*this); return s; }

private:
    It m_i1, m_i2;
};

template <typename It>
RangeFromIterators<It> MakeRangeFromIterators(It i1, It i2)
{
    return RangeFromIterators<It>(i1,i2);
}

template <typename T>
RangeFromIterators<typename T::const_iterator> MakeRangeFromIterators(const T& x)
{
    return RangeFromIterators<typename T::const_iterator>(x.begin(),x.end());
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// Defines a range in terms of a pair of iterators i1,i2.  

template <typename It>
class RangeFromBiDirectionalIterators
{
public:
    typedef typename std::iterator_traits<It>::value_type value_type;

    RangeFromBiDirectionalIterators(It i1, It i2) : m_i1(i1), m_i2(i2) {}

    explicit operator bool() const { return m_i1 != m_i2; }

    ssize_t size() const { return m_i2 - m_i1; }
    bool empty() const { return m_i2 == m_i1; }

    value_type operator[](ssize_t i) const { return m_i1[i]; }

    const value_type& operator*() const { return *m_i1; }
    const value_type* operator->() const { return &*m_i1; }

    typedef It const_iterator;
    const_iterator begin() const { return m_i1; }
    const_iterator end() const { return m_i2; }

    void setbegin(It i1) { m_i1 = i1; }
    void setend(It i2) { m_i2 = i2; }

    RangeFromBiDirectionalIterators& operator++() { ++m_i1; return *this; }
    const RangeFromBiDirectionalIterators operator++(int) { RangeFromBiDirectionalIterators s = *this; ++(*this); return s; }
    RangeFromBiDirectionalIterators& operator--() { --m_i1; return *this; }
    const RangeFromBiDirectionalIterators operator--(int) { RangeFromBiDirectionalIterators s = *this; --(*this); return s; }
    
    It GetIt1() { return m_i1; }

private:
    It m_i1, m_i2;
};

template <typename It>
RangeFromBiDirectionalIterators<It> MakeRangeFromBiDirectionalIterators(It i1, It i2)
{
    return RangeFromBiDirectionalIterators<It>(i1,i2);
}

template <typename T>
RangeFromBiDirectionalIterators<typename T::const_iterator> MakeRangeFromBiDirectionalIterators(const T& x)
{
    return RangeFromBiDirectionalIterators<typename T::const_iterator>(x.begin(),x.end());
}

/*
template <typename T>
RangeFromBiDirectionalIterators<typename T::iterator> MakeRangeFromBiDirectionalIterators(T& x)
{
    return RangeFromBiDirectionalIterators<typename T::iterator>(x.begin(),x.end());
}
*/

///////////////////////////////////////////////////////////////////////////////////////////////////
// Make xvector<const T*> look like a Range on type T

template <typename T>
class RangeFromVectorOfPointers
{
public:
    using const_iterator = typename xvector<const T*>::const_iterator;
    using value_type = T;

    RangeFromVectorOfPointers(const_iterator i1, const_iterator i2) : m_i1(i1), m_i2(i2) {}

    explicit operator bool() const { return m_i1 != m_i2; }

    ssize_t size() const { return m_i2 - m_i1; }
    bool empty() const { return m_i2 == m_i1; }

    const value_type& operator[](ssize_t i) const { return *m_i1[i]; }

    const value_type& operator*() const { return **m_i1; }
    const value_type* operator->() const { return &**m_i1; }

    const_iterator begin() const { return m_i1; }
    const_iterator end() const { return m_i2; }

    void setbegin(const_iterator i1) { m_i1 = i1; }
    void setend(const_iterator i2) { m_i2 = i2; }

    RangeFromVectorOfPointers& operator++() { ++m_i1; return *this; }
    const RangeFromVectorOfPointers operator++(int) { RangeFromVectorOfPointers s = *this; ++(*this); return s; }
    RangeFromVectorOfPointers& operator--() { --m_i1; return *this; }
    const RangeFromVectorOfPointers operator--(int) { RangeFromVectorOfPointers s = *this; --(*this); return s; }

private:
    const_iterator m_i1, m_i2;
};

template <typename T>
RangeFromVectorOfPointers<T> MakeRangeFromVectorOfPointers(const xvector<const T*>& x)
{
    return RangeFromVectorOfPointers<T>(x.begin(),x.end());
}

} // namespace ceda

#endif // include guard