chromium/third_party/libc++/src/include/__algorithm/is_permutation.h

// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___ALGORITHM_IS_PERMUTATION_H
#define _LIBCPP___ALGORITHM_IS_PERMUTATION_H

#include <__algorithm/comp.h>
#include <__algorithm/iterator_operations.h>
#include <__config>
#include <__functional/identity.h>
#include <__functional/invoke.h>
#include <__iterator/concepts.h>
#include <__iterator/distance.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/next.h>
#include <__type_traits/is_callable.h>
#include <__utility/move.h>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_PUSH_MACROS
#include <__undef_macros>

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class = void>
struct _ConstTimeDistance : false_type { … };

#if _LIBCPP_STD_VER >= 20

_ConstTimeDistance<_Iter1, _Sent1, _Iter2, _Sent2, __enable_if_t<sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>>>;

#else

template <class _Iter1, class _Iter2>
struct _ConstTimeDistance<
    _Iter1,
    _Iter1,
    _Iter2,
    _Iter2,
    __enable_if_t< is_same<typename iterator_traits<_Iter1>::iterator_category, random_access_iterator_tag>::value &&
                   is_same<typename iterator_traits<_Iter2>::iterator_category, random_access_iterator_tag>::value > >
    : true_type {};

#endif // _LIBCPP_STD_VER >= 20

// Internal functions

// For each element in [f1, l1) see if there are the same number of equal elements in [f2, l2)
template <class _AlgPolicy,
          class _Iter1,
          class _Sent1,
          class _Iter2,
          class _Sent2,
          class _Proj1,
          class _Proj2,
          class _Pred>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation_impl(
    _Iter1 __first1,
    _Sent1 __last1,
    _Iter2 __first2,
    _Sent2 __last2,
    _Pred&& __pred,
    _Proj1&& __proj1,
    _Proj2&& __proj2) { … }

// 2+1 iterators, predicate. Not used by range algorithms.
template <class _AlgPolicy, class _ForwardIterator1, class _Sentinel1, class _ForwardIterator2, class _BinaryPredicate>
_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
    _ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, _BinaryPredicate&& __pred) { … }

// 2+2 iterators, predicate, non-constant time `distance`.
template <class _AlgPolicy,
          class _Iter1,
          class _Sent1,
          class _Iter2,
          class _Sent2,
          class _Proj1,
          class _Proj2,
          class _Pred>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
    _Iter1 __first1,
    _Sent1 __last1,
    _Iter2 __first2,
    _Sent2 __last2,
    _Pred&& __pred,
    _Proj1&& __proj1,
    _Proj2&& __proj2,
    /*_ConstTimeDistance=*/false_type) { … }

// 2+2 iterators, predicate, specialization for constant-time `distance` call.
template <class _AlgPolicy,
          class _Iter1,
          class _Sent1,
          class _Iter2,
          class _Sent2,
          class _Proj1,
          class _Proj2,
          class _Pred>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
    _Iter1 __first1,
    _Sent1 __last1,
    _Iter2 __first2,
    _Sent2 __last2,
    _Pred&& __pred,
    _Proj1&& __proj1,
    _Proj2&& __proj2,
    /*_ConstTimeDistance=*/true_type) { … }

// 2+2 iterators, predicate
template <class _AlgPolicy,
          class _Iter1,
          class _Sent1,
          class _Iter2,
          class _Sent2,
          class _Proj1,
          class _Proj2,
          class _Pred>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __is_permutation(
    _Iter1 __first1,
    _Sent1 __last1,
    _Iter2 __first2,
    _Sent2 __last2,
    _Pred&& __pred,
    _Proj1&& __proj1,
    _Proj2&& __proj2) { … }

// Public interface

// 2+1 iterators, predicate
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
_LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation(
    _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred) { … }

// 2+1 iterators
template <class _ForwardIterator1, class _ForwardIterator2>
_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { … }

#if _LIBCPP_STD_VER >= 14

// 2+2 iterators
template <class _ForwardIterator1, class _ForwardIterator2>
_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation(
    _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { … }

// 2+2 iterators, predicate
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool is_permutation(
    _ForwardIterator1 __first1,
    _ForwardIterator1 __last1,
    _ForwardIterator2 __first2,
    _ForwardIterator2 __last2,
    _BinaryPredicate __pred) { … }

#endif // _LIBCPP_STD_VER >= 14

_LIBCPP_END_NAMESPACE_STD

_LIBCPP_POP_MACROS

#endif // _LIBCPP___ALGORITHM_IS_PERMUTATION_H