concatenated_sequences.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// 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/seqan/seqan3/blob/master/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <seqan3/std/iterator>
#include <seqan3/std/ranges>
#include <type_traits>
#include <vector>
 
#include <seqan3/core/concept/cereal.hpp>
#include <seqan3/range/container/concept.hpp>
#include <seqan3/range/detail/random_access_iterator.hpp>
#include <seqan3/range/views/as_const.hpp>
#include <seqan3/range/views/join.hpp>
#include <seqan3/range/views/slice.hpp>
#include <seqan3/utility/views/repeat_n.hpp>
 
#if SEQAN3_WITH_CEREAL
#include <cereal/types/vector.hpp>
#endif
 
namespace seqan3::detail
{
 
template <typename value_type, bool const_>
struct concatenated_sequences_reference_proxy :
    public std::conditional_t<const_,
                              decltype(std::declval<value_type const &>() | views::as_const | views::slice(0,1)),
                              decltype(std::declval<value_type &>() | views::slice(0,1))>
{
    using base_t =
        std::conditional_t<const_,
                           decltype(std::declval<value_type const &>() | views::as_const | views::slice(0,1)),
                           decltype(std::declval<value_type &>() | views::slice(0,1))>;
 
    using base_t::base_t;
 
    concatenated_sequences_reference_proxy(base_t && rhs) : base_t{std::move(rhs)} {}
 
    operator value_type() const
    {
        value_type ret;
        ret.resize(std::ranges::size(*this));
        std::ranges::copy(*this, std::ranges::begin(ret));
        return ret;
    }
};
 
} // namespace seqan3::detail
 
namespace seqan3
{
 
template <typename inner_type,
          typename data_delimiters_type = std::vector<typename inner_type::size_type>>
    requires reservible_container<std::remove_reference_t<inner_type>> &&
             reservible_container<std::remove_reference_t<data_delimiters_type>> &&
             std::is_same_v<std::ranges::range_size_t<inner_type>, std::ranges::range_value_t<data_delimiters_type>>
class concatenated_sequences
{
protected:
    std::decay_t<inner_type> data_values;
    data_delimiters_type data_delimiters{0};
 
public:
 
    using value_type = std::decay_t<inner_type>;
 
    using reference = detail::concatenated_sequences_reference_proxy<value_type, false>;
 
    using const_reference = detail::concatenated_sequences_reference_proxy<value_type, true>;
 
    using iterator = detail::random_access_iterator<concatenated_sequences>;
 
    using const_iterator = detail::random_access_iterator<concatenated_sequences const>;
 
    using difference_type = std::ranges::range_difference_t<data_delimiters_type>;
 
    using size_type = std::ranges::range_size_t<data_delimiters_type>;
 
    // this signals to range-v3 that something is a container :|
    using allocator_type    = void;
 
protected:
    // unfortunately we cannot specialise the variable template so we have to add an auxiliary here
    template <std::ranges::range t>
    static constexpr bool is_compatible_with_value_type_aux(std::type_identity<t>)
    {
        return range_dimension_v<t> == range_dimension_v<value_type> &&
               std::convertible_to<std::ranges::range_reference_t<t>, std::ranges::range_value_t<value_type>>;
    }
 
    static constexpr bool is_compatible_with_value_type_aux(...)
    {
        return false;
    }
 
    // we explicitly check same-ness, because these types may not be fully resolved, yet
    template <std::ranges::range t>
    static constexpr bool is_compatible_with_value_type = is_compatible_with_value_type_aux(std::type_identity<t>{});
 
    // cannot use the concept, because this class is not yet fully defined
    template <typename t>
        requires is_compatible_with_value_type<std::iter_reference_t<t>>
    static constexpr bool iter_value_t_is_compatible_with_value_type = true;
 
