Horizon
Loading...
Searching...
No Matches
inplace_merge.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//===----------------------------------------------------------------------===//
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_INPLACE_MERGE_HPP
22#define RANGES_V3_ALGORITHM_INPLACE_MERGE_HPP
23
24#include <functional>
25#include <memory>
26#include <new>
27#include <type_traits>
28
30
51#include <range/v3/utility/static_const.hpp>
53
54#include <range/v3/detail/prologue.hpp>
55
56namespace ranges
57{
59 namespace detail
60 {
61 struct merge_adaptive_fn
62 {
63 private:
64 template<typename I, typename C, typename P>
65 static void impl(I first, I middle, I last, iter_difference_t<I> len1,
66 iter_difference_t<I> len2, iter_value_t<I> * const buf,
67 C & pred, P & proj)
68 {
69 auto tmpbuf = make_raw_buffer(buf);
70 if(len1 <= len2)
71 {
72 auto p = ranges::move(first, middle, tmpbuf.begin()).out;
73 merge(make_move_iterator(buf),
74 make_move_iterator(p.base().base()),
75 make_move_iterator(std::move(middle)),
76 make_move_iterator(std::move(last)),
77 std::move(first),
78 std::ref(pred),
79 std::ref(proj),
80 std::ref(proj));
81 }
82 else
83 {
84 auto p = ranges::move(middle, last, tmpbuf.begin()).out;
87 merge(make_move_iterator(RBi{std::move(middle)}),
88 make_move_iterator(RBi{std::move(first)}),
89 make_move_iterator(Rv{p.base().base()}),
90 make_move_iterator(Rv{buf}),
91 RBi{std::move(last)},
92 not_fn(std::ref(pred)),
93 std::ref(proj),
94 std::ref(proj));
95 }
96 }
97
98 public:
99 template(typename I, typename C = less, typename P = identity)(
100 requires bidirectional_iterator<I> AND sortable<I, C, P>)
101 void operator()(I first, I middle, I last, iter_difference_t<I> len1,
102 iter_difference_t<I> len2, iter_value_t<I> * buf,
103 std::ptrdiff_t buf_size, C pred = C{}, P proj = P{}) const
104 {
105 using D = iter_difference_t<I>;
106 while(true)
107 {
108 // if middle == last, we're done
109 if(len2 == 0)
110 return;
111 // shrink [first, middle) as much as possible (with no moves),
112 // returning if it shrinks to 0
113 for(; true; ++first, --len1)
114 {
115 if(len1 == 0)
116 return;
117 if(invoke(pred, invoke(proj, *middle), invoke(proj, *first)))
118 break;
119 }
120 if(len1 <= buf_size || len2 <= buf_size)
121 {
122 merge_adaptive_fn::impl(std::move(first),
123 std::move(middle),
124 std::move(last),
125 len1,
126 len2,
127 buf,
128 pred,
129 proj);
130 return;
131 }
132 // first < middle < end
133 // *first > *middle
134 // partition [first, m1) [m1, middle) [middle, m2) [m2, last) such
135 // that
136 // all elements in:
137 // [first, m1) <= [middle, m2)
138 // [middle, m2) < [m1, middle)
139 // [m1, middle) <= [m2, last)
140 // and m1 or m2 is in the middle of its range
141 I m1; // "median" of [first, middle)
142 I m2; // "median" of [middle, last)
143 D len11; // distance(first, m1)
144 D len21; // distance(middle, m2)
145 // binary search smaller range
146 if(len1 < len2)
147 { // len >= 1, len2 >= 2
148 len21 = len2 / 2;
149 m2 = next(middle, len21);
150 m1 = upper_bound(first,
151 middle,
152 invoke(proj, *m2),
153 std::ref(pred),
154 std::ref(proj));
155 len11 = distance(first, m1);
156 }
157 else
158 {
159 if(len1 == 1)
160 { // len1 >= len2 && len2 > 0, therefore len2 == 1
161 // It is known *first > *middle
162 ranges::iter_swap(first, middle);
163 return;
164 }
165 // len1 >= 2, len2 >= 1
166 len11 = len1 / 2;
167 m1 = next(first, len11);
168 m2 = lower_bound(middle,
169 last,
170 invoke(proj, *m1),
171 std::ref(pred),
172 std::ref(proj));
173 len21 = distance(middle, m2);
174 }
175 D len12 = len1 - len11; // distance(m1, middle)
176 D len22 = len2 - len21; // distance(m2, last)
177 // [first, m1) [m1, middle) [middle, m2) [m2, last)
178 // swap middle two partitions
179 middle = rotate(m1, std::move(middle), m2).begin();
180 // len12 and len21 now have swapped meanings
181 // merge smaller range with recursive call and larger with tail
182 // recursion elimination
183 if(len11 + len21 < len12 + len22)
184 {
185 (*this)(std::move(first),
186 std::move(m1),
187 middle,
188 len11,
189 len21,
190 buf,
191 buf_size,
192 std::ref(pred),
193 std::ref(proj));
194 first = std::move(middle);
195 middle = std::move(m2);
196 len1 = len12;
197 len2 = len22;
198 }
199 else
200 {
201 (*this)(middle,
202 std::move(m2),
203 std::move(last),
204 len12,
205 len22,
206 buf,
207 buf_size,
208 std::ref(pred),
209 std::ref(proj));
210 last = std::move(middle);
211 middle = std::move(m1);
212 len1 = len11;
213 len2 = len21;
214 }
215 }
216 }
217 };
218
219 RANGES_INLINE_VARIABLE(merge_adaptive_fn, merge_adaptive)
220
221 struct inplace_merge_no_buffer_fn
222 {
223 template(typename I, typename C = less, typename P = identity)(
224 requires bidirectional_iterator<I> AND sortable<I, C, P>)
225 void operator()(I first, I middle, I last, iter_difference_t<I> len1,
226 iter_difference_t<I> len2, C pred = C{}, P proj = P{}) const
227 {
228 merge_adaptive(std::move(first),
229 std::move(middle),
230 std::move(last),
231 len1,
232 len2,
233 static_cast<iter_value_t<I> *>(nullptr),
234 0,
235 std::move(pred),
236 std::move(proj));
237 }
238 };
239
240 RANGES_INLINE_VARIABLE(inplace_merge_no_buffer_fn, inplace_merge_no_buffer)
241 } // namespace detail
243
246 RANGES_FUNC_BEGIN(inplace_merge)
247
248 // TODO reimplement to only need forward iterators
249
250
251 template(typename I, typename S, typename C = less, typename P = identity)(
252 requires bidirectional_iterator<I> AND sortable<I, C, P>)
253 I RANGES_FUNC(inplace_merge)(
254 I first, I middle, S last, C pred = C{}, P proj = P{})
255 {
256 using value_type = iter_value_t<I>;
257 auto len1 = distance(first, middle);
258 auto len2_and_end = enumerate(middle, last);
259 auto buf_size = ranges::min(len1, len2_and_end.first);
260 std::pair<value_type *, std::ptrdiff_t> buf{nullptr, 0};
261 std::unique_ptr<value_type, detail::return_temporary_buffer> h;
262 if(detail::is_trivially_copy_assignable_v<value_type> && 8 < buf_size)
263 {
264 buf = detail::get_temporary_buffer<value_type>(buf_size);
265 h.reset(buf.first);
266 }
267 detail::merge_adaptive(std::move(first),
268 std::move(middle),
269 len2_and_end.second,
270 len1,
271 len2_and_end.first,
272 buf.first,
273 buf.second,
274 std::move(pred),
275 std::move(proj));
276 return len2_and_end.second;
277 }
278
280 template(typename Rng, typename C = less, typename P = identity)(
281 requires bidirectional_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
282 borrowed_iterator_t<Rng> RANGES_FUNC(inplace_merge)(
283 Rng && rng, iterator_t<Rng> middle, C pred = C{}, P proj = P{})
284 {
285 return (*this)(begin(rng),
286 std::move(middle),
287 end(rng),
288 std::move(pred),
289 std::move(proj));
290 }
291
292 RANGES_FUNC_END(inplace_merge)
293
294 namespace cpp20
295 {
296 using ranges::inplace_merge;
297 }
299} // namespace ranges
300
301#include <range/v3/detail/epilogue.hpp>
302
303#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
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition meta.hpp:255
compose< quote< not_ >, Fn > not_fn
Logically negate the result of invocable Fn.
Definition meta.hpp:3009
Definition basic_iterator.hpp:532