Array.h

Go to the documentation of this file.

// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
// SPDX-FileCopyrightText: 2024 Jorrit Rouwe
// SPDX-License-Identifier: MIT
 
#pragma once
 
#include <Jolt/Core/STLAllocator.h>
#include <Jolt/Core/HashCombine.h>
 
JPH_NAMESPACE_BEGIN
 
template <class T, class Allocator = STLAllocator<T>>
class [[nodiscard]] Array : private Allocator
{
public:
    using value_type = T;
    using allocator_type = Allocator;
    using size_type = size_t;
    using difference_type = typename Allocator::difference_type;
    using pointer = T *;
    using const_pointer = const T *;
    using reference = T &;
    using const_reference = const T &;
 
    using const_iterator = const T *;
    using iterator = T *;
 
    class rev_it
    {
    public:
                            rev_it() = default;
        explicit            rev_it(T *inValue)              : mValue(inValue) { }
 
                            rev_it(const rev_it &) = default;
        rev_it &            operator = (const rev_it &) = default;
 
        bool                operator == (const rev_it &inRHS) const { return mValue == inRHS.mValue; }
        bool                operator != (const rev_it &inRHS) const { return mValue != inRHS.mValue; }
 
        rev_it &            operator ++ ()                  { --mValue; return *this; }
        rev_it              operator ++ (int)               { return rev_it(mValue--); }
        rev_it &            operator -- ()                  { ++mValue; return *this; }
        rev_it              operator -- (int)               { return rev_it(mValue++); }
 
        rev_it              operator + (int inValue) const  { return rev_it(mValue - inValue); }
        rev_it              operator - (int inValue) const  { return rev_it(mValue + inValue); }
 
        rev_it &            operator += (int inValue)       { mValue -= inValue; return *this; }
        rev_it &            operator -= (int inValue)       { mValue += inValue; return *this; }
 
        T &                 operator * () const             { return *mValue; }
        T &                 operator -> () const            { return *mValue; }
 
    private:
        T *                 mValue;
    };
 
    class crev_it
    {
    public:
                            crev_it() = default;
        explicit            crev_it(const T *inValue)       : mValue(inValue) { }
 
                            crev_it(const crev_it &) = default;
        explicit            crev_it(const rev_it &inValue)  : mValue(inValue.mValue) { }
        crev_it &           operator = (const crev_it &) = default;
        crev_it &           operator = (const rev_it &inRHS) { mValue = inRHS.mValue; return *this; }
 
        bool                operator == (const crev_it &inRHS) const { return mValue == inRHS.mValue; }
        bool                operator != (const crev_it &inRHS) const { return mValue != inRHS.mValue; }
 
        crev_it &           operator ++ ()                  { --mValue; return *this; }
        crev_it             operator ++ (int)               { return crev_it(mValue--); }
        crev_it &           operator -- ()                  { ++mValue; return *this; }
        crev_it             operator -- (int)               { return crev_it(mValue++); }
 
        crev_it             operator + (int inValue)        { return crev_it(mValue - inValue); }
        crev_it             operator - (int inValue)        { return crev_it(mValue + inValue); }
 
        crev_it &           operator += (int inValue)       { mValue -= inValue; return *this; }
        crev_it &           operator -= (int inValue)       { mValue += inValue; return *this; }
 
        const T &           operator * () const             { return *mValue; }
        const T &           operator -> () const            { return *mValue; }
 
    private:
        const T *           mValue;
    };
 
    using reverse_iterator = rev_it;
    using const_reverse_iterator = crev_it;
 
private:
    inline void             move(pointer inDestination, pointer inSource, size_type inCount)
    {
        if constexpr (std::is_trivially_copyable<T>())
            memmove(inDestination, inSource, inCount * sizeof(T));
        else
        {
            if (inDestination < inSource)
            {
                for (T *destination_end = inDestination + inCount; inDestination < destination_end; ++inDestination, ++inSource)
                {
                    new (inDestination) T(std::move(*inSource));
                    inSource->~T();
                }
            }
            else
            {
                for (T *destination = inDestination + inCount - 1, *source = inSource + inCount - 1; destination >= inDestination; --destination, --source)
                {
                    new (destination) T(std::move(*source));
                    source->~T();
                }
            }
        }
    }
 