    // cannot use the concept, because this class is not yet fully defined
    template <std::ranges::range t>
        requires is_compatible_with_value_type<std::ranges::range_reference_t<t>>
    static constexpr bool range_value_t_is_compatible_with_value_type = true;
 
public:
    concatenated_sequences() = default;
    constexpr concatenated_sequences(concatenated_sequences const &) = default;
    constexpr concatenated_sequences(concatenated_sequences &&) = default;
    constexpr concatenated_sequences & operator=(concatenated_sequences const &) = default;
    constexpr concatenated_sequences & operator=(concatenated_sequences &&) = default;
    ~concatenated_sequences() = default;
 
    template <std::ranges::input_range rng_of_rng_type>
    concatenated_sequences(rng_of_rng_type && rng_of_rng)
        requires range_value_t_is_compatible_with_value_type<rng_of_rng_type>
    {
        if constexpr (std::ranges::sized_range<rng_of_rng_type>)
            data_delimiters.reserve(std::ranges::size(rng_of_rng) + 1);
 
        for (auto && val : rng_of_rng)
        {
            data_values.insert(data_values.end(), val.begin(), val.end());
            data_delimiters.push_back(data_delimiters.back() + val.size());
        }
    }
 
    template <std::ranges::forward_range rng_type>
    concatenated_sequences(size_type const count, rng_type && value)
        requires is_compatible_with_value_type<rng_type>
    {
        // TODO SEQAN_UNLIKELY
        if (count == 0)
            return;
 
        insert(cend(), count, std::forward<rng_type>(value));
    }
 
    template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
    concatenated_sequences(begin_iterator_type begin_it, end_iterator_type end_it)
        requires std::sized_sentinel_for<end_iterator_type, begin_iterator_type> &&
                 iter_value_t_is_compatible_with_value_type<begin_iterator_type>
    {
        insert(cend(), begin_it, end_it);
    }
 
    template <std::ranges::forward_range value_type_t = value_type>
        requires is_compatible_with_value_type<value_type_t>
    concatenated_sequences(std::initializer_list<value_type_t> ilist)
    {
        assign(std::begin(ilist), std::end(ilist));
    }
 
    template <std::ranges::forward_range value_type_t>
    concatenated_sequences & operator=(std::initializer_list<value_type_t> ilist)
        requires is_compatible_with_value_type<value_type_t>
    {
        assign(std::begin(ilist), std::end(ilist));
        return *this;
    }
 
    template <std::ranges::input_range rng_of_rng_type>
    void assign(rng_of_rng_type && rng_of_rng)
        requires range_value_t_is_compatible_with_value_type<rng_of_rng_type>
    {
        concatenated_sequences rhs{std::forward<rng_of_rng_type>(rng_of_rng)};
        swap(rhs);
    }
 
    template <std::ranges::forward_range rng_type>
    void assign(size_type const count, rng_type && value)
        requires (is_compatible_with_value_type<rng_type>)
    {
        concatenated_sequences rhs{count, value};
        swap(rhs);
    }
 
    template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
    void assign(begin_iterator_type begin_it, end_iterator_type end_it)
        requires iter_value_t_is_compatible_with_value_type<begin_iterator_type> &&
                 std::sized_sentinel_for<end_iterator_type, begin_iterator_type>
    {
        concatenated_sequences rhs{begin_it, end_it};
        swap(rhs);
    }
 
    template <std::ranges::forward_range rng_type = value_type>
    void assign(std::initializer_list<rng_type> ilist)
        requires is_compatible_with_value_type<rng_type>
    {
        assign(std::begin(ilist), std::end(ilist));
    }
 
 
    iterator begin() noexcept
    {
        return iterator{*this};
    }
 
    const_iterator begin() const noexcept
    {
        return const_iterator{*this};
    }
 
    const_iterator cbegin() const noexcept
    {
        return const_iterator{*this};
    }
 
    iterator end() noexcept
    {
        return iterator{*this, size()};
    }
 
    const_iterator end() const noexcept
    {
        return const_iterator{*this, size()};
    }
 
