Vector.h

/*
  ==============================================================================
    DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 
    Copyright 2022- by sonible GmbH.
 
    This file is part of VCTR - Versatile Container Templates Reconceptualized.
 
    VCTR is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License version 3
    only, as published by the Free Software Foundation.
 
    VCTR is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License version 3 for more details.
 
    You should have received a copy of the GNU Lesser General Public License
    version 3 along with VCTR.  If not, see <https://www.gnu.org/licenses/>.
  ==============================================================================
*/
 
namespace vctr
{
 
// clang-format off
template <class ElementType>
struct DefaultVectorAllocator
{
    using DefaultVectorAllocatorType = std::allocator<ElementType>;
};
 
template <is::number ElementType>
struct DefaultVectorAllocator<ElementType>
{
    using DefaultVectorAllocatorType = AlignedAllocator<ElementType, Config::maxSIMDRegisterSize>;
};
// clang-format on
 
namespace detail
{
 
template <class Allocator>
struct UnderlyingAllocatorExtractor
{
    using Type = Allocator;
};
 
template <class ElementType>
struct UnderlyingAllocatorExtractor<DefaultVectorAllocator<ElementType>>
{
    using Type = typename DefaultVectorAllocator<ElementType>::DefaultVectorAllocatorType;
};
 
template <class T, template <class> class Allocator>
struct StdVector
{
    using Type = std::vector<T, typename UnderlyingAllocatorExtractor<Allocator<T>>::Type>;
};
 
template <template <class> class Allocator>
struct StdVector<bool, Allocator>
{
    using Type = VectorBoolWorkaround<typename UnderlyingAllocatorExtractor<Allocator<std::byte>>::Type>;
};
 
template <class T, template <class> class Allocator>
using StdVectorType = typename StdVector<T, Allocator>::Type;
 
} // namespace detail
 
template <is::nonConst ElementType, template <class> class Allocator = DefaultVectorAllocator>
class Vector : public VctrBase<ElementType, detail::StdVectorType<ElementType, Allocator>, std::dynamic_extent>
{
private:
    using StdVectorType = detail::StdVectorType<ElementType, Allocator>;
    using Vctr = VctrBase<ElementType, StdVectorType, std::dynamic_extent>;
 
    template <class OtherAllocator>
    static constexpr bool isDifferentAllocatorTypeWithSameValueType = (! std::is_same_v<typename detail::UnderlyingAllocatorExtractor<Allocator<ElementType>>::Type, OtherAllocator>) && std::is_same_v<ElementType, typename OtherAllocator::value_type>;
 
    using ConstIterator = typename StdVectorType::const_iterator;
 
public:
    //==============================================================================
    using value_type = typename Vctr::value_type;
 
    //==============================================================================
    // Constructors
    //==============================================================================
    constexpr Vector() = default;
 
    template <std::convertible_to<Allocator<ElementType>> Alloc>
    Vector (Alloc&& allocator) : Vctr (StdVectorType (allocator)) {}
 
    constexpr Vector (size_t size) : Vctr (StdVectorType (size)) {}
 
    constexpr Vector (size_t size, ElementType initialValue) : Vctr (StdVectorType (size, initialValue)) {}
 
    constexpr Vector (std::initializer_list<ElementType> il) : Vctr (StdVectorType (il)) {}
 
    template <is::suitableInitializerForElementType<ElementType> First, std::same_as<First>... Other>
    requires (sizeof...(Other) > 0) && (! std::convertible_to<First, size_t>)
    constexpr Vector (First&& first, Other&&... other)
    {
        reserve (1 + sizeof...(other));
        push_back (std::forward<First> (first));
        (push_back (std::forward<Other> (other)), ...);
    }
 
    constexpr Vector (const Vector& other) : Vctr (StdVectorType (other.storage)) {}
 
    constexpr Vector (Vector&& other) : Vctr (std::move (other.storage)) {}
 
    template <is::triviallyCopyableWithDataAndSize OtherContainer>
    requires (! std::same_as<Vector, OtherContainer>)
    constexpr Vector (const OtherContainer& other)
    {
        Vctr::copyFrom (other.data(), other.size());
    }
 
    template <is::iteratorCopyable OtherContainer>
    constexpr Vector (const OtherContainer& other) : Vector (other.begin(), other.end()) {}
 
    constexpr Vector (const ElementType* data, size_t size)
    {
        Vctr::copyFrom (data, size);
    }
 
    template <is::inputIteratorToConstructValuesOfType<ElementType> Iterator, std::sentinel_for<Iterator> Sentinel>
    constexpr Vector (Iterator first, Sentinel last) : Vctr (StdVectorType (first, last)) {}
 