    inline void             reallocate(size_type inNewCapacity)
    {
        JPH_ASSERT(inNewCapacity > 0 && inNewCapacity >= mSize);
 
        pointer ptr;
        if constexpr (AllocatorHasReallocate<Allocator>::sValue)
        {
            // Reallocate data block
            ptr = get_allocator().reallocate(mElements, mCapacity, inNewCapacity);
        }
        else
        {
            // Copy data to a new location
            ptr = get_allocator().allocate(inNewCapacity);
            if (mElements != nullptr)
            {
                move(ptr, mElements, mSize);
                get_allocator().deallocate(mElements, mCapacity);
            }
        }
        mElements = ptr;
        mCapacity = inNewCapacity;
    }
 
    inline void             destruct(size_type inStart, size_type inEnd)
    {
        if constexpr (!std::is_trivially_destructible<T>())
            if (inStart < inEnd)
                for (T *element = mElements + inStart, *element_end = mElements + inEnd; element < element_end; ++element)
                    element->~T();
    }
 
public:
    inline void             reserve(size_type inNewSize)
    {
        if (mCapacity < inNewSize)
            reallocate(inNewSize);
    }
 
    inline void             resize(size_type inNewSize)
    {
        destruct(inNewSize, mSize);
        reserve(inNewSize);
 
        if constexpr (!std::is_trivially_constructible<T>())
            for (T *element = mElements + mSize, *element_end = mElements + inNewSize; element < element_end; ++element)
                new (element) T;
        mSize = inNewSize;
    }
 
    inline void             resize(size_type inNewSize, const T &inValue)
    {
        JPH_ASSERT(&inValue < mElements || &inValue >= mElements + mSize, "Can't pass an element from the array to resize");
 
        destruct(inNewSize, mSize);
        reserve(inNewSize);
 
        for (T *element = mElements + mSize, *element_end = mElements + inNewSize; element < element_end; ++element)
            new (element) T(inValue);
        mSize = inNewSize;
    }
 
    inline void             clear()
    {
        destruct(0, mSize);
        mSize = 0;
    }
 
private:
    inline void             grow(size_type inAmount = 1)
    {
        size_type min_size = mSize + inAmount;
        if (min_size > mCapacity)
        {
            size_type new_capacity = max(min_size, mCapacity * 2);
            reserve(new_capacity);
        }
    }
 
    inline void             deallocate()
    {
        get_allocator().deallocate(mElements, mCapacity);
        mElements = nullptr;
        mCapacity = 0;
    }
 
    inline void             destroy()
    {
        if (mElements != nullptr)
        {
            clear();
            deallocate();
        }
    }
 
public:
    template <class Iterator>
    inline void             assign(Iterator inBegin, Iterator inEnd)
    {
        clear();
        reserve(size_type(std::distance(inBegin, inEnd)));
 
        for (Iterator element = inBegin; element != inEnd; ++element)
            new (&mElements[mSize++]) T(*element);
    }
 
    inline void             assign(std::initializer_list<T> inList)
    {
        clear();
        reserve(size_type(inList.size()));
 
        for (const T &v : inList)
            new (&mElements[mSize++]) T(v);
    }
 
                            Array() = default;
 
    explicit inline         Array(const Allocator &inAllocator) :
        Allocator(inAllocator)
    {
    }
 
    explicit inline         Array(size_type inLength, const Allocator &inAllocator = { }) :
        Allocator(inAllocator)
    {
        resize(inLength);
    }
 
    inline                  Array(size_type inLength, const T &inValue, const Allocator &inAllocator = { }) :
        Allocator(inAllocator)
    {
        resize(inLength, inValue);
    }
 
    inline                  Array(std::initializer_list<T> inList, const Allocator &inAllocator = { }) :
        Allocator(inAllocator)
    {
        assign(inList);
    }
 
    inline                  Array(const_iterator inBegin, const_iterator inEnd, const Allocator &inAllocator = { }) :
        Allocator(inAllocator)
    {
        assign(inBegin, inEnd);
    }
 
    inline                  Array(const Array<T, Allocator> &inRHS) :
        Allocator(inRHS.get_allocator())
    {
        assign(inRHS.begin(), inRHS.end());
    }
 
