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
|
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
+
+
+
+
+
+
+
+
+
+
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
+
-
+
-
+
-
+
+
+
|
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, int options)
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 ([[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];
}
|
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
|
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
465
466
467
|
+
-
+
+
-
+
+
+
+
+
+
+
+
+
+
+
+
+
-
+
+
|
} @finally {
[object1 release];
}
}
- (void)sort
{
[self sortUsingSelector: @selector(compare:)
[self sortWithOptions: 0];
options: 0];
}
- (void)sortUsingSelector: (SEL)selector
- (void)sortWithOptions: (int)options
quicksort(self, 0, count - 1, options);
quicksortWithBlock(self, 0, count - 1, comparator, options);
}
#endif
- (void)reverse
{
size_t i, j, count = [self count];
if (count == 0 || count == 1)
return;
|