| 1 | /*! |
|---|
| 2 | @file |
|---|
| 3 | Defines `boost::hana::detail::has_duplicates`. |
|---|
| 4 | |
|---|
| 5 | Copyright Louis Dionne 2013-2022 |
|---|
| 6 | Distributed under the Boost Software License, Version 1.0. |
|---|
| 7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) |
|---|
| 8 | */ |
|---|
| 9 | |
|---|
| 10 | #ifndef BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP |
|---|
| 11 | #define BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP |
|---|
| 12 | |
|---|
| 13 | #include <boost/hana/config.hpp> |
|---|
| 14 | #include <boost/hana/detail/fast_and.hpp> |
|---|
| 15 | #include <boost/hana/equal.hpp> |
|---|
| 16 | |
|---|
| 17 | #include <cstddef> |
|---|
| 18 | #include <utility> |
|---|
| 19 | |
|---|
| 20 | |
|---|
| 21 | namespace boost { namespace hana { namespace detail { |
|---|
| 22 | template <typename T, typename ...U> |
|---|
| 23 | constexpr std::size_t pack_count() { |
|---|
| 24 | std::size_t c = 0; |
|---|
| 25 | std::size_t expand[] = {0, // avoid empty array |
|---|
| 26 | (decltype(hana::equal(std::declval<T>(), std::declval<U>()))::value |
|---|
| 27 | ? ++c |
|---|
| 28 | : c)... |
|---|
| 29 | }; |
|---|
| 30 | (void)expand; |
|---|
| 31 | |
|---|
| 32 | return c; |
|---|
| 33 | } |
|---|
| 34 | |
|---|
| 35 | //! @ingroup group-details |
|---|
| 36 | //! Returns whether any of the `T`s are duplicate w.r.t. `hana::equal`. |
|---|
| 37 | //! |
|---|
| 38 | //! In particular, this does not check whether all of the `T`s are unique |
|---|
| 39 | //! as _types_, but rather whether they are unique when compared as |
|---|
| 40 | //! `hana::equal(std::declval<T>(), std::declval<U>())`. This assumes |
|---|
| 41 | //! the comparison to return an `IntegralConstant` that can be explicitly |
|---|
| 42 | //! converted to `bool`. |
|---|
| 43 | //! |
|---|
| 44 | //! @note |
|---|
| 45 | //! Since this utility is mostly used in assertions to check that there |
|---|
| 46 | //! are no duplicates in a sequence, we expect it to return `false` most |
|---|
| 47 | //! of the time (otherwise we will assert). Hence, this implementation is |
|---|
| 48 | //! biased towards the fact that we __will__ have to compare every pair of |
|---|
| 49 | //! elements in most cases, and it does not try to be lazy. |
|---|
| 50 | //! |
|---|
| 51 | //! @todo |
|---|
| 52 | //! This implementation is O(n^2). We could do it in O(n), but that would |
|---|
| 53 | //! require a more elaborate setup including storage with O(1) lookup |
|---|
| 54 | //! (which could be based on a compile-time hash). If we implement such |
|---|
| 55 | //! storage for associative sequences, we could use it to optimize this. |
|---|
| 56 | template <typename ...T> |
|---|
| 57 | struct has_duplicates { |
|---|
| 58 | static constexpr bool value = |
|---|
| 59 | sizeof...(T) > 0 && |
|---|
| 60 | !detail::fast_and<(detail::pack_count<T, T...>() == 1)...>::value |
|---|
| 61 | ; |
|---|
| 62 | }; |
|---|
| 63 | } }} // end namespace boost::hana |
|---|
| 64 | |
|---|
| 65 | #endif // !BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP |
|---|
| 66 | |
|---|
