AbstractIndex.h

Go to the documentation of this file.

//
//      ██╗██████╗     ██╗     ██╗██████╗ ███████╗
//      ██║██╔══██╗    ██║     ██║██╔══██╗██╔════╝      ** JPLSpatial **
//      ██║██████╔╝    ██║     ██║██████╔╝███████╗
// ██   ██║██╔═══╝     ██║     ██║██╔══██╗╚════██║      https://github.com/Jaytheway/JPLSpatial
// ╚█████╔╝██║         ███████╗██║██████╔╝███████║
//  ╚════╝ ╚═╝         ╚══════╝╚═╝╚═════╝ ╚══════╝
//
//   Copyright Jaroslav Pevno, JPLSpatial is offered under the terms of the ISC license:
//
//   Permission to use, copy, modify, and/or distribute this software for any purpose with or
//   without fee is hereby granted, provided that the above copyright notice and this permission
//   notice appear in all copies. THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
//   WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
//   AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
//   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
//   WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
//   CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 
#pragma once
 
#include <bit>
#include <concepts>
#include <stdint.h>
 
namespace JPL
{
    namespace RingImpl
    {
        enum class EOperationMode
        {
            Modulo,         // wrap Ring using modulo % operator, ring can be any size
            Pow2BitManip,   // wrap Ring using bit manipulation, requires Ring size to be power of 2
        };
 
        enum class EWriteDirection
        {
            Forward,    // increment index on write
            Backward,   // decrement index on write
        };
 
        template<class T> concept COperationMode = std::same_as<T, EOperationMode>;
        template<class T> concept CWriteDirection = std::same_as<T, EWriteDirection>;
 
        template<COperationMode auto OperationMode>
        class AbstractRingWrap;
 
        template<CWriteDirection auto WriteDirection, COperationMode auto OperationMode>
        class AbstarctRingBase;
    }
 
    //==============================================================================
    template<uint32_t MaxWindow,
        RingImpl::CWriteDirection auto WriteDirection,
        RingImpl::COperationMode auto OperationMode>
    class AbstractRingIndex;
 
    //==============================================================================
    template<uint32_t MaxWindow> using RingIndexForwardFast = AbstractRingIndex<MaxWindow, RingImpl::EWriteDirection::Forward, RingImpl::EOperationMode::Pow2BitManip>;
    template<uint32_t MaxWindow> using RingIndexBackwardFast = AbstractRingIndex<MaxWindow, RingImpl::EWriteDirection::Backward, RingImpl::EOperationMode::Pow2BitManip>;
    
    template<uint32_t MaxWindow> using RingIndexForward = AbstractRingIndex<MaxWindow, RingImpl::EWriteDirection::Forward, RingImpl::EOperationMode::Modulo>;
    template<uint32_t MaxWindow> using RingIndexBackward = AbstractRingIndex<MaxWindow, RingImpl::EWriteDirection::Backward, RingImpl::EOperationMode::Modulo>;
 
    //==============================================================================
    template<uint32_t MaxWindow,
        RingImpl::CWriteDirection auto WriteDirection,
        RingImpl::COperationMode auto OperationMode>
    class AbstractRingIndex : private RingImpl::AbstarctRingBase<WriteDirection, OperationMode>
    {
    private:
        using Base = RingImpl::AbstarctRingBase<WriteDirection, OperationMode>;
 
    public:
        struct Index
        {
            uint32_t WriteIndex;
            uint32_t MirrorIndex;
        };
 
    public:
        explicit AbstractRingIndex(uint32_t minSize)
            : Base(minSize)
            , mIndex(0, Base::GetMirrorIndex(0, MaxWindow))
        {
        }
 
        AbstractRingIndex(const AbstractRingIndex&) = default;
        AbstractRingIndex& operator=(const AbstractRingIndex&) = default;
 
        [[nodiscard]] inline uint32_t GetTotalSize() const { return Base::mRing + MaxWindow; }
        [[nodiscard]] inline uint32_t GetRingSize() const { return Base::mRing; }
        [[nodiscard]] inline Index GetCurrent() const { return mIndex; }
        inline void Reset() { UpdateWriteIndex(0); }
 
        inline Index operator ++() requires(WriteDirection == RingImpl::EWriteDirection::Forward)
        {
            const uint32_t newWriteIndex = Base::IncrementIndex(mIndex.WriteIndex);
            UpdateWriteIndex(newWriteIndex);
            return mIndex;
        }
 
        inline Index operator ++(int) requires(WriteDirection == RingImpl::EWriteDirection::Forward)
        {
            const Index currentIndex = mIndex;
            const uint32_t newWriteIndex = Base::IncrementIndex(mIndex.WriteIndex);
            UpdateWriteIndex(newWriteIndex);
            return currentIndex;
        }
 
        inline Index operator --() requires(WriteDirection == RingImpl::EWriteDirection::Backward)
        {
            const uint32_t newWriteIndex = Base::DecrementIndex(mIndex.WriteIndex);
            UpdateWriteIndex(newWriteIndex);
            return mIndex;
        }
 
        inline Index operator --(int) requires(WriteDirection == RingImpl::EWriteDirection::Backward)
        {
            const Index currentIndex = mIndex;
            const uint32_t newWriteIndex = Base::DecrementIndex(mIndex.WriteIndex);
            UpdateWriteIndex(newWriteIndex);
            return currentIndex;
        }
 
        [[nodiscard]] inline uint32_t GetOffset(uint32_t offset) const
        {
            // start of contiguous `MaxWindow` window at an offset from the WriteIndex
            return Base::GetOffset(mIndex.WriteIndex, offset);
        }
 