    const_iterator cend() const noexcept
    {
        return const_iterator{*this, size()};
    }
 
    reference at(size_type const i)
    {
        //TODO add SEQAN_UNLIKELY
        if (i >= size())
            throw std::out_of_range{"Trying to access element behind the last in concatenated_sequences."};
        return (*this)[i];
    }
 
    const_reference at(size_type const i) const
    {
        //TODO add SEQAN_UNLIKELY
        if (i >= size())
            throw std::out_of_range{"Trying to access element behind the last in concatenated_sequences."};
        return (*this)[i];
    }
 
    reference operator[](size_type const i)
    {
        assert(i < size());
        return data_values | views::slice(data_delimiters[i], data_delimiters[i+1]);
    }
 
    const_reference operator[](size_type const i) const
    {
        assert(i < size());
        return data_values | views::as_const | views::slice(data_delimiters[i], data_delimiters[i+1]);
    }
 
    reference front()
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    const_reference front() const
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    reference back()
    {
        assert(size() > 0);
        return (*this)[size()-1];
    }
 
    const_reference back() const
    {
        assert(size() > 0);
        return (*this)[size()-1];
    }
 
    reference concat()
    {
        return data_values | views::slice(static_cast<size_type>(0), concat_size());
    }
 
    const_reference concat() const
    {
        return data_values | views::as_const | views::slice(static_cast<size_type>(0), concat_size());
    }
 
    std::pair<decltype(data_values) &, decltype(data_delimiters) &> raw_data()
    {
        return {data_values, data_delimiters};
    }
 
    std::pair<decltype(data_values) const &, decltype(data_delimiters) const &> raw_data() const
    {
        return {std::as_const(data_values), std::as_const(data_delimiters)};
    }
 
    SEQAN3_DEPRECATED_310 std::pair<decltype(data_values) &, decltype(data_delimiters) &> data()
    {
        return raw_data();
    }
 
    SEQAN3_DEPRECATED_310 std::pair<decltype(data_values) const &, decltype(data_delimiters) const &> data() const
    {
        return raw_data();
    }
 
    bool empty() const noexcept
    {
        return size() == 0;
    }
 
    size_type size() const noexcept
    {
        return data_delimiters.size() - 1;
    }
 
    size_type max_size() const noexcept
    {
        return data_delimiters.max_size() - 1;
    }
 
    size_type capacity() const noexcept
    {
        return data_delimiters.capacity();
    }
 
    void reserve(size_type const new_cap)
    {
        data_delimiters.reserve(new_cap + 1);
    }
 
    void shrink_to_fit()
    {
        data_values.shrink_to_fit();
        data_delimiters.shrink_to_fit();
    }
 
    size_type concat_size() const noexcept
    {
        return data_values.size();
    }
 
    size_type concat_capacity() const noexcept
    {
        return data_values.capacity();
    }
 
    void concat_reserve(size_type const new_cap)
    {
        data_values.reserve(new_cap);
    }
 
 
    void clear() noexcept
    {
        data_values.clear();
        data_delimiters.clear();
        data_delimiters.push_back(0);
    }
 
    template <std::ranges::forward_range rng_type>
    iterator insert(const_iterator pos, rng_type && value)
        requires is_compatible_with_value_type<rng_type>
    {
        return insert(pos, 1, std::forward<rng_type>(value));
    }
    // no specialisation for temporaries, since we have to copy anyway
 
