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,61 @@ __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 +_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; + + _It __first1 = __first; + _It __rbegin = __get_rbegin(__first, __last); + for(; __first1 != __rbegin; ++__first1) { + std::iter_swap(__first1, __rbegin); + } + + return shift_right(__first, __last, __n - 1); +} + +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_exec_policy.pass.cpp =================================================================== --- /dev/null +++ libcxx/test/std/algorithms/alg.shift/shift_exec_policy.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// 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); + +#include +#include +#include + +template +void test(T container, It begin, It end) +{ + auto left_check = container[20]; + auto right_check = container[0]; + + auto shifted_container = shift_left(begin, end, 20); + assert(left_check == shifted_container[0]); + shifted_container = shift_right(begin, end, 20); + assert(right_check == shifted_container[0]); +} + +struct E +{ + unsigned x; + bool operator==(E rhs) { return x == rhs.x; } +}; + +int main(int, char**) +{ + std::vector vec(100); + std::iota(vec.begin(), vec.end(), 0); + + std::vector evec; + for (unsigned i = 0; i < 100; ++i) evec.push_back(E { i }); + + int arr[100]; + for (unsigned i = 0; i < 100; ++i) arr[i] = i; + + test(vec, vec.begin(), vec.end()); + test(evec, evec.begin(), evec.end()); + test(arr, arr, arr + 100); + + // Execution policy overloads: + // The execution policies have no effect on the shift function. + shift_left(/*std::execution::sequenced_policy*/ 0, vec.begin(), vec.end(), 0); + shift_right(/*std::execution::parallel_policy*/ 1, vec.begin(), vec.end(), 0); + + return 0; +} 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; +}