]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Defines `boost::hana::detail::has_duplicates`. | |
4 | ||
f51cf556 | 5 | Copyright Louis Dionne 2013-2022 |
7c673cae FG |
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 | ||
1e59de90 | 21 | namespace boost { namespace hana { namespace detail { |
7c673cae FG |
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 | }; | |
1e59de90 | 63 | } }} // end namespace boost::hana |
7c673cae FG |
64 | |
65 | #endif // !BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP |