small_vector.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2022 deCODE Genetics
// Copyright (c) 2006-2020, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2020, Knut Reinert & MPI für molekulare Genetik
// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
// shipped with this file and also available at: https://github.com/biocpp/biocpp-core/blob/main/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <array>
#include <type_traits>
 
#if __has_include(<cereal/types/array.hpp>)
#    include <cereal/types/array.hpp>
#endif
 
#include <bio/meta/detail/int_types.hpp>
#include <bio/meta/type_traits/template_inspection.hpp>
#include <bio/ranges/views/repeat_n.hpp>
 
namespace bio::ranges
{
 
template <typename value_type_, size_t capacity_>
class small_vector
{
private:
    static constexpr bool is_noexcept = std::is_nothrow_copy_constructible_v<value_type_>;
 
public:
    using value_type      = value_type_;                                
    using reference       = value_type &;                               
    using const_reference = value_type const &;                         
    using iterator        = value_type *;                               
    using const_iterator  = value_type const *;                         
    using difference_type = ptrdiff_t;                                  
    using size_type       = meta::detail::min_viable_uint_t<capacity_>; 
 
 
    // this signals to range-v3 that something is a container :|
    using allocator_type = void;
 
    constexpr small_vector() noexcept                                 = default; 
    constexpr small_vector(small_vector const &) noexcept             = default; 
    constexpr small_vector(small_vector &&) noexcept                  = default; 
    constexpr small_vector & operator=(small_vector const &) noexcept = default; 
    constexpr small_vector & operator=(small_vector &&) noexcept      = default; 
    ~small_vector() noexcept                                          = default; 
 
    explicit constexpr small_vector(std::array<value_type, capacity_> const & array) noexcept(is_noexcept) :
      data_{array}, sz{capacity_}
    {}
 
    template <size_t capacity2>
    explicit constexpr small_vector(std::array<value_type, capacity2> const & array) noexcept(is_noexcept) :
      sz{capacity2}
    {
        static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
        std::ranges::copy(array, data_.begin());
    }
 
    template <size_t capacity2>
    explicit constexpr small_vector(value_type const (&array)[capacity2]) noexcept(is_noexcept) : sz{capacity2}
    {
        static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
        std::ranges::copy(array, data_.begin());
    }
 
    template <typename... other_value_type>
        requires(std::same_as<value_type, other_value_type> && ...)
    constexpr small_vector(other_value_type... args) noexcept(is_noexcept) :
      data_{args...}, sz{sizeof...(other_value_type)}
    {
        static_assert(sizeof...(other_value_type) <= capacity_, "Value list must not exceed the capacity.");
    }
 
    template <std::forward_iterator begin_it_type, typename end_it_type>
        requires(std::sentinel_for<end_it_type, begin_it_type> &&
                 std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>)
    constexpr small_vector(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept) : small_vector{}
    {
        assign(begin_it, end_it);
    }
 
    template <meta::different_from<small_vector> other_range_t>
        requires(std::ranges::input_range<other_range_t>)
    explicit constexpr small_vector(other_range_t && range) noexcept(is_noexcept) :
      small_vector{std::ranges::begin(range), std::ranges::end(range)}
    {}
 
    constexpr small_vector(size_type n, value_type value) noexcept(is_noexcept) : small_vector{} { assign(n, value); }
 
    constexpr small_vector & operator=(std::initializer_list<value_type> ilist) noexcept(is_noexcept)
    {
        assign(std::ranges::begin(ilist), std::ranges::end(ilist));
        return *this;
    }
 
    constexpr void assign(std::initializer_list<value_type> ilist) noexcept(is_noexcept)
    {
        assign(std::ranges::begin(ilist), std::ranges::end(ilist));
    }
 
    constexpr void assign(size_type const count, value_type const value) noexcept(is_noexcept)
    {
        clear();
        auto tmp = views::repeat_n(value, count);
        assign(std::ranges::begin(tmp), std::ranges::end(tmp));
    }
 
    template <std::ranges::input_range other_range_t>
        requires std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
    constexpr void assign(other_range_t && range) noexcept(is_noexcept)
    {
        assign(std::ranges::begin(range), std::ranges::end(range));
    }
 
