include/ftl/StaticVector.h

/*
 * Copyright 2020 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>

namespace android::ftl {

constexpr struct IteratorRangeTag {} IteratorRange;

// Fixed-capacity, statically allocated counterpart of std::vector. Akin to std::array, StaticVector
// allocates contiguous storage for N elements of type T at compile time, but stores at most (rather
// than exactly) N elements. Unlike std::array, its default constructor does not require T to have a
// default constructor, since elements are constructed in-place as the vector grows. Operations that
// insert an element (emplace_back, push_back, etc.) fail when the vector is full. The API otherwise
// adheres to standard containers, except the unstable_erase operation that does not preserve order,
// and the replace operation that destructively emplaces.
//
// StaticVector<T, 1> is analogous to an iterable std::optional, but StaticVector<T, 0> is an error.
//
// Example usage:
//
//     ftl::StaticVector<char, 3> vector;
//     assert(vector.empty());
//
//     vector = {'a', 'b'};
//     assert(vector.size() == 2u);
//
//     vector.push_back('c');
//     assert(vector.full());
//
//     assert(!vector.push_back('d'));
//     assert(vector.size() == 3u);
//
//     vector.unstable_erase(vector.begin());
//     assert(vector == (ftl::StaticVector{'c', 'b'}));
//
//     vector.pop_back();
//     assert(vector.back() == 'c');
//
//     const char array[] = "hi";
//     vector = ftl::StaticVector(array);
//     assert(vector == (ftl::StaticVector{'h', 'i', '\0'}));
//
template <typename T, size_t N>
class StaticVector final {
    static_assert(N > 0);

    // There is ambiguity when constructing from two iterator-like elements like pointers:
    // they could be an iterator range, or arguments for in-place construction. Assume the
    // latter unless they are input iterators and cannot be used to construct elements. If
    // the former is intended, the caller can pass an IteratorRangeTag to disambiguate.
    template <typename I, typename Traits = std::iterator_traits<I>>
    using IsInputIterator = std::conjunction<
            std::is_base_of<std::input_iterator_tag, typename Traits::iterator_category>,
            std::negation<std::is_constructible<T, I>>>;

public:
    using value_type = T;
    using size_type = size_t;
    using difference_type = ptrdiff_t;

    using pointer = value_type*;
    using reference = value_type&;
    using iterator = pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;

    using const_pointer = const value_type*;
    using const_reference = const value_type&;
    using const_iterator = const_pointer;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    // Creates an empty vector.
    StaticVector() = default;

    // Copies and moves a vector, respectively.
    StaticVector(const StaticVector& other)
          : StaticVector(IteratorRange, other.begin(), other.end()) {}
    StaticVector(StaticVector&& other) { swap<Empty>(other); }

    // Copies at most N elements from a smaller convertible vector.
    template <typename U, size_t M, typename = std::enable_if_t<M <= N>>
    StaticVector(const StaticVector<U, M>& other)
          : StaticVector(IteratorRange, other.begin(), other.end()) {}

    // Copies at most N elements from an array.
    template <typename U, size_t M>
    explicit StaticVector(U (&array)[M])
          : StaticVector(IteratorRange, std::begin(array), std::end(array)) {}

    // Copies at most N elements from the range [first, last).
    //
    // IteratorRangeTag disambiguates with initialization from two iterator-like elements.
    //
    template <typename Iterator, typename = std::enable_if_t<IsInputIterator<Iterator>{}>>
    StaticVector(Iterator first, Iterator last) : StaticVector(IteratorRange, first, last) {
        using V = typename std::iterator_traits<Iterator>::value_type;
        static_assert(std::is_constructible_v<value_type, V>, "Incompatible iterator range");
    }

    template <typename Iterator>
    StaticVector(IteratorRangeTag, Iterator first, Iterator last)
          : mSize(std::min(max_size(), static_cast<size_type>(std::distance(first, last)))) {
        std::uninitialized_copy(first, first + mSize, begin());
    }

    // Constructs at most N elements. The template arguments T and N are inferred using the
    // deduction guide defined below. Note that T is determined from the first element, and
    // subsequent elements must have convertible types:
    //
    //     ftl::StaticVector vector = {1, 2, 3};
    //     static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<int, 3>>);
    //
    //     const auto copy = "quince"s;
    //     auto move = "tart"s;
    //     ftl::StaticVector vector = {copy, std::move(move)};
    //
    //     static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 2>>);
    //
    template <typename E, typename... Es,
              typename = std::enable_if_t<std::is_constructible_v<value_type, E>>>
    StaticVector(E&& element, Es&&... elements)
          : StaticVector(std::index_sequence<0>{}, std::forward<E>(element),
                         std::forward<Es>(elements)...) {
        static_assert(sizeof...(elements) < N, "Too many elements");
    }

    // Constructs at most N elements. The template arguments T and N are inferred using the
    // deduction guide defined below. Element types must be convertible to the specified T:
    //
    //     ftl::StaticVector vector(std::in_place_type<std::string>, "red", "velvet", "cake");
    //     static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 3>>);
    //
    template <typename... Es>
    explicit StaticVector(std::in_place_type_t<T>, Es... elements)
          : StaticVector(std::forward<Es>(elements)...) {}

    ~StaticVector() { std::destroy(begin(), end()); }

    StaticVector& operator=(const StaticVector& other) {
        StaticVector copy(other);
        swap(copy);
        return *this;
    }

    StaticVector& operator=(StaticVector&& other) {
        std::destroy(begin(), end());
        mSize = 0;
        swap<Empty>(other);
        return *this;
    }

    template <typename = void>
    void swap(StaticVector&);

    static constexpr size_type max_size() { return N; }
    size_type size() const { return mSize; }

    bool empty() const { return size() == 0; }
    bool full() const { return size() == max_size(); }

    iterator begin() { return std::launder(reinterpret_cast<pointer>(mData)); }
    const_iterator begin() const { return cbegin(); }
    const_iterator cbegin() const { return mut().begin(); }

    iterator end() { return begin() + size(); }
    const_iterator end() const { return cend(); }
    const_iterator cend() const { return mut().end(); }

    reverse_iterator rbegin() { return std::make_reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { return crbegin(); }
    const_reverse_iterator crbegin() const { return mut().rbegin(); }

    reverse_iterator rend() { return std::make_reverse_iterator(begin()); }
    const_reverse_iterator rend() const { return crend(); }
    const_reverse_iterator crend() const { return mut().rend(); }

    iterator last() { return end() - 1; }
    const_iterator last() const { return mut().last(); }

    reference front() { return *begin(); }
    const_reference front() const { return mut().front(); }

    reference back() { return *last(); }
    const_reference back() const { return mut().back(); }

    reference operator[](size_type i) { return *(begin() + i); }
    const_reference operator[](size_type i) const { return mut()[i]; }

    // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
    // replacing at end() is erroneous.
    //
    // The element is emplaced via move constructor, so type T does not need to define copy/move
    // assignment, e.g. its data members may be const.
    //
    // The arguments may directly or indirectly refer to the element being replaced.
    //
    // Iterators to the replaced element point to its replacement, and others remain valid.
    //
    template <typename... Args>
    reference replace(const_iterator it, Args&&... args) {
        value_type element{std::forward<Args>(args)...};
        std::destroy_at(it);
        // This is only safe because exceptions are disabled.
        return *construct_at(it, std::move(element));
    }

    // Appends an element, and returns an iterator to it. If the vector is full, the element is not
    // inserted, and the end() iterator is returned.
    //
    // On success, the end() iterator is invalidated.
    //
    template <typename... Args>
    iterator emplace_back(Args&&... args) {
        if (full()) return end();
        const iterator it = construct_at(end(), std::forward<Args>(args)...);
        ++mSize;
        return it;
    }

    // Appends an element unless the vector is full, and returns whether the element was inserted.
    //
    // On success, the end() iterator is invalidated.
    //
    bool push_back(value_type v) {
        // Two statements for sequence point.
        const iterator it = emplace_back(std::move(v));
        return it != end();
    }

    // Removes the last element. The vector must not be empty, or the call is erroneous.
    //
    // The last() and end() iterators are invalidated.
    //
    void pop_back() { unstable_erase(last()); }

    // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
    // this moves the last element to the slot of the erased element.
    //
    // The last() and end() iterators, as well as those to the erased element, are invalidated.
    //
    void unstable_erase(const_iterator it) {
        std::destroy_at(it);
        if (it != last()) {
            // Move last element and destroy its source for destructor side effects. This is only
            // safe because exceptions are disabled.
            construct_at(it, std::move(back()));
            std::destroy_at(last());
        }
        --mSize;
    }

private:
    struct Empty {};

    StaticVector& mut() const { return *const_cast<StaticVector*>(this); }

    // Recursion for variadic constructor.
    template <size_t I, typename E, typename... Es>
    StaticVector(std::index_sequence<I>, E&& element, Es&&... elements)
          : StaticVector(std::index_sequence<I + 1>{}, std::forward<Es>(elements)...) {
        construct_at(begin() + I, std::forward<E>(element));
    }

    // Base case for variadic constructor.
    template <size_t I>
    explicit StaticVector(std::index_sequence<I>) : mSize(I) {}

    // TODO: Replace with std::construct_at in C++20.
    template <typename... Args>
    static pointer construct_at(const_iterator it, Args&&... args) {
        void* const ptr = const_cast<void*>(static_cast<const void*>(it));
        return new (ptr) value_type{std::forward<Args>(args)...};
    }

    size_type mSize = 0;
    std::aligned_storage_t<sizeof(value_type), alignof(value_type)> mData[N];
};

// Deduction guide for array constructor.
template <typename T, size_t N>
StaticVector(T (&)[N]) -> StaticVector<std::remove_cv_t<T>, N>;

// Deduction guide for variadic constructor.
template <typename T, typename... Us, typename V = std::decay_t<T>,
          typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
StaticVector(T&&, Us&&...) -> StaticVector<V, 1 + sizeof...(Us)>;

// Deduction guide for in-place constructor.
template <typename T, typename... Us>
StaticVector(std::in_place_type_t<T>, Us&&...) -> StaticVector<T, sizeof...(Us)>;

template <typename T, size_t N>
template <typename E>
void StaticVector<T, N>::swap(StaticVector& other) {
    auto [to, from] = std::make_pair(this, &other);
    if (from == this) return;

    // Assume this vector has fewer elements, so the excess of the other vector will be moved to it.
    auto [min, max] = std::make_pair(size(), other.size());

    // No elements to swap if moving into an empty vector.
    if constexpr (std::is_same_v<E, Empty>) {
        assert(min == 0);
    } else {
        if (min > max) {
            std::swap(from, to);
            std::swap(min, max);
        }

        // Swap elements [0, min).
        std::swap_ranges(begin(), begin() + min, other.begin());

        // No elements to move if sizes are equal.
        if (min == max) return;
    }

    // Move elements [min, max) and destroy their source for destructor side effects.
    const auto [first, last] = std::make_pair(from->begin() + min, from->begin() + max);
    std::uninitialized_move(first, last, to->begin() + min);
    std::destroy(first, last);

    std::swap(mSize, other.mSize);
}

template <typename T, size_t N>
inline void swap(StaticVector<T, N>& lhs, StaticVector<T, N>& rhs) {
    lhs.swap(rhs);
}

// TODO: Replace with operator<=> in C++20.
template <typename T, size_t N, size_t M>
inline bool operator==(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
    return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template <typename T, size_t N, size_t M>
inline bool operator<(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

template <typename T, size_t N, size_t M>
inline bool operator>(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
    return rhs < lhs;
}

template <typename T, size_t N, size_t M>
inline bool operator!=(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
    return !(lhs == rhs);
}

template <typename T, size_t N, size_t M>
inline bool operator>=(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
    return !(lhs < rhs);
}

template <typename T, size_t N, size_t M>
inline bool operator<=(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
    return !(rhs < lhs);
}

} // namespace android::ftl