small_vector.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2006-2019, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2019, 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/seqan/seqan3/blob/master/LICENSE.md
// -----------------------------------------------------------------------------------------------------

#pragma once

#include <array>
#include <type_traits>

#if SEQAN3_WITH_CEREAL
#include <cereal/types/array.hpp>
#endif // SEQAN3_WITH_CEREAL

#include <seqan3/core/concept/cereal.hpp>
#include <seqan3/core/detail/int_types.hpp>
#include <seqan3/core/type_traits/template_inspection.hpp>
#include <seqan3/range/view/repeat_n.hpp>
#include <seqan3/range/view/take.hpp>
#include <seqan3/std/algorithm>
#include <seqan3/std/ranges>

namespace seqan3
{

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 = const value_type &;                   
    using iterator        = value_type *;                         
    using const_iterator  = value_type const *;                   
    using difference_type = ptrdiff_t;                            
    using size_type       = 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<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::ForwardIterator begin_it_type, std::Sentinel<begin_it_type> end_it_type>
        requires std::Constructible<value_type, /*ranges::iter_reference_t*/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 <std::ranges::InputRange other_range_t>
        requires !std::is_same_v<remove_cvref_t<other_range_t>, small_vector>
                 /*ICE: && std::Constructible<value_type, reference_t<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 = view::repeat_n(value, count);
        assign(std::ranges::begin(tmp), std::ranges::end(tmp));
    }

    template <std::ranges::InputRange other_range_t>
        requires std::Constructible<value_type, /*ranges::range_reference_t*/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::ForwardIterator begin_it_type, std::Sentinel<begin_it_type> end_it_type>
    constexpr void assign(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
        requires std::Constructible<value_type, /*ranges::iter_reference_t*/reference_t<begin_it_type>>
    {
        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 = view::repeat_n(value, count);
        return insert(pos, std::ranges::begin(tmp), std::ranges::end(tmp));
    }

    template <std::ForwardIterator begin_it_type, std::Sentinel<begin_it_type> end_it_type>
        requires std::Constructible<value_type, /*ranges::iter_reference_t*/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);

        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>
        requires cap2 <= capacity_ /* resolves ambiguousness when comparing two small_vectors of unequal capacity */
    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>
        requires cap2 <= capacity_
    friend constexpr bool operator!=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        return !(lhs == rhs);
    }

    template <size_t cap2>
        requires cap2 <= capacity_
    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>
        requires cap2 <= capacity_
    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>
        requires cap2 <= capacity_
    friend constexpr bool operator<=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        return !(lhs > rhs);
    }

    template <size_t cap2>
        requires cap2 <= capacity_
    friend constexpr bool operator>=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
    {
        return !(lhs < rhs);
    }

protected:
    std::array<value_type, capacity_> data_{};
    size_type sz{0};

    template <CerealArchive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(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 seqan3