28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
static struct {
Class isa;
} placeholder;
@interface OFMutableArrayPlaceholder: OFMutableArray
@end
static OFComparisonResult
compare(id left, id right, SEL selector)
{
OFComparisonResult (*comparator)(id, SEL, id) =
(OFComparisonResult (*)(id, SEL, id))
[left methodForSelector: selector];
return comparator(left, selector, right);
}
quicksort(OFMutableArray *array, size_t left, size_t right, SEL selector,
OFArraySortOptions options)
{
OFComparisonResult ascending, descending;
if (options & OFArraySortDescending) {
ascending = OFOrderedDescending;
descending = OFOrderedAscending;
} else {
ascending = OFOrderedAscending;
descending = OFOrderedDescending;
}
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;
}
}
static void
quicksortWithFunction(OFMutableArray *array, size_t left, size_t right,
OFCompareFunction compare, void *context, OFArraySortOptions options)
{
OFComparisonResult ascending, descending;
if (options & OFArraySortDescending) {
ascending = OFOrderedDescending;
descending = OFOrderedAscending;
|
<
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
static struct {
Class isa;
} placeholder;
@interface OFMutableArrayPlaceholder: OFMutableArray
@end
static void
quicksort(OFMutableArray *array, size_t left, size_t right,
OFCompareFunction compare, void *context, OFArraySortOptions options)
{
OFComparisonResult ascending, descending;
if (options & OFArraySortDescending) {
ascending = OFOrderedDescending;
descending = OFOrderedAscending;
|
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
if (compare([array objectAtIndex: i], pivot, context) ==
descending)
[array exchangeObjectAtIndex: i
withObjectAtIndex: right];
if (i > 0)
quicksortWithFunction(array, left, i - 1, compare,
context, options);
left = i + 1;
}
}
@implementation OFMutableArrayPlaceholder
- (instancetype)init
|
|
|
|
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
if (compare([array objectAtIndex: i], pivot, context) ==
descending)
[array exchangeObjectAtIndex: i
withObjectAtIndex: right];
if (i > 0)
quicksort(array, left, i - 1, compare, context,
options);
left = i + 1;
}
}
@implementation OFMutableArrayPlaceholder
- (instancetype)init
|
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
|
}
}
- (void)sort
{
[self sortUsingSelector: @selector(compare:) options: 0];
}
- (void)sortUsingSelector: (SEL)selector
options: (OFArraySortOptions)options
{
size_t count = self.count;
if (count == 0 || count == 1)
return;
quicksort(self, 0, count - 1, selector, options);
}
- (void)sortUsingFunction: (OFCompareFunction)compare
context: (void *)context
options: (OFArraySortOptions)options
{
size_t count = self.count;
if (count == 0 || count == 1)
return;
quicksortWithFunction(self, 0, count - 1, compare, context, options);
}
#ifdef OF_HAVE_BLOCKS
static OFComparisonResult
blockCompare(id left, id right, void *context)
{
OFComparator block = (OFComparator)context;
return block(left, right);
}
- (void)sortUsingComparator: (OFComparator)comparator
options: (OFArraySortOptions)options
{
size_t count = self.count;
if (count == 0 || count == 1)
return;
quicksortWithFunction(self, 0, count - 1, blockCompare, comparator,
options);
}
#endif
- (void)reverse
{
size_t i, j, count = self.count;
|
>
>
>
>
>
>
>
>
>
>
>
|
|
|
<
|
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
|
}
}
- (void)sort
{
[self sortUsingSelector: @selector(compare:) options: 0];
}
static OFComparisonResult
selectorCompare(id left, id right, void *context)
{
SEL selector = context;
OFComparisonResult (*comparator)(id, SEL, id) =
(OFComparisonResult (*)(id, SEL, id))
[left methodForSelector: selector];
return comparator(left, selector, right);
}
- (void)sortUsingSelector: (SEL)selector
options: (OFArraySortOptions)options
{
size_t count = self.count;
if (count == 0 || count == 1)
return;
quicksort(self, 0, count - 1, selectorCompare, selector, options);
}
- (void)sortUsingFunction: (OFCompareFunction)compare
context: (void *)context
options: (OFArraySortOptions)options
{
size_t count = self.count;
if (count == 0 || count == 1)
return;
quicksort(self, 0, count - 1, compare, context, options);
}
#ifdef OF_HAVE_BLOCKS
static OFComparisonResult
blockCompare(id left, id right, void *context)
{
OFComparator block = (OFComparator)context;
return block(left, right);
}
- (void)sortUsingComparator: (OFComparator)comparator
options: (OFArraySortOptions)options
{
size_t count = self.count;
if (count == 0 || count == 1)
return;
quicksort(self, 0, count - 1, blockCompare, comparator, options);
}
#endif
- (void)reverse
{
size_t i, j, count = self.count;
|