    inline                  Array(Array<T, Allocator> &&inRHS) noexcept :
        Allocator(std::move(inRHS.get_allocator())),
        mSize(inRHS.mSize),
        mCapacity(inRHS.mCapacity),
        mElements(inRHS.mElements)
    {
        inRHS.mSize = 0;
        inRHS.mCapacity = 0;
        inRHS.mElements = nullptr;
    }
 
    inline                  ~Array()
    {
        destroy();
    }
 
    inline Allocator &      get_allocator()
    {
        return *this;
    }
 
    inline const Allocator &get_allocator() const
    {
        return *this;
    }
 
    inline void             push_back(const T &inValue)
    {
        JPH_ASSERT(&inValue < mElements || &inValue >= mElements + mSize, "Can't pass an element from the array to push_back");
 
        grow();
 
        T *element = mElements + mSize++;
        new (element) T(inValue);
    }
 
    inline void             push_back(T &&inValue)
    {
        grow();
 
        T *element = mElements + mSize++;
        new (element) T(std::move(inValue));
    }
 
    template <class... A>
    inline T &              emplace_back(A &&... inValue)
    {
        grow();
 
        T *element = mElements + mSize++;
        new (element) T(std::forward<A>(inValue)...);
        return *element;
    }
 
    inline void             pop_back()
    {
        JPH_ASSERT(mSize > 0);
        mElements[--mSize].~T();
    }
 
    inline bool             empty() const
    {
        return mSize == 0;
    }
 
    inline size_type        size() const
    {
        return mSize;
    }
 
    inline size_type        capacity() const
    {
        return mCapacity;
    }
 
    void                    shrink_to_fit()
    {
        if (mElements != nullptr)
        {
            if (mSize == 0)
                deallocate();
            else if (mCapacity > mSize)
                reallocate(mSize);
        }
    }
 
    void                    swap(Array<T, Allocator> &inRHS) noexcept
    {
        std::swap(get_allocator(), inRHS.get_allocator());
        std::swap(mSize, inRHS.mSize);
        std::swap(mCapacity, inRHS.mCapacity);
        std::swap(mElements, inRHS.mElements);
    }
 
    template <class Iterator>
    void                    insert(const_iterator inPos, Iterator inBegin, Iterator inEnd)
    {
        size_type num_elements = size_type(std::distance(inBegin, inEnd));
        if (num_elements > 0)
        {
            // After grow() inPos may be invalid
            size_type first_element = inPos - mElements;
 
            grow(num_elements);
 
            T *element_begin = mElements + first_element;
            T *element_end = element_begin + num_elements;
            move(element_end, element_begin, mSize - first_element);
 
            for (T *element = element_begin; element < element_end; ++element, ++inBegin)
                new (element) T(*inBegin);
 
            mSize += num_elements;
        }
    }
 
    void                    insert(const_iterator inPos, const T &inValue)
    {
        JPH_ASSERT(&inValue < mElements || &inValue >= mElements + mSize, "Can't pass an element from the array to insert");
 
        // After grow() inPos may be invalid
        size_type first_element = inPos - mElements;
 
        grow();
 
        T *element = mElements + first_element;
        move(element + 1, element, mSize - first_element);
 
        new (element) T(inValue);
        mSize++;
    }
 
    iterator                erase(const_iterator inIter)
    {
        size_type p = size_type(inIter - begin());
        JPH_ASSERT(p < mSize);
        mElements[p].~T();
        if (p + 1 < mSize)
            move(mElements + p, mElements + p + 1, mSize - p - 1);
        --mSize;
        return const_cast<iterator>(inIter);
    }
 
    iterator                erase(const_iterator inBegin, const_iterator inEnd)
    {
        size_type p = size_type(inBegin - begin());
        size_type n = size_type(inEnd - inBegin);
        JPH_ASSERT(inEnd <= end());
        destruct(p, p + n);
        if (p + n < mSize)
            move(mElements + p, mElements + p + n, mSize - p - n);
        mSize -= n;
        return const_cast<iterator>(inBegin);
    }
 
    inline const_iterator   begin() const
    {
        return mElements;
    }
 
    inline const_iterator   end() const
    {
        return mElements + mSize;
    }
 
    inline crev_it          rbegin() const
    {
        return crev_it(mElements + mSize - 1);
    }
 
    inline crev_it          rend() const
    {
        return crev_it(mElements - 1);
    }
 
    inline const_iterator   cbegin() const
    {
        return begin();
    }
 
