concatenated_sequences.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 <type_traits>
#include <vector>

#include <range/v3/view/const.hpp>
#include <range/v3/view/join.hpp>
#include <range/v3/view/repeat_n.hpp>
#include <range/v3/view/slice.hpp>

#include <seqan3/core/concept/cereal.hpp>
#include <seqan3/core/type_traits/all.hpp>
#include <seqan3/range/shortcuts.hpp>
#include <seqan3/range/container/concept.hpp>
#include <seqan3/range/detail/random_access_iterator.hpp>
#include <seqan3/std/iterator>
#include <seqan3/std/ranges>

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

namespace seqan3
{

template <typename inner_type,
          typename data_delimiters_type = std::vector<typename inner_type::size_type>>
    requires ReservableContainer<std::remove_reference_t<inner_type>> &&
             ReservableContainer<std::remove_reference_t<data_delimiters_type>> &&
             std::is_same_v<size_type_t<inner_type>, value_type_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 = decltype(data_values | ranges::view::slice(0, 1));

    using const_reference = decltype(std::as_const(data_values) | ranges::view::slice(0, 1) | ranges::view::const_);

    using iterator = detail::random_access_iterator<concatenated_sequences>;

    using const_iterator = detail::random_access_iterator<concatenated_sequences const>;

    using difference_type = difference_type_t<data_delimiters_type>;

    using size_type = size_type_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 <typename t>
        requires (dimension_v<t> == dimension_v<value_type> + 1) &&
                 std::is_same_v<remove_cvref_t<innermost_value_type_t<value_type>>,
                                remove_cvref_t<innermost_value_type_t<t>>>
    static constexpr bool is_compatible_this_aux = true;

    // cannot use the concept, because this class is not yet fully defined
    template <typename t>
    static constexpr bool is_compatible_this = is_compatible_this_aux<t>                                    ||
                                               std::is_same_v<remove_cvref_t<t>, concatenated_sequences>    ||
                                               std::is_same_v<remove_cvref_t<t>, iterator>                  ||
                                               std::is_same_v<remove_cvref_t<t>, const_iterator>;

    // we explicitly check same-ness, because these types may not be fully resolved, yet
    template <typename t>
    static constexpr bool is_compatible_value = Compatible<value_type, t>                           ||
                                                std::is_same_v<remove_cvref_t<t>, value_type>       ||
                                                std::is_same_v<remove_cvref_t<t>, reference>        ||
                                                std::is_same_v<remove_cvref_t<t>, const_reference>;
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::InputRange rng_of_rng_type>
    concatenated_sequences(rng_of_rng_type && rng_of_rng)
        requires is_compatible_this<rng_of_rng_type>
    {
        if constexpr (std::ranges::SizedRange<rng_of_rng_type>)
            data_delimiters.reserve(seqan3::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::ForwardRange rng_type>
    concatenated_sequences(size_type const count, rng_type && value)
        requires is_compatible_value<rng_type>
    {
        // TODO SEQAN_UNLIKELY
        if (count == 0)
            return;

        insert(cend(), count, std::forward<rng_type>(value));
    }

    template <std::ForwardIterator begin_iterator_type, std::SizedSentinel<begin_iterator_type> end_iterator_type>
    concatenated_sequences(begin_iterator_type begin_it, end_iterator_type end_it)
        requires is_compatible_this<begin_iterator_type>
    {
        insert(cend(), begin_it, end_it);
    }

    template <std::ranges::ForwardRange rng_type = value_type>
    concatenated_sequences(std::initializer_list<rng_type> ilist)
        requires is_compatible_value<rng_type>
    {
        assign(std::begin(ilist), std::end(ilist));
    }

    template <std::ranges::ForwardRange rng_type>
    concatenated_sequences & operator=(std::initializer_list<rng_type> ilist)
        requires is_compatible_value<rng_type>
    {
        assign(std::begin(ilist), std::end(ilist));
        return *this;
    }

    template <std::ranges::InputRange rng_of_rng_type>
    void assign(rng_of_rng_type && rng_of_rng)
        requires is_compatible_this<rng_of_rng_type>
    {
        concatenated_sequences rhs{std::forward<rng_of_rng_type>(rng_of_rng)};
        swap(rhs);
    }

    template <typename rng_type>
    void assign(size_type const count, rng_type && value)
        requires (std::ranges::ForwardRange<rng_type> && is_compatible_value<rng_type>)
    {
        concatenated_sequences rhs{count, value};
        swap(rhs);
    }

    template <std::ForwardIterator begin_iterator_type, typename end_iterator_type>
    void assign(begin_iterator_type begin_it, end_iterator_type end_it)
        requires is_compatible_this<begin_iterator_type> &&
                 std::SizedSentinel<end_iterator_type, begin_iterator_type>
    {
        concatenated_sequences rhs{begin_it, end_it};
        swap(rhs);
    }

    template <std::ranges::ForwardRange rng_type = value_type>
    void assign(std::initializer_list<rng_type> ilist)
        requires is_compatible_value<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 | ranges::view::slice(data_delimiters[i], data_delimiters[i+1]);
    }

    const_reference operator[](size_type const i) const
    {
        assert(i < size());
        return data_values | ranges::view::slice(data_delimiters[i], data_delimiters[i+1])
                           | ranges::view::const_;
    }

    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 | ranges::view::slice(static_cast<size_type>(0), concat_size());
    }

