diff options
Diffstat (limited to 'Menes')
| -rw-r--r-- | Menes/Menes.h | 1 | ||||
| -rw-r--r-- | Menes/radixSortWithSelector.h | 51 | ||||
| -rw-r--r-- | Menes/radixSortWithSelector.mm | 112 |
3 files changed, 164 insertions, 0 deletions
diff --git a/Menes/Menes.h b/Menes/Menes.h index 737520d..99f3029 100644 --- a/Menes/Menes.h +++ b/Menes/Menes.h @@ -41,6 +41,7 @@ #define Menes_Menes_H #include "Menes/invocationWithSelector.h" +#include "Menes/radixSortWithSelector.h" #include "Menes/yieldToSelector.h" #endif//Menes_Menes_H diff --git a/Menes/radixSortWithSelector.h b/Menes/radixSortWithSelector.h new file mode 100644 index 0000000..d148cb3 --- /dev/null +++ b/Menes/radixSortWithSelector.h @@ -0,0 +1,51 @@ +/* Cydia - iPhone UIKit Front-End for Debian APT + * Copyright (C) 2008-2011 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. +*/ +/* }}} */ + +#ifndef Menes_radixSort_H +#define Menes_radixSort_H + +#include <Foundation/Foundation.h> + +typedef uint32_t (*MenesRadixSortFunction)(id, void *); + +@interface NSMutableArray (MenesRadixSortWithSelector) +- (void) radixSortUsingFunction:(MenesRadixSortFunction)function withContext:(void *)argument; +@end + +#endif//Menes_radixSort_H diff --git a/Menes/radixSortWithSelector.mm b/Menes/radixSortWithSelector.mm new file mode 100644 index 0000000..949a14b --- /dev/null +++ b/Menes/radixSortWithSelector.mm @@ -0,0 +1,112 @@ +/* Cydia - iPhone UIKit Front-End for Debian APT + * Copyright (C) 2008-2011 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" + +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; +} + +@end |