diff options
Diffstat (limited to 'contrib/libc++/include/algorithm')
| -rw-r--r-- | contrib/libc++/include/algorithm | 113 |
1 files changed, 85 insertions, 28 deletions
diff --git a/contrib/libc++/include/algorithm b/contrib/libc++/include/algorithm index d924a7d..1ce14b4 100644 --- a/contrib/libc++/include/algorithm +++ b/contrib/libc++/include/algorithm @@ -593,7 +593,7 @@ template <class BidirectionalIterator, class Compare> #include <utility> #include <memory> #include <iterator> -#include <cstdlib> +#include <cstddef> #include <__undef_min_max> @@ -2103,12 +2103,31 @@ reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _Out template <class _ForwardIterator> _ForwardIterator -__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, false_type) +__rotate_left(_ForwardIterator __first, _ForwardIterator __last) +{ + typedef typename iterator_traits<_ForwardIterator>::value_type value_type; + value_type __tmp = _VSTD::move(*__first); + _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first); + *__lm1 = _VSTD::move(__tmp); + return __lm1; +} + +template <class _BidirectionalIterator> +_BidirectionalIterator +__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) +{ + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; + _BidirectionalIterator __lm1 = _VSTD::prev(__last); + value_type __tmp = _VSTD::move(*__lm1); + _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last); + *__first = _VSTD::move(__tmp); + return __fp1; +} + +template <class _ForwardIterator> +_ForwardIterator +__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { - if (__first == __middle) - return __last; - if (__middle == __last) - return __first; _ForwardIterator __i = __middle; while (true) { @@ -2156,15 +2175,11 @@ __gcd(_Integral __x, _Integral __y) template<typename _RandomAccessIterator> _RandomAccessIterator -__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, true_type) +__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; - if (__first == __middle) - return __last; - if (__middle == __last) - return __first; const difference_type __m1 = __middle - __first; const difference_type __m2 = __last - __middle; if (__m1 == __m2) @@ -2172,15 +2187,15 @@ __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomA _VSTD::swap_ranges(__first, __middle, __middle); return __middle; } - const difference_type __g = __gcd(__m1, __m2); + const difference_type __g = _VSTD::__gcd(__m1, __m2); for (_RandomAccessIterator __p = __first + __g; __p != __first;) { - value_type __t(*--__p); + value_type __t(_VSTD::move(*--__p)); _RandomAccessIterator __p1 = __p; _RandomAccessIterator __p2 = __p1 + __m1; do { - *__p1 = *__p2; + *__p1 = _VSTD::move(*__p2); __p1 = __p2; const difference_type __d = __last - __p2; if (__m1 < __d) @@ -2188,7 +2203,7 @@ __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomA else __p2 = __first + (__m1 - __d); } while (__p2 != __p); - *__p1 = __t; + *__p1 = _VSTD::move(__t); } return __first + __m2; } @@ -2196,22 +2211,64 @@ __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomA template <class _ForwardIterator> inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator +__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, + _VSTD::forward_iterator_tag) +{ + typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type; + if (_VSTD::is_trivially_move_assignable<value_type>::value) + { + if (_VSTD::next(__first) == __middle) + return _VSTD::__rotate_left(__first, __last); + } + return _VSTD::__rotate_forward(__first, __middle, __last); +} + +template <class _BidirectionalIterator> +inline _LIBCPP_INLINE_VISIBILITY +_BidirectionalIterator +__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, + _VSTD::bidirectional_iterator_tag) +{ + typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type; + if (_VSTD::is_trivially_move_assignable<value_type>::value) + { + if (_VSTD::next(__first) == __middle) + return _VSTD::__rotate_left(__first, __last); + if (_VSTD::next(__middle) == __last) + return _VSTD::__rotate_right(__first, __last); + } + return _VSTD::__rotate_forward(__first, __middle, __last); +} + +template <class _RandomAccessIterator> +inline _LIBCPP_INLINE_VISIBILITY +_RandomAccessIterator +__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, + _VSTD::random_access_iterator_tag) +{ + typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type; + if (_VSTD::is_trivially_move_assignable<value_type>::value) + { + if (_VSTD::next(__first) == __middle) + return _VSTD::__rotate_left(__first, __last); + if (_VSTD::next(__middle) == __last) + return _VSTD::__rotate_right(__first, __last); + return _VSTD::__rotate_gcd(__first, __middle, __last); + } + return _VSTD::__rotate_forward(__first, __middle, __last); +} + +template <class _ForwardIterator> +inline _LIBCPP_INLINE_VISIBILITY +_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { + if (__first == __middle) + return __last; + if (__middle == __last) + return __first; return _VSTD::__rotate(__first, __middle, __last, - integral_constant - < - bool, - is_convertible - < - typename iterator_traits<_ForwardIterator>::iterator_category, - random_access_iterator_tag - >::value && - is_trivially_copy_assignable - < - typename iterator_traits<_ForwardIterator>::value_type - >::value - >()); + typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category()); } // rotate_copy |