    const_reference concat() const
    {
        return data_values | ranges::view::slice(static_cast<size_type>(0), concat_size()) | ranges::view::const_;
    }

    std::pair<decltype(data_values) &, decltype(data_delimiters) &> data()
    {
        return {data_values, data_delimiters};
    }

    std::pair<decltype(data_values) const &, decltype(data_delimiters) const &> data() const
    {
        return {std::as_const(data_values), std::as_const(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::ForwardRange rng_type>
    iterator insert(const_iterator pos, rng_type && value)
        requires is_compatible_value<rng_type>
    {
        return insert(pos, 1, std::forward<rng_type>(value));
    }
    // no specialisation for temporaries, since we have to copy anyway

    template <std::ranges::ForwardRange rng_type>
    iterator insert(const_iterator pos, size_type const count, rng_type && value)
        requires is_compatible_value<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 view::flat_repeat_n that is like
         *  ranges::view::repeat_n(value, count) | std::view::join | ranges::view::bounded;
         * but preserves random access and size.
         *
         * then do
         *  auto concatenated = ranges::view::flat_repeat_n(value, count);
         *  insert(pos, concatenated.cbegin(), concatenated.cend())
         */

        size_type value_len = 0;
        if constexpr (std::ranges::SizedRange<rng_type>)
            value_len = seqan3::size(value);
        else
            value_len = std::distance(seqan3::begin(value), seqan3::end(value));

        data_values.reserve(data_values.size() + count * value_len);
        auto placeholder = ranges::view::repeat_n(value_type_t<rng_type>{}, count * value_len)
                         | std::view::common;
        // insert placeholder so the tail is moved once:
        data_values.insert(data_values.begin() + data_delimiters[pos_as_num],
                           seqan3::begin(placeholder),
                           seqan3::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::ForwardIterator begin_iterator_type, typename end_iterator_type>
    iterator insert(const_iterator pos, begin_iterator_type first, end_iterator_type last)
        requires is_compatible_this<begin_iterator_type> &&
                 std::SizedSentinel<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::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)
        {
            // constant for sized ranges and/or random access ranges, linear otherwise
            if constexpr (std::ranges::SizedRange<std::decay_t<decltype(*first)>>)
                full_len += seqan3::size(*first);
            else
                full_len += std::distance(seqan3::begin(*first), seqan3::end(*first));

            data_delimiters[pos_as_num + 1 + i] += full_len;
        }

        // adapt values of inserted region
        auto placeholder = ranges::view::repeat_n(value_type_t<value_type>{}, full_len)
                         | std::view::common;
        // insert placeholder so the tail is moved only once:
        data_values.insert(data_values.begin() + data_delimiters[pos_as_num],
                           seqan3::begin(placeholder),
                           seqan3::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::ForwardRange rng_type>
    iterator insert(const_iterator pos, std::initializer_list<rng_type> const & ilist)
        requires is_compatible_value<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 += seqan3::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::ForwardRange rng_type>
    void push_back(rng_type && value)
        requires is_compatible_value<rng_type>
    {
        data_values.insert(data_values.end(), seqan3::begin(value), seqan3::end(value));
        data_delimiters.push_back(data_delimiters.back() + seqan3::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::ForwardRange rng_type>
    void resize(size_type const count, rng_type && value)
        requires is_compatible_value<rng_type>
    {
        assert(count < max_size());
        assert(concat_size() + count * seqan3::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 data() == rhs.data();
    }

    constexpr bool operator!=(concatenated_sequences const & rhs) const noexcept
    {
        return data() != rhs.data();
    }

    constexpr bool operator<(concatenated_sequences const & rhs) const noexcept
    {
        return data() < rhs.data();
    }

    constexpr bool operator>(concatenated_sequences const & rhs) const noexcept
    {
        return data() > rhs.data();
    }

    constexpr bool operator<=(concatenated_sequences const & rhs) const noexcept
    {
        return data() <= rhs.data();
    }

    constexpr bool operator>=(concatenated_sequences const & rhs) const noexcept
    {
        return data() >= rhs.data();
    }

    template <CerealArchive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        archive(data_values, data_delimiters);
    }
};

} // namespace seqan3