This is SortList.m in view mode; [Download] [Up]
/*
* A subclass of List with a built-in sorting capability. The ShellSort
* code from the example program "SortingInAction" is used here, modified
* slightly to work closely with the List object's data representation, i.e.
* the array of objects pointed to by 'dataPtr'.
*
* The user of this class must set the SortingList's delegate to an object
* which responds to the 'lessThan:(int)position1 :(int)position2' method,
* which returns YES if object1 should be deemed to be "less than" object2
* in a way that makes sense to the caller.
*
* Written by Rich Plevin, 24 Jun 92.
*
* This code may be freely used, copied and modified. The author disclaims
* any warranty of any kind, expressed or implied, as to its fitness for any
* particular use.
*
* 8/18/92 - More general structure implemented (can set sort, comparison, and
* value methods. (value method returns the value for sorted key). added
* insertion method which inserts object in order. added sort flag and
* autosort feature.
*
* 8/19/92 - Added mergeList method and overrode indexOf to use binary search
*
* For legal stuff see the file COPYRIGHT
*/
#include "SortList.h"
#define STRIDE_FACTOR 3 // good value for stride factor is not well-understood
// 3 is a fairly good choice (Sedgewick)
@implementation SortList
- _updateChain
{
if (!delegate) {
compObject = self;
if ([self respondsTo:compareMethod]) {
compMethod = compareMethod;
}
else {
compMethod = @selector(compare::);
}
}
else {
if ([delegate respondsTo:compareMethod]) {
compObject = delegate;
compMethod = compareMethod;
}
else if ([delegate respondsTo:@selector(compare::)]) {
compObject = delegate;
compMethod = @selector(compare::);
}
else if ([self respondsTo:compareMethod]) {
compObject = self;
compMethod = compareMethod;
}
else {
compObject = self;
compMethod = @selector(compare::);
}
}
return self;
}
- initCount:(unsigned int)numSlots
{
[super initCount:numSlots];
compareMethod = @selector(compare::);
compMethod = @selector(compare::);
sortMethod = @selector(shellsort);
compObject = self;
sorted = NO;
autoSort = NO;
return self;
}
- (unsigned int)indexOf:anObject
/* overridden to use binary search. assumes that object used for search and
* object in list return the same key value
*/
{
int index1 = 0, index2 = numElements - 1, mid, mark, val;
if (anObject == nil)
return NX_NOT_IN_LIST;
if (sorted == NO)
return [super indexOf:anObject];
mid = (index2 + index1)/2;
while (mid > index1) {
if (anObject == dataPtr[mid])
return mid;
if ((val = (int)[compObject perform:compMethod with:anObject
with:dataPtr[mid]]) < 0) {
index2 = mid;
}
else if (val == 0) {
mark = mid;
while (val == 0) {
if (anObject == dataPtr[mark]) {
return mark;
}
mark--;
val = (int)[compObject perform:compMethod with:anObject
with:dataPtr[mark]];
}
mark = mid + 1;
while (val == 0) {
if (anObject == dataPtr[mark]) {
return mark;
}
mark++;
val = (int)[compObject perform:compMethod with:anObject
with:dataPtr[mark]];
}
return NX_NOT_IN_LIST;
}
else {
index1 = mid;
}
mid = (index2 + index1)/2;
}
if (anObject == dataPtr[index1]) {
return index1;
}
if (anObject == dataPtr[index2]) {
return index2;
}
return NX_NOT_IN_LIST;
}
- addObject:anObject
{
if (anObject == nil) return nil;
[super addObject:anObject];
[self update];
return self;
}
- addObjectIfAbsent:anObject
{
if (anObject == nil) return nil;
[super addObjectIfAbsent:anObject];
[self update];
return self;
}
- insertObject:anObject at:(unsigned int)index
{
id returnObj;
if (returnObj = [super insertObject:anObject at:index])
[self update];
return returnObj;
}
- replaceObject:anObject with:newObject
{
id returnObj;
if (returnObj = [super replaceObject:anObject with:newObject])
[self update];
return returnObj;
}
- replaceObjectAt:(unsigned int)index with:newObject;
{
id returnObj;
if (returnObj = [super replaceObjectAt:index with:newObject])
[self update];
return returnObj;
}
- update
/* sorts list if autoSort is enabled, otherwise just sets the sorted flag
* to NO.
*/
{
if (autoSort)
[self sort];
else
sorted = NO;
return self;
}
- (BOOL)isSorted
{
return sorted;
}
- setAutoSort:(BOOL)sortFlag
{
autoSort = sortFlag;
return self;
}
- (BOOL)doesAutoSort
{
return autoSort;
}
- setDelegate:obj
{
delegate = obj;
[self _updateChain];
return self;
}
- delegate
{
return delegate;
}
- useSortMethod:(SEL)method
/* sort method can be defined in a subclass or in a delegate(??). when -sort
* is called, the SortList first checks the delegate then itself. If neither
* can respond, then a default(shellsort) is used.
*/
{
sortMethod = method;
return self;
}
- (SEL)sortMethod
{
return sortMethod;
}
- useComparisonMethod:(SEL)method
/* sets the method used to compare the objects. Overrides SortList's and
* delegate's -compare:: methods. Note that the compare method can, and in
* most cases should, use the set valueMethod, if any were set.
*/
{
compareMethod = method;
[self _updateChain];
return self;
}
- (SEL)comparisonMethod
{
return compareMethod;
}
- useValueMethod:(SEL)method
/* sets method used to get value for sort key from objects. */
{
valueMethod = method;
return self;
}
- (SEL)valueMethod
{
return valueMethod;
}
- sort
/* the chain goes something like this: delegate:sortMethod, self:sortMethod,
* self:shellsort (default).
*/
{
if (!delegate) {
if ([self respondsTo:sortMethod])
[self perform:sortMethod with:self];
else [self shellsort];
}
else {
if ([delegate respondsTo:sortMethod])
[delegate perform:sortMethod with:self];
else if ([self respondsTo:sortMethod]) {
[self perform:sortMethod with:self];
}
else [self shellsort];
}
sorted = YES;
return self;
}
- insertObject:anObject
/* Inserts object into list in sorted order. if the list is not sorted, the
* list sorts itself regardless of whether autosort is enabled.
*/
{
int index1 = 0, index2 = numElements - 1, mid, val;
if (!sorted)
[self sort];
if (anObject == nil)
return nil;
mid = (index2 + index1)/2;
if ([self count] == 0) {
[self insertObject:anObject at:0];
return self;
}
while (mid > index1) {
if (anObject == dataPtr[mid])
return self;
if ((val = (int)[compObject perform:compMethod with:anObject
with:dataPtr[mid]]) < 0) {
index2 = mid;
} else if (val == 0) {
[self insertObject:anObject at:mid + 1];
return self;
} else {
index1 = mid;
}
mid = (index2 + index1)/2;
} if ((val = (int)[compObject perform:compMethod with:anObject
with:dataPtr[index1]]) < 0) {
[self insertObject:anObject at:index1];
} else if ((val = (int)[compObject perform:compMethod with:anObject
with:dataPtr[index2]]) > 0) {
[self insertObject:anObject at:index2 + 1];
} else {
[self insertObject:anObject at:index1 + 1];
}
sorted = YES;
return self;
}
- mergeList:otherList
/* merges otherList into the list, the new list is sorted. */
{
int i, j, val, ocount;
BOOL otherSorted, isSortList;
if (![otherList isKindOf:[List class]]) {
return nil;
}
if ([otherList respondsTo:@selector(isSorted)] &&
[otherList respondsTo:@selector(sort)]) {
isSortList = YES;
otherSorted = [otherList isSorted];
}
else {
otherSorted = NO;
isSortList = NO;
}
ocount = [otherList count];
i = j = 0;
if (!otherSorted && sorted) {
for (i = 0; i < ocount; i++) {
[self insertObject:[otherList objectAt:i]];
}
}
else if (otherSorted && sorted) {
while (j < ocount) {
while ((val = (int)[compObject perform:compMethod
with:dataPtr[i]
with:[otherList objectAt:j]]) < 0) {
i++;
if (i >= numElements) {
i = numElements - 1;
}
}
[self insertObject:[otherList objectAt:j] at:i];
j++;
}
}
else if (!otherSorted && !sorted) {
[self appendList:otherList];
[self sort];
}
return self;
}
- (unsigned int)indexOfObjectWithKey:proxy
{
int index1 = 0, index2 = numElements - 1, mid, mark, val;
if (proxy == nil || [self count] == 0)
return NX_NOT_IN_LIST;
if (sorted == NO) {
[self sort];
}
// return [super indexOf:anObject];
mid = (index2 + index1)/2;
while (mid > index1) {
if ((val = (int)[compObject perform:compMethod with:proxy
with:dataPtr[mid]]) < 0) {
index2 = mid;
}
else if (val == 0) {
mark = mid;
while (val == 0) {
mark--;
val = (int)[compObject perform:compMethod with:proxy
with:dataPtr[mark]];
}
return mark + 1;
}
else {
index1 = mid;
}
mid = (index2 + index1)/2;
}
if (((int)[compObject perform:compMethod with:proxy
with:dataPtr[index1]]) == 0) {
return index1;
}
if (((int)[compObject perform:compMethod with:proxy
with:dataPtr[index2]]) == 0) {
return index2;
}
return NX_NOT_IN_LIST;
}
/*
* This code was extracted from the /NextDeveloper/Examples/SortingInAction program.
* The original author's comment:
*
* Because Shellsort is a variation on Insertion Sort, it has the same
* inconsistency that I noted in the InsertionSort class. Notice where I
* subtract a move to compensate for calling a swap for visual purposes.
*
* Author: Julie Zelenski, NeXT Developer Support
* You may freely copy, distribute and reuse the code in this example.
* NeXT disclaims any warranty of any kind, expressed or implied, as to
* its fitness for any particular use.
*
* [This sounds like there is unnecessary work happening in this routine, but I
* didn't dig into it enough to figure out what to change - rjp]
*
* Depending on what methods are set (and whether a delegate is set), the
* comparison method will vary. The chain of precedence is:
* delegate:comparisonMethod, delegate:compare::, self:comparisonMethod,
* self:compare::.
*/
- shellsort
{
int c, d, stride;
BOOL found;
stride = 1;
while (stride <= numElements)
stride = stride * STRIDE_FACTOR + 1;
while (stride > STRIDE_FACTOR - 1 ) {
/* loop to sort for each value of stride */
stride = stride / STRIDE_FACTOR;
for (c = stride; c < numElements; c++) {
found = NO;
d = c - stride;
while ( d >= 0 && !found ) {
/* move to left until correct place */
int target = d + stride ;
if ((int)[compObject perform:compMethod
with:dataPtr[target]
with:dataPtr[d]] < 0) {
id tmp = dataPtr[target]; /* swap the elements */
dataPtr[target] = dataPtr[d];
dataPtr[d] = tmp ;
d -= stride; /* jump by stride factor */
} else
found = YES;
}
}
}
return self;
}
- (int)compare:object1 :object2
{
if ([object1 respondsTo:valueMethod] &&
[object2 respondsTo:valueMethod]) {
return [object1 perform:valueMethod] -
[object2 perform:valueMethod];
}
else
return ((int)object1) - ((int)object2);
}
@end
@implementation SortingListDelegate
/*
* Dummy delegated method
*/
- (int)compare:object1 :object2
{
return 0;
}
- sort:aList
{
[aList shellsort];
return self;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.