Re: NSMutableArray comparator; sorting on insert
Re: NSMutableArray comparator; sorting on insert
- Subject: Re: NSMutableArray comparator; sorting on insert
- From: Clark Cox <email@hidden>
- Date: Fri, 16 Jan 2009 09:37:31 -0800
On Fri, Jan 16, 2009 at 8:27 AM, David Harper <email@hidden> wrote:
> Hello,
>
> I have written a comparator that returns an NSComparisonResult based on the comparison of two objects as required for
>
> [(NSMutableArray *)someArray sortUsingSelector:@selector(theSelector:)]
>
> Now, I want this array to remain sorted after each insert. For now I am inserting, then sorting, but this is not ideal. Is there a way to perform an insert using the same selector to find the correct index before inserting?
Code that I've written for just this purpose in the past essentially
performs a binary search on the array (that assumes that it's already
sorted) to find the index where I should insert the new object, and I
just insert it there. This is much more efficient than adding the
object and *then* re-sorting the array.
Something along the lines of (both methods assume that the array is
already sorted):
@interface NSMutableArray (CSCSortedInsertion)
-(void)CSC_insertObject:(id)object inArraySortedUsingSelector:(SEL)selector;
-(void)CSC_insertObjects:(NSArray*)objects
inArraySortedUsingSelector:(SEL)selector;
@end
typedef NSComparisonResult (*CompareFunction)(id,SEL,id);
@implementation NSMutableArray (CSCSortedInsertion)
static inline NSUInteger FindIndexForInsertionWithKnownBounds(NSArray
*array, id object, SEL selector, NSUInteger low, NSUInteger high) {
NSUInteger index = low;
while (index < high) {
const NSUInteger mid = (index + high)/2;
id test = [array objectAtIndex: mid];
if (((CompareFunction)objc_msgSend(test, selector, object)) < 0) {
index = mid + 1;
} else {
high = mid;
}
}
return index;
}
static inline NSUInteger FindIndexForInsertion(NSArray *array, id
object, SEL selector) {
return FindIndexForInsertionWithKnownBounds(array, object,
selector, 0, array.count);
}
-(void)CSC_insertObject:(id)object inArraySortedUsingSelector:(SEL)selector {
[self insertObject: object atIndex: FindIndexForInsertion(self,
object, selector)];
}
-(void)CSC_insertObjects:(NSArray*)objects
inArraySortedUsingSelector:(SEL)selector {
objects = [objects sortedArrayUsingSelector: selector];
NSUInteger index = 0;
NSUInteger count = self.count;
for(id object in objects) {
//Since objects is sorted, we can rule out any index that is
less than the one for the last insertion
index = FindIndexForInsertionWithKnownBounds(self, object,
selector, index, count++);
[self insertObject: object atIndex: index];
}
}
@end
--
Clark S. Cox III
email@hidden
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden