Horizon
stable_sort.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-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 // Copyright (c) 1994
14 // Hewlett-Packard Company
15 //
16 // Permission to use, copy, modify, distribute and sell this software
17 // and its documentation for any purpose is hereby granted without fee,
18 // provided that the above copyright notice appear in all copies and
19 // that both that copyright notice and this permission notice appear
20 // in supporting documentation. Hewlett-Packard Company makes no
21 // representations about the suitability of this software for any
22 // purpose. It is provided "as is" without express or implied warranty.
23 //
24 // Copyright (c) 1996
25 // Silicon Graphics Computer Systems, Inc.
26 //
27 // Permission to use, copy, modify, distribute and sell this software
28 // and its documentation for any purpose is hereby granted without fee,
29 // provided that the above copyright notice appear in all copies and
30 // that both that copyright notice and this permission notice appear
31 // in supporting documentation. Silicon Graphics makes no
32 // representations about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied warranty.
34 //
35 
36 #ifndef RANGES_V3_ALGORITHM_STABLE_SORT_HPP
37 #define RANGES_V3_ALGORITHM_STABLE_SORT_HPP
38 
39 #include <functional>
40 #include <iterator>
41 #include <memory>
42 
43 #include <range/v3/range_fwd.hpp>
44 
60 #include <range/v3/utility/static_const.hpp>
61 
62 #include <range/v3/detail/prologue.hpp>
63 
64 namespace ranges
65 {
68 
70  namespace detail
71  {
72  template<typename I, typename C, typename P>
73  void inplace_stable_sort(I first, I last, C & pred, P & proj)
74  {
75  if(last - first < 15)
76  return detail::insertion_sort(first, last, pred, proj), void();
77  I middle = first + (last - first) / 2;
78  detail::inplace_stable_sort(first, middle, pred, proj);
79  detail::inplace_stable_sort(middle, last, pred, proj);
80  detail::inplace_merge_no_buffer(first,
81  middle,
82  last,
83  middle - first,
84  last - middle,
85  std::ref(pred),
86  std::ref(proj));
87  }
88 
89  template<typename I1, typename I2, typename D, typename C, typename P>
90  void merge_sort_loop(I1 first, I1 last, I2 result, D step_size, C & pred,
91  P & proj)
92  {
93  D two_step = 2 * step_size;
94  while(last - first >= two_step)
95  {
96  result = merge(make_move_iterator(first),
97  make_move_iterator(first + step_size),
98  make_move_iterator(first + step_size),
99  make_move_iterator(first + two_step),
100  result,
101  std::ref(pred),
102  std::ref(proj),
103  std::ref(proj))
104  .out;
105  first += two_step;
106  }
107  step_size = ranges::min(D(last - first), step_size);
108  merge(make_move_iterator(first),
109  make_move_iterator(first + step_size),
110  make_move_iterator(first + step_size),
111  make_move_iterator(last),
112  result,
113  std::ref(pred),
114  std::ref(proj),
115  std::ref(proj));
116  }
117 
118  constexpr int merge_sort_chunk_size()
119  {
120  return 7;
121  }
122 
123  template<typename I, typename D, typename C, typename P>
124  void chunk_insertion_sort(I first, I last, D chunk_size, C & pred, P & proj)
125  {
126  while(last - first >= chunk_size)
127  {
128  detail::insertion_sort(first, first + chunk_size, pred, proj);
129  first += chunk_size;
130  }
131  detail::insertion_sort(first, last, pred, proj);
132  }
133 
134  // buffer points to raw memory, we create objects, and then restore the buffer to
135  // raw memory by destroying the objects on return.
136  template<typename I, typename V, typename C, typename P>
137  void merge_sort_with_buffer(I first, I last, V * buffer, C & pred, P & proj)
138  {
139  iter_difference_t<I> len = last - first,
140  step_size = detail::merge_sort_chunk_size();
141  detail::chunk_insertion_sort(first, last, step_size, pred, proj);
142  if(step_size >= len)
143  return;
144  // The first call to merge_sort_loop moves into raw storage. Construct
145  // on-demand and keep track of how many objects we need to destroy.
146  V * buffer_end = buffer + static_cast<std::ptrdiff_t>(len);
147  auto tmpbuf = make_raw_buffer(buffer);
148  detail::merge_sort_loop(first, last, tmpbuf.begin(), step_size, pred, proj);
149  step_size *= 2;
150  loop:
151  detail::merge_sort_loop(
152  buffer, buffer_end, first, (std::ptrdiff_t)step_size, pred, proj);
153  step_size *= 2;
154  if(step_size >= len)
155  return;
156  detail::merge_sort_loop(first, last, buffer, step_size, pred, proj);
157  step_size *= 2;
158  goto loop;
159  }
160 
161  // buffer points to raw memory
162  template<typename I, typename V, typename C, typename P>
163  void stable_sort_adaptive(I first, I last, V * buffer, std::ptrdiff_t buffer_size,
164  C & pred, P & proj)
165  {
166  iter_difference_t<I> len = (last - first + 1) / 2;
167  I middle = first + len;
168  if(len > buffer_size)
169  {
170  detail::stable_sort_adaptive(
171  first, middle, buffer, buffer_size, pred, proj);
172  detail::stable_sort_adaptive(
173  middle, last, buffer, buffer_size, pred, proj);
174  }
175  else
176  {
177  detail::merge_sort_with_buffer(first, middle, buffer, pred, proj);
178  detail::merge_sort_with_buffer(middle, last, buffer, pred, proj);
179  }
180  detail::merge_adaptive(first,
181  middle,
182  last,
183  middle - first,
184  last - middle,
185  buffer,
186  buffer_size,
187  std::ref(pred),
188  std::ref(proj));
189  }
190  } // namespace detail
192 
193  RANGES_FUNC_BEGIN(stable_sort)
194 
195 
196  template(typename I, typename S, typename C = less, typename P = identity)(
197  requires sortable<I, C, P> AND random_access_iterator<I> AND
198  sentinel_for<S, I>)
199  I RANGES_FUNC(stable_sort)(I first, S end_, C pred = C{}, P proj = P{})
200  {
201  I last = ranges::next(first, end_);
202  using D = iter_difference_t<I>;
203  using V = iter_value_t<I>;
204  D len = last - first;
205  auto buf =
206  len > 256 ? detail::get_temporary_buffer<V>(len) : detail::value_init{};
207  std::unique_ptr<V, detail::return_temporary_buffer> h{buf.first};
208  if(buf.first == nullptr)
209  detail::inplace_stable_sort(first, last, pred, proj);
210  else
211  detail::stable_sort_adaptive(
212  first, last, buf.first, buf.second, pred, proj);
213  return last;
214  }
215 
217  template(typename Rng, typename C = less, typename P = identity)(
218  requires sortable<iterator_t<Rng>, C, P> AND random_access_range<Rng>)
219  borrowed_iterator_t<Rng> //
220  RANGES_FUNC(stable_sort)(Rng && rng, C pred = C{}, P proj = P{}) //
221  {
222  return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
223  }
224 
225  RANGES_FUNC_END(stable_sort)
226 
227  namespace cpp20
228  {
229  using ranges::stable_sort;
230  }
232 } // namespace ranges
233 
234 #include <range/v3/detail/epilogue.hpp>
235 
236 #endif
CPP_concept sortable
\concept sortable
Definition: concepts.hpp:865
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