pairwise_combine.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2006-2021, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2021, 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 <cmath>
#include <seqan3/std/ranges>
 
#include <seqan3/core/detail/iterator_traits.hpp>
#include <seqan3/core/range/detail/adaptor_for_view_without_args.hpp>
#include <seqan3/utility/range/concept.hpp>
#include <seqan3/utility/tuple/common_tuple.hpp>
#include <seqan3/utility/type_traits/detail/transformation_trait_or.hpp>
 
namespace seqan3::detail
{
template <std::ranges::view underlying_range_type>
    requires  std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
class pairwise_combine_view : public std::ranges::view_interface<pairwise_combine_view<underlying_range_type>>
{
private:
 
    template <typename range_type>
    class basic_iterator;
 
    using iterator = basic_iterator<underlying_range_type>;
    using const_iterator = transformation_trait_or_t<std::type_identity<basic_iterator<underlying_range_type const>>,
                                                     void>;
 
public:
    pairwise_combine_view() = default; 
    pairwise_combine_view(pairwise_combine_view const &) = default; 
    pairwise_combine_view(pairwise_combine_view &&) = default; 
    pairwise_combine_view & operator=(pairwise_combine_view const &) = default; 
    pairwise_combine_view & operator=(pairwise_combine_view &&) = default; 
    ~pairwise_combine_view() = default; 
 
    explicit constexpr pairwise_combine_view(underlying_range_type range) : u_range{std::move(range)}
    {
        // Check if range is empty.
        if (std::ranges::empty(u_range))
        {
            back_iterator = std::ranges::end(u_range);
        }
        else
        {
            if constexpr (std::ranges::bidirectional_range<underlying_range_type>)
            { // Simply take one before the end. We can do this as we require underlying_range_type to be a common range.
                back_iterator = std::ranges::prev(std::ranges::end(u_range));
            }
            else
            { // For all other cases we need to set the back_iterator in linear time to the correct position.
                back_iterator = std::ranges::begin(u_range);
                if constexpr (std::ranges::sized_range<underlying_range_type>)
                {
                    std::ranges::advance(back_iterator, std::ranges::size(u_range) - 1);
                }
                else // We don't have the size, so we need to increment until one before the end in a linear pass.
                {
                    auto tmp_it = back_iterator;
                    do
                    {
                        back_iterator = tmp_it;
                    } while (++tmp_it != std::ranges::end(u_range));
                }
            }
        }
    }
 
    template <typename other_range_t>
        requires (!std::same_as<std::remove_cvref_t<other_range_t>, pairwise_combine_view>) &&
                 std::ranges::viewable_range<other_range_t> &&  // Must come after self type check to avoid conflicts with the move constructor.
                 std::constructible_from<underlying_range_type,
                                         std::ranges::ref_view<std::remove_reference_t<other_range_t>>>
            //TODO: Investigate: the following expression is equivalent to the one above but raises a weird assertion in
            //      the ranges adaptor suggesting that the pairwise_combine_view is not a viewable_range.
            //      std::constructible_from<underlying_range_type, decltype(std::views::all(std::declval<other_range_t &&>()))>
    explicit constexpr pairwise_combine_view(other_range_t && range) :
        pairwise_combine_view{std::views::all(std::forward<other_range_t>(range))}
    {}
 
    constexpr iterator begin() noexcept
    {
        return {std::ranges::begin(u_range), std::ranges::begin(u_range), std::ranges::end(u_range)};
    }
 
    constexpr const_iterator begin() const noexcept
        requires const_iterable_range<underlying_range_type>
    {
        return {std::ranges::cbegin(u_range), std::ranges::cbegin(u_range), std::ranges::cend(u_range)};
    }
 
    constexpr iterator end() noexcept
    {
        return {back_iterator, std::ranges::begin(u_range), std::ranges::end(u_range)};
    }
 
    constexpr const_iterator end() const noexcept
        requires const_iterable_range<underlying_range_type>
    {
        return {back_iterator, std::ranges::cbegin(u_range), std::ranges::cend(u_range)};
    }
 
#if SEQAN3_WORKAROUND_GCC_NON_TEMPLATE_REQUIRES
    template <typename = underlying_range_type>
#endif // SEQAN3_WORKAROUND_GCC_NON_TEMPLATE_REQUIRES
    constexpr auto size() const noexcept
        requires std::ranges::sized_range<underlying_range_type>
    {
        auto const size = std::ranges::size(u_range);
        return (size * (size - 1)) / 2;
    }
 
private:
 
    underlying_range_type u_range{};
    std::ranges::iterator_t<underlying_range_type> back_iterator{};
};
 
template <std::ranges::viewable_range other_range_t>
pairwise_combine_view(other_range_t && range) ->
    pairwise_combine_view<std::views::all_t<other_range_t>>;
 
template <std::ranges::view underlying_range_type>
    requires std::ranges::forward_range<underlying_range_type> && std::ranges::common_range<underlying_range_type>
template <typename range_type>
class pairwise_combine_view<underlying_range_type>::basic_iterator
    : public maybe_iterator_category<std::ranges::iterator_t<range_type>>
{
private:
 
    template <typename other_range_type>
        requires std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    friend class basic_iterator;
 
    using underlying_iterator_type = std::ranges::iterator_t<range_type>;
    using underlying_val_t = std::iter_value_t<underlying_iterator_type>;
    using underlying_ref_t = std::iter_reference_t<underlying_iterator_type>;
 
public:
    using difference_type = std::ptrdiff_t;
    using value_type = std::tuple<underlying_val_t, underlying_val_t>;
    using reference = common_tuple<underlying_ref_t, underlying_ref_t>;
    using pointer = void;
    using iterator_concept = detail::iterator_concept_tag_t<underlying_iterator_type>;
 
    basic_iterator() = default; 
    basic_iterator(basic_iterator const &) = default; 
    basic_iterator(basic_iterator &&) = default; 
    basic_iterator & operator=(basic_iterator const &) = default; 
    basic_iterator & operator=(basic_iterator &&) = default; 
    ~basic_iterator() = default; 
 
    constexpr basic_iterator(underlying_iterator_type iter,
                             underlying_iterator_type begin_it,
                             underlying_iterator_type end_it) noexcept :
        first_it{iter},
        second_it{std::ranges::next(iter, 1, end_it)},
        begin_it{begin_it},
        end_it{end_it}
    {}
 
    template <typename other_range_type>
        requires std::convertible_to<other_range_type, range_type &> &&
                 std::same_as<std::remove_const_t<other_range_type>, std::remove_const_t<range_type>>
    constexpr basic_iterator(basic_iterator<other_range_type> other) noexcept :
        basic_iterator{std::move(other.first_it), std::move(other.begin_it), std::move(other.end_it)}
    {}
 
    constexpr reference operator*() const
        noexcept(noexcept(*std::declval<underlying_iterator_type>()))
    {
        return reference{*first_it, *second_it};
    }
 
    constexpr reference operator[](size_t const index) const
        noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        return *(*this + index);
    }
 
    constexpr basic_iterator & operator++(/*pre-increment*/)
        noexcept(noexcept(++std::declval<underlying_iterator_type &>()))
    {
        if (++second_it == end_it)
        {
            ++first_it;
            second_it = first_it;
            ++second_it;
        }
        return *this;
    }
 
    constexpr basic_iterator operator++(int /*post-increment*/)
        noexcept(noexcept(std::declval<underlying_iterator_type &>()++))
    {
        basic_iterator tmp{*this};
        ++*this;
        return tmp;
    }
 
    constexpr basic_iterator & operator--(/*pre-decrement*/)
        noexcept(noexcept(--std::declval<underlying_iterator_type &>()))
        requires std::bidirectional_iterator<underlying_iterator_type>
    {
        if (--second_it == first_it)
        {
            --first_it;
            second_it = end_it;
            --second_it;
        }
        return *this;
    }
 
    constexpr basic_iterator operator--(int /*post-decrement*/)
        noexcept(noexcept(std::declval<underlying_iterator_type &>()--))
        requires std::bidirectional_iterator<underlying_iterator_type>
    {
        basic_iterator tmp{*this};
        --*this;
        return tmp;
    }
 
    constexpr basic_iterator & operator+=(difference_type const offset)
        noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        from_index(to_index() + offset);
        return *this;
    }
 
    constexpr basic_iterator operator+(difference_type const offset) const
        noexcept(noexcept(std::declval<basic_iterator &>() += 1))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        basic_iterator tmp{*this};
        return (tmp += offset);
    }
 
    constexpr friend basic_iterator operator+(difference_type const offset, basic_iterator iter)
        noexcept(noexcept(std::declval<basic_iterator<range_type> &>().from_index(1)))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        iter.from_index(iter.to_index() + offset);
        return iter;
    }
 
    constexpr basic_iterator & operator-=(difference_type const offset)
        noexcept(noexcept(std::declval<basic_iterator &>().from_index(1)))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        from_index(to_index() - offset);
        return *this;
    }
 
    constexpr basic_iterator operator-(difference_type const offset) const
        noexcept(noexcept(std::declval<basic_iterator &>() -= 1))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        basic_iterator tmp{*this};
        return (tmp -= offset);
    }
 
    template <typename other_range_type>
        requires std::random_access_iterator<underlying_iterator_type> &&
                 std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    constexpr difference_type operator-(basic_iterator<other_range_type> const & rhs) const
        noexcept(noexcept(std::declval<basic_iterator &>().to_index()))
    {
        return static_cast<difference_type>(to_index() - rhs.to_index());
    }
 
    //NOTE: The comparison operators should be implemented as friends, but due to a bug in gcc friend function
    // cannot yet be constrained. To avoid unexpected errors with the comparison all operators are implemented as
    // direct members and not as friends.
 
    template <typename other_range_type>
        requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>> &&
                 std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    constexpr bool operator==(basic_iterator<other_range_type> const & rhs) const
        noexcept(noexcept(std::declval<underlying_iterator_type &>() == std::declval<underlying_iterator_type &>()))
    {
        return std::tie(first_it, second_it) == std::tie(rhs.first_it, rhs.second_it);
    }
 
    template <typename other_range_type>
        requires std::equality_comparable_with<underlying_iterator_type, std::ranges::iterator_t<other_range_type>> &&
                 std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    constexpr bool operator!=(basic_iterator<other_range_type> const & rhs) const
        noexcept(noexcept(std::declval<underlying_iterator_type &>() != std::declval<underlying_iterator_type &>()))
    {
        return !(*this == rhs);
    }
 
    template <typename other_range_type>
        requires std::totally_ordered_with<underlying_iterator_type,
                                               std::ranges::iterator_t<other_range_type>> &&
                 std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    constexpr bool operator<(basic_iterator<other_range_type> const & rhs) const
        noexcept(noexcept(std::declval<underlying_iterator_type &>() < std::declval<underlying_iterator_type &>()))
    {
        return std::tie(first_it, second_it) < std::tie(rhs.first_it, rhs.second_it);
    }
 
    template <typename other_range_type>
        requires std::totally_ordered_with<underlying_iterator_type,
                                               std::ranges::iterator_t<other_range_type>> &&
                 std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    constexpr bool operator>(basic_iterator<other_range_type> const & rhs) const
        noexcept(noexcept(std::declval<underlying_iterator_type &>() > std::declval<underlying_iterator_type &>()))
 
    {
        return std::tie(first_it, second_it) > std::tie(rhs.first_it, rhs.second_it);
    }
 
    template <typename other_range_type>
        requires std::totally_ordered_with<underlying_iterator_type,
                                               std::ranges::iterator_t<other_range_type>> &&
                 std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    constexpr bool operator<=(basic_iterator<other_range_type> const & rhs) const
        noexcept(noexcept(std::declval<underlying_iterator_type &>() <= std::declval<underlying_iterator_type &>()))
    {
        return std::tie(first_it, second_it) <= std::tie(rhs.first_it, rhs.second_it);
    }
 
    template <typename other_range_type>
        requires std::totally_ordered_with<underlying_iterator_type,
                                               std::ranges::iterator_t<other_range_type>> &&
                 std::same_as<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
    constexpr bool operator>=(basic_iterator<other_range_type> const & rhs) const
        noexcept(noexcept(std::declval<underlying_iterator_type &>() >= std::declval<underlying_iterator_type &>()))
    {
        return std::tie(first_it, second_it) >= std::tie(rhs.first_it, rhs.second_it);
    }
 
private:
 
    constexpr size_t to_index() const
        noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>()))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        size_t src_size = end_it - begin_it;
        size_t index_i = first_it - begin_it;
        size_t index_j = second_it - begin_it;
        return (src_size * (src_size - 1)/2) - (src_size - index_i) * ((src_size - index_i) - 1)/2 +
               index_j - index_i - 1;
    }
 
    constexpr void from_index(size_t const index)
        noexcept(noexcept(std::declval<underlying_iterator_type &>() - std::declval<underlying_iterator_type &>()) &&
                 noexcept(std::declval<underlying_iterator_type &>() + 1))
        requires std::random_access_iterator<underlying_iterator_type>
    {
        size_t src_size = end_it - begin_it;
        size_t index_i = src_size - 2 -
                         std::floor(std::sqrt(-8 * index + 4 * src_size * (src_size - 1) - 7)/2.0 - 0.5);
        size_t index_j = index + index_i + 1 - src_size * (src_size - 1)/2 + (src_size - index_i) *
                         ((src_size - index_i) - 1)/2;
        first_it = begin_it + index_i;
        second_it = begin_it + index_j;
    }
 
    underlying_iterator_type first_it{};
    underlying_iterator_type second_it{};
    underlying_iterator_type begin_it{};
    underlying_iterator_type end_it{};
};
 
} // namespace seqan3::detail
 
namespace seqan3::views
{
inline constexpr auto pairwise_combine = detail::adaptor_for_view_without_args<detail::pairwise_combine_view>{};
 
} // namespace seqan3::views