aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm-project/libcxx/include/__algorithm/rotate.h
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/libcxx/include/__algorithm/rotate.h')
-rw-r--r--contrib/llvm-project/libcxx/include/__algorithm/rotate.h214
1 files changed, 214 insertions, 0 deletions
diff --git a/contrib/llvm-project/libcxx/include/__algorithm/rotate.h b/contrib/llvm-project/libcxx/include/__algorithm/rotate.h
new file mode 100644
index 000000000000..fcf8444a65a0
--- /dev/null
+++ b/contrib/llvm-project/libcxx/include/__algorithm/rotate.h
@@ -0,0 +1,214 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_ROTATE_H
+#define _LIBCPP___ALGORITHM_ROTATE_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/move.h>
+#include <__algorithm/move_backward.h>
+#include <__algorithm/swap_ranges.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/prev.h>
+#include <__utility/move.h>
+#include <__utility/swap.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _AlgPolicy, class _ForwardIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
+__rotate_left(_ForwardIterator __first, _ForwardIterator __last)
+{
+ typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
+ value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__first);
+ // TODO(ranges): pass `_AlgPolicy` to `move`.
+ _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
+ *__lm1 = _VSTD::move(__tmp);
+ return __lm1;
+}
+
+template <class _AlgPolicy, class _BidirectionalIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
+__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
+{
+ typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+ // TODO(ranges): pass `_AlgPolicy` to `prev`.
+ _BidirectionalIterator __lm1 = _VSTD::prev(__last);
+ value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__lm1);
+ // TODO(ranges): pass `_AlgPolicy` to `move_backward`.
+ _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
+ *__first = _VSTD::move(__tmp);
+ return __fp1;
+}
+
+template <class _AlgPolicy, class _ForwardIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator
+__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
+{
+ _ForwardIterator __i = __middle;
+ while (true)
+ {
+ _IterOps<_AlgPolicy>::iter_swap(__first, __i);
+ ++__first;
+ if (++__i == __last)
+ break;
+ if (__first == __middle)
+ __middle = __i;
+ }
+ _ForwardIterator __r = __first;
+ if (__first != __middle)
+ {
+ __i = __middle;
+ while (true)
+ {
+ _IterOps<_AlgPolicy>::iter_swap(__first, __i);
+ ++__first;
+ if (++__i == __last)
+ {
+ if (__first == __middle)
+ break;
+ __i = __middle;
+ }
+ else if (__first == __middle)
+ __middle = __i;
+ }
+ }
+ return __r;
+}
+
+template<typename _Integral>
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _Integral
+__algo_gcd(_Integral __x, _Integral __y)
+{
+ do
+ {
+ _Integral __t = __x % __y;
+ __x = __y;
+ __y = __t;
+ } while (__y);
+ return __x;
+}
+
+template <class _AlgPolicy, typename _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
+__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
+{
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+
+ const difference_type __m1 = __middle - __first;
+ const difference_type __m2 = __last - __middle;
+ if (__m1 == __m2)
+ {
+ // TODO(ranges): pass `_AlgPolicy` to `swap_ranges`.
+ _VSTD::swap_ranges(__first, __middle, __middle);
+ return __middle;
+ }
+ const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
+ for (_RandomAccessIterator __p = __first + __g; __p != __first;)
+ {
+ value_type __t(_IterOps<_AlgPolicy>::__iter_move(--__p));
+ _RandomAccessIterator __p1 = __p;
+ _RandomAccessIterator __p2 = __p1 + __m1;
+ do
+ {
+ *__p1 = _IterOps<_AlgPolicy>::__iter_move(__p2);
+ __p1 = __p2;
+ const difference_type __d = __last - __p2;
+ if (__m1 < __d)
+ __p2 += __m1;
+ else
+ __p2 = __first + (__m1 - __d);
+ } while (__p2 != __p);
+ *__p1 = _VSTD::move(__t);
+ }
+ return __first + __m2;
+}
+
+template <class _AlgPolicy, class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
+__rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
+ _VSTD::forward_iterator_tag)
+{
+ typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
+ if (is_trivially_move_assignable<value_type>::value)
+ {
+ if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+ return std::__rotate_left<_AlgPolicy>(__first, __last);
+ }
+ return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
+}
+
+template <class _AlgPolicy, class _BidirectionalIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
+__rotate_impl(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
+ bidirectional_iterator_tag)
+{
+ typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+ if (is_trivially_move_assignable<value_type>::value)
+ {
+ if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+ return std::__rotate_left<_AlgPolicy>(__first, __last);
+ if (_IterOps<_AlgPolicy>::next(__middle) == __last)
+ return std::__rotate_right<_AlgPolicy>(__first, __last);
+ }
+ return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
+}
+
+template <class _AlgPolicy, class _RandomAccessIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
+__rotate_impl(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
+ random_access_iterator_tag)
+{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+ if (is_trivially_move_assignable<value_type>::value)
+ {
+ if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+ return std::__rotate_left<_AlgPolicy>(__first, __last);
+ if (_IterOps<_AlgPolicy>::next(__middle) == __last)
+ return std::__rotate_right<_AlgPolicy>(__first, __last);
+ return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);
+ }
+ return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
+}
+
+template <class _AlgPolicy, class _RandomAccessIterator, class _IterCategory>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+_RandomAccessIterator __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle,
+ _RandomAccessIterator __last, _IterCategory __iter_category) {
+ if (__first == __middle)
+ return __last;
+ if (__middle == __last)
+ return __first;
+
+ return std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __iter_category);
+}
+
+template <class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
+{
+ return std::__rotate<_ClassicAlgPolicy>(__first, __middle, __last,
+ typename iterator_traits<_ForwardIterator>::iterator_category());
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_ROTATE_H