    template <is::suitableInitializerFunctionForElementType<ElementType> Fn>
    constexpr Vector (size_t size, Fn&& initializerFunction)
    {
        reserve (size);
        for (size_t i = 0; i < size; ++i)
            push_back (initializerFunction (i));
    }
 
    template <is::expression Expression>
    constexpr Vector (Expression&& e)
    {
        resize (e.size());
        Vctr::assignExpressionTemplate (std::forward<Expression> (e));
    }
 
    //==============================================================================
    // Operators
    //==============================================================================
    template <has::sizeAndDataWithElementType<ElementType> Container>
    constexpr Vector& operator= (Container&& containerToCopyDataFrom)
    {
        if constexpr (has::begin<Container> &&
                      has::end<Container> &&
                      (! is::view<Container>) &&
                      (! std::is_reference_v<Container>))
        {
            if constexpr (std::same_as<Container, Vector>)
            {
                Vctr::storage = std::move (containerToCopyDataFrom.storage);
            }
            else if constexpr (std::same_as<Container, StdVectorType>)
            {
                Vctr::storage = std::move (containerToCopyDataFrom);
            }
            else
            {
                Vctr::storage.assign (std::make_move_iterator (containerToCopyDataFrom.begin()), std::make_move_iterator (containerToCopyDataFrom.end()));
            }
        }
        else
        {
            Vctr::copyFrom (containerToCopyDataFrom.data(), containerToCopyDataFrom.size());
        }
 
        return *this;
    }
 
    constexpr Vector& operator= (const Vector& other)
    {
        // Forwards to the generic operator above. This is needed since the compiler does not recognize
        // the generic implementation as a copy assignment operator.
        return *this = other.storage;
    }
 
    constexpr Vector& operator= (std::initializer_list<ElementType> elementsToAssign)
    {
        Vctr::storage.assign (std::move (elementsToAssign));
        return *this;
    }
 
    template <is::expression E>
    constexpr void operator= (const E& expression)
    {
        resize (expression.size());
        Vctr::assignExpressionTemplate (expression);
    }
 
    //==============================================================================
    // Accessing the underlying vector.
    //==============================================================================
    constexpr StdVectorType& getUnderlyingVector() { return Vctr::storage; }
 
    constexpr const StdVectorType& getUnderlyingVector() const { return Vctr::storage; }
 
    constexpr StdVectorType&& moveUnderlyingVector() && { return std::move (Vctr::storage); }
 
    constexpr operator StdVectorType&() { return Vctr::storage; }
 
    constexpr operator const StdVectorType&() const { return Vctr::storage; }
 
    constexpr operator StdVectorType() && { return std::move (Vctr::storage); }
 
    template <class OtherAllocator>
    requires isDifferentAllocatorTypeWithSameValueType<OtherAllocator>
    operator std::vector<ElementType, OtherAllocator>() const
    {
        return std::vector<ElementType, OtherAllocator> (Vctr::begin(), Vctr::end());
    }
 
    //==============================================================================
    // Resizing, initialization, and clearing
    //==============================================================================
    constexpr void resize (size_t i) { Vctr::storage.resize (i); }
 
    constexpr void reserve (size_t i) { Vctr::storage.reserve (i); }
 
    constexpr void shrink_to_fit() { Vctr::storage.shrink_to_fit(); }
 
    constexpr void init (size_t newSize, const value_type& value)
    {
        resize (newSize);
        Vctr::fill (value);
    }
 
    template <is::suitableInitializerFunctionForElementType<ElementType> Fn>
    constexpr void init (size_t newSize, Fn&& initializerFunction)
    {
        resize (newSize);
        for (size_t i = 0; i < newSize; ++i)
            Vctr::at (i) = initializerFunction (i);
    }
 
    constexpr void clear() noexcept { Vctr::storage.clear(); }
 
    //==============================================================================
    // Allocator
    //==============================================================================
    constexpr Allocator<ElementType> get_allocator() const noexcept { return Vctr::storage.get_allocator(); }
 
    //==============================================================================
    // Size and capacity
    //==============================================================================
    constexpr size_t capacity() const noexcept { return Vctr::storage.capacity(); }
 
    constexpr size_t max_size() const noexcept { return Vctr::storage.max_size(); }
 
    //==============================================================================
    // Erasing elements from the Vector
    //==============================================================================
    constexpr auto erase (ConstIterator elementToErase)
    {
        // Undefined behaviour if elementToErase does not refer to an element in this Vector
        VCTR_ASSERT (Vctr::contains (elementToErase));
        return Vctr::storage.erase (elementToErase);
    }
 
    constexpr auto erase (size_t idx)
    {
        return erase (Vctr::storage.begin() + idx);
    }
 
    constexpr auto erase (ConstIterator first, ConstIterator last)
    {
        // Undefined behaviour if the range between first and last does not refer to a range in this Vector
        VCTR_ASSERT (Vctr::contains (first));
        VCTR_ASSERT (Vctr::contains (last) || last == Vctr::end());
 
        return Vctr::storage.erase (first, last);
    }
 
    constexpr auto erase (size_t startIdx, size_t numElements)
    {
        auto it = Vctr::storage.begin() + startIdx;
        return erase (it, it + numElements);
    }
 
    template <std::equality_comparable_with<ElementType> T>
    constexpr auto eraseFirstOccurrenceOf (const T& value)
    {
        auto it = Vctr::find (value);
        return it != Vctr::end() ? erase (it) : it;
    }
 
    template <is::functionWithSignatureOrImplicitlyConvertible<bool (const ElementType&)> Fn>
    constexpr auto eraseFirstOccurrenceIf (Fn&& predicate)
    {
        auto it = Vctr::findIf (std::forward<Fn> (predicate));
        return it != Vctr::end() ? erase (it) : it;
    }
 
    template <std::equality_comparable_with<ElementType> T>
    constexpr bool eraseAllOccurrencesOf (const T& value)
    {
        auto beginOfElementsToRemove = std::remove (Vctr::begin(), Vctr::end(), value);
        if (beginOfElementsToRemove == Vctr::end())
            return false;
 
        erase (beginOfElementsToRemove, Vctr::end());
        return true;
    }
 
    template <is::functionWithSignatureOrImplicitlyConvertible<bool (const ElementType&)> Fn>
    constexpr bool eraseAllOccurrencesIf (Fn&& predicate)
    {
        auto beginOfElementsToRemove = std::remove_if (Vctr::begin(), Vctr::end(), std::forward<Fn> (predicate));
        if (beginOfElementsToRemove == Vctr::end())
            return false;
 
        erase (beginOfElementsToRemove, Vctr::end());
        return true;
    }
 
    //==============================================================================
    // Adding elements to the Vector
    //==============================================================================
    constexpr ElementType& push_back (ElementType&& newElement)
    {
        Vctr::storage.push_back (std::move (newElement));
        return Vctr::storage.back();
    }
 
    constexpr ElementType& push_back (const ElementType& newElement)
    {
        Vctr::storage.push_back (newElement);
        return Vctr::storage.back();
    }
 
    constexpr ElementType pop_back()
    {
        VCTR_ASSERT (! Vctr::empty());
        auto x = std::move (Vctr::storage.back());
        Vctr::storage.pop_back();
        return x;
    }
 
    template <class... Args>
    constexpr void emplace_back (Args&&... args) { Vctr::storage.emplace_back (std::forward<Args> (args)...); }
 
    constexpr void swap (Vector& other) noexcept { Vctr::storage.swap (other.storage); }
 
    template <is::anyVctr VctrToAppend>
    void append (VctrToAppend&& vctrToAppend, bool moveValuesFromSrc = false)
    {
        insert (Vctr::end(), std::forward<VctrToAppend> (vctrToAppend), moveValuesFromSrc);
    }
 
    auto insert (ConstIterator pos, const ElementType& value)
    {
        // Undefined behaviour if pos does not refer to an element in this Vector
        VCTR_ASSERT (pos == Vctr::end() || Vctr::contains (pos));
        return Vctr::storage.insert (pos, value);
    }
 
    auto insert (size_t idx, const ElementType& value) { return insert (Vctr::begin() + idx, value); }
 
    auto insert (ConstIterator pos, ElementType&& value)
    {
        // Undefined behaviour if pos does not refer to an element in this Vector
        VCTR_ASSERT (pos == Vctr::end() || Vctr::contains (pos));
        return Vctr::storage.insert (pos, std::move (value));
    }
 
    auto insert (size_t idx, ElementType&& value) { return insert (Vctr::begin() + idx, std::move (value)); }
 
    auto insert (ConstIterator pos, size_t numCopies, const ElementType& value)
    {
        // Undefined behaviour if pos does not refer to an element in this Vector
        VCTR_ASSERT (pos == Vctr::end() || Vctr::contains (pos));
        return Vctr::storage.insert (pos, numCopies, value);
    }
 
    auto insert (size_t idx, size_t numCopies, const ElementType& value) { return insert (Vctr::begin() + idx, numCopies, value); }
 
