pairwise_combine.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 <cmath>

#include <seqan3/range/concept.hpp>
#include <seqan3/range/view/detail.hpp>
#include <seqan3/std/ranges>

namespace seqan3::detail
{
template <std::ranges::View underlying_range_type>
    requires  std::ranges::ForwardRange<underlying_range_type> && std::ranges::CommonRange<underlying_range_type>
// !\endcond
class pairwise_combine_view : public ranges::view_interface<pairwise_combine_view<underlying_range_type>>
{
private:

    template <typename range_type>
    class iterator_type
    {
    private:

        template <typename other_range_type>
            requires std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        friend class iterator_type;

        using underlying_iterator_type = std::ranges::iterator_t<range_type>;
        using underlying_val_t = typename std::iterator_traits<underlying_iterator_type>::value_type;
        using underlying_ref_t = typename std::iterator_traits<underlying_iterator_type>::reference;
    public:

        using difference_type   = std::ptrdiff_t;
        using value_type        = std::tuple<underlying_val_t, underlying_val_t>;
        using reference         = std::tuple<underlying_ref_t, underlying_ref_t>;
        using pointer           = void;
        using iterator_category = iterator_tag_t<underlying_iterator_type>;

        constexpr iterator_type()                                  noexcept = default; 
        constexpr iterator_type(iterator_type const &)             noexcept = default; 
        constexpr iterator_type(iterator_type &&)                  noexcept = default; 
        constexpr iterator_type & operator=(iterator_type const &) noexcept = default; 
        constexpr iterator_type & operator=(iterator_type &&)      noexcept = default; 
        ~iterator_type()                                           noexcept = default; 

        constexpr iterator_type(underlying_iterator_type iter,
                                underlying_iterator_type begin_it,
                                underlying_iterator_type end_it) noexcept :
            first_it{iter},
            second_it{++iter},
            begin_it{begin_it},
            end_it{end_it}
        {}

        template <std::ConvertibleTo<range_type &> other_range_type>
            requires std::Same<std::remove_const_t<other_range_type>, std::remove_const_t<range_type>>
        constexpr iterator_type(iterator_type<other_range_type> other) noexcept :
            iterator_type{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 {*first_it, *second_it};
        }

        constexpr reference operator[](size_t const index)
            noexcept(noexcept(std::declval<iterator_type &>().from_index(1)))
            requires std::RandomAccessIterator<underlying_iterator_type>
        {
            from_index(index);
            return **this;
        }

        constexpr iterator_type & 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 iterator_type operator++(int /*post-increment*/)
            noexcept(noexcept(std::declval<underlying_iterator_type &>()++))
        {
            iterator_type tmp{*this};
            ++*this;
            return tmp;
        }

        constexpr iterator_type & operator--(/*pre-decrement*/)
            noexcept(noexcept(--std::declval<underlying_iterator_type &>()))
            requires std::BidirectionalIterator<underlying_iterator_type>
        {
            if (--second_it == first_it)
            {
                --first_it;
                second_it = end_it;
                --second_it;
            }
            return *this;
        }

        constexpr iterator_type operator--(int /*post-decrement*/)
            noexcept(noexcept(std::declval<underlying_iterator_type &>()--))
            requires std::BidirectionalIterator<underlying_iterator_type>
        {
            iterator_type tmp{*this};
            --*this;
            return tmp;
        }

        constexpr iterator_type & operator+=(difference_type const offset)
            noexcept(noexcept(std::declval<iterator_type &>().from_index(1)))
            requires std::RandomAccessIterator<underlying_iterator_type>
        {
            from_index(to_index() + offset);
            return *this;
        }

        constexpr iterator_type operator+(difference_type const offset)
            noexcept(noexcept(std::declval<iterator_type &>() += 1))
            requires std::RandomAccessIterator<underlying_iterator_type>
        {
            iterator_type tmp{*this};
            return (tmp += offset);
        }

        constexpr friend iterator_type operator+(difference_type const offset, iterator_type iter)
            noexcept(noexcept(std::declval<iterator_type<range_type> &>().from_index(1)))
            requires std::RandomAccessIterator<underlying_iterator_type>
        {
            iter.from_index(iter.to_index() + offset);
            return iter;
        }

        constexpr iterator_type & operator-=(difference_type const offset)
            noexcept(noexcept(std::declval<iterator_type &>().from_index(1)))
            requires std::RandomAccessIterator<underlying_iterator_type>
        {
            from_index(to_index() - offset);
            return *this;
        }

