- Inherits From:
- NSObject
- Declared In:
- EDSortedArray.h
This behaviour can be emulated, of course, using NSMutableArrays and (binary) search but EDSortedArray, which is based on red-black trees, has better performance characteristics. When objects are inserted into ordered collections, O(lg n) instead of O(n). Contains and index-of tests can also be carried out in O(lg n) instead of O(n). Inserting/removing at the end and retrieving objects by index is marginally slower, O(lg n) instead of O(1). NSSets are even faster at contains tests, O(1), but they do no support ordered collections. The main disadvantage of binary search trees is their memory usage, 20 bytes per object rather than 4 to 8 in an array.
A final note: NSArrays are implemented extremely well and in collections with less than at least about 3000 objects performance gains are negligible; NSArray might even be faster! However, beyond a certain size the performance difference is more than noticeable. In the end, you might still want to use the tree based sorted arrays unless you already have the binary search insert written somewhere else.
This datastructure does not implement the copying and coding protocols as binary search trees are usually required in the context of algorithms, rather than data storage.
SEL comparator;
void *sentinel;
void *rootNode;
void *minimumNode;
comparator All instance variables are private. sentinel rootNode minimumNode
Creating sorted arraysAdding and removing objects
- - init
- - initWithComparisonSelector:
Querying the array
- - addObject:
- - addObjectsFromArray:
- - removeObject:
- - removeObjectAtIndex:
Retrieving the comparison selector
- - count
- - minimumObject
- - maximumObject
- - containsObject:
- - member:
- - smallerOrEqualMember:
- - successorForObject:
- - objectAtIndex:
- - indexOfObject:
- - objectEnumerator
- - allObjects
- - comparisonSelector
- (void)addObject:(id)anObject
Adds the specified object to the receiver. anObject is sent a retain message as it is added to the receiver.
- (void)addObjectsFromArray:(NSArray *)someObjects
Adds each object contained in someObjects to the receiver. The objects are sent a retain message.
- (NSArray *)allObjects
Returns an array containing the receiver's objects, or an empty array if the receiver has no objects. The order of the objects in the array is the same as in the receiver.
- (SEL)comparisonSelector
Returns the selector that is used to compare objects in the tree.
- (BOOL)containsObject:(id)anObject
Returns YES if anObject is present in the receiver, NO otherwise.
- (unsigned int)count
Returns the number of objects in the receiver.
- (unsigned int)indexOfObject:(id)anObject
Returns the lowest index whose corresponding object is equal to anObject. Objects are considered equal if invoking the comparison method in one with the other as parameter returns NSOrderedSame. If none of the objects in the receiver are equal to anObject, indexOfObject: returns NSNotFound.
- (id)init
Initialises a newly allocated red-black tree with compare: as comparison selector.
- (id)initWithComparisonSelector:(SEL)aSelector
Initialises a newly allocated red-black tree with aSelector as comparison selector.
- (id)maximumObject
Returns the largest object (as defined by the comparison selector) in the receiver.
- (id)member:(id)anObject
If anObject is present in the receiver (as determined by the comparison selector), the instance in the receiver is returned. Otherwise, returns nil.
- (id)minimumObject
Returns the smallest object (as defined by the comparison selector) in the receiver.
- (id)objectAtIndex:(unsigned int)index
Returns the object located at index. If index is too large, i.e. if index is greater than or equal to the value returned by count, an NSInvalidArgumentException is raised.
- (NSEnumerator *)objectEnumerator
Returns an enumerator object that lets you access each object in the receiver, in order, starting with the element at index 0. You should not modify the receiver while using the enumerator. For a more detailed explanation and sample code see the description of the same method in NSArray.
- (void)removeObject:(id)anObject
Removes anObject from the receiver. The removed object is sent a release message. This method raises an exception if anObject was not in the tree before.
Note that it is possible to have several objects that compare as equal in the tree. This method will remove any one of them.
- (void)removeObjectAtIndex:(unsigned int)index
Removes the object at index. The removed object receives a release message. If index is too large, i.e. if index is greater than or equal to the value returned by count, an NSInvalidArgumentException is raised.
- (id)smallerOrEqualMember:(id)anObject
If anObject is present in the receiver (as determined by the comparison selector), the instance in the receiver is returned. Otherwise, returns the greatest object smaller than anObject, or nil if no such object exists.
- (id)successorForObject:(id)anObject
Returns the object directly following anObject in the order defined by the comparison selector or nil if anObject is the largest object.