ArrayVector.h

Go to the documentation of this file.

/*
 * ArrayVector.h
 *
 * Copyright (c) 2023 Dominic Clark
 *
 * This file is part of LMMS - https://lmms.io
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This program 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
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program (see COPYING); if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301 USA.
 *
 */
 
#ifndef LMMS_ARRAY_VECTOR_H
#define LMMS_ARRAY_VECTOR_H
 
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <memory>
#include <new>
#include <stdexcept>
#include <utility>
#include <type_traits>
 
namespace lmms {

template<typename T, std::size_t N>
class ArrayVector
{
public:
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using reference = T&;
        using const_reference = const T&;
        using pointer = T*;
        using const_pointer = const T*;
        using iterator = pointer;
        using const_iterator = const_pointer;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
        ArrayVector() = default;
 
        ArrayVector(const ArrayVector& other) noexcept(std::is_nothrow_copy_constructible_v<T>) :
                m_size{other.m_size}
        {
                std::uninitialized_copy(other.begin(), other.end(), begin());
        }
 
        ArrayVector(ArrayVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>) :
                m_size{other.m_size}
        {
                std::uninitialized_move(other.begin(), other.end(), begin());
                other.clear();
        }
 
        ArrayVector(size_type count, const T& value) noexcept(std::is_nothrow_copy_constructible_v<T>) :
                m_size{count}
        {
                assert(count <= N);
                std::uninitialized_fill_n(begin(), count, value);
        }
 
        explicit ArrayVector(size_type count) noexcept(std::is_nothrow_default_constructible_v<T>) :
                m_size{count}
        {
                assert(count <= N);
                std::uninitialized_value_construct_n(begin(), count);
        }
 
        template<std::input_iterator It>
        ArrayVector(It first, It last)
        {
                // Can't check the size first as the iterator may not be multipass
                const auto end = std::uninitialized_copy(first, last, begin());
                m_size = end - begin();
                assert(m_size <= N);
        }
 
        ArrayVector(std::initializer_list<T> il) noexcept(std::is_nothrow_copy_constructible_v<T>) :
                m_size{il.size()}
        {
                assert(il.size() <= N);
                std::uninitialized_copy(il.begin(), il.end(), begin());
        }
 
        ~ArrayVector() { std::destroy(begin(), end()); }
 
        ArrayVector& operator=(const ArrayVector& other)
                noexcept(std::is_nothrow_copy_assignable_v<T> && std::is_nothrow_copy_constructible_v<T>)
        {
                if (this != &other) {
                        const auto toAssign = std::min(other.size(), size());
                        const auto assignedFromEnd = other.begin() + toAssign;
                        const auto assignedToEnd = std::copy(other.begin(), other.begin() + toAssign, begin());
                        std::destroy(assignedToEnd, end());
                        std::uninitialized_copy(assignedFromEnd, other.end(), end());
                        m_size = other.size();
                }
                return *this;
        }
 
        ArrayVector& operator=(ArrayVector&& other)
                noexcept(std::is_nothrow_move_assignable_v<T> && std::is_nothrow_move_constructible_v<T>)
        {
                if (this != &other) {
                        const auto toAssign = std::min(other.size(), size());
                        const auto assignedFromEnd = other.begin() + toAssign;
                        const auto assignedToEnd = std::move(other.begin(), other.begin() + toAssign, begin());
                        std::destroy(assignedToEnd, end());
                        std::uninitialized_move(assignedFromEnd, other.end(), end());
                        m_size = other.size();
                        other.clear();
                }
                return *this;
        }
 
        ArrayVector& operator=(std::initializer_list<T> il)
                noexcept(std::is_nothrow_copy_assignable_v<T> && std::is_nothrow_copy_constructible_v<T>)
        {
                assert(il.size() <= N);
                const auto toAssign = std::min(il.size(), size());
                const auto assignedFromEnd = il.begin() + toAssign;
                const auto assignedToEnd = std::copy(il.begin(), assignedFromEnd, begin());
                std::destroy(assignedToEnd, end());
                std::uninitialized_copy(assignedFromEnd, il.end(), end());
                m_size = il.size();
                return *this;
        }
 