    private:
        inline void UpdateWriteIndex(uint32_t newIndex)
        {
            mIndex.WriteIndex = newIndex;
            mIndex.MirrorIndex = Base::GetMirrorIndex(newIndex, MaxWindow);
        }
 
    private:
        Index mIndex;
    };
 
    //==============================================================================
    template<uint32_t MaxWindow,
        RingImpl::CWriteDirection auto WriteDirection,
        RingImpl::COperationMode auto OperationMode> requires(MaxWindow <= 1)
        class AbstractRingIndex<MaxWindow, WriteDirection, OperationMode> : private RingImpl::AbstarctRingBase<WriteDirection, OperationMode>
    {
    private:
        using Base = RingImpl::AbstarctRingBase<WriteDirection, OperationMode>;
 
    public:
        using Index = uint32_t;
 
    public:
        explicit AbstractRingIndex(uint32_t minSize)
            : Base(minSize)
            , mIndex(0)
        {
        }
 
        AbstractRingIndex(const AbstractRingIndex&) = default;
        AbstractRingIndex& operator=(const AbstractRingIndex&) = default;
 
        [[nodiscard]] inline uint32_t GetTotalSize() const { return Base::mRing; }
        [[nodiscard]] inline uint32_t GetRingSize() const { return Base::mRing; }
        [[nodiscard]] inline Index GetCurrent() const { return mIndex; }
        inline void Reset() { mIndex = { 0 }; }
 
        inline Index operator ++()
        {
            mIndex = Base::IncrementIndex(mIndex);
            return mIndex;
        }
 
        inline Index operator ++(int)
        {
            const Index currentIndex = mIndex;
            mIndex = Base::IncrementIndex(mIndex);
            return currentIndex;
        }
 
        inline Index operator --()
        {
            mIndex = Base::DecrementIndex(mIndex);
            return mIndex;
        }
 
        inline Index operator --(int)
        {
            const Index currentIndex = mIndex;
            mIndex = Base::DecrementIndex(mIndex);
            return currentIndex;
        }
 
        [[nodiscard]] inline uint32_t GetOffset(int32_t offset) const
        {
            return Base::GetOffset(mIndex, offset);
        }
 
    private:
        Index mIndex;
    };
} // namespace JPL
 
//==============================================================================
//
//   Code beyond this point is implementation detail...
//
//==============================================================================
namespace JPL
{
    namespace RingImpl
    {
        template<> class AbstractRingWrap<EOperationMode::Pow2BitManip>
        {
        protected:
            explicit AbstractRingWrap(uint32_t minSize) : mRing(std::bit_ceil(minSize)), mSizeMask(mRing - 1) {}
            
            AbstractRingWrap(const AbstractRingWrap&) = default;
            AbstractRingWrap& operator=(const AbstractRingWrap&) = default;
 
            inline uint32_t Wrap(uint32_t index) const { return (index & mSizeMask); }
 
        protected:
            uint32_t mRing;
            uint32_t mSizeMask;
        };
 
        template<> class AbstractRingWrap<EOperationMode::Modulo>
        {
        protected:
            explicit AbstractRingWrap(uint32_t minSize) : mRing(minSize) {}
            
            AbstractRingWrap(const AbstractRingWrap&) = default;
            AbstractRingWrap& operator=(const AbstractRingWrap&) = default;
 
            inline uint32_t Wrap(uint32_t index) const { return (index % mRing); }
 
        protected:
            uint32_t mRing;
        };
 
        template<CWriteDirection auto WriteDirection, COperationMode auto OperationMode>
        class AbstarctRingBase : protected AbstractRingWrap<OperationMode>
        {
        private:
            using WrapBase = AbstractRingWrap<OperationMode>;
 
        protected:
            explicit AbstarctRingBase(uint32_t minSize) : WrapBase(minSize) {}
 
            AbstarctRingBase(const AbstarctRingBase&) = default;
            AbstarctRingBase& operator=(const AbstarctRingBase&) = default;
 
            inline uint32_t IncrementIndex(uint32_t index) const requires(WriteDirection == EWriteDirection::Forward)
            {
                return WrapBase::Wrap(index + 1u);
            }
 
            inline uint32_t DecrementIndex(uint32_t index) const requires(WriteDirection == EWriteDirection::Backward)
            {
                return WrapBase::Wrap((int32_t(index) - 1));
            }
 
            inline uint32_t GetOffset(uint32_t index, uint32_t offset) const
            {
                if constexpr (WriteDirection == EWriteDirection::Forward)
                {
                    return WrapBase::Wrap(index + WrapBase::mRing - offset);
                }
                else
                {
                    return WrapBase::Wrap(index + WrapBase::mRing + offset);
                }
            }
 
            inline uint32_t GetMirrorIndex(uint32_t index, uint32_t maxWindow) const
            {
                // (branch version)
                //if (index < maxWindow) // mirror only if inside first 'maxWindow'
                //    mirrorIndex = return mRing + index;
 
                // (branch-less simple version)
                // mirrorIndex = (index < maxWindow) * mRing + index;
 
                // (branch-less clever version)
                // This logic works for both, power of 2 mRing and non-power of 2 mRing.
                const uint32_t mirrorOff = (int32_t(index - maxWindow) >> 31) & WrapBase::mRing; // 0 or mRing
                return (index + mirrorOff);
            }
        };
    } // namespace RingImpl
} // namespace JPL