contrib/llvm-project/libcxx/include/__algorithm/next_permutation.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H
  10 #define _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H
  11
  12 #include <__algorithm/comp.h>
  13 #include <__algorithm/comp_ref_type.h>
  14 #include <__algorithm/reverse.h>
  15 #include <__config>
  16 #include <__iterator/iterator_traits.h>
  17 #include <__utility/swap.h>
  18
  19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  20 #pragma GCC system_header
  21 #endif
  22
  23 _LIBCPP_BEGIN_NAMESPACE_STD
  24
  25 template <class _Compare, class _BidirectionalIterator>
  26 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
  27 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
  28 {
  29     _BidirectionalIterator __i = __last;
  30     if (__first == __last || __first == --__i)
  31         return false;
  32     while (true)
  33     {
  34         _BidirectionalIterator __ip1 = __i;
  35         if (__comp(*--__i, *__ip1))
  36         {
  37             _BidirectionalIterator __j = __last;
  38             while (!__comp(*__i, *--__j))
  39                 ;
  40             swap(*__i, *__j);
  41             _VSTD::reverse(__ip1, __last);
  42             return true;
  43         }
  44         if (__i == __first)
  45         {
  46             _VSTD::reverse(__first, __last);
  47             return false;
  48         }
  49     }
  50 }
  51
  52 template <class _BidirectionalIterator, class _Compare>
  53 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
  54 bool
  55 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
  56 {
  57     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
  58     return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp);
  59 }
  60
  61 template <class _BidirectionalIterator>
  62 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
  63 bool
  64 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
  65 {
  66     return _VSTD::next_permutation(__first, __last,
  67                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
  68 }
  69
  70 _LIBCPP_END_NAMESPACE_STD
  71
  72 #endif // _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H