Horizon
inplace_merge.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_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 
29 #include <range/v3/range_fwd.hpp>
30 
51 #include <range/v3/utility/static_const.hpp>
53 
54 #include <range/v3/detail/prologue.hpp>
55 
56 namespace 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;
85  using RBi = ranges::reverse_iterator<I>;
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
CPP_concept sortable
\concept sortable
Definition: concepts.hpp:865
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
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