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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
/* Cydia - iPhone UIKit Front-End for Debian APT
* Copyright (C) 2008-2012 Jay Freeman (saurik)
*/
/* Modified BSD License {{{ */
/*
* Redistribution and use in source and binary
* forms, with or without modification, are permitted
* provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the
* above copyright notice, this list of conditions
* and the following disclaimer.
* 2. Redistributions in binary form must reproduce the
* above copyright notice, this list of conditions
* and the following disclaimer in the documentation
* and/or other materials provided with the
* distribution.
* 3. The name of the author may not be used to endorse
* or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
* BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/* }}} */
#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
|
