Separate out Menes/radixSortWithSelector.*.

1 files changed, 112 insertions, 0 deletions

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