Index: include/algorithm =================================================================== --- include/algorithm +++ 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 */ @@ -5781,6 +5794,72 @@ __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; + + for (unsigned __i = 0; __i < __n; ++__i, ++__first); + + return __first; +} + +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 typename enable_if< + !is_same::value, + _It +>::type +__shift_right_impl(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n, _Ft) +{ + auto __size = _VSTD::distance(__first, __last); + if (__n <= 0 || __size <= 0 || __n >= __size) return __first; + + auto __mid = __last; + for (unsigned __i = 0; __i < __n; ++__i, --__mid); + + return move_backward(__first, __mid, __last); +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX14 typename enable_if< + is_same::value, + _It +>::type +__shift_right_impl(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n, _Ft) +{ + auto __size = _VSTD::distance(__first, __last); + if (__n <= 0 || __size <= 0 || __n >= __size) return __first; + + auto __mid = __first; + for (unsigned __i = 0; __i < (__size - __n); ++__i, ++__mid); + __rotate_forward(__first, __mid, __last); + + for (unsigned __i = 0; __i < __n; ++__i, ++__first); + return __first; +} + +template +_LIBCPP_CONSTEXPR_AFTER_CXX14 _It +shift_right(_It __first, _It __last, typename iterator_traits<_It>::difference_type __n) +{ return __shift_right_impl(__first, __last, __n, + typename std::iterator_traits<_It>::iterator_category()); } + +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: test/std/algorithms/alg.shift/shift_exec_policy.pass.cpp =================================================================== --- /dev/null +++ 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: test/std/algorithms/alg.shift/shift_left.pass.cpp =================================================================== --- /dev/null +++ test/std/algorithms/alg.shift/shift_left.pass.cpp @@ -0,0 +1,137 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "test_macros.h" +#include "test_iterators.h" + +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_; +}; + +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 + for (size_t n = 1; n < 10; ++n) + { + T input[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + + std::array expected; + std::iota(expected.begin(), expected.end(), n); + + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, n); + + for (unsigned x = 0; x < 10 - n; ++x) + assert(*it++ == expected[x]); + + // The complication here (the "min") is because things are different when the + // shift count is more than half the size of the sequence. + // I don't think this is necessary? + // assert(std::all_of(std::next(b, std::size(input) - std::min(n, std::size(input) - n)), e, hasBeenMoved)); + } + + // 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**) +{ + test>(); + test>(); + test>(); + test(); + + test>(); + test>(); + test>(); + test(); + + return 0; +} Index: test/std/algorithms/alg.shift/shift_right.pass.cpp =================================================================== --- /dev/null +++ test/std/algorithms/alg.shift/shift_right.pass.cpp @@ -0,0 +1,137 @@ +//===----------------------------------------------------------------------===// +// +// 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" + +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_; +}; + +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 + for (size_t n = 1; n < 10; ++n) + { + T input[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + + std::array expected; + std::iota(expected.begin(), expected.end(), 0); + + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, n); + + for (unsigned i = 0; i < 10 - n; ++i) + assert(*it++ == expected[i]); + + // The complication here (the "min") is because things are different when the + // shift count is more than half the size of the sequence. + // I don't think this is necessary? + // assert(std::all_of(std::next(b, std::size(input) - std::min(n, std::size(input) - n)), e, hasBeenMoved)); + } + + // 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**) +{ + test>(); + test>(); + test>(); + test(); + + test>(); + test>(); + test>(); + test(); + + return 0; +}