Index: src/OFArray.h ================================================================== --- src/OFArray.h +++ src/OFArray.h @@ -373,27 +373,49 @@ */ - (void)makeObjectsPerformSelector: (SEL)selector withObject: (nullable id)object; /*! - * @brief Returns a sorted copy of the array. + * @brief Returns a copy of the array sorted in ascending order. * * @return A sorted copy of the array */ - (OFArray OF_GENERIC(ObjectType) *)sortedArray; /*! - * @brief Returns a sorted copy of the array. + * @brief Returns a copy of the array sorted using the specified selector and + * options. + * + * @param selector The selector to use to sort the array. It's signature + * should be the same as that of @ref compare:. + * @param options The options to use when sorting the array.@n + * Possible values are: + * Value | Description + * ---------------------------|------------------------- + * `OF_ARRAY_SORT_DESCENDING` | Sort in descending order + * @return A sorted copy of the array + */ +- (OFArray OF_GENERIC(ObjectType) *)sortedArrayUsingSelector: (SEL)selector + options: (int)options; + +#ifdef OF_HAVE_BLOCKS +/*! + * @brief Returns a copy of the array sorted using the specified selector and + * options. * + * @param comparator The comparator to use to sort the array * @param options The options to use when sorting the array.@n * Possible values are: * Value | Description * ---------------------------|------------------------- * `OF_ARRAY_SORT_DESCENDING` | Sort in descending order * @return A sorted copy of the array */ -- (OFArray OF_GENERIC(ObjectType) *)sortedArrayWithOptions: (int)options; +- (OFArray OF_GENERIC(ObjectType) *) + sortedArrayUsingComparator: (of_comparator_t)comparator + options: (int)options; +#endif /*! * @brief Returns a copy of the array with the order reversed. * * @return A copy of the array with the order reversed Index: src/OFArray.m ================================================================== --- src/OFArray.m +++ src/OFArray.m @@ -733,20 +733,37 @@ [new makeImmutable]; return new; } -- (OFArray *)sortedArrayWithOptions: (int)options +- (OFArray *)sortedArrayUsingSelector: (SEL)selector + options: (int)options +{ + OFMutableArray *new = [[self mutableCopy] autorelease]; + + [new sortUsingSelector: selector + options: options]; + + [new makeImmutable]; + + return new; +} + +#ifdef OF_HAVE_BLOCKS +- (OFArray *)sortedArrayUsingComparator: (of_comparator_t)comparator + options: (int)options { OFMutableArray *new = [[self mutableCopy] autorelease]; - [new sortWithOptions: options]; + [new sortUsingComparator: comparator + options: options]; [new makeImmutable]; return new; } +#endif - (OFArray *)reversedArray { OFMutableArray *new = [[self mutableCopy] autorelease]; Index: src/OFMutableArray.h ================================================================== --- src/OFMutableArray.h +++ src/OFMutableArray.h @@ -178,24 +178,42 @@ */ - (void)exchangeObjectAtIndex: (size_t)index1 withObjectAtIndex: (size_t)index2; /*! - * @brief Sorts the array. + * @brief Sorts the array in ascending order. */ - (void)sort; /*! - * @brief Sorts the array. + * @brief Sorts the array using the specified selector and options. + * + * @param selector The selector to use to sort the array. It's signature + * should be the same as that of @ref compare:. + * @param options The options to use when sorting the array.@n + * Possible values are: + * Value | Description + * ---------------------------|------------------------- + * `OF_ARRAY_SORT_DESCENDING` | Sort in descending order + */ +- (void)sortUsingSelector: (SEL)selector + options: (int)options; + +#ifdef OF_HAVE_BLOCKS +/*! + * @brief Sorts the array using the specified comparator and options. * + * @param comparator The comparator to use to sort the array * @param options The options to use when sorting the array.@n * Possible values are: * Value | Description * ---------------------------|------------------------- * `OF_ARRAY_SORT_DESCENDING` | Sort in descending order */ -- (void)sortWithOptions: (int)options; +- (void)sortUsingComparator: (of_comparator_t)comparator + options: (int)options; +#endif /*! * @brief Reverts the order of the objects in the array. */ - (void)reverse; Index: src/OFMutableArray.m ================================================================== --- src/OFMutableArray.m +++ src/OFMutableArray.m @@ -33,12 +33,69 @@ } placeholder; @interface OFMutableArray_placeholder: OFMutableArray @end +static of_comparison_result_t +compare(id left, id right, SEL selector) +{ + of_comparison_result_t (*comparator)(id, SEL, id) = + (of_comparison_result_t (*)(id, SEL, id)) + [left methodForSelector: selector]; + + return comparator(left, selector, right); +} + +static void +quicksort(OFMutableArray *array, size_t left, size_t right, SEL selector, + int options) +{ + of_comparison_result_t ascending, descending; + + if (options & OF_ARRAY_SORT_DESCENDING) { + ascending = OF_ORDERED_DESCENDING; + descending = OF_ORDERED_ASCENDING; + } else { + ascending = OF_ORDERED_ASCENDING; + descending = OF_ORDERED_DESCENDING; + } + + while (left < right) { + size_t i = left; + size_t j = right - 1; + id pivot = [array objectAtIndex: right]; + + do { + while (compare([array objectAtIndex: i], pivot, + selector) != descending && i < right) + i++; + + while (compare([array objectAtIndex: j], pivot, + selector) != ascending && j > left) + j--; + + if (i < j) + [array exchangeObjectAtIndex: i + withObjectAtIndex: j]; + } while (i < j); + + if (compare([array objectAtIndex: i], pivot, selector) == + descending) + [array exchangeObjectAtIndex: i + withObjectAtIndex: right]; + + if (i > 0) + quicksort(array, left, i - 1, selector, options); + + left = i + 1; + } +} + +#ifdef OF_HAVE_BLOCKS static void -quicksort(OFMutableArray *array, size_t left, size_t right, int options) +quicksortWithBlock(OFMutableArray *array, size_t left, size_t right, + of_comparator_t comparator, int options) { of_comparison_result_t ascending, descending; if (options & OF_ARRAY_SORT_DESCENDING) { ascending = OF_ORDERED_DESCENDING; @@ -52,33 +109,35 @@ size_t i = left; size_t j = right - 1; id pivot = [array objectAtIndex: right]; do { - while ([[array objectAtIndex: i] compare: pivot] != + while (comparator([array objectAtIndex: i], pivot) != descending && i < right) i++; - while ([[array objectAtIndex: j] compare: pivot] != + while (comparator([array objectAtIndex: j], pivot) != ascending && j > left) j--; if (i < j) [array exchangeObjectAtIndex: i withObjectAtIndex: j]; } while (i < j); - if ([[array objectAtIndex: i] compare: pivot] == descending) + if (comparator([array objectAtIndex: i], pivot) == descending) [array exchangeObjectAtIndex: i withObjectAtIndex: right]; if (i > 0) - quicksort(array, left, i - 1, options); + quicksortWithBlock(array, left, i - 1, comparator, + options); left = i + 1; } } +#endif @implementation OFMutableArray_placeholder - init { return (id)[[OFMutableArray_adjacent alloc] init]; @@ -370,22 +429,37 @@ } } - (void)sort { - [self sortWithOptions: 0]; + [self sortUsingSelector: @selector(compare:) + options: 0]; +} + +- (void)sortUsingSelector: (SEL)selector + options: (int)options +{ + size_t count = [self count]; + + if (count == 0 || count == 1) + return; + + quicksort(self, 0, count - 1, selector, options); } -- (void)sortWithOptions: (int)options +#ifdef OF_HAVE_BLOCKS +- (void)sortUsingComparator: (of_comparator_t)comparator + options: (int)options { size_t count = [self count]; if (count == 0 || count == 1) return; - quicksort(self, 0, count - 1, options); + quicksortWithBlock(self, 0, count - 1, comparator, options); } +#endif - (void)reverse { size_t i, j, count = [self count]; Index: src/OFObject.h ================================================================== --- src/OFObject.h +++ src/OFObject.h @@ -45,10 +45,22 @@ /*! Both objects are equal */ OF_ORDERED_SAME = 0, /*! The left object is bigger than the right */ OF_ORDERED_DESCENDING = 1 } of_comparison_result_t; + +#ifdef OF_HAVE_BLOCKS +/*! + * @brief A comparator to compare two objects. + * + * @param left The left object + * @param right The right object + * @return The order of the objects + */ +typedef of_comparison_result_t (^of_comparator_t)(id _Nonnull left, + id _Nonnull right); +#endif /*! * @brief An enum for storing endianess. */ typedef enum { Index: tests/OFArrayTests.m ================================================================== --- tests/OFArrayTests.m +++ tests/OFArrayTests.m @@ -257,11 +257,12 @@ [m[1] addObject: @"0"]; [m[1] addObject: @"z"]; TEST(@"-[sortedArray]", [[m[1] sortedArray] isEqual: [arrayClass arrayWithObjects: @"0", @"Bar", @"Baz", @"Foo", @"z", nil]] && - [[m[1] sortedArrayWithOptions: OF_ARRAY_SORT_DESCENDING] + [[m[1] sortedArrayUsingSelector: @selector(compare:) + options: OF_ARRAY_SORT_DESCENDING] isEqual: [arrayClass arrayWithObjects: @"z", @"Foo", @"Baz", @"Bar", @"0", nil]]) EXPECT_EXCEPTION(@"Detect out of range in -[objectAtIndex:]", OFOutOfRangeException, [a[0] objectAtIndex: [a[0] count]])