v3/algorithm/rotate.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013 //===----------------------------------------------------------------------===//
0014 //
0015 //                     The LLVM Compiler Infrastructure
0016 //
0017 // This file is dual licensed under the MIT and the University of Illinois Open
0018 // Source Licenses. See LICENSE.TXT for details.
0019 //
0020 //===----------------------------------------------------------------------===//
0021 #ifndef RANGES_V3_ALGORITHM_ROTATE_HPP
0022 #define RANGES_V3_ALGORITHM_ROTATE_HPP
0023
0024 #include <type_traits>
0025 #include <utility>
0026
0027 #include <range/v3/range_fwd.hpp>
0028
0029 #include <range/v3/algorithm/move.hpp>
0030 #include <range/v3/algorithm/move_backward.hpp>
0031 #include <range/v3/algorithm/swap_ranges.hpp>
0032 #include <range/v3/iterator/operations.hpp>
0033 #include <range/v3/iterator/traits.hpp>
0034 #include <range/v3/range/access.hpp>
0035 #include <range/v3/range/concepts.hpp>
0036 #include <range/v3/range/traits.hpp>
0037 #include <range/v3/utility/move.hpp>
0038 #include <range/v3/utility/static_const.hpp>
0039 #include <range/v3/utility/swap.hpp>
0040 #include <range/v3/view/subrange.hpp>
0041
0042 #include <range/v3/detail/prologue.hpp>
0043
0044 namespace ranges
0045 {
0046     /// \addtogroup group-algorithms
0047     /// @{
0048     /// \cond
0049     namespace detail
0050     {
0051         template<typename I> // Forward
0052         constexpr subrange<I> rotate_left(I first, I last)
0053         {
0054             iter_value_t<I> tmp = iter_move(first);
0055             I lm1 = ranges::move(next(first), last, first).out;
0056             *lm1 = std::move(tmp);
0057             return {lm1, last};
0058         }
0059
0060         template<typename I> // Bidirectional
0061         constexpr subrange<I> rotate_right(I first, I last)
0062         {
0063             I lm1 = prev(last);
0064             iter_value_t<I> tmp = iter_move(lm1);
0065             I fp1 = move_backward(first, lm1, last).out;
0066             *first = std::move(tmp);
0067             return {fp1, last};
0068         }
0069
0070         template<typename I, typename S> // Forward
0071         constexpr subrange<I> rotate_forward(I first, I middle, S last)
0072         {
0073             I i = middle;
0074             while(true)
0075             {
0076                 ranges::iter_swap(first, i);
0077                 ++first;
0078                 if(++i == last)
0079                     break;
0080                 if(first == middle)
0081                     middle = i;
0082             }
0083             I r = first;
0084             if(first != middle)
0085             {
0086                 I j = middle;
0087                 while(true)
0088                 {
0089                     ranges::iter_swap(first, j);
0090                     ++first;
0091                     if(++j == last)
0092                     {
0093                         if(first == middle)
0094                             break;
0095                         j = middle;
0096                     }
0097                     else if(first == middle)
0098                         middle = j;
0099                 }
0100             }
0101             return {r, i};
0102         }
0103
0104         template<typename D>
0105         constexpr D gcd(D x, D y)
0106         {
0107             do
0108             {
0109                 D t = x % y;
0110                 x = y;
0111                 y = t;
0112             } while(y);
0113             return x;
0114         }
0115
0116         template<typename I> // Random
0117         constexpr subrange<I> rotate_gcd(I first, I middle, I last)
0118         {
0119             auto const m1 = middle - first;
0120             auto const m2 = last - middle;
0121             if(m1 == m2)
0122             {
0123                 swap_ranges(first, middle, middle);
0124                 return {middle, last};
0125             }
0126             auto const g = detail::gcd(m1, m2);
0127             for(I p = first + g; p != first;)
0128             {
0129                 iter_value_t<I> t = iter_move(--p);
0130                 I p1 = p;
0131                 I p2 = p1 + m1;
0132                 do
0133                 {
0134                     *p1 = iter_move(p2);
0135                     p1 = p2;
0136                     auto const d = last - p2;
0137                     if(m1 < d)
0138                         p2 += m1;
0139                     else
0140                         p2 = first + (m1 - d);
0141                 } while(p2 != p);
0142                 *p1 = std::move(t);
0143             }
0144             return {first + m2, last};
0145         }
0146
0147         template<typename I, typename S>
0148         constexpr subrange<I> rotate_(I first, I middle, S last, std::forward_iterator_tag)
0149         {
0150             return detail::rotate_forward(first, middle, last);
0151         }
0152
0153         template<typename I>
0154         constexpr subrange<I> rotate_(I first, I middle, I last, std::forward_iterator_tag)
0155         {
0156             using value_type = iter_value_t<I>;
0157             if(detail::is_trivially_move_assignable_v<value_type>)
0158             {
0159                 if(next(first) == middle)
0160                     return detail::rotate_left(first, last);
0161             }
0162             return detail::rotate_forward(first, middle, last);
0163         }
0164
0165         template<typename I>
0166         constexpr subrange<I> rotate_(I first, I middle, I last, std::bidirectional_iterator_tag)
0167         {
0168             using value_type = iter_value_t<I>;
0169             if(detail::is_trivially_move_assignable_v<value_type>)
0170             {
0171                 if(next(first) == middle)
0172                     return detail::rotate_left(first, last);
0173                 if(next(middle) == last)
0174                     return detail::rotate_right(first, last);
0175             }
0176             return detail::rotate_forward(first, middle, last);
0177         }
0178
0179         template<typename I>
0180         constexpr subrange<I> rotate_(I first, I middle, I last, std::random_access_iterator_tag)
0181         {
0182             using value_type = iter_value_t<I>;
0183             if(detail::is_trivially_move_assignable_v<value_type>)
0184             {
0185                 if(next(first) == middle)
0186                     return detail::rotate_left(first, last);
0187                 if(next(middle) == last)
0188                     return detail::rotate_right(first, last);
0189                 return detail::rotate_gcd(first, middle, last);
0190             }
0191             return detail::rotate_forward(first, middle, last);
0192         }
0193     } // namespace detail
0194     /// \endcond
0195
0196     RANGES_FUNC_BEGIN(rotate)
0197
0198         /// \brief function template \c rotate
0199         template(typename I, typename S)(
0200             requires permutable<I> AND sentinel_for<S, I>)
0201         constexpr subrange<I> RANGES_FUNC(rotate)(I first, I middle, S last) //
0202         {
0203             if(first == middle)
0204             {
0205                 first = ranges::next(std::move(first), last);
0206                 return {first, first};
0207             }
0208             if(middle == last)
0209             {
0210                 return {first, middle};
0211             }
0212             return detail::rotate_(first, middle, last, iterator_tag_of<I>{});
0213         }
0214
0215         /// \overload
0216         template(typename Rng, typename I = iterator_t<Rng>)(
0217             requires range<Rng> AND permutable<I>)
0218         constexpr borrowed_subrange_t<Rng> RANGES_FUNC(rotate)(Rng && rng, I middle) //
0219         {
0220             return (*this)(begin(rng), std::move(middle), end(rng));
0221         }
0222
0223     RANGES_FUNC_END(rotate)
0224
0225     namespace cpp20
0226     {
0227         using ranges::rotate;
0228     }
0229     /// @}
0230 } // namespace ranges
0231
0232 #include <range/v3/detail/epilogue.hpp>
0233
0234 #endif