concatenated_sequences.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 <iterator>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
 
#include <bio/ranges/container/concept.hpp>
#include <bio/ranges/detail/random_access_iterator.hpp>
#include <bio/ranges/views/repeat_n.hpp>
#include <bio/ranges/views/slice.hpp>
 
namespace bio::ranges
{
 
template <typename underlying_container_type,
          typename data_delimiters_type = std::vector<typename underlying_container_type::size_type>>
    requires(detail::reservible_container<std::remove_reference_t<underlying_container_type>> &&
             detail::reservible_container<std::remove_reference_t<data_delimiters_type>> &&
             std::is_same_v<std::ranges::range_size_t<underlying_container_type>,
                            std::ranges::range_value_t<data_delimiters_type>>)
class concatenated_sequences
{
protected:
    std::decay_t<underlying_container_type> data_values;
    data_delimiters_type                    data_delimiters{0};
 
public:
 
    using value_type = decltype(std::declval<std::decay_t<underlying_container_type> &>() | views::slice(0, 1));
 
    using reference = value_type;
 
    using const_reference = decltype(std::as_const(data_values) | views::slice(0, 1));
 
    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 &&) noexcept             = default;
    constexpr concatenated_sequences & operator=(concatenated_sequences const &)     = default;
    constexpr concatenated_sequences & operator=(concatenated_sequences &&) noexcept = default;
    ~concatenated_sequences()                                                        = default;
 
    template <meta::different_from<concatenated_sequences> rng_of_rng_type>
        requires(std::ranges::input_range<rng_of_rng_type> &&
                 range_value_t_is_compatible_with_value_type<rng_of_rng_type>)
    concatenated_sequences(rng_of_rng_type && rng_of_rng)
    {
        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::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::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 {data_values, data_delimiters};
    }
 
    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;
        }
 
        // insert placeholder so the tail is moved only once:
        data_values.insert(data_values.begin() + data_delimiters[pos_as_num],
                           full_len,
                           std::ranges::range_value_t<value_type>{});
 
        // 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 push_back() { data_delimiters.push_back(data_delimiters.back()); }
 
    void push_back_inner(std::ranges::range_value_t<underlying_container_type> const value)
    {
        data_values.push_back(value);
        ++data_delimiters.back();
    }
 
    template <std::ranges::forward_range rng_type>
    void append_inner(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.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();
    }
 
    template <typename archive_t>
    void serialize(archive_t & archive)
    {
        archive(data_values, data_delimiters);
    }
};
 
} // namespace bio::ranges