]> git.saurik.com Git - cydia.git/blob - Menes/radixSortWithSelector.mm
Allow user to select a specific candidate version.
[cydia.git] / Menes / radixSortWithSelector.mm
1 /* Cydia - iPhone UIKit Front-End for Debian APT
2 * Copyright (C) 2008-2015 Jay Freeman (saurik)
3 */
4
5 /* GNU General Public License, Version 3 {{{ */
6 /*
7 * Cydia is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published
9 * by the Free Software Foundation, either version 3 of the License,
10 * or (at your option) any later version.
11 *
12 * Cydia is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with Cydia. If not, see <http://www.gnu.org/licenses/>.
19 **/
20 /* }}} */
21
22 #include "CyteKit/UCPlatform.h"
23
24 #include "Menes/radixSortWithSelector.h"
25
26 #include <objc/runtime.h>
27
28 struct RadixItem_ {
29 size_t index;
30 uint32_t key;
31 };
32
33 @implementation NSMutableArray (MenesRadixSortWithSelector)
34
35 - (void) radixSortUsingFunction:(MenesRadixSortFunction)function withContext:(void *)argument {
36 size_t count([self count]);
37 struct RadixItem_ *swap(new RadixItem_[count * 2]);
38
39 for (size_t i(0); i != count; ++i) {
40 RadixItem_ &item(swap[i]);
41 item.index = i;
42
43 id object([self objectAtIndex:i]);
44 item.key = function(object, argument);
45 }
46
47 struct RadixItem_ *lhs(swap), *rhs(swap + count);
48
49 static const size_t width = 32;
50 static const size_t bits = 11;
51 static const size_t slots = 1 << bits;
52 static const size_t passes = (width + (bits - 1)) / bits;
53
54 size_t *hist(new size_t[slots]);
55
56 for (size_t pass(0); pass != passes; ++pass) {
57 memset(hist, 0, sizeof(size_t) * slots);
58
59 for (size_t i(0); i != count; ++i) {
60 uint32_t key(lhs[i].key);
61 key >>= pass * bits;
62 key &= _not(uint32_t) >> width - bits;
63 ++hist[key];
64 }
65
66 size_t offset(0);
67 for (size_t i(0); i != slots; ++i) {
68 size_t local(offset);
69 offset += hist[i];
70 hist[i] = local;
71 }
72
73 for (size_t i(0); i != count; ++i) {
74 uint32_t key(lhs[i].key);
75 key >>= pass * bits;
76 key &= _not(uint32_t) >> width - bits;
77 rhs[hist[key]++] = lhs[i];
78 }
79
80 RadixItem_ *tmp(lhs);
81 lhs = rhs;
82 rhs = tmp;
83 }
84
85 delete [] hist;
86
87 const void **values(new const void *[count]);
88 for (size_t i(0); i != count; ++i)
89 values[i] = [self objectAtIndex:lhs[i].index];
90 CFArrayReplaceValues((CFMutableArrayRef) self, CFRangeMake(0, count), values, count);
91 delete [] values;
92
93 delete [] swap;
94 }
95
96 - (void) radixSortUsingSelector:(SEL)selector {
97 if ([self count] == 0)
98 return;
99
100 IMP imp(class_getMethodImplementation([[self lastObject] class], selector));
101 [self radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(imp) withContext:selector];
102 }
103
104 @end