Horizon
Loading...
Searching...
No Matches
sort.hpp
Go to the documentation of this file.
1
2// 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
40
54#include <range/v3/utility/static_const.hpp>
55
56#include <range/v3/detail/prologue.hpp>
57
58namespace 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
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