-/* Radix Sort {{{ */
-typedef uint32_t (*SKRadixFunction)(id, void *);
-
-@interface NSMutableArray (Radix)
-- (void) radixSortUsingFunction:(SKRadixFunction)function withContext:(void *)argument;
-@end
-
-struct RadixItem_ {
- size_t index;
- uint32_t key;
-};
-
-@implementation NSMutableArray (Radix)
-
-- (void) radixSortUsingFunction:(SKRadixFunction)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;
-}
-
-@end
-/* }}} */
projects / cydia.git / blobdiff