    template <std::ranges::forward_range rng_type>
    iterator insert(const_iterator pos, size_type const count, rng_type && value)
        requires is_compatible_with_value_type<rng_type>
    {
        auto const pos_as_num = std::distance(cbegin(), pos); // we want to insert BEFORE this position
        // TODO SEQAN_UNLIKELY
        if (count == 0)
            return begin() + pos_as_num;
 
        /* TODO implement views::flat_repeat_n that is like
         *  views::repeat_n(value, count) | views::join | ranges::views::bounded;
         * but preserves random access and size.
         *
         * then do
         *  auto concatenated = ranges::views::flat_repeat_n(value, count);
         *  insert(pos, concatenated.cbegin(), concatenated.cend())
         */
 
        size_type value_len = 0;
        if constexpr (std::ranges::sized_range<rng_type>)
            value_len = std::ranges::size(value);
        else
            value_len = std::distance(std::ranges::begin(value), std::ranges::end(value));
 
        data_values.reserve(data_values.size() + count * value_len);
        auto placeholder = views::repeat_n(std::ranges::range_value_t<rng_type>{}, count * value_len)
                         | std::views::common;
        // insert placeholder so the tail is moved once:
        data_values.insert(data_values.begin() + data_delimiters[pos_as_num],
                           std::ranges::begin(placeholder),
                           std::ranges::end(placeholder));
 
        // assign the actual values to the placeholder:
        size_t i = data_delimiters[pos_as_num];
        for (size_t j = 0; j < count; ++j)
            for (auto && v : value)
                data_values[i++] = v;
 
        data_delimiters.reserve(data_values.size() + count);
        data_delimiters.insert(data_delimiters.begin() + pos_as_num,
                               count,
                               *(data_delimiters.begin() + pos_as_num));
 
        // adapt delimiters of inserted
        for (size_type i = 0; i < count; ++i)
            data_delimiters[pos_as_num + i + 1] += value_len * (i + 1);
 
        // adapt delimiters after that
        // TODO parallel execution policy or vectorization?
        std::for_each(data_delimiters.begin() + pos_as_num + count + 1,
                      data_delimiters.end(),
                      [full_len = value_len * count] (auto & d) { d += full_len; });
 
        return begin() + pos_as_num;
    }
 
    template <std::forward_iterator begin_iterator_type, typename end_iterator_type>
    iterator insert(const_iterator pos, begin_iterator_type first, end_iterator_type last)
        requires iter_value_t_is_compatible_with_value_type<begin_iterator_type> &&
                 std::sized_sentinel_for<end_iterator_type, begin_iterator_type>
    {
        auto const pos_as_num = std::distance(cbegin(), pos);
        // TODO SEQAN_UNLIKELY
        if (last - first == 0)
            return begin() + pos_as_num;
 
        auto const ilist =
            std::ranges::subrange<begin_iterator_type, end_iterator_type>(first,
                                                                          last,
                                                                          std::ranges::distance(first, last));
 
        data_delimiters.reserve(data_values.size() + ilist.size());
        data_delimiters.insert(data_delimiters.begin() + pos_as_num,
                               ilist.size(),
                               *(data_delimiters.begin() + pos_as_num));
 
 
        // adapt delimiters of inserted region
        size_type full_len = 0;
        for (size_type i = 0; i < ilist.size(); ++i, ++first)
        {
            full_len += std::ranges::distance(*first);
            data_delimiters[pos_as_num + 1 + i] += full_len;
        }
 
        // adapt values of inserted region
        auto placeholder = views::repeat_n(std::ranges::range_value_t<value_type>{}, full_len)
                         | std::views::common;
        // insert placeholder so the tail is moved only once:
        data_values.insert(data_values.begin() + data_delimiters[pos_as_num],
                           std::ranges::begin(placeholder),
                           std::ranges::end(placeholder));
 
        // assign the actual values to the placeholder:
        size_t i = data_delimiters[pos_as_num];
        for (auto && v0 : ilist)
            for (auto && v1 : v0)
                data_values[i++] = v1;
 
 
        // adapt delimiters behind inserted region
        // TODO parallel execution policy or vectorization?
        std::for_each(data_delimiters.begin() + pos_as_num + ilist.size() + 1,
                      data_delimiters.end(),
                      [full_len] (auto & d) { d += full_len; });
 
        return begin() + pos_as_num;
    }
 
