ObjFW  Check-in [daa11c19cb]

 * @param object The object to perform the selector with on all objects in the
 *	      array
 */
- (void)makeObjectsPerformSelector: (SEL)selector
			withObject: (nullable id)object;

/*!
 * @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 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) *)
    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
 */
- (OFArray OF_GENERIC(ObjectType) *)reversedArray;

	[new sort];

	[new makeImmutable];

	return new;
}

- (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 sortUsingComparator: comparator
			 options: options];

	[new makeImmutable];

	return new;
}
#endif

- (OFArray *)reversedArray
{
	OFMutableArray *new = [[self mutableCopy] autorelease];

	[new reverse];

 * @param index1 The index of the first object to exchange
 * @param index2 The index of the second object to exchange
 */
- (void)exchangeObjectAtIndex: (size_t)index1
	    withObjectAtIndex: (size_t)index2;

/*!
 * @brief Sorts the array in ascending order.
 */
- (void)sort;

/*!
 * @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)sortUsingComparator: (of_comparator_t)comparator
		    options: (int)options;
#endif

/*!
 * @brief Reverts the order of the objects in the array.
 */
- (void)reverse;

/*!

static struct {
	Class isa;
} 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
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;
		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 (comparator([array objectAtIndex: i], pivot) !=
			    descending && i < right)
				i++;

			while (comparator([array objectAtIndex: j], pivot) !=
			    ascending && j > left)
				j--;

			if (i < j)
				[array exchangeObjectAtIndex: i
					   withObjectAtIndex: j];
		} while (i < j);

		if (comparator([array objectAtIndex: i], pivot) == descending)
			[array exchangeObjectAtIndex: i
				   withObjectAtIndex: right];

		if (i > 0)
			quicksortWithBlock(array, left, i - 1, comparator,
			    options);

		left = i + 1;
	}
}
#endif

@implementation OFMutableArray_placeholder
- init
{
	return (id)[[OFMutableArray_adjacent alloc] init];
}

	} @finally {
		[object1 release];
	}
}

- (void)sort
{
	[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);
}

#ifdef OF_HAVE_BLOCKS
- (void)sortUsingComparator: (of_comparator_t)comparator
		    options: (int)options
{
	size_t count = [self count];

	if (count == 0 || count == 1)
		return;

	quicksortWithBlock(self, 0, count - 1, comparator, options);
}
#endif

- (void)reverse
{
	size_t i, j, count = [self count];

	if (count == 0 || count == 1)
		return;

	/*! The left object is smaller than the right */
	OF_ORDERED_ASCENDING = -1,
	/*! 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 {
	/*! Most significant byte first (big endian) */
	OF_BYTE_ORDER_BIG_ENDIAN,

	m[1] = [[a[0] mutableCopy] autorelease];
	[m[1] addObject: @"0"];
	[m[1] addObject: @"z"];
	TEST(@"-[sortedArray]",
	    [[m[1] sortedArray] isEqual: [arrayClass arrayWithObjects:
	    @"0", @"Bar", @"Baz", @"Foo", @"z", nil]] &&
	    [[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]])

	EXPECT_EXCEPTION(@"Detect out of range in -[removeObjectsInRange:]",