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