Index: libcxx/include/algorithm =================================================================== --- libcxx/include/algorithm +++ libcxx/include/algorithm @@ -631,6 +631,19 @@ bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); +template + ForwardIterator shift_left(ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); +template + ForwardIterator shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); +template + ForwardIterator shift_right(ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); +template + ForwardIterator shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); + } // std */ @@ -5674,6 +5687,77 @@ __less::value_type>()); } +#if _LIBCPP_VERSION > 17 + +template +_LIBCPP_CONSTEXPR_AFTER_CXX14 _It +shift_left(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n) +{ + auto __size = _VSTD::distance(__first, __last); + if (__n <= 0 || __size <= 0 || __n >= __size) return __first; + + _It __first1 = __first; + _It __first2 = __first; + for(__first2++; __first2 != __last; ++__first1, (void)++__first2) { + std::iter_swap(__first1, __first2); + } + + return shift_left(__first, __last, __n - 1); +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX14 _It +shift_left(_Ep&&, _It __first, _It __last, typename iterator_traits<_It>::difference_type __n) +{ return shift_left(__first, __last, __n); } + +template +_LIBCPP_CONSTEXPR_AFTER_CXX14 _It +__get_rbegin(_It __first, _It __last) +{ + _It __first1 = __first; + for (__first1++; __first1 != __last; ++__first, (void)++__first1) {} + return __first; +} + +template::difference_type> +_LIBCPP_CONSTEXPR_AFTER_CXX14 _It +__n_before_end(_It __first, _It __last, _St __n) +{ + _It __first1 = __first; + for (_St __i = 0; __i < __n; ++__i, (void)++__first1) {} + for (; __first1 != __last; ++__first, (void)++__first1) {} + return __first; +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX14 _It +shift_right(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n) +{ + auto __size = _VSTD::distance(__first, __last); + if (__n <= 0 || __size <= 0 || __n >= __size) return __first; + if (__n > __size / 2) return shift_left(__first, __last, __size - __n); + + _It __current = __first; + _It __before = __n_before_end(__first, __last, __n); + _It __rbegin = __get_rbegin(__first, __last); + + while(__current != __rbegin) { + _It __before1 = __before; + do { + std::iter_swap(__current++, __before1++); + } while (__before1 != __last && __current != __rbegin); + } + + return __first; +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX14 _It +shift_right(_Ep&&, _It __first, _It __last, typename iterator_traits<_It>::difference_type __n) +{ return shift_right(__first, __last, __n); } + +#endif // _LIBCPP_VERSION > 17 + _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS Index: libcxx/test/std/algorithms/alg.shift/shift_left.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/algorithms/alg.shift/shift_left.pass.cpp @@ -0,0 +1,161 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 + +// + +// template +// constexpr ForwardIterator +// shift_left(ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); // C++20 +// +// Effects: If n <= 0 or n >= last - first, does nothing. +// Otherwise, moves the element from position first + n + i into position +// first + i for each non-negative integer i < (last - first) - n. +// Does so in order starting from i = 0 and proceeding to i = (last - first) - n - 1. +// +// Returns: first + (last - first - n) if n is positive and n < last - first, +// otherwise first if n is positive, otherwise last. + + +#include +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" + +constexpr bool test_constexpr() { + int ia[] = {0, 1, 1, 3, 4}; + const int expected[] = {1, 1, 3, 4, 0}; + const size_t shift = 1; + + std::shift_left(std::begin(ia), std::end(ia), shift); + return std::equal(std::begin(expected), std::end(expected), std::begin(ia)); +} + +struct MInt +{ + MInt (int v) : v_{v} {} + MInt ( ) : v_{0} {} + + MInt (const MInt &rhs) : v_{rhs.v_} {} + MInt ( MInt &&rhs) : v_{rhs.v_} { rhs.v_ = -1;} + + MInt& operator=(const MInt &rhs) { v_ = rhs.v_; return *this; } + MInt& operator=( MInt &&rhs) { v_ = rhs.v_; rhs.v_ = -1; return *this; } + + int v_; +}; + +template +bool hasBeenMoved(const T&) { return true; } + +template <> +bool hasBeenMoved(const MInt& t) { return t.v_ == -1; } + +bool operator==(const MInt &rhs, const MInt &lhs) +{ return lhs.v_ == rhs.v_ && lhs.v_ != -1; } // we shouldn't be comparing moved-from objects + +template +void test() +{ + using T = typename std::iterator_traits::value_type; + + // n < 0 + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, -1); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n == 0 + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 0); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n > 0 && n < len + { + T input[] = {0, 1, 2}; + const T expected[] = {1, 2, 0}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 1); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 3, 4, 5, 6, 7, 8, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 2); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 7, 8, 1, 2, 3, 4, 5, 6 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 6); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n == len + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, std::size(input)); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n > len + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, std::size(input) + 1); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } +} + +int main(int, char**) +{ + static_assert(test_constexpr()); + + test>(); + test>(); + test>(); + test(); + + test>(); + test>(); + test>(); + test(); + + return 0; +} Index: libcxx/test/std/algorithms/alg.shift/shift_right.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/algorithms/alg.shift/shift_right.pass.cpp @@ -0,0 +1,165 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17 + +// + +// template +// constexpr ForwardIterator +// shift_right(ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); // C++20 +// +// Effects: If n <= 0 or n >= last - first, does nothing. +// Otherwise, moves the element from position first + i into position +// first + n + i for each non-negative integer i < (last - first) - n. +// If ForwardIterator satisfies the Cpp17BidirectionalIterator requirements, +// does so in order starting from i = (last - first) - n - 1 and proceeding to i = 0. +// +// Returns: first + n if n is positive and n < last - first, +// otherwise last if n is positive, otherwise first. + +#include +#include +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" + +constexpr bool test_constexpr() { + int ia[] = {0, 1, 1, 3, 4}; + const int expected[] = {4, 0, 1, 1, 3}; + const size_t shift = 1; + + std::shift_right(std::begin(ia), std::end(ia), shift); + return std::equal(std::begin(expected), std::end(expected), std::begin(ia)); +} + +struct MInt +{ + MInt (int v) : v_{v} {} + MInt ( ) : v_{0} {} + + MInt (const MInt &rhs) : v_{rhs.v_} {} + MInt ( MInt &&rhs) : v_{rhs.v_} { rhs.v_ = -1;} + + MInt& operator=(const MInt &rhs) { v_ = rhs.v_; return *this; } + MInt& operator=( MInt &&rhs) { v_ = rhs.v_; rhs.v_ = -1; return *this; } + + int v_; +}; + +template +bool hasBeenMoved(const T&) { return true; } + +template <> +bool hasBeenMoved(const MInt& t) { + std::cout << t.v_ << std::endl; + return t.v_ == -1; +} + +bool operator==(const MInt &rhs, const MInt &lhs) +{ return lhs.v_ == rhs.v_ && lhs.v_ != -1; } // we shouldn't be comparing moved-from objects + +template +void test() +{ + using T = typename std::iterator_traits::value_type; + + // n < 0 + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, -1); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n == 0 + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 0); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n > 0 && n < len + { + T input[] = {0, 1, 2}; + const T expected[] = {2, 0, 1}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 1); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 7, 8, 1, 2, 3, 4, 5, 6 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 2); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 3, 4, 5, 6, 7, 8, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 6); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n == len + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, std::size(input)); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } + + // n > len + { + T input[] = {0, 1, 2}; + const T expected[] = {0, 1, 2}; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, std::size(input) + 1); + assert(std::equal(std::begin(expected), std::end(expected), b)); + assert(it == b); + } +} + +int main(int, char**) +{ + static_assert(test_constexpr()); + + test>(); + test>(); + test>(); + test(); + + test>(); + test>(); + test>(); + test(); + + return 0; +}