Line data Source code
1 : #ifndef ROUTING_KIT_SORT_H
2 : #define ROUTING_KIT_SORT_H
3 :
4 : #include <routingkit/permutation.h>
5 :
6 : #include <vector>
7 : #include <assert.h>
8 : #include <algorithm>
9 : #include <functional>
10 :
11 : namespace RoutingKit{
12 :
13 : //
14 : // A sort permutation p of a vector v is a permutation such that
15 : // v[p[0]] <= v[p[1]] <= v[p[2]] <= ... . Applying a sort permutation p of v to
16 : // v yields a sorted vector.
17 : //
18 : // The functions in this header follow the following naming sheme:
19 : //
20 : // 1) compute_[inverse_][stable_]sort_using_[(key|less|comparator](vector, ...order...)
21 : // 2) [stable_]sort_using_[key|less|comparator](vector, ...order...)
22 : // 3) is_sorted_using_[key|less|comparator](vector, ...order...)
23 : //
24 : //
25 : // The functionality is explained as following:
26 : //
27 : // * The functions of category 1 compute sort permutations but do not actually
28 : // sort any array. The sorting is done by applying the resulting permutation
29 : // to one or more vectors.
30 : // * The functions of category 2 copy their argument vector, sort the copy and
31 : // return it. If an rvalue vector is given as parameter then the copy is
32 : // omitted.
33 : // * The functions of category 3 sort their argument array inplace.
34 : // * The functions of category 4 do not sort anything but check whether their
35 : // argument array is sorted.
36 : // * "inverse" indicates that not a sort permutation but its inverse is
37 : // computed. In combination with the _using_key function it is slightly
38 : // faster to compute an inverse sort permutation and then to use
39 : // apply_inverse_permutation then to compute a sort permutation and to use
40 : // apply_permutation.
41 : // * "stable" indicates that the relative order of values that compare equally
42 : // is not changed.
43 : // * "key" indicates that elements are sorted using bucket sort. All functions
44 : // take a (key_count, get_key) pair of parameters to specify the order.
45 : // get_key is a function object that must map every element onto a value in
46 : // [0,key_count). get_key is assumed to have a quick execution and is
47 : // called several times per sort operation. However, get_key is never
48 : // copied.
49 : // * "comparator" indicates that an STL like comparator is used and needs to
50 : // be passed to every function.
51 : // * "less" indicates that < is used for comparision. No order paramters need
52 : // to be passed to the functions.
53 : //
54 :
55 : template<class T, class C>
56 0 : std::vector<unsigned> compute_stable_sort_permutation_using_comparator(const std::vector<T>&v, const C&is_less){
57 0 : std::vector<unsigned>p = identity_permutation(v.size());
58 0 : std::stable_sort(
59 : p.begin(), p.end(),
60 : [&](unsigned l, unsigned r){
61 0 : return is_less(v[l], v[r]);
62 : }
63 : );
64 0 : return p; // NVRO
65 : }
66 :
67 : template<class T, class C>
68 : std::vector<T>stable_sort_using_comparator(const std::vector<T>&v, const C&is_less){
69 : std::vector<T>r = v;
70 : std::stable_sort(r.begin(), r.end(), is_less);
71 : return r; // NVRO
72 : }
73 :
74 : template<class T, class C>
75 : std::vector<T>stable_sort_using_comparator(std::vector<T>&&v, const C&is_less){
76 : std::stable_sort(v.begin(), v.end(), is_less);
77 : return std::move(v); // NVRO
78 : }
79 :
80 : template<class T, class C>
81 : std::vector<unsigned> compute_sort_permutation_using_comparator(const std::vector<T>&v, const C&is_less){
82 : std::vector<unsigned>p = identity_permutation(v.size());
83 : std::sort(
84 : p.begin(), p.end(),
85 : [&](unsigned l, unsigned r){
86 : return is_less(v[l], v[r]);
87 : }
88 : );
89 : return p; // NVRO
90 : }
91 :
92 : template<class T, class C>
93 : std::vector<T>sort_using_comparator(const std::vector<T>&v, const C&is_less){
94 : std::vector<T>r = v;
95 : std::sort(r.begin(), r.end(), is_less);
96 : return r; // NVRO
97 : }
98 :
99 : template<class T, class C>
100 : std::vector<T>sort_using_comparator(std::vector<T>&&v, const C&is_less){
101 : std::sort(v.begin(), v.end(), is_less);
102 : return std::move(v); // NVRO
103 : }
104 :
105 :
106 : template<class T, class C>
107 : bool is_sorted_using_comparator(const std::vector<T>&v, const C&is_less){
108 0 : for(unsigned i=1; i<v.size(); ++i)
109 0 : if(is_less(v[i], v[i-1]))
110 : return false;
111 : return true;
112 : }
113 :
114 :
115 : template<class T, class C>
116 : std::vector<unsigned> compute_inverse_sort_permutation_using_comparator(const std::vector<T>&v, const C&is_less){
117 : return invert_permutation(compute_sort_permutation_using_comparator(v, is_less));
118 : }
119 :
120 : template<class T, class C>
121 0 : std::vector<unsigned> compute_inverse_stable_sort_permutation_using_comparator(const std::vector<T>&v, const C&is_less){
122 0 : return invert_permutation(compute_stable_sort_permutation_using_comparator(v, is_less));
123 : }
124 :
125 :
126 :
127 : namespace detail{
128 : const unsigned bucket_sort_min_key_to_element_ratio = 16;
129 :
130 : template<class T, class K>
131 22888 : std::vector<unsigned>compute_key_pos(const std::vector<T>&v, unsigned key_count, const K&get_key){
132 22888 : std::vector<unsigned>key_pos(key_count, 0);
133 1266536 : for(unsigned i=0; i<v.size(); ++i){
134 1243648 : unsigned k = get_key(v[i]);
135 : assert(k <= key_count && "key is too large");
136 1243648 : ++key_pos[k];
137 : }
138 : unsigned sum = 0;
139 324410 : for(unsigned i=0; i<key_count; ++i){
140 301522 : unsigned tmp = sum + key_pos[i];
141 301522 : key_pos[i] = sum;
142 : sum = tmp;
143 : }
144 22888 : return key_pos; // NVRO
145 : }
146 :
147 : template<class K>
148 : struct CompareByKey{
149 : explicit CompareByKey(unsigned n, const K&k):get_key(k){
150 : #ifndef NDEBUG
151 : key_count = n;
152 : #else
153 : (void)n;
154 : #endif
155 : }
156 :
157 : template<class T>
158 : bool operator()(const T&l, const T&r)const{
159 0 : unsigned l_key = get_key(l);
160 : assert(l_key < key_count);
161 0 : unsigned r_key = get_key(r);
162 : assert(r_key < key_count);
163 : return l_key < r_key;
164 : }
165 :
166 : #ifndef NDEBUG
167 : unsigned key_count;
168 : #endif
169 : const K&get_key;
170 : };
171 :
172 : template<class K>
173 : CompareByKey<K> make_compare_by_key(unsigned n, const K&k){
174 : return CompareByKey<K>(n, k);
175 : }
176 : }
177 :
178 : namespace detail{
179 : // Sorting by key uses bucket sort if the number of elements is
180 : // not significantly smaller than the number of keys. Otherwise
181 : // we use the sort by comparator function, which (at the time
182 : // of writing this comment) forward to std::sort and
183 : // std::stable_sort. Bucket sort is always stable whereas
184 : // comparator-based sort is not. To avoid code dublication, we
185 : // therefore have maybe_stable functions that take a compile time
186 : // boolean which inidcates whether the fallback function should
187 : // be stable.
188 :
189 : template<bool is_stable, class T, class K>
190 3396 : std::vector<unsigned> compute_maybe_stable_sort_permutation_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
191 : std::vector<unsigned>p;
192 :
193 3396 : if(v.size() >= key_count / bucket_sort_min_key_to_element_ratio){
194 3396 : p.resize(v.size());
195 3396 : std::vector<unsigned>key_pos = detail::compute_key_pos(v, key_count, get_key);
196 304296 : for(unsigned i=0; i<v.size(); ++i){
197 300900 : unsigned k = get_key(v[i]);
198 : assert(k <= key_count && "key is too large");
199 300900 : p[key_pos[k]] = i;
200 300900 : ++key_pos[k];
201 : }
202 3396 : }else if(is_stable){
203 0 : p = compute_stable_sort_permutation_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
204 : }else{
205 : p = compute_sort_permutation_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
206 : }
207 3396 : return p; // NVRO
208 0 : }
209 :
210 : }
211 :
212 : template<class T, class K>
213 : std::vector<unsigned> compute_sort_permutation_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
214 : return detail::compute_maybe_stable_sort_permutation_using_key<false>(v, key_count, get_key);
215 : }
216 :
217 : template<class T, class K>
218 : std::vector<unsigned> compute_stable_sort_permutation_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
219 3396 : return detail::compute_maybe_stable_sort_permutation_using_key<true>(v, key_count, get_key);
220 : }
221 :
222 : namespace detail{
223 : template<bool is_stable, class T, class K>
224 19492 : std::vector<unsigned> compute_inverse_maybe_stable_sort_permutation_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
225 : std::vector<unsigned>p;
226 19492 : if(v.size() >= key_count / bucket_sort_min_key_to_element_ratio){
227 19492 : p.resize(v.size());
228 19492 : std::vector<unsigned>key_pos = detail::compute_key_pos(v, key_count, get_key);
229 962240 : for(unsigned i=0; i<v.size(); ++i){
230 942748 : unsigned k = get_key(v[i]);
231 : assert(k <= key_count && "key is too large");
232 942748 : p[i] = key_pos[k];
233 942748 : ++key_pos[k];
234 : }
235 19492 : } else if(is_stable){
236 0 : p = compute_inverse_stable_sort_permutation_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
237 : }else{
238 : p = compute_inverse_sort_permutation_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
239 : }
240 19492 : return p; // NVRO
241 0 : }
242 : }
243 :
244 : template<class T, class K>
245 : std::vector<unsigned> compute_inverse_sort_permutation_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
246 : return detail::compute_inverse_maybe_stable_sort_permutation_using_key<false>(v, key_count, get_key);
247 : }
248 :
249 : template<class T, class K>
250 : std::vector<unsigned> compute_inverse_stable_sort_permutation_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
251 19492 : return detail::compute_inverse_maybe_stable_sort_permutation_using_key<true>(v, key_count, get_key);
252 : }
253 :
254 : namespace detail{
255 : template<bool is_stable, class T, class K>
256 : std::vector<T>maybe_stable_sort_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
257 : std::vector<T>r;
258 :
259 : if(v.size() >= key_count / bucket_sort_min_key_to_element_ratio){
260 : std::vector<unsigned>key_pos = detail::compute_key_pos(v, key_count, get_key);
261 : r.resize(v.size());
262 :
263 : for(unsigned i=0; i<v.size(); ++i){
264 : unsigned k = get_key(v[i]);
265 : assert(k <= key_count && "key is too large");
266 : r[key_pos[k]] = v[i];
267 : ++key_pos[k];
268 : }
269 : } else if(is_stable) {
270 : r = stable_sort_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
271 : } else {
272 : r = sort_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
273 : }
274 : return r; // NVRO
275 : }
276 :
277 : template<bool is_stable, class T, class K>
278 : std::vector<T>maybe_stable_sort_using_key(std::vector<T>&&v, unsigned key_count, const K&get_key){
279 : std::vector<T>r;
280 : if(v.size() >= key_count / bucket_sort_min_key_to_element_ratio){
281 : std::vector<unsigned>key_pos = detail::compute_key_pos(v, key_count, get_key);
282 : r.resize(v.size());
283 :
284 : for(unsigned i=0; i<v.size(); ++i){
285 : unsigned k = get_key(v[i]);
286 : assert(k <= key_count && "key is too large");
287 : r[key_pos[k]] = std::move(v[i]);
288 : ++key_pos[k];
289 : }
290 : } else if(is_stable) {
291 : r = stable_sort_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
292 : } else {
293 : r = sort_using_comparator(v, detail::make_compare_by_key(key_count, get_key));
294 : }
295 : return r; // NVRO
296 : }
297 : }
298 :
299 : template<class T, class K>
300 : std::vector<T>sort_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
301 : return detail::maybe_stable_sort_using_key<false>(v, key_count, get_key); // NVRO
302 : }
303 :
304 : template<class T, class K>
305 : std::vector<T>sort_using_key(std::vector<T>&&v, unsigned key_count, const K&get_key){
306 : return detail::maybe_stable_sort_using_key<false>(std::move(v), key_count, get_key); // NVRO
307 : }
308 :
309 : template<class T, class K>
310 : std::vector<T>stable_sort_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
311 : return detail::maybe_stable_sort_using_key<true>(v, key_count, get_key); // NVRO
312 : }
313 :
314 : template<class T, class K>
315 : std::vector<T>stable_sort_using_key(std::vector<T>&&v, unsigned key_count, const K&get_key){
316 : return detail::maybe_stable_sort_using_key<true>(std::move(v), key_count, get_key); // NVRO
317 : }
318 :
319 :
320 : template<class T, class K>
321 : bool is_sorted_using_key(const std::vector<T>&v, unsigned key_count, const K&get_key){
322 : for(unsigned i=1; i<v.size(); ++i)
323 : if(get_key(v[i]) < get_key(v[i-1]))
324 : return false;
325 : return true;
326 : }
327 :
328 :
329 :
330 :
331 :
332 :
333 : template<class T>
334 : std::vector<unsigned> compute_sort_permutation_using_less(const std::vector<T>&v){
335 : return compute_sort_permutation_using_comparator(v, [](const T&l, const T&r){return l < r;});
336 : }
337 :
338 : template<class T>
339 : std::vector<unsigned> compute_stable_sort_permutation_using_less(const std::vector<T>&v){
340 : return compute_stable_sort_permutation_using_comparator(v, [](const T&l, const T&r){return l < r;});
341 : }
342 :
343 : template<class T>
344 : std::vector<unsigned> compute_inverse_sort_permutation_using_less(const std::vector<T>&v){
345 : return invert_permutation(compute_sort_permutation_using_less(v));
346 : }
347 :
348 : template<class T>
349 : std::vector<unsigned> compute_inverse_stable_sort_permutation_using_less(const std::vector<T>&v){
350 : return invert_permutation(compute_stable_sort_permutation_using_less(v));
351 : }
352 :
353 : template<class T>
354 : std::vector<T>stable_sort_using_less(const std::vector<T>&v){
355 : return stable_sort_using_comparator(v, [](const T&l, const T&r){return l < r;});
356 : }
357 :
358 : template<class T>
359 : std::vector<T>stable_sort_using_less(std::vector<T>&&v){
360 : return stable_sort_using_comparator(std::move(v), [](const T&l, const T&r){return l < r;});
361 : }
362 :
363 : template<class T>
364 : std::vector<T>sort_using_less(const std::vector<T>&v){
365 : return sort_using_comparator(v, [](const T&l, const T&r){return l < r;});
366 : }
367 :
368 : template<class T>
369 : std::vector<T>sort_using_less(std::vector<T>&&v){
370 : return sort_using_comparator(std::move(v), [](const T&l, const T&r){return l < r;});
371 : }
372 :
373 : template<class T>
374 : bool is_sorted_using_less(const std::vector<T>&v){
375 0 : return is_sorted_using_comparator(v, [](const T&l, const T&r){return l < r;});
376 : }
377 :
378 : } // RoutingKit
379 :
380 : #endif
|