    inline const_iterator   cend() const
    {
        return end();
    }
 
    inline crev_it          crbegin() const
    {
        return rbegin();
    }
 
    inline crev_it          crend() const
    {
        return rend();
    }
 
    inline iterator         begin()
    {
        return mElements;
    }
 
    inline iterator         end()
    {
        return mElements + mSize;
    }
 
    inline rev_it           rbegin()
    {
        return rev_it(mElements + mSize - 1);
    }
 
    inline rev_it           rend()
    {
        return rev_it(mElements - 1);
    }
 
    inline const T *        data() const
    {
        return mElements;
    }
 
    inline T *              data()
    {
        return mElements;
    }
 
    inline T &              operator [] (size_type inIdx)
    {
        JPH_ASSERT(inIdx < mSize);
        return mElements[inIdx];
    }
 
    inline const T &        operator [] (size_type inIdx) const
    {
        JPH_ASSERT(inIdx < mSize);
        return mElements[inIdx];
    }
 
    inline T &              at(size_type inIdx)
    {
        JPH_ASSERT(inIdx < mSize);
        return mElements[inIdx];
    }
 
    inline const T &        at(size_type inIdx) const
    {
        JPH_ASSERT(inIdx < mSize);
        return mElements[inIdx];
    }
 
    inline const T &        front() const
    {
        JPH_ASSERT(mSize > 0);
        return mElements[0];
    }
 
    inline T &              front()
    {
        JPH_ASSERT(mSize > 0);
        return mElements[0];
    }
 
    inline const T &        back() const
    {
        JPH_ASSERT(mSize > 0);
        return mElements[mSize - 1];
    }
 
    inline T &              back()
    {
        JPH_ASSERT(mSize > 0);
        return mElements[mSize - 1];
    }
 
    Array<T, Allocator> &   operator = (const Array<T, Allocator> &inRHS)
    {
        if (static_cast<const void *>(this) != static_cast<const void *>(&inRHS))
            assign(inRHS.begin(), inRHS.end());
 
        return *this;
    }
 
    Array<T, Allocator> &   operator = (Array<T, Allocator> &&inRHS) noexcept
    {
        if (static_cast<const void *>(this) != static_cast<const void *>(&inRHS))
        {
            destroy();
 
            get_allocator() = std::move(inRHS.get_allocator());
 
            mSize = inRHS.mSize;
            mCapacity = inRHS.mCapacity;
            mElements = inRHS.mElements;
 
            inRHS.mSize = 0;
            inRHS.mCapacity = 0;
            inRHS.mElements = nullptr;
        }
 
        return *this;
    }
 
    Array<T, Allocator> &   operator = (std::initializer_list<T> inRHS)
    {
        assign(inRHS);
 
        return *this;
    }
 
    bool                    operator == (const Array<T, Allocator> &inRHS) const
    {
        if (mSize != inRHS.mSize)
            return false;
        for (size_type i = 0; i < mSize; ++i)
            if (!(mElements[i] == inRHS.mElements[i]))
                return false;
        return true;
    }
 
    bool                    operator != (const Array<T, Allocator> &inRHS) const
    {
        if (mSize != inRHS.mSize)
            return true;
        for (size_type i = 0; i < mSize; ++i)
            if (mElements[i] != inRHS.mElements[i])
                return true;
        return false;
    }
 
    uint64                  GetHash() const
    {
        // Hash length first
        uint64 ret = Hash<uint32> { } (uint32(size()));
 
        // Then hash elements
        for (const T *element = mElements, *element_end = mElements + mSize; element < element_end; ++element)
            HashCombine(ret, *element);
 
        return ret;
    }
 
private:
    size_type               mSize = 0;
    size_type               mCapacity = 0;
    T *                     mElements = nullptr;
};
 
JPH_NAMESPACE_END
 
JPH_SUPPRESS_WARNING_PUSH
JPH_CLANG_SUPPRESS_WARNING("-Wc++98-compat")
 
namespace std
{
    template <class T, class Allocator>
    struct hash<JPH::Array<T, Allocator>>
    {
        size_t operator () (const JPH::Array<T, Allocator> &inRHS) const
        {
            return std::size_t(inRHS.GetHash());
        }
    };
}
 
JPH_SUPPRESS_WARNING_POP