Horizon
stable_partition.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 //===-------------------------- 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 
30 #include <range/v3/range_fwd.hpp>
31 
46 #include <range/v3/utility/static_const.hpp>
48 
49 #include <range/v3/detail/prologue.hpp>
50 
51 namespace 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
CPP_concept permutable
\concept permutable
Definition: concepts.hpp:840
CPP_concept indirect_unary_predicate
\concept indirect_unary_predicate
Definition: concepts.hpp:632
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.