utl/include/utl/container/ring_iterator.h

/*!
 * \file container/ring_iterator.h
 * \brief
 *      A ring/circular iterator.
 *
 * \copyright Copyright (C) 2021 Christos Choutouridis <christos@choutouridis.net>
 *
 * <dl class=\"section copyright\"><dt>License</dt><dd>
 * The MIT License (MIT)
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * </dd></dl>
 */

#ifndef utl_container_ring_iterator_h__
#define utl_container_ring_iterator_h__

#include <utl/core/impl.h>

#include <iterator>
#include <type_traits>
#include <atomic>

namespace utl {

template<typename Iter_t, size_t N, bool Atomic=false>
class ring_iterator {
    //! \name STL iterator traits "forwarding"
    //! @{
    protected:
        using traits_type = std::iterator_traits<Iter_t>;

    public:
        using iterator_type     = Iter_t;
        using iterator_category = typename traits_type::iterator_category;
        using value_type        = typename traits_type::value_type;
        using difference_type   = typename traits_type::difference_type;
        using reference         = typename traits_type::reference;
        using pointer           = typename traits_type::pointer;
    //! @}


    //! \name Constructor / Destructor
    //! @{
    public:
        constexpr ring_iterator(const Iter_t base =nullptr) noexcept :
            base_(base), iter_(base) { }

        constexpr ring_iterator(const Iter_t base, size_t elem) noexcept :
            base_(base), iter_(base + elem) { }

        constexpr ring_iterator(const ring_iterator& it) noexcept :
            base_(it.base_), iter_(it.iter_) { }

        constexpr ring_iterator& operator= (const ring_iterator& it) noexcept {
            base_ = it.base_;
            iter_ = it.iter_;
            return *this;
        }
    //! @}

    //! \name Forward iterator requirements
    //! @{
    public:
        constexpr reference operator*() const noexcept {
            return *iter_;
        }

        constexpr pointer operator->() const noexcept {
            return iter_;
        }

        constexpr ring_iterator& operator++() noexcept {
            if (static_cast<size_t>(++iter_ - base_) >= N)
                iter_ = base_;
            return *this;
        }

        constexpr ring_iterator operator++(int) noexcept {
            ring_iterator it = *this;
            if (static_cast<size_t>(++iter_ - base_) >= N)
                iter_ = base_;
            return it;
        }
    //! @}

    //! \name Bidirectional iterator requirements
    //! @{
    public:
        constexpr ring_iterator& operator--() noexcept {
            if (--iter_ < base_)
                iter_ = base_ + N -1;
            return *this;
        }
        constexpr ring_iterator operator--(int) noexcept {
            ring_iterator it = *this;
            if (--iter_ < base_)
                iter_ = base_ + N -1;
            return it;
        }
    //! @}

    //! \name Random access iterator requirements
    //! @{
        constexpr reference operator[](difference_type n) const noexcept {
            difference_type k = iter_ - base_;          // ptrdiff from base_
            return (static_cast<size_t>(k + n) < N) ?
                base_[k + n] :      // on range
                base_[k + n - N];   // out of range, loop
        }
        constexpr ring_iterator& operator+=(difference_type n) noexcept {
            difference_type k = iter_ - base_;          // ptrdiff from base_
            iter_ += (static_cast<size_t>(k + n) < N) ?
                n :                 // on range
                n - N;              // out of range, loop
            return *this;
        }

        constexpr ring_iterator operator+(difference_type n) const noexcept {
            difference_type k = iter_ - base_;          // ptrdiff from base_
            return (static_cast<size_t>(k + n) < N) ?
                ring_iterator(base_, k + n) :           // on range
                ring_iterator(base_, k + n - N);        // out of range, loop
        }
        constexpr ring_iterator& operator-=(difference_type n) noexcept {
            difference_type k = iter_ - base_;          // ptrdiff from base_
            iter_ -= ((k - n) < 0)?
                n - N:                                  // out of range, loop
                n;                                      // on range
            return *this;
        }
        constexpr ring_iterator operator-(difference_type n) const noexcept {
            difference_type k = iter_ - base_;          // ptrdiff from base_
            return ((k - n) < 0) ?
                ring_iterator(base_, k - n + N) :       // out of range, loop
                ring_iterator(base_, k - n);            // on range
        }
    //! @}

    //! \name Data members and access
    //! @{
        constexpr const Iter_t& base() const noexcept {
            return base_;
        }
        constexpr const Iter_t& iter() const noexcept {
            return iter_;
        }
        constexpr size_t size() noexcept {
            return N;
        }

        constexpr operator Iter_t() noexcept { return iter_; }
        constexpr operator const Iter_t() const noexcept { return iter_; }

