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/iterator_operations.h>
  15 #include <__algorithm/reverse.h>
  16 #include <__config>
  17 #include <__iterator/iterator_traits.h>
  18 #include <__utility/move.h>
  19 #include <__utility/pair.h>
  20
  21 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  22 #  pragma GCC system_header
  23 #endif
  24
  25 _LIBCPP_BEGIN_NAMESPACE_STD
  26
  27 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator, class _Sentinel>
  28 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_BidirectionalIterator, bool>
  29 __next_permutation(_BidirectionalIterator __first, _Sentinel __last, _Compare&& __comp)
  30 {
  31     using _Result = pair<_BidirectionalIterator, bool>;
  32
  33     _BidirectionalIterator __last_iter = _IterOps<_AlgPolicy>::next(__first, __last);
  34     _BidirectionalIterator __i = __last_iter;
  35     if (__first == __last || __first == --__i)
  36         return _Result(std::move(__last_iter), false);
  37
  38     while (true)
  39     {
  40         _BidirectionalIterator __ip1 = __i;
  41         if (__comp(*--__i, *__ip1))
  42         {
  43             _BidirectionalIterator __j = __last_iter;
  44             while (!__comp(*__i, *--__j))
  45                 ;
  46             _IterOps<_AlgPolicy>::iter_swap(__i, __j);
  47             std::__reverse<_AlgPolicy>(__ip1, __last_iter);
  48             return _Result(std::move(__last_iter), true);
  49         }
  50         if (__i == __first)
  51         {
  52             std::__reverse<_AlgPolicy>(__first, __last_iter);
  53             return _Result(std::move(__last_iter), false);
  54         }
  55     }
  56 }
  57
  58 template <class _BidirectionalIterator, class _Compare>
  59 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
  60 bool
  61 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
  62 {
  63   return std::__next_permutation<_ClassicAlgPolicy>(
  64       std::move(__first), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp)).second;
  65 }
  66
  67 template <class _BidirectionalIterator>
  68 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
  69 bool
  70 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
  71 {
  72     return _VSTD::next_permutation(__first, __last, __less<>());
  73 }
  74
  75 _LIBCPP_END_NAMESPACE_STD
  76
  77 #endif // _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H