    template <std::forward_iterator begin_it_type, typename end_it_type>
        requires(std::sentinel_for<end_it_type, begin_it_type> &&
                 std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>)
    constexpr void assign(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
    {
        clear();
        insert(cbegin(), begin_it, end_it);
    }
 
    constexpr iterator begin() noexcept { return &data_[0]; }
 
    constexpr const_iterator begin() const noexcept { return &data_[0]; }
 
    constexpr const_iterator cbegin() const noexcept { return &data_[0]; }
 
    constexpr iterator end() noexcept { return &data_[sz]; }
 
    constexpr const_iterator end() const noexcept { return &data_[sz]; }
 
    constexpr const_iterator cend() const noexcept { return &data_[sz]; }
 
    reference at(size_type const i)
    {
        if (i >= size()) // [[unlikely]]
        {
            throw std::out_of_range{"Trying to access element behind the last in small_vector."};
        }
        return (*this)[i];
    }
 
    const_reference at(size_type const i) const
    {
        if (i >= size()) // [[unlikely]]
        {
            throw std::out_of_range{"Trying to access element behind the last in small_vector."};
        }
        return (*this)[i];
    }
 
    constexpr reference operator[](size_type const i) noexcept
    {
        assert(i < size());
        return data_[i];
    }
 
    constexpr const_reference operator[](size_type const i) const noexcept
    {
        assert(i < size());
        return data_[i];
    }
 
    constexpr reference front() noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    constexpr const_reference front() const noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    constexpr reference back() noexcept
    {
        assert(size() > 0);
        return (*this)[size() - 1];
    }
 
    constexpr const_reference back() const noexcept
    {
        assert(size() > 0);
        return (*this)[size() - 1];
    }
 
    constexpr value_type * data() noexcept { return data_.data(); }
 
    constexpr value_type const * data() const noexcept { return data_.data(); }
 
    constexpr bool empty() const noexcept { return size() == 0; }
 
    constexpr size_type size() const noexcept { return sz; }
 
    constexpr size_type max_size() const noexcept { return capacity_; }
 
    constexpr size_type capacity() const noexcept { return capacity_; }
 
    constexpr void reserve(size_type) const noexcept
    {
        // no-op
    }
 
    constexpr void shrink_to_fit() const noexcept
    {
        // no-op
    }
 
    constexpr void clear() noexcept { sz = 0; }
 
    constexpr iterator insert(const_iterator pos, value_type const value) noexcept(is_noexcept)
    {
        return insert(pos, 1, value);
    }
 
    constexpr iterator insert(const_iterator pos, size_type const count, value_type const value) noexcept(is_noexcept)
    {
        auto tmp = views::repeat_n(value, count);
        return insert(pos, std::ranges::begin(tmp), std::ranges::end(tmp));
    }
 
    template <std::forward_iterator begin_it_type, typename end_it_type>
        requires(std::sentinel_for<end_it_type, begin_it_type> &&
                 std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>)
    constexpr iterator insert(const_iterator pos, begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
    {
        auto const pos_as_num = std::ranges::distance(cbegin(), pos);
        auto const length     = std::ranges::distance(begin_it, end_it);
 
        assert(pos_as_num + length <= capacity());
 
        if (length == 0)
            return begin(); // nothing to insert
 
        for (size_type i = sz + length - 1; i > pos_as_num + length - 1; --i)
            data_[i] = data_[i - length];
 
        std::ranges::copy(begin_it, end_it, &data_[pos_as_num]);
        sz += length;
        return begin() + pos_as_num;
    }
 
    constexpr iterator insert(const_iterator pos, std::initializer_list<value_type> const & ilist) noexcept(is_noexcept)
    {
        return insert(pos, ilist.begin(), ilist.end());
    }
 
    constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
    {
        if (begin_it >= end_it) // [[unlikely]]
            return begin() + std::ranges::distance(cbegin(), end_it);
 
        size_type const length = std::ranges::distance(begin_it, end_it);
        auto            out_it = begin() + std::ranges::distance(cbegin(), begin_it);
 
        while (end_it != cend())
            *(out_it++) = *(end_it++);
 
        sz -= length;
        return begin() + std::ranges::distance(cbegin(), begin_it);
    }
 
    constexpr iterator erase(const_iterator pos) noexcept { return erase(pos, pos + 1); }
 
    constexpr void push_back(value_type const value) noexcept
    {
        assert(sz < capacity_);
        data_[sz] = value;
        ++sz;
    }
 
    constexpr void pop_back() noexcept
    {
        assert(sz > 0);
        --sz;
    }
 
    constexpr void resize(size_type const count) noexcept
    {
        assert(count <= capacity_);
        sz = count;
    }
 
    constexpr void resize(size_type const count, value_type const value) noexcept
    {
        assert(count <= capacity_);
        for (size_t i = sz; i < count; ++i)
            data_[i] = value;
        sz = count;
    }
 
    constexpr void swap(small_vector & rhs) noexcept(is_noexcept)
    {
        auto tmp = *this;
 
        data_ = rhs.data_;
        sz    = rhs.sz;
 
        rhs.data_ = tmp.data_;
        rhs.sz    = tmp.sz;
    }
 
    constexpr void swap(small_vector && rhs) noexcept(is_noexcept)
    {
        data_ = rhs.data_;
        sz    = rhs.sz;
    }
 
    friend constexpr void swap(small_vector & lhs, small_vector & rhs) noexcept(is_noexcept) { lhs.swap(rhs); }
 
    friend constexpr void swap(small_vector && lhs, small_vector && rhs) noexcept(is_noexcept) { lhs.swap(rhs); }
 
 
    template <size_t cap2>
    friend constexpr bool operator==(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        return std::ranges::equal(lhs, rhs);
    }
 
    template <size_t cap2>
    friend constexpr bool operator<(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
            if (lhs[i] > rhs[i])
                return false;
            else if (lhs[i] < rhs[i])
                return true;
        return lhs.size() < rhs.size();
    }
 
    template <size_t cap2>
    friend constexpr bool operator>(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
            if (lhs[i] < rhs[i])
                return false;
            else if (lhs[i] > rhs[i])
                return true;
        return lhs.size() > rhs.size();
    }
 
    template <size_t cap2>
    friend constexpr bool operator<=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        return !(lhs > rhs);
    }
 
    template <size_t cap2>
    friend constexpr bool operator>=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        return !(lhs < rhs);
    }
 
public:
 
    std::array<value_type, capacity_> data_{};
    size_type                         sz{0};
 
public:
 
    template <typename archive_t>
    void serialize(archive_t & archive)
    {
        archive(data_);
        archive(sz);
    }
};
 
template <size_t capacity2, typename value_type>
small_vector(const value_type (&array)[capacity2]) -> small_vector<value_type, capacity2>;
 
} // namespace bio::ranges