    protected:
        Iter_t base_;
        Iter_t iter_;
    //! @}
};

// Forward iterator requirements
template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator==(const ring_iterator<Iter_L, N>& lhs, const ring_iterator<Iter_R, N>& rhs)
noexcept {
    return lhs.iter() == rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator!=(const ring_iterator<Iter_L, N>& lhs, const ring_iterator<Iter_R, N>& rhs)
noexcept {
    return lhs.iter() != rhs.iter();
}

// Random access iterator requirements
template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator<(const ring_iterator<Iter_L, N>& lhs, const ring_iterator<Iter_R, N>& rhs)
noexcept {
    return lhs.iter() < rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator<=(const ring_iterator<Iter_L, N>& lhs, const ring_iterator<Iter_R, N>& rhs)
noexcept {
    return lhs.iter() <= rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator>(const ring_iterator<Iter_L, N>& lhs, const ring_iterator<Iter_R, N>& rhs)
noexcept {
    return lhs.iter() > rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator>=(const ring_iterator<Iter_L, N>& lhs, const ring_iterator<Iter_R, N>& rhs)
noexcept {
    return lhs.iter() >= rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline auto operator-(const ring_iterator<Iter_L, N>& lhs, const ring_iterator<Iter_R, N>& rhs)
noexcept
-> decltype(lhs.iter() - rhs.iter()) {
    auto diff = lhs.iter() - rhs.iter();
    return diff < 0 ?
            diff + N :  // loop
            diff;       // no loop
}

template<typename Iter, size_t N>
inline ring_iterator<Iter, N> operator+(std::ptrdiff_t lhs, const ring_iterator<Iter, N>& rhs)
noexcept {
    ring_iterator<Iter, N> it(rhs.iter());
    return it += lhs;
}






template<typename Iter_t, size_t N>
class ring_iterator<Iter_t, N, true> {
    //! \name STL iterator traits "forwarding"
    //! @{
    protected:
        using traits_type = std::iterator_traits<Iter_t>;

    public:
        using iterator_type     = Iter_t;
        using iterator_category = typename traits_type::iterator_category;
        using value_type        = typename traits_type::value_type;
        using difference_type   = typename traits_type::difference_type;
        using reference         = typename traits_type::reference;
        using pointer           = typename traits_type::pointer;
    //! @}


    //! \name Constructor / Destructor
    //! @{
    public:
        constexpr ring_iterator(const Iter_t base =nullptr) noexcept :
            base_(base), iter_(base) { }

        constexpr ring_iterator(const Iter_t base, size_t elem) noexcept :
            base_(base), iter_(base + elem) { }

        constexpr ring_iterator(const ring_iterator& it) noexcept :
            base_(it.base_) {
            iter_ =  it.iter_.load(std::memory_order_acquire);
        }

        constexpr ring_iterator& operator= (const ring_iterator& it) noexcept {
            base_ = it.base_;
            iter_ = it.iter_.load(std::memory_order_acquire);
            return *this;
        }
    //! @}

    //! \name Forward iterator requirements
    //! @{
    public:
        constexpr reference operator*() const noexcept {
            return *iter_.load(std::memory_order_acquire);
        }

        constexpr pointer operator->() const noexcept {
            return iter_.load(std::memory_order_acquire);
        }

        constexpr ring_iterator& operator++() noexcept {
            Iter_t itnew, it = iter_.load(std::memory_order_acquire);
            do {
                itnew = it;
                if (static_cast<size_t>(++itnew - base_) >= N)
                    itnew = base_;
            } while (!iter_.compare_exchange_weak(it, itnew, std::memory_order_acq_rel));
            return *this;
        }
        constexpr ring_iterator operator++(int) noexcept {
            ring_iterator ret = *this;
            Iter_t itnew, it = iter_.load(std::memory_order_acquire);
            do {
                itnew = it;
                if (static_cast<size_t>(++itnew - base_) >= N)
                    itnew = base_;
            } while (!iter_.compare_exchange_weak(it, itnew, std::memory_order_acq_rel));
            return ret;
        }
    //! @}

    //! \name Bidirectional iterator requirements
    //! @{
    public:
        constexpr ring_iterator& operator--() noexcept {
            Iter_t itnew, it = iter_.load(std::memory_order_acquire);
            do {
                itnew = it;
                if (--itnew < base_)
                    itnew = base_ + N -1;
            } while (!iter_.compare_exchange_weak(it, itnew, std::memory_order_acq_rel));
            return *this;
        }
        constexpr ring_iterator operator--(int) noexcept {
            ring_iterator ret = *this;
            Iter_t itnew, it = iter_.load(std::memory_order_acquire);
            do {
                itnew = it;
                if (--itnew < base_)
                    itnew = base_ + N -1;
            } while (!iter_.compare_exchange_weak(it, itnew, std::memory_order_acq_rel));
            return ret;
        }
    //! @}

    //! \name Random access iterator requirements
    //! @{
        constexpr reference operator[](difference_type n) const noexcept {
            difference_type k = iter_.load(std::memory_order_acquire) - base_; // ptrdiff from base_
            return (static_cast<size_t>(k + n) < N) ?
                base_[k + n] :                          // on range
                base_[k + n - N];                       // out of range, loop
        }
        constexpr ring_iterator& operator+=(difference_type n) noexcept {
            Iter_t itnew, it = iter_.load(std::memory_order_acquire);
            do {
                itnew = it;
                difference_type k = it - base_;         // ptrdiff from base_
                itnew += (static_cast<size_t>(k + n) < N) ?
                    n :                                 // on range
                    n - N;                              // out of range, loop
            } while (!iter_.compare_exchange_weak(it, itnew, std::memory_order_acquire));
            return *this;
        }
        constexpr ring_iterator operator+(difference_type n) const noexcept {
            difference_type k = iter_.load(std::memory_order_acquire) - base_; // ptrdiff from base_
            return (static_cast<size_t>(k + n) < N) ?
                ring_iterator(base_, k + n) :           // on range
                ring_iterator(base_, k + n - N);        // out of range, loop
        }
        constexpr ring_iterator& operator-=(difference_type n) noexcept {
            Iter_t itnew, it = iter_.load(std::memory_order_acquire);
            do {
                itnew = it;
                difference_type k = it - base_;         // ptrdiff from base_
                itnew -= ((k - n) < 0)?
                    n - N:                              // out of range, loop
                    n;                                  // on range
            } while (!iter_.compare_exchange_weak(it, itnew, std::memory_order_acquire));
            return *this;
        }
        constexpr ring_iterator operator-(difference_type n) const noexcept {
            difference_type k = iter_.load(std::memory_order_acquire) - base_; // ptrdiff from base_
            return ((k - n) < 0) ?
                ring_iterator(base_, k - n + N) :       // out of range, loop
                ring_iterator(base_, k - n);            // on range
        }
    //! @}

    //! \name Data members and access
    //! @{
        constexpr const Iter_t& base() const noexcept {
            return base_;
        }
        constexpr const Iter_t iter() const noexcept {
            return iter_.load(std::memory_order_acquire);
        }
        constexpr size_t size() noexcept {
            return N;
        }

        constexpr operator Iter_t() noexcept { return iter_.load(std::memory_order_acquire); }
        constexpr operator const Iter_t() const noexcept { return iter_.load(std::memory_order_acquire); }

    protected:
        Iter_t base_;
        std::atomic<Iter_t> iter_;
    //! @}
};

// Forward iterator requirements
template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator==(const ring_iterator<Iter_L, N, true>& lhs, const ring_iterator<Iter_R, N, true>& rhs)
noexcept {
    return lhs.iter() == rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator!=(const ring_iterator<Iter_L, N, true>& lhs, const ring_iterator<Iter_R, N, true>& rhs)
noexcept {
    return lhs.iter() != rhs.iter();
}

// Random access iterator requirements
template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator<(const ring_iterator<Iter_L, N, true>& lhs, const ring_iterator<Iter_R, N, true>& rhs)
noexcept {
    return lhs.iter() < rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator<=(const ring_iterator<Iter_L, N, true>& lhs, const ring_iterator<Iter_R, N, true>& rhs)
noexcept {
    return lhs.iter() <= rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator>(const ring_iterator<Iter_L, N, true>& lhs, const ring_iterator<Iter_R, N, true>& rhs)
noexcept {
    return lhs.iter() > rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline bool operator>=(const ring_iterator<Iter_L, N, true>& lhs, const ring_iterator<Iter_R, N, true>& rhs)
noexcept {
    return lhs.iter() >= rhs.iter();
}

template<typename Iter_L, typename Iter_R, size_t N>
inline auto operator-(const ring_iterator<Iter_L, N, true>& lhs, const ring_iterator<Iter_R, N, true>& rhs)
noexcept
-> decltype(lhs.iter() - rhs.iter()) {
    auto diff = lhs.iter() - rhs.iter();
    return diff < 0 ?
            diff + N :  // loop
            diff;       // no loop
}

template<typename Iter, size_t N>
inline ring_iterator<Iter, N, true> operator+(std::ptrdiff_t lhs, const ring_iterator<Iter, N, true>& rhs)
noexcept {
    ring_iterator<Iter, N, true> it(rhs.iter());
    return it += lhs;
}

} //namespace utl;

#endif /* utl_container_ring_iterator_h__ */