pairwise_combine.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 <cmath>
#include <ranges>
 
#include <bio/meta/type_traits/transformation_trait_or.hpp>
#include <bio/ranges/concept.hpp>
#include <bio/ranges/views/detail.hpp>
 
namespace bio::ranges::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_type2>
    class basic_iterator;
 
    using iterator = basic_iterator<underlying_range_type>;
    using const_iterator =
      meta::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 &&) noexcept             = default; 
    pairwise_combine_view & operator=(pairwise_combine_view const &)     = default; 
    pairwise_combine_view & operator=(pairwise_combine_view &&) noexcept = 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 <meta::different_from<pairwise_combine_view> other_range_t>
        requires(std::ranges::viewable_range<other_range_t> &&
                 std::constructible_from<underlying_range_type, std::views::all_t<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)};
    }
 
    constexpr auto size() const noexcept
        requires std::ranges::sized_range<underlying_range_type>
    {
        return (std::ranges::size(u_range) * (std::ranges::size(u_range) - 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
{
private:
    template <typename range_type2>
    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_ref_t, underlying_ref_t>;
    using reference         = std::tuple<underlying_ref_t, underlying_ref_t>;
    using pointer           = void;
    using iterator_category = detail::iterator_category_tag_t<underlying_iterator_type>;
    using iterator_concept  = detail::iterator_concept_tag_t<underlying_iterator_type>;
 
    basic_iterator()                                       = default; 
    basic_iterator(basic_iterator const &)                 = default; 
    basic_iterator(basic_iterator &&) noexcept             = default; 
    basic_iterator & operator=(basic_iterator const &)     = default; 
    basic_iterator & operator=(basic_iterator &&) noexcept = 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());
    }
 
    constexpr friend bool operator==(basic_iterator const lhs, basic_iterator const rhs) noexcept(
      noexcept(std::declval<underlying_iterator_type &>() == std::declval<underlying_iterator_type &>()))
    {
        return std::tie(lhs.first_it, lhs.second_it) == std::tie(rhs.first_it, rhs.second_it);
    }
 
    constexpr friend auto operator<=>(basic_iterator const lhs, basic_iterator const rhs) noexcept(
      noexcept(std::declval<underlying_iterator_type &>() < std::declval<underlying_iterator_type &>()))
    {
        return std::tie(lhs.first_it, lhs.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 - static_cast<size_t>(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 bio::ranges::detail
 
namespace bio::ranges::views
{
inline constexpr auto pairwise_combine = detail::adaptor_for_view_without_args<detail::pairwise_combine_view>{};
 
} // namespace bio::ranges::views