Horizon
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_SORT_HPP
37 #define RANGES_V3_ALGORITHM_SORT_HPP
38 
39 #include <range/v3/range_fwd.hpp>
40 
54 #include <range/v3/utility/static_const.hpp>
55 
56 #include <range/v3/detail/prologue.hpp>
57 
58 namespace ranges
59 {
61  namespace detail
62  {
63  template<typename I, typename C, typename P>
64  inline constexpr I unguarded_partition(I first, I last, C & pred, P & proj)
65  {
66  I mid = first + (last - first) / 2, penultimate = ranges::prev(last);
67  auto &&x = *first, &&y = *mid, &&z = *penultimate;
68  auto &&a = invoke(proj, (decltype(x) &&)x),
69  &&b = invoke(proj, (decltype(y) &&)y),
70  &&c = invoke(proj, (decltype(z) &&)z);
71 
72  // Find the median:
73  I pivot_pnt =
74  invoke(pred, a, b)
75  ? (invoke(pred, b, c) ? mid
76  : (invoke(pred, a, c) ? penultimate : first))
77  : (invoke(pred, a, c) ? first
78  : (invoke(pred, b, c) ? penultimate : mid));
79 
80  // Do the partition:
81  while(true)
82  {
83  auto && v = *pivot_pnt;
84  auto && pivot = invoke(proj, (decltype(v) &&)v);
85  while(invoke(pred, invoke(proj, *first), pivot))
86  ++first;
87  --last;
88  while(invoke(pred, pivot, invoke(proj, *last)))
89  --last;
90  if(!(first < last))
91  return first;
92  ranges::iter_swap(first, last);
93  pivot_pnt =
94  pivot_pnt == first ? last : (pivot_pnt == last ? first : pivot_pnt);
95  ++first;
96  }
97  }
98 
99  template<typename I, typename C, typename P>
100  inline constexpr void unguarded_linear_insert(I last,
101  iter_value_t<I> val,
102  C & pred,
103  P & proj)
104  {
105  I next_ = prev(last);
106  while(invoke(pred, invoke(proj, val), invoke(proj, *next_)))
107  {
108  *last = iter_move(next_);
109  last = next_;
110  --next_;
111  }
112  *last = std::move(val);
113  }
114 
115  template<typename I, typename C, typename P>
116  inline constexpr void linear_insert(I first, I last, C & pred, P & proj)
117  {
118  iter_value_t<I> val = iter_move(last);
119  if(invoke(pred, invoke(proj, val), invoke(proj, *first)))
120  {
121  move_backward(first, last, last + 1);
122  *first = std::move(val);
123  }
124  else
125  detail::unguarded_linear_insert(last, std::move(val), pred, proj);
126  }
127 
128  template<typename I, typename C, typename P>
129  inline constexpr void insertion_sort(I first, I last, C & pred, P & proj)
130  {
131  if(first == last)
132  return;
133  for(I i = next(first); i != last; ++i)
134  detail::linear_insert(first, i, pred, proj);
135  }
136 
137  template<typename I, typename C, typename P>
138  inline constexpr void unguarded_insertion_sort(I first, I last, C & pred, P & proj)
139  {
140  for(I i = first; i != last; ++i)
141  detail::unguarded_linear_insert(i, iter_move(i), pred, proj);
142  }
143 
144  constexpr int introsort_threshold()
145  {
146  return 16;
147  }
148 
149  template<typename I, typename C, typename P>
150  inline constexpr void final_insertion_sort(I first, I last, C & pred, P & proj)
151  {
152  if(last - first > detail::introsort_threshold())
153  {
154  detail::insertion_sort(
155  first, first + detail::introsort_threshold(), pred, proj);
156  detail::unguarded_insertion_sort(
157  first + detail::introsort_threshold(), last, pred, proj);
158  }
159  else
160  detail::insertion_sort(first, last, pred, proj);
161  }
162 
163  template<typename Size>
164  inline constexpr Size log2(Size n)
165  {
166  Size k = 0;
167  for(; n != 1; n >>= 1)
168  ++k;
169  return k;
170  }
171 
172  template<typename I, typename Size, typename C, typename P>
173  inline constexpr void introsort_loop(I first, I last, Size depth_limit, C & pred, P & proj)
174  {
175  while(last - first > detail::introsort_threshold())
176  {
177  if(depth_limit == 0)
178  return partial_sort(
179  first, last, last, std::ref(pred), std::ref(proj)),
180  void();
181  I cut = detail::unguarded_partition(first, last, pred, proj);
182  detail::introsort_loop(cut, last, --depth_limit, pred, proj);
183  last = cut;
184  }
185  }
186  } // namespace detail
188 
191 
192  // Introsort: Quicksort to a certain depth, then Heapsort. Insertion
193  // sort below a certain threshold.
194  // TODO Forward iterators, like EoP?
195 
196  RANGES_FUNC_BEGIN(sort)
197 
198 
199  template(typename I, typename S, typename C = less, typename P = identity)(
200  requires sortable<I, C, P> AND random_access_iterator<I> AND
201  sentinel_for<S, I>)
202  constexpr I RANGES_FUNC(sort)(I first, S end_, C pred = C{}, P proj = P{})
203  {
204  I last = ranges::next(first, std::move(end_));
205  if(first != last)
206  {
207  detail::introsort_loop(
208  first, last, detail::log2(last - first) * 2, pred, proj);
209  detail::final_insertion_sort(first, last, pred, proj);
210  }
211  return last;
212  }
213 
215  template(typename Rng, typename C = less, typename P = identity)(
216  requires sortable<iterator_t<Rng>, C, P> AND random_access_range<Rng>)
217  constexpr borrowed_iterator_t<Rng> //
218  RANGES_FUNC(sort)(Rng && rng, C pred = C{}, P proj = P{}) //
219  {
220  return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
221  }
222 
223  RANGES_FUNC_END(sort)
224 
225  namespace cpp20
226  {
227  using ranges::sort;
228  }
230 } // namespace ranges
231 
232 #include <range/v3/detail/epilogue.hpp>
233 
234 #endif
CPP_concept sortable
\concept sortable
Definition: concepts.hpp:865
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