Loading...
Searching...
No Matches
pairwise_combine.hpp
Go to the documentation of this file.
// SPDX-FileCopyrightText: 2006-2025 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
#pragma once
#include <cmath>
#include <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::begin(u_range), std::ranges::begin(u_range), std::ranges::end(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::begin(u_range), std::ranges::end(u_range)};
}
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>
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
adaptor_for_view_without_args.hpp
Provides seqan3::detail::adaptor_for_view_without_args.
cmath
common_tuple.hpp
Provides seqan3::common_tuple.
std::declval
T declval(T... args)
std::floor
T floor(T... args)
std::forward
T forward(T... args)
seqan3::field::offset
@ offset
Sequence (seqan3::field::seq) relative start position (0-based), unsigned value.
Definition record.hpp:66
seqan3::common_tuple
seqan::stl::tuple< t... > common_tuple
A std::tuple implementation that incorporates most changes from C++23's standard library.
Definition common_tuple.hpp:24
seqan3::views::pairwise_combine
constexpr auto pairwise_combine
A view adaptor that generates all pairwise combinations of the elements of the underlying range.
Definition pairwise_combine.hpp:647
iterator_traits.hpp
Provides various transformation traits for use on iterators.
seqan3::views
The SeqAn namespace for views.
Definition char_strictly_to.hpp:19
std::rel_ops::operator!=
T operator!=(T... args)
std::sqrt
T sqrt(T... args)
std::tie
T tie(T... args)
transformation_trait_or.hpp
Provides seqan3::detail::transformation_trait_or.
concept.hpp
Additional non-standard concepts for ranges.
Hide me