        void assign(size_type count, const T& value)
                noexcept(std::is_nothrow_copy_assignable_v<T> && std::is_nothrow_copy_constructible_v<T>)
        {
                assert(count <= N);
                const auto temp = value;
                const auto toAssign = std::min(count, size());
                const auto toConstruct = count - toAssign;
                const auto assignedToEnd = std::fill_n(begin(), toAssign, temp);
                std::destroy(assignedToEnd, end());
                std::uninitialized_fill_n(assignedToEnd, toConstruct, temp);
                m_size = count;
        }
 
        template<std::input_iterator It>
        void assign(It first, It last)
        {
                // Can't check the size first as the iterator may not be multipass
                auto pos = begin();
                for (; first != last && pos != end(); ++pos, ++first) {
                        *pos = *first;
                }
                std::destroy(pos, end());
                pos = std::uninitialized_copy(first, last, pos);
                m_size = pos - begin();
                assert(m_size <= N);
        }
 
        reference at(size_type index)
        {
                if (index >= m_size) { throw std::out_of_range{"index out of range"}; }
                return data()[index];
        }
 
        const_reference at(size_type index) const
        {
                if (index >= m_size) { throw std::out_of_range{"index out of range"}; }
                return data()[index];
        }
 
        reference operator[](size_type index) noexcept
        {
                assert(index < m_size);
                return data()[index];
        }
 
        const_reference operator[](size_type index) const noexcept
        {
                assert(index < m_size);
                return data()[index];
        }
 
        reference front() noexcept { return operator[](0); }
        const_reference front() const noexcept { return operator[](0); }
 
        reference back() noexcept { return operator[](m_size - 1); }
        const_reference back() const noexcept { return operator[](m_size - 1); }
 
        pointer data() noexcept { return *std::launder(reinterpret_cast<T(*)[N]>(m_data)); }
        const_pointer data() const noexcept { return *std::launder(reinterpret_cast<const T(*)[N]>(m_data)); }
 
        iterator begin() noexcept { return data(); }
        const_iterator begin() const noexcept { return data(); }
        const_iterator cbegin() const noexcept { return data(); }
 
        iterator end() noexcept { return data() + m_size; }
        const_iterator end() const noexcept { return data() + m_size; }
        const_iterator cend() const noexcept { return data() + m_size; }
 
        reverse_iterator rbegin() noexcept { return std::reverse_iterator{end()}; }
        const_reverse_iterator rbegin() const noexcept { return std::reverse_iterator{end()}; }
        const_reverse_iterator crbegin() const noexcept { return std::reverse_iterator{cend()}; }
 
        reverse_iterator rend() noexcept { return std::reverse_iterator{begin()}; }
        const_reverse_iterator rend() const noexcept { return std::reverse_iterator{begin()}; }
        const_reverse_iterator crend() const noexcept { return std::reverse_iterator{cbegin()}; }
 
        bool empty() const noexcept { return m_size == 0; }
        bool full() const noexcept { return m_size == N; }
        size_type size() const noexcept { return m_size; }
        size_type max_size() const noexcept { return N; }
        size_type capacity() const noexcept { return N; }
 
        void clear() noexcept
        {
                std::destroy(begin(), end());
                m_size = 0;
        }
 
        iterator insert(const_iterator pos, const T& value) { return emplace(pos, value); }
        iterator insert(const_iterator pos, T&& value) { return emplace(pos, std::move(value)); }
 
        iterator insert(const_iterator pos, size_type count, const T& value)
        {
                assert(m_size + count <= N);
                assert(cbegin() <= pos && pos <= cend());
                const auto mutPos = begin() + (pos - cbegin());
                const auto newEnd = std::uninitialized_fill_n(end(), count, value);
                std::rotate(mutPos, end(), newEnd);
                m_size += count;
                return mutPos;
        }
 
        template<std::input_iterator It>
        iterator insert(const_iterator pos, It first, It last)
        {
                // Can't check the size first as the iterator may not be multipass
                assert(cbegin() <= pos && pos <= cend());
                const auto mutPos = begin() + (pos - cbegin());
                const auto newEnd = std::uninitialized_copy(first, last, end());
                std::rotate(mutPos, end(), newEnd);
                m_size = newEnd - begin();
                assert(m_size <= N);
                return mutPos;
        }
 
        iterator insert(const_iterator pos, std::initializer_list<T> il) { return insert(pos, il.begin(), il.end()); }
 
        template<typename... Args>
        iterator emplace(const_iterator pos, Args&&... args)
        {
                assert(cbegin() <= pos && pos <= cend());
                const auto mutPos = begin() + (pos - cbegin());
                emplace_back(std::forward<Args>(args)...);
                std::rotate(mutPos, end() - 1, end());
                return mutPos;
        }
 
        iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
        iterator erase(const_iterator first, const_iterator last)
        {
                assert(cbegin() <= first && first <= last && last <= cend());
                const auto mutFirst = begin() + (first - cbegin());
                const auto mutLast = begin() + (last - cbegin());
                const auto newEnd = std::move(mutLast, end(), mutFirst);
                std::destroy(newEnd, end());
                m_size = newEnd - begin();
                return mutFirst;
        }
 
        void push_back(const T& value) { emplace_back(value); }
        void push_back(T&& value) { emplace_back(std::move(value)); }
 
        template<typename... Args>
        reference emplace_back(Args&&... args)
        {
                assert(!full());
                const auto result = std::construct_at(end(), std::forward<Args>(args)...);
                ++m_size;
                return *result;
        }
 
        void pop_back()
        {
                assert(!empty());
                --m_size;
                std::destroy_at(end());
        }
 
        void resize(size_type size)
        {
                if (size > N) { throw std::length_error{"size exceeds maximum size"}; }
                if (size < m_size) {
                        std::destroy(begin() + size, end());
                } else {
                        std::uninitialized_value_construct(end(), begin() + size);
                }
                m_size = size;
        }
 
        void resize(size_type size, const value_type& value)
        {
                if (size > N) { throw std::length_error{"size exceeds maximum size"}; }
                if (size < m_size) {
                        std::destroy(begin() + size, end());
                } else {
                        std::uninitialized_fill(end(), begin() + size, value);
                }
                m_size = size;
        }
 
        void swap(ArrayVector& other)
                noexcept(std::is_nothrow_swappable_v<T> && std::is_nothrow_move_constructible_v<T>)
        {
                using std::swap;
                swap(*this, other);
        }
 
        friend void swap(ArrayVector& a, ArrayVector& b)
                noexcept(std::is_nothrow_swappable_v<T> && std::is_nothrow_move_constructible_v<T>)
        {
                const auto toSwap = std::min(a.size(), b.size());
                const auto aSwapEnd = a.begin() + toSwap;
                const auto bSwapEnd = b.begin() + toSwap;
                std::swap_ranges(a.begin(), aSwapEnd, b.begin());
                std::uninitialized_move(aSwapEnd, a.end(), bSwapEnd);
                std::uninitialized_move(bSwapEnd, b.end(), aSwapEnd);
                std::destroy(aSwapEnd, a.end());
                std::destroy(bSwapEnd, b.end());
                std::swap(a.m_size, b.m_size);
        }
 
        friend constexpr auto operator<=>(const ArrayVector& l, const ArrayVector& r)
        {
                return std::lexicographical_compare_three_way(l.begin(), l.end(), r.begin(), r.end());
        }
 
        friend bool operator==(const ArrayVector& l, const ArrayVector& r)
        {
                return std::equal(l.begin(), l.end(), r.begin(), r.end());
        }
 
private:
        alignas(T) std::byte m_data[std::max(N * sizeof(T), std::size_t{1})]; // Intentionally a raw array
        size_type m_size = 0;
};
 
} // namespace lmms
 
#endif // LMMS_ARRAY_VECTOR_H