    template <std::ranges::forward_range rng_type>
    iterator insert(const_iterator pos, std::initializer_list<rng_type> const & ilist)
        requires is_compatible_with_value_type<rng_type>
    {
        return insert(pos, ilist.begin(), ilist.end());
    }
 
    iterator erase(const_iterator first, const_iterator last)
    {
        auto const dist = std::distance(cbegin(), last);
        // TODO SEQAN_UNLIKELY
        if (last - first == 0)
            return begin() + dist;
 
        auto const distf = std::distance(cbegin(), first);
 
        // we need to scan once over the input
        size_type sum_size{0};
        for (; first != last; ++first)
            sum_size += std::ranges::size(*first);
 
        data_values.erase(data_values.begin() + data_delimiters[distf],
                          data_values.begin() + data_delimiters[dist]);
 
        data_delimiters.erase(data_delimiters.begin() + distf + 1,
                              data_delimiters.begin() + dist + 1);
 
        // adapt delimiters after that
        // TODO parallel execution policy or vectorization?
        std::for_each(data_delimiters.begin() + distf + 1,
                      data_delimiters.end(),
                      [sum_size] (auto & d) { d -= sum_size; });
        return begin() + dist;
    }
 
    iterator erase(const_iterator pos)
    {
       return erase(pos, pos + 1);
    }
 
    template <std::ranges::forward_range rng_type>
    void push_back(rng_type && value)
        requires is_compatible_with_value_type<rng_type>
    {
        data_values.insert(data_values.end(), std::ranges::begin(value), std::ranges::end(value));
        data_delimiters.push_back(data_delimiters.back() + std::ranges::size(value));
    }
 
    void pop_back()
    {
        assert(size() > 0);
        auto back_length = data_delimiters[size()] - data_delimiters[size() - 1];
        data_values.resize(data_values.size() - back_length);
        data_delimiters.pop_back();
    }
 
    void resize(size_type const count)
    {
        assert(count < max_size());
        data_delimiters.resize(count + 1, data_delimiters.back());
        data_values.resize(data_delimiters.back());
    }
 
    template <std::ranges::forward_range rng_type>
    void resize(size_type const count, rng_type && value)
        requires is_compatible_with_value_type<rng_type>
    {
        assert(count < max_size());
        assert(concat_size() + count * std::ranges::size(value) < data_values.max_size());
 
        if (count < size())
            resize(count);
        else if (count > size())
            insert(cend(), count - size(), std::forward<rng_type>(value));
    }
 
    constexpr void swap(concatenated_sequences & rhs) noexcept
    {
        std::swap(data_values, rhs.data_values);
        std::swap(data_delimiters, rhs.data_delimiters);
    }
 
    constexpr void swap(concatenated_sequences && rhs) noexcept
    {
        std::swap(data_values, rhs.data_values);
        std::swap(data_delimiters, rhs.data_delimiters);
    }
 
    constexpr bool operator==(concatenated_sequences const & rhs) const noexcept
    {
        return raw_data() == rhs.raw_data();
    }
 
    constexpr bool operator!=(concatenated_sequences const & rhs) const noexcept
    {
        return raw_data() != rhs.raw_data();
    }
 
    constexpr bool operator<(concatenated_sequences const & rhs) const noexcept
    {
        return raw_data() < rhs.raw_data();
    }
 
    constexpr bool operator>(concatenated_sequences const & rhs) const noexcept
    {
        return raw_data() > rhs.raw_data();
    }
 
    constexpr bool operator<=(concatenated_sequences const & rhs) const noexcept
    {
        return raw_data() <= rhs.raw_data();
    }
 
    constexpr bool operator>=(concatenated_sequences const & rhs) const noexcept
    {
        return raw_data() >= rhs.raw_data();
    }
 
    template <cereal_archive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        archive(data_values, data_delimiters);
    }
};
 
} // namespace seqan3