        constexpr iterator_type operator-(difference_type const offset)
            noexcept(noexcept(std::declval<iterator_type &>() -= 1))
            requires std::RandomAccessIterator<underlying_iterator_type>
        {
            iterator_type tmp{*this};
            return (tmp -= offset);
        }

        template <typename other_range_type>
            requires std::RandomAccessIterator<underlying_iterator_type> &&
                     std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        constexpr difference_type operator-(iterator_type<other_range_type> const & rhs) const
            noexcept(noexcept(std::declval<iterator_type &>().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::EqualityComparableWith<underlying_iterator_type, std::ranges::iterator_t<other_range_type>> &&
                     std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        constexpr bool operator==(iterator_type<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::EqualityComparableWith<underlying_iterator_type, std::ranges::iterator_t<other_range_type>> &&
                     std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        constexpr bool operator!=(iterator_type<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::StrictTotallyOrderedWith<underlying_iterator_type,
                                                   std::ranges::iterator_t<other_range_type>> &&
                     std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        constexpr bool operator<(iterator_type<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::StrictTotallyOrderedWith<underlying_iterator_type,
                                                   std::ranges::iterator_t<other_range_type>> &&
                     std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        constexpr bool operator>(iterator_type<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::StrictTotallyOrderedWith<underlying_iterator_type,
                                                   std::ranges::iterator_t<other_range_type>> &&
                     std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        constexpr bool operator<=(iterator_type<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::StrictTotallyOrderedWith<underlying_iterator_type,
                                                   std::ranges::iterator_t<other_range_type>> &&
                     std::Same<std::remove_const_t<range_type>, std::remove_const_t<other_range_type>>
        constexpr bool operator>=(iterator_type<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::RandomAccessIterator<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::RandomAccessIterator<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{};
    };

public:

    using iterator          = iterator_type<underlying_range_type>;
    using const_iterator    = transformation_trait_or_t<std::type_identity<iterator_type<underlying_range_type const>>,
                                                        void>;
    using reference         = typename iterator::reference;
    using const_reference   = reference;
    using value_type        = typename iterator::value_type;
    using size_type         = detail::transformation_trait_or_t<seqan3::size_type<underlying_range_type>, void>;
    using difference_type   = difference_type_t<iterator>;

    constexpr pairwise_combine_view() = default;
    constexpr pairwise_combine_view(pairwise_combine_view const &) = default;
    constexpr pairwise_combine_view(pairwise_combine_view &&) = default;
    constexpr pairwise_combine_view & operator=(pairwise_combine_view const &) = default;
    constexpr 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::BidirectionalRange<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::SizedRange<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<remove_cvref_t<other_range_t>, pairwise_combine_view> &&
                 std::ranges::ViewableRange<other_range_t> &&  // Must come after self type check to avoid conflicts with the move constructor.
                 std::Constructible<underlying_range_type, 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 ViewableRange.
            //      std::Constructible<underlying_range_type, decltype(std::ranges::view::all(std::declval<other_range_t &&>()))>
    explicit constexpr pairwise_combine_view(other_range_t && range) :
        pairwise_combine_view{std::ranges::view::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 ConstIterableRange<underlying_range_type>
    {
        return {std::ranges::begin(u_range), std::ranges::begin(u_range), std::ranges::end(u_range)};
    }

    constexpr const_iterator cbegin() const noexcept
        requires ConstIterableRange<underlying_range_type>
    {
        return begin();
    }

    constexpr iterator end() noexcept
    {
        return {back_iterator, std::ranges::begin(u_range), std::ranges::end(u_range)};
    }

    constexpr const_iterator end() const noexcept
        requires ConstIterableRange<underlying_range_type>
    {
        return {back_iterator, std::ranges::begin(u_range), std::ranges::end(u_range)};
    }

    constexpr const_iterator cend() const noexcept
        requires ConstIterableRange<underlying_range_type>
    {
        return end();
    }

    constexpr size_type size() const noexcept
        requires std::ranges::SizedRange<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::ViewableRange other_range_t>
pairwise_combine_view(other_range_t && range) ->
    pairwise_combine_view<std::ranges::all_view<other_range_t>>;

} // namespace seqan3::detail

namespace seqan3::view
{
inline constexpr auto pairwise_combine = detail::adaptor_for_view_without_args<detail::pairwise_combine_view>{};

} // namespace seqan3::view