    template <is::inputIteratorToConstructValuesOfType<ElementType> InputIterator>
    auto insert (ConstIterator pos, InputIterator first, InputIterator last)
    {
        // Undefined behaviour if pos does not refer to an element in this Vector
        VCTR_ASSERT (pos == Vctr::end() || Vctr::contains (pos));
 
        if constexpr (is::contiguousIteratorWithValueTypeSameAs<ElementType, InputIterator>)
        {
            // The range between first and last must not be elements of this Vector
            VCTR_ASSERT (! Vctr::contains (first));
            VCTR_ASSERT (! Vctr::contains (last));
        }
 
        return Vctr::storage.insert (pos, first, last);
    }
 
    template <is::inputIteratorToConstructValuesOfType<ElementType> InputIterator>
    auto insert (size_t idx, InputIterator first, InputIterator last)
    {
        return insert (Vctr::begin() + idx, first, last);
    }
 
    auto insert (ConstIterator pos, std::initializer_list<ElementType> initList)
    {
        // Undefined behaviour if pos does not refer to an element in this Vector
        VCTR_ASSERT (pos == Vctr::end() || Vctr::contains (pos));
        return Vctr::storage.insert (pos, initList);
    }
 
    auto insert (size_t idx, std::initializer_list<ElementType> initList) { return insert (Vctr::begin() + idx, std::move (initList)); }
 
    template <is::anyVctr VctrToInsert>
    auto insert (ConstIterator pos, VctrToInsert&& vctrToInsert, bool moveValuesFromSrc = false)
    {
        // Undefined behaviour if pos does not refer to an element in this Vector
        VCTR_ASSERT (pos == Vctr::end() || Vctr::contains (pos));
 
        // If it is no view and no reference, the container passed in has no dependencies outside this scope,
        // so we can safely move its elements in every case
        if constexpr ((! is::view<VctrToInsert>) &&(! std::is_reference_v<VctrToInsert>) )
            moveValuesFromSrc = true;
 
        if (moveValuesFromSrc)
            return Vctr::storage.insert (pos, std::make_move_iterator (vctrToInsert.begin()), std::make_move_iterator (vctrToInsert.end()));
 
        return Vctr::storage.insert (pos, vctrToInsert.begin(), vctrToInsert.end());
    }
 
    template <is::anyVctr VctrToInsert>
    auto insert (size_t idx, VctrToInsert&& vctrToInsert, bool moveValuesFromSrc = false)
    {
        return insert (Vctr::begin() + idx, std::forward<VctrToInsert> (vctrToInsert), moveValuesFromSrc);
    }
};
 
template <class OwnedElementType>
class OwnedVector : public Vector<std::unique_ptr<OwnedElementType>>
{
private:
    using VectorType = Vector<std::unique_ptr<OwnedElementType>>;
 
public:
    OwnedVector() = default;
 
    OwnedVector (std::initializer_list<OwnedElementType*> elementsToOwn)
    {
        VectorType::reserve (elementsToOwn.size());
        for (auto* ptr : elementsToOwn)
            VectorType::emplace_back (ptr);
    }
 
    template <class... Args>
    OwnedVector (Args&&... args) : VectorType (std::forward<Args> (args)...) {}
 
    constexpr auto eraseOccurrenceOf (const OwnedElementType* address)
    {
        auto it = VectorType::findIf ([&] (auto& p) { return p.get() == address; });
        return it != VectorType::end() ? VectorType::erase (it) : it;
    }
};
 
//==============================================================================
// Deduction guides
//==============================================================================
 
template <is::triviallyCopyableWithDataAndSize OtherContainer>
Vector (const OtherContainer& other) -> Vector<ValueType<OtherContainer>>;
 
template <is::iteratorCopyable OtherContainer>
Vector (const OtherContainer& other) -> Vector<ValueType<OtherContainer>>;
 
template <std::input_iterator Iterator, std::sentinel_for<Iterator> Sentinel>
Vector (Iterator first, Sentinel last) -> Vector<std::iter_value_t<Iterator>>;
 
template <is::suitableInitializerFunction Fn>
Vector (size_t size, Fn&& initializerFunction) -> Vector<std::invoke_result_t<Fn, size_t>>;
 
template <is::expression Expression>
Vector (Expression&& e) -> Vector<ValueType<Expression>>;
 
template <is::uniquePtr FirstArg, is::uniquePtr... Args>
requires (are::same<FirstArg, Args...>)
OwnedVector (FirstArg&&, Args&&...) -> OwnedVector<typename FirstArg::element_type>;
 
} // namespace vctr