Horizon
Loading...
Searching...
No Matches
stable_partition.hpp
Go to the documentation of this file.
1
2// 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//===-------------------------- algorithm ---------------------------------===//
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_STABLE_PARTITION_HPP
22#define RANGES_V3_ALGORITHM_STABLE_PARTITION_HPP
23
24#include <functional>
25#include <memory>
26#include <type_traits>
27
28#include <meta/meta.hpp>
29
31
46#include <range/v3/utility/static_const.hpp>
48
49#include <range/v3/detail/prologue.hpp>
50
51namespace ranges
52{
55
57 namespace detail
58 {
59 template<typename I, typename C, typename P, typename D, typename Pair>
60 I stable_partition_impl(I first, I last, C pred, P proj, D len, Pair const p,
61 std::forward_iterator_tag fi)
62 {
63 // *first is known to be false
64 // len >= 1
65 if(len == 1)
66 return first;
67 if(len == 2)
68 {
69 I tmp = first;
70 if(invoke(pred, invoke(proj, *++tmp)))
71 {
72 ranges::iter_swap(first, tmp);
73 return tmp;
74 }
75 return first;
76 }
77 if(len <= p.second)
78 { // The buffer is big enough to use
79 // Move the falses into the temporary buffer, and the trues to the front
80 // of the line Update first to always point to the last of the trues
81 auto tmpbuf = make_raw_buffer(p.first);
82 auto buf = tmpbuf.begin();
83 *buf = iter_move(first);
84 ++buf;
85 auto res = partition_copy(make_move_iterator(next(first)),
86 make_move_sentinel(last),
87 first,
88 buf,
89 std::ref(pred),
90 std::ref(proj));
91 // All trues now at start of range, all falses in buffer
92 // Move falses back into range, but don't mess up first which points to
93 // first false
94 ranges::move(p.first, res.out2.base().base(), res.out1);
95 // h destructs moved-from values out of the temp buffer, but doesn't
96 // deallocate buffer
97 return res.out1;
98 }
99 // Else not enough buffer, do in place
100 // len >= 3
101 D half = len / 2; // half >= 2
102 I middle = next(first, half);
103 // recurse on [first, middle), *first know to be false
104 // F?????????????????
105 // f m l
106 I begin_false =
107 detail::stable_partition_impl(first, middle, pred, proj, half, p, fi);
108 // TTTFFFFF??????????
109 // f ff m l
110 // recurse on [middle, last], except increase middle until *(middle) is false,
111 // *last know to be true
112 I m1 = middle;
113 D len_half = len - half;
114 while(invoke(pred, invoke(proj, *m1)))
115 {
116 if(++m1 == last)
117 return ranges::rotate(begin_false, middle, last).begin();
118 --len_half;
119 }
120 // TTTFFFFFTTTF??????
121 // f ff m m1 l
122 I end_false =
123 detail::stable_partition_impl(m1, last, pred, proj, len_half, p, fi);
124 // TTTFFFFFTTTTTFFFFF
125 // f ff m sf l
126 return ranges::rotate(begin_false, middle, end_false).begin();
127 // TTTTTTTTFFFFFFFFFF
128 // |
129 }
130
131 template<typename I, typename S, typename C, typename P>
132 I stable_partition_impl(I first, S last, C pred, P proj,
133 std::forward_iterator_tag fi)
134 {
135 using difference_type = iter_difference_t<I>;
136 difference_type const alloc_limit = 3; // might want to make this a function
137 // of trivial assignment.
138 // Either prove all true and return first or point to first false
139 while(true)
140 {
141 if(first == last)
142 return first;
143 if(!invoke(pred, invoke(proj, *first)))
144 break;
145 ++first;
146 }
147 // We now have a reduced range [first, last)
148 // *first is known to be false
149 using value_type = iter_value_t<I>;
150 auto len_end = enumerate(first, last);
151 auto p = len_end.first >= alloc_limit
152 ? detail::get_temporary_buffer<value_type>(len_end.first)
153 : detail::value_init{};
154 std::unique_ptr<value_type, detail::return_temporary_buffer> const h{p.first};
155 return detail::stable_partition_impl(
156 first, len_end.second, pred, proj, len_end.first, p, fi);
157 }
158
159 template<typename I, typename C, typename P, typename D, typename Pair>
160 I stable_partition_impl(I first, I last, C pred, P proj, D len, Pair p,
161 std::bidirectional_iterator_tag bi)
162 {
163 // *first is known to be false
164 // *last is known to be true
165 // len >= 2
166 if(len == 2)
167 {
168 ranges::iter_swap(first, last);
169 return last;
170 }
171 if(len == 3)
172 {
173 I tmp = first;
174 if(invoke(pred, invoke(proj, *++tmp)))
175 {
176 ranges::iter_swap(first, tmp);
177 ranges::iter_swap(tmp, last);
178 return last;
179 }
180 ranges::iter_swap(tmp, last);
181 ranges::iter_swap(first, tmp);
182 return tmp;
183 }
184 if(len <= p.second)
185 { // The buffer is big enough to use
186 // Move the falses into the temporary buffer, and the trues to the front
187 // of the line Update first to always point to the last of the trues
188 auto tmpbuf = ranges::make_raw_buffer(p.first);
189 auto buf = tmpbuf.begin();
190 *buf = iter_move(first);
191 ++buf;
192 auto res = partition_copy(make_move_iterator(next(first)),
193 make_move_sentinel(last),
194 first,
195 buf,
196 std::ref(pred),
197 std::ref(proj));
198 first = res.out1;
199 // move *last, known to be true
200 *first = iter_move(res.in);
201 ++first;
202 // All trues now at start of range, all falses in buffer
203 // Move falses back into range, but don't mess up first which points to
204 // first false
205 ranges::move(p.first, res.out2.base().base(), first);
206 // h destructs moved-from values out of the temp buffer, but doesn't
207 // deallocate buffer
208 return first;
209 }
210 // Else not enough buffer, do in place
211 // len >= 4
212 I middle = first;
213 D half = len / 2; // half >= 2
214 advance(middle, half);
215 // recurse on [first, middle-1], except reduce middle-1 until *(middle-1) is
216 // true, *first know to be false F????????????????T f m l
217 I m1 = middle;
218 I begin_false = first;
219 D len_half = half;
220 while(!invoke(pred, invoke(proj, *--m1)))
221 {
222 if(m1 == first)
223 goto first_half_done;
224 --len_half;
225 }
226 // F???TFFF?????????T
227 // f m1 m l
228 begin_false =
229 detail::stable_partition_impl(first, m1, pred, proj, len_half, p, bi);
230 first_half_done:
231 // TTTFFFFF?????????T
232 // f ff m l
233 // recurse on [middle, last], except increase middle until *(middle) is false,
234 // *last know to be true
235 m1 = middle;
236 len_half = len - half;
237 while(invoke(pred, invoke(proj, *m1)))
238 {
239 if(++m1 == last)
240 return ranges::rotate(begin_false, middle, ++last).begin();
241 --len_half;
242 }
243 // TTTFFFFFTTTF?????T
244 // f ff m m1 l
245 I end_false =
246 detail::stable_partition_impl(m1, last, pred, proj, len_half, p, bi);
247 // TTTFFFFFTTTTTFFFFF
248 // f ff m sf l
249 return ranges::rotate(begin_false, middle, end_false).begin();
250 // TTTTTTTTFFFFFFFFFF
251 // |
252 }
253
254 template<typename I, typename S, typename C, typename P>
255 I stable_partition_impl(I first, S end_, C pred, P proj,
256 std::bidirectional_iterator_tag bi)
257 {
258 using difference_type = iter_difference_t<I>;
259 using value_type = iter_value_t<I>;
260 difference_type const alloc_limit =
261 4; // might want to make this a function of trivial assignment
262 // Either prove all true and return first or point to first false
263 while(true)
264 {
265 if(first == end_)
266 return first;
267 if(!invoke(pred, invoke(proj, *first)))
268 break;
269 ++first;
270 }
271 // first points to first false, everything prior to first is already set.
272 // Either prove [first, last) is all false and return first, or point last to
273 // last true
274 I last = ranges::next(first, end_);
275 do
276 {
277 if(first == --last)
278 return first;
279 } while(!invoke(pred, invoke(proj, *last)));
280 // We now have a reduced range [first, last]
281 // *first is known to be false
282 // *last is known to be true
283 // len >= 2
284 auto len = distance(first, last) + 1;
285 auto p = len >= alloc_limit ? detail::get_temporary_buffer<value_type>(len)
286 : detail::value_init{};
287 std::unique_ptr<value_type, detail::return_temporary_buffer> const h{p.first};
288 return detail::stable_partition_impl(first, last, pred, proj, len, p, bi);
289 }
290 } // namespace detail
292
293 RANGES_FUNC_BEGIN(stable_partition)
294
295
296 template(typename I, typename S, typename C, typename P = identity)(
297 requires bidirectional_iterator<I> AND sentinel_for<S, I> AND
298 indirect_unary_predicate<C, projected<I, P>> AND permutable<I>)
299 I RANGES_FUNC(stable_partition)(I first, S last, C pred, P proj = P{})
300 {
301 return detail::stable_partition_impl(std::move(first),
302 std::move(last),
303 std::ref(pred),
304 std::ref(proj),
305 iterator_tag_of<I>());
306 }
307
308 // BUGBUG Can this be optimized if Rng has O1 size?
310 template(typename Rng, typename C, typename P = identity)(
311 requires bidirectional_range<Rng> AND
312 indirect_unary_predicate<C, projected<iterator_t<Rng>, P>> AND
313 permutable<iterator_t<Rng>>)
314 borrowed_iterator_t<Rng> //
315 RANGES_FUNC(stable_partition)(Rng && rng, C pred, P proj = P{}) //
316 {
317 return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
318 }
319
320 RANGES_FUNC_END(stable_partition)
321
322 namespace cpp20
323 {
324 using ranges::stable_partition;
325 }
327} // namespace ranges
328
329#include <range/v3/detail/epilogue.hpp>
330
331#endif
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
Tiny meta-programming library.