adding comparison operators to fixed_shape. by vakokako · Pull Request #2352

adding comparison operators to fixed_shape. by vakokako · Pull Request #2352 · xtensor-stack/xtensor

Conversation

This fixes issue with xfixed_adaptor, where it's iterators couldn't be compared, as they hold fixed_shape as shape(), the XTENSOR_ASSERT failed.
It's also tempting to add < operator, but my implementation in c++14, which doesn't have fold expressions, contains recursion, in my tests it's still not a problem, since the function is constexpr, but maybe you have more experience with compiler optimizations since it's not guaranteed to be computed statically and it's not a good solution, can you check?

template<class T>
constexpr bool lexicographical_compare(const std::integer_sequence<T>& f1,const std::integer_sequence<T>& f2) {
    return false;
}
template<class T, T V1, T...X1>
constexpr bool lexicographical_compare(const std::integer_sequence<T, V1, X1...>& f1,const std::integer_sequence<T>& f2) {
    return false;
}
template<class T, T V2, T...X2>
constexpr bool lexicographical_compare(const std::integer_sequence<T>& f1,const std::integer_sequence<T, V2, X2...>& f2) {
    return true;
}
template<class T, T V1, T...X1, T V2, T...X2>
constexpr bool lexicographical_compare(const std::integer_sequence<T, V1, X1...>& f1,const std::integer_sequence<T, V2, X2...>& f2) {
    if  (V1 < V2) {
        return true;
    } else if  (V2 < V1) {
        return false;
    } else {
        return lexicographical_compare(std::integer_sequence<T, X1...>{}, std::integer_sequence<T, X2...>{});
    }
}

template <std::size_t... X1, std::size_t... X2>
XTENSOR_FIXED_SHAPE_CONSTEXPR bool operator<(const fixed_shape<X1...>& lhs, const fixed_shape<X2...>& rhs)
{
    return lexicographical_compare(std::index_sequence<X1...>{}, std::index_sequence<X2...>{});
}

Thanks for this fix!

I don't see the implementation of operator< in this PR, maybe you forgot to push the commit? Regarding the implementation, I think you can provide two implementations (one when the number of values is the same in both sequence, one when they're different), and use tag dispatching in the API function:

namespace detail
{
    template <class T, T... I1, T... I2>
    constexpr bool lexicographical_compare(const std::integer_sequence<T, I1...>& f1,const std::integer_sequence<T, I2...>& f2, 
    std::false_type)
    {
        return sizeof...(I1) < sizeof...(I2);
    }

    template <class T, T... I1, T... I2>
    constexpr bool lexicographical_compare(const std::integer_sequence<T, I1...>& f1,const std::integer_sequence<T, I2...>& f2, 
    std::true_type)
    {
        return std::is_same<std::integer_sequence<T, I1...>, std::integer_sequence<T, I2...>>::value;
    }
}

template <class T, T... I1, T... I2>
constexpr bool lexicographical_compare(const std::integer_sequence<T, I1...>& f1,const std::integer_sequence<T, I2...>& f2)
{
    return detail::lexicographical_compare(f1, f2, std::integral_constant<bool, sizeof...(I1) == sizeof...(I2)>());
}

ok, tag dispatch as a replacement of if constexpr is nice, but your implementation doesn't compare the values with < operator, only checks for equality. And in case of not equal sizes, you still need to compare the values. Would that still be done with recursion?

Ha sorry, I've responded too fast ;) The comparison can be implemented this way:

namespace detail
{
    template <bool... bv>
    using bool_sequence = std::integer_sequence<bool, bv...>;

    template <bool... bs>
    using all_true = std::is_same<bool_sequence<true, bs...>, bool_sequence<bs..., true>;

    template <class T, T... I1, T... I2>
    constexpr bool lexicographical_compare(const std::integer_sequence<T, I1...>& f1,const std::integer_sequence<T, I2...>& f2, 
    std::true_type)
    {
        return all_true<(I1 < I2)...>::value;
    }
}

thanks, the only case left that doesn't work: when sizes are different, we still need to compare values:

lexicographical_compare({1, 3}, {1, 2, 3}); // returns true, has to be false

I actually wonder if comparing shapes is equivalent to a lexicographic comparison. Consider {3, 2} and {2, 4, 5}. The former is lexicographiccaly less than the latter. However, due to the broadcasting rules, we should compare {1, 3, 2} and {2, 4, 5}, and in that case the result is the opposite.

On the other hand, we don't provide a special comparison for other kinds of shapes (i.e. std::vector, std::array or xt::svector).

And the implementation I've provided checks that all the values in the first sequence are less than the corresponding values in the second sequence instead of stopping when the first comparison is true. I need to think a bit about it, I don't see any non recursive trivial implementation. We could use a recursion with classes to guarantee the compiler optimizes it away, but that would be far less readable.

Conversation

2 participants