Horizon
rotate.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2014-present
5 //
6 // Use, modification and distribution is subject to the
7 // Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //
11 // Project home: https://github.com/ericniebler/range-v3
12 //
13 //===----------------------------------------------------------------------===//
14 //
15 // The LLVM Compiler Infrastructure
16 //
17 // This file is dual licensed under the MIT and the University of Illinois Open
18 // Source Licenses. See LICENSE.TXT for details.
19 //
20 //===----------------------------------------------------------------------===//
21 #ifndef RANGES_V3_ALGORITHM_ROTATE_HPP
22 #define RANGES_V3_ALGORITHM_ROTATE_HPP
23 
24 #include <type_traits>
25 #include <utility>
26 
27 #include <range/v3/range_fwd.hpp>
28 
38 #include <range/v3/utility/static_const.hpp>
41 
42 #include <range/v3/detail/prologue.hpp>
43 
44 namespace ranges
45 {
49  namespace detail
50  {
51  template<typename I> // Forward
52  constexpr subrange<I> rotate_left(I first, I last)
53  {
54  iter_value_t<I> tmp = iter_move(first);
55  I lm1 = ranges::move(next(first), last, first).out;
56  *lm1 = std::move(tmp);
57  return {lm1, last};
58  }
59 
60  template<typename I> // Bidirectional
61  constexpr subrange<I> rotate_right(I first, I last)
62  {
63  I lm1 = prev(last);
64  iter_value_t<I> tmp = iter_move(lm1);
65  I fp1 = move_backward(first, lm1, last).out;
66  *first = std::move(tmp);
67  return {fp1, last};
68  }
69 
70  template<typename I, typename S> // Forward
71  constexpr subrange<I> rotate_forward(I first, I middle, S last)
72  {
73  I i = middle;
74  while(true)
75  {
76  ranges::iter_swap(first, i);
77  ++first;
78  if(++i == last)
79  break;
80  if(first == middle)
81  middle = i;
82  }
83  I r = first;
84  if(first != middle)
85  {
86  I j = middle;
87  while(true)
88  {
89  ranges::iter_swap(first, j);
90  ++first;
91  if(++j == last)
92  {
93  if(first == middle)
94  break;
95  j = middle;
96  }
97  else if(first == middle)
98  middle = j;
99  }
100  }
101  return {r, i};
102  }
103 
104  template<typename D>
105  constexpr D gcd(D x, D y)
106  {
107  do
108  {
109  D t = x % y;
110  x = y;
111  y = t;
112  } while(y);
113  return x;
114  }
115 
116  template<typename I> // Random
117  constexpr subrange<I> rotate_gcd(I first, I middle, I last)
118  {
119  auto const m1 = middle - first;
120  auto const m2 = last - middle;
121  if(m1 == m2)
122  {
123  swap_ranges(first, middle, middle);
124  return {middle, last};
125  }
126  auto const g = detail::gcd(m1, m2);
127  for(I p = first + g; p != first;)
128  {
129  iter_value_t<I> t = iter_move(--p);
130  I p1 = p;
131  I p2 = p1 + m1;
132  do
133  {
134  *p1 = iter_move(p2);
135  p1 = p2;
136  auto const d = last - p2;
137  if(m1 < d)
138  p2 += m1;
139  else
140  p2 = first + (m1 - d);
141  } while(p2 != p);
142  *p1 = std::move(t);
143  }
144  return {first + m2, last};
145  }
146 
147  template<typename I, typename S>
148  constexpr subrange<I> rotate_(I first, I middle, S last, std::forward_iterator_tag)
149  {
150  return detail::rotate_forward(first, middle, last);
151  }
152 
153  template<typename I>
154  constexpr subrange<I> rotate_(I first, I middle, I last, std::forward_iterator_tag)
155  {
156  using value_type = iter_value_t<I>;
157  if(detail::is_trivially_move_assignable_v<value_type>)
158  {
159  if(next(first) == middle)
160  return detail::rotate_left(first, last);
161  }
162  return detail::rotate_forward(first, middle, last);
163  }
164 
165  template<typename I>
166  constexpr subrange<I> rotate_(I first, I middle, I last, std::bidirectional_iterator_tag)
167  {
168  using value_type = iter_value_t<I>;
169  if(detail::is_trivially_move_assignable_v<value_type>)
170  {
171  if(next(first) == middle)
172  return detail::rotate_left(first, last);
173  if(next(middle) == last)
174  return detail::rotate_right(first, last);
175  }
176  return detail::rotate_forward(first, middle, last);
177  }
178 
179  template<typename I>
180  constexpr subrange<I> rotate_(I first, I middle, I last, std::random_access_iterator_tag)
181  {
182  using value_type = iter_value_t<I>;
183  if(detail::is_trivially_move_assignable_v<value_type>)
184  {
185  if(next(first) == middle)
186  return detail::rotate_left(first, last);
187  if(next(middle) == last)
188  return detail::rotate_right(first, last);
189  return detail::rotate_gcd(first, middle, last);
190  }
191  return detail::rotate_forward(first, middle, last);
192  }
193  } // namespace detail
195 
196  RANGES_FUNC_BEGIN(rotate)
197 
198 
199  template(typename I, typename S)(
200  requires permutable<I> AND sentinel_for<S, I>)
201  constexpr subrange<I> RANGES_FUNC(rotate)(I first, I middle, S last) //
202  {
203  if(first == middle)
204  {
205  first = ranges::next(std::move(first), last);
206  return {first, first};
207  }
208  if(middle == last)
209  {
210  return {first, middle};
211  }
212  return detail::rotate_(first, middle, last, iterator_tag_of<I>{});
213  }
214 
216  template(typename Rng, typename I = iterator_t<Rng>)(
217  requires range<Rng> AND permutable<I>)
218  constexpr borrowed_subrange_t<Rng> RANGES_FUNC(rotate)(Rng && rng, I middle) //
219  {
220  return (*this)(begin(rng), std::move(middle), end(rng));
221  }
222 
223  RANGES_FUNC_END(rotate)
224 
225  namespace cpp20
226  {
227  using ranges::rotate;
228  }
230 } // namespace ranges
231 
232 #include <range/v3/detail/epilogue.hpp>
233 
234 #endif
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251