boost/hana/detail/has_duplicates.hpp

   1 /*!
   2 @file
   3 Defines `boost::hana::detail::has_duplicates`.
   4
   5 @copyright Louis Dionne 2013-2017
   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 BOOST_HANA_NAMESPACE_BEGIN 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 } BOOST_HANA_NAMESPACE_END
  64
  65 #endif // !BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP