On Fri, Jan 16, 2009 at 8:27 AM, David Harper <dave.har...@rogers.com> 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 clarkc...@gmail.com _______________________________________________ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com