Array.h

Go to the documentation of this file.

#pragma once
 
 
#include "math/MathBasic.h"
#include "objects/containers/Allocators.h"
#include "objects/containers/ArrayView.h"
 
#ifdef SPH_GCC
#pragma GCC diagnostic ignored "-Wstringop-overflow"
#endif
 
NAMESPACE_SPH_BEGIN
 
template <typename T, typename TAllocator = Mallocator, typename TCounter = Size>
class CopyableArray;
 
template <typename TValue>
struct NumericLimits;
 
template <>
struct NumericLimits<uint64_t> {
    static constexpr uint64_t max() {
        return uint64_t(-1);
    }
};
 
template <>
struct NumericLimits<uint32_t> {
    static constexpr uint32_t max() {
        return uint32_t(-1);
    }
};
 
template <typename T, typename TAllocator = Mallocator, typename TCounter = Size>
class Array : private TAllocator, public Noncopyable {
private:
    using StorageType = typename WrapReferenceType<T>::Type;
    StorageType* data = nullptr;
    TCounter actSize = 0;
    TCounter maxSize = 0;
 
    static constexpr TCounter maxValue = NumericLimits<TCounter>::max();
 
public:
    using Type = T;
    using Counter = TCounter;
 
    Array() = default;
 
    explicit Array(const TCounter elementCnt, const TCounter allocatedSize = maxValue) {
        this->alloc(elementCnt, allocatedSize);
 
        // emplace elements
        if (!std::is_trivially_default_constructible<T>::value) {
            for (TCounter i = 0; i < actSize; ++i) {
                new (data + i) StorageType();
            }
        }
    }
 
    Array(std::initializer_list<StorageType> list) {
        actSize = list.size();
        maxSize = actSize;
        MemoryBlock block = TAllocator::allocate(maxSize * sizeof(StorageType), alignof(StorageType));
        SPH_ASSERT(block.ptr);
        data = (StorageType*)block.ptr;
        TCounter i = 0;
        for (auto& l : list) {
            new (data + i) StorageType(l);
            i++;
        }
    }
 
    Array(Array&& other) {
        std::swap(data, other.data);
        std::swap(maxSize, other.maxSize);
        std::swap(actSize, other.actSize);
    }
 
    ~Array() {
        // explicitly destroy all constructed elements
        if (!std::is_trivially_destructible<T>::value) {
            for (TCounter i = 0; i < actSize; ++i) {
                data[i].~StorageType();
            }
        }
        if (data) {
            MemoryBlock block(data, maxSize * sizeof(StorageType));
            TAllocator::deallocate(block);
            data = nullptr;
        }
    }
 
    Array& operator=(Array&& other) {
        std::swap(data, other.data);
        std::swap(maxSize, other.maxSize);
        std::swap(actSize, other.actSize);
        return *this;
    }
 
    Array& operator=(const CopyableArray<T, TAllocator, TCounter>& other) {
        const Array& rhs = other;
        this->resize(rhs.size());
        for (TCounter i = 0; i < rhs.size(); ++i) {
            data[i] = rhs[i];
        }
        return *this;
    }
 
    template <typename U, typename = std::enable_if_t<std::is_lvalue_reference<T>::value, U>>
    Array& operator=(Array<U>&& other) {
        SPH_ASSERT(this->size() == other.size());
        for (TCounter i = 0; i < other.size(); ++i) {
            (*this)[i] = std::forward<U>(other[i]);
        }
        return *this;
    }
 
    Array clone() const {
        Array newArray;
        newArray.reserve(actSize);
        for (const T& value : *this) {
            newArray.emplaceBack(value);
        }
        return newArray;
    }
 
    INLINE T& operator[](const TCounter idx) noexcept {
        SPH_ASSERT(unsigned(idx) < unsigned(actSize), idx, actSize);
        return data[idx];
    }
 
    INLINE const T& operator[](const TCounter idx) const noexcept {
        SPH_ASSERT(unsigned(idx) < unsigned(actSize), idx, actSize);
        return data[idx];
    }
 
    INLINE T& front() noexcept {
        SPH_ASSERT(actSize > 0);
        return data[0];
    }
 
    INLINE const T& front() const noexcept {
        SPH_ASSERT(actSize > 0);
        return data[0];
    }
 
    INLINE T& back() noexcept {
        SPH_ASSERT(actSize > 0);
        return data[actSize - 1];
    }
 
    INLINE const T& back() const noexcept {
        SPH_ASSERT(actSize > 0);
        return data[actSize - 1];
    }
 
    void fill(const T& t) {
        for (auto& v : *this) {
            v = t;
        }
    }
 
    INLINE TCounter size() const noexcept {
        return actSize;
    }
 
    INLINE TCounter capacity() const noexcept {
        return maxSize;
    }
 
    INLINE bool empty() const noexcept {
        return actSize == 0;
    }
 
    void resize(const TCounter newSize) {
        // check suspiciously high values
        SPH_ASSERT(newSize < (NumericLimits<TCounter>::max() >> 1));
        if (newSize <= maxSize) {
            // enough elements is already allocated
            if (newSize >= actSize) {
                // enlarging array, we need to construct some new elements
                if (!std::is_trivially_default_constructible<T>::value) {
                    for (TCounter i = actSize; i < newSize; ++i) {
                        new (data + i) StorageType();
                    }
                }
            } else {
                if (!std::is_trivially_destructible<T>::value) {
                    // shrinking array, we need to delete some elements
                    for (TCounter i = newSize; i < actSize; ++i) {
                        data[i].~StorageType();
                    }
                }
            }
        } else {
            // requested more elements than allocate, need to reallocated.
            // allocate twice the current number or the new size, whatever is higher, to avoid frequent
            // reallocation when pushing elements one by one
            const TCounter actNewSize = max(2 * maxSize, newSize);
            Array newArray(0, actNewSize);
            // copy all elements into the new array, using move constructor
            for (TCounter i = 0; i < actSize; ++i) {
                new (newArray.data + i) StorageType(std::move(data[i]));
            }
            // default-construct new elements
            if (!std::is_trivially_default_constructible<T>::value) {
                for (TCounter i = actSize; i < newSize; ++i) {
                    new (newArray.data + i) StorageType();
                }
            }
            // move the array into this
            *this = std::move(newArray);
        }
        actSize = newSize;
    }
 
    void resizeAndSet(const TCounter newSize, const T& value) {
        const TCounter currentSize = actSize;
        this->resize(newSize);
        for (TCounter i = currentSize; i < actSize; ++i) {
            (*this)[i] = value;
        }
    }
 
    void reserve(const TCounter newMaxSize) {
        SPH_ASSERT(newMaxSize < (NumericLimits<TCounter>::max() >> 1));
        if (newMaxSize > maxSize) {
            const TCounter actNewSize = max(2 * maxSize, newMaxSize);
            Array newArray;
            // don't use the Array(0, actNewSize) constructor to allow using emplaceBack for types without
            // default constructor
            newArray.alloc(0, actNewSize);
            // copy all elements into the new array, using move constructor
            for (TCounter i = 0; i < actSize; ++i) {
                new (newArray.data + i) StorageType(std::move(data[i]));
            }
            newArray.actSize = actSize;
            // move the array into this
            *this = std::move(newArray);
        }
    }
 
    void shrink() {
        Array newArray;
        newArray.pushAll(std::move(*this));
        *this = std::move(newArray);
    }
 
    template <typename U>
    INLINE void push(U&& u) {
        resize(actSize + 1);
        data[actSize - 1] = std::forward<U>(u);
    }
 
    template <typename TIter>
    void pushAll(const TIter first, const TIter last) {
        for (TIter iter = first; iter != last; ++iter) {
            push(*iter);
        }
    }
 
    void pushAll(const Array& other) {
        reserve(actSize + other.size());
        pushAll(other.cbegin(), other.cend());
    }
 
    void pushAll(Array&& other) {
        reserve(actSize + other.size());
        for (T& value : other) {
            push(std::move(value));
        }
    }
 
    template <typename... TArgs>
    StorageType& emplaceBack(TArgs&&... args) {
        reserve(actSize + 1);
        SPH_ASSERT(maxSize > actSize);
        StorageType* ptr = new (data + actSize) StorageType(std::forward<TArgs>(args)...);
        SPH_ASSERT(ptr);
        actSize++;
        return *ptr;
    }
 
    template <typename U>
    void insert(const TCounter position, U&& value) {
        SPH_ASSERT(position <= actSize);
        this->resize(actSize + 1);
        std::move_backward(this->begin() + position, this->end() - 1, this->end());
        data[position] = std::forward<U>(value);
    }
 
    template <typename TIterator>
    void insert(const TCounter position, const TIterator first, const TIterator last) {
        SPH_ASSERT(position <= actSize);
        if (SPH_UNLIKELY(first == last)) {
            // inserting an empty range
            return;
        }
        const Size count = std::distance(first, last);
        this->resize(actSize + count);
        std::move_backward(this->begin() + position, this->end() - count, this->end());
        Size i = position;
        for (TIterator iter = first; iter != last; ++iter) {
            data[i++] = *iter;
        }
    }
 
    INLINE T pop() {
        SPH_ASSERT(actSize > 0);
        T value = data[actSize - 1];
        resize(actSize - 1);
        return value;
    }
 
    void remove(const TCounter idx) {
        SPH_ASSERT(idx < actSize);
        for (TCounter i = idx; i < actSize - 1; ++i) {
            data[i] = std::move(data[i + 1]);
        }
        resize(actSize - 1);
    }
 
    void remove(const ArrayView<const TCounter> idxs) {
        Size shift = 0;
        if (SPH_UNLIKELY(idxs.empty())) {
            return;
        }
 
        // move all elements between indices
        for (Size k = 0; k < idxs.size() - 1; ++k) {
            SPH_ASSERT(idxs[k] < idxs[k + 1]);
            for (TCounter i = idxs[k]; i < idxs[k + 1] - 1; ++i) {
                data[i - shift] = std::move(data[i + 1]);
            }
            shift++;
        }
        // move all elements after last index
        for (TCounter i = idxs.back(); i < actSize - 1; ++i) {
            data[i - shift] = std::move(data[i + 1]);
        }
 
        resize(actSize - idxs.size());
    }
 
    template <typename TIter>
    void remove(TIter first, TIter last) {
        SPH_ASSERT(first <= last);
        if (SPH_UNLIKELY(first == last)) {
            return;
        }
        const Size count = last - first;
        SPH_ASSERT(Size(first - begin()) + count <= actSize);
 
        for (TIter iter = first; iter != end() - count; ++iter) {
            *iter = std::move(*(iter + count));
        }
        resize(actSize - count);
    }
 
    void clear() {
        if (!std::is_trivially_destructible<T>::value) {
            for (TCounter i = 0; i < actSize; ++i) {
                data[i].~StorageType();
            }
        }
        actSize = 0;
    }
 
    void swap(Array& other) {
        std::swap(data, other.data);
        std::swap(maxSize, other.maxSize);
        std::swap(actSize, other.actSize);
    }
 
    INLINE Iterator<StorageType> begin() noexcept {
        return Iterator<StorageType>(data, data, data + actSize);
    }
 
    INLINE Iterator<const StorageType> begin() const noexcept {
        return Iterator<const StorageType>(data, data, data + actSize);
    }
 
    INLINE Iterator<const StorageType> cbegin() const noexcept {
        return Iterator<const StorageType>(data, data, data + actSize);
    }
 
    INLINE Iterator<StorageType> end() noexcept {
        return Iterator<StorageType>(data + actSize, data, data + actSize);
    }
 
    INLINE Iterator<const StorageType> end() const noexcept {
        return Iterator<const StorageType>(data + actSize, data, data + actSize);
    }
 
    INLINE Iterator<const StorageType> cend() const noexcept {
        return Iterator<const StorageType>(data + actSize, data, data + actSize);
    }
 
    const TAllocator& allocator() const {
        return *this;
    }
 
    TAllocator& allocator() {
        return *this;
    }
 
    INLINE operator ArrayView<T, TCounter>() noexcept {
        return ArrayView<T, TCounter>(data, actSize);
    }
 
    INLINE operator ArrayView<const T, TCounter>() const noexcept {
        return ArrayView<const T, TCounter>(data, actSize);
    }
 
    ArrayView<T, TCounter> view() noexcept {
        return ArrayView<T, TCounter>(data, actSize);
    }
 
    ArrayView<const T, TCounter> view() const noexcept {
        return ArrayView<const T, TCounter>(data, actSize);
    }
 
    bool operator==(const Array& other) const noexcept {
        return view() == other.view();
    }
 
    bool operator!=(const Array& other) const noexcept {
        return view() != other.view();
    }
 
    template <typename TStream, typename = std::enable_if_t<HasStreamOperator<T, TStream>::value>>
    friend TStream& operator<<(TStream& stream, const Array& array) {
        for (const T& t : array) {
            stream << t << std::endl;
        }
        return stream;
    }
 
private:
    void alloc(const TCounter elementCnt, const TCounter allocatedSize) {
        actSize = elementCnt;
        maxSize = allocatedSize;
        if (allocatedSize == maxValue) {
            maxSize = actSize;
        }
        // allocate maxSize elements
        MemoryBlock block = TAllocator::allocate(maxSize * sizeof(StorageType), alignof(StorageType));
        SPH_ASSERT(block.ptr);
        data = (StorageType*)block.ptr;
    }
};
 
template <typename T, typename TAllocator, typename TCounter>
class CopyableArray {
private:
    const Array<T, TAllocator, TCounter>& array;
 
public:
    CopyableArray(const Array<T, TAllocator, TCounter>& array)
        : array(array) {}
 
    operator const Array<T, TAllocator, TCounter>&() const {
        return array;
    }
};
 
template <typename T, typename TAllocator, typename TCounter>
INLINE CopyableArray<T, TAllocator, TCounter> copyable(const Array<T, TAllocator, TCounter>& array) {
    return CopyableArray<T, TAllocator, TCounter>(array);
}
 
template <typename T0, typename... TArgs>
Array<std::decay_t<T0>> makeArray(T0&& t0, TArgs&&... rest) {
    return Array<std::decay_t<T0>>{ std::forward<T0>(t0), std::forward<TArgs>(rest)... };
}
 
template <typename T0, typename... TArgs>
Array<T0&> tieToArray(T0& t0, TArgs&... rest) {
    return Array<T0&>{ t0, rest... };
}
 
 
NAMESPACE_SPH_END
 
namespace std {
template <typename T, typename TCounter>
void swap(Sph::Array<T, TCounter>& ar1, Sph::Array<T, TCounter>& ar2) {
    ar1.swap(ar2);
}
} // namespace std