This is SortedList.m in view mode; [Download] [Up]
/*###########################################################
Written by Don McGregor Version 1.0, Feb 1992.
This code is free for any use. GNU copyleft
rules apply. This code has no warrantability
of fitness for a particular use, I am not
responsible for any damage to data that might
be caused by bugs, etc, etc.
I encourage others to examine and improve on this
code, and to post the improvements to the net.
Don McGregor, mcgregdr@conan.ie.orst.edu (for now).
$Log: SortedList.m,v $
Revision 1.4 94/05/29 15:00:38 ediger
change some printf format specs to eliminate compiler warnings
Revision 1.3 93/10/28 23:10:29 ediger
corrected comparison between two UNSIGNED_LONG keys. didn't do it at all
correctly due to sloppy, cut-n-paste-without thinking style.
Revision 1.2 93/10/27 23:45:02 ediger
SortedList that handles "unsigned longs" as one of the built-in data
types it sorts on. Still doesn't sort correctly, though.
###########################################################*/
#import "SortedList.h"
@implementation SortedList
static char rcsident[] = "$Id";
+ initialize
{
/*-----------------------------------------------------------
Sets the class version; useful for unarchiving several
older versions of the object as time improves it.
-----------------------------------------------------------*/
[SortedList setVersion:CURRENT_SORTED_LIST_VERSION];
return self;
}
- initCount:(unsigned int)numSlots
{
/*-----------------------------------------------------------
Initialize the data and internal structures. This should
not be used to reinitialize an already alloc'd and init'd
instance; instead, free the list first and then create
a new one.
This is the designated initializer for the class.
-----------------------------------------------------------*/
[super initCount:numSlots];
sortOrder = ASCENDING;
caseSensitive = YES;
keyDataType = -1; //causes error if not set
//to something else
return self;
}
- setKeyMethod:(SEL)theMethod
{
/*-----------------------------------------------------------
set the method used to sort the key by. This uses the SEL to
do that, so the user can set an arbitrary method by which
to sort, rather than forcing a particular method name to be
used on the objects that make up the sortedList.
This also checks to make sure all the objects currently in
the list can respond to the message. If any object can't,
nil is returned instead of self. (The key method is still
reset, though.)
if the accessor method is new the SortedList is also completely
resorted when this method is called. Since there is a new
accessor method, the list order might be completely different.
-----------------------------------------------------------*/
int i, listSize;
BOOL uhOh = NO;
if(keyMethod != theMethod)
{
keyMethod = theMethod;
listSize = [self count]; //Could have just directly gotten inst. var...
for(i = 0; i < listSize; i++)
{
if(!([[self objectAt:i] respondsTo:keyMethod]))
uhOh = YES;
}
if(uhOh == YES) //Return nil, punt on trying to reorder list
return nil;
[self insertionSort]; //new accessor method, new order too.
}
return self;
}
- (SEL)keyMethod
{
/*-----------------------------------------------------------
Returns the method by which the sortedList finds the
key the list is sorted by.
-----------------------------------------------------------*/
return keyMethod;
}
- setSortOrder:(int)theSortOrder
{
/*-----------------------------------------------------------
Just sets the way in which the sortedList is maintained,
either ascending order (1,2,3,4...) or descending (5,4,3,2,1).
Also resorts the list if this is a change from the prior
sort order. This can be done by simply reversing the order
of the list; no fancy sorts needed. This does it by removing
the top object and putting it at the end size times.
Can't use addObject: in the for loop, even though it looks
like a good place for it; that method calls insertObject:at:
internally and sends the message to self. that blows up
when the message gets sent to this object.
-----------------------------------------------------------*/
int i, size;
id tempObj;
if(sortOrder != theSortOrder)
{
sortOrder = theSortOrder;
size = [self count];
for(i = 0; i < size; i++)
{
tempObj = [self removeObjectAt:0];
[super insertObject:tempObj at:(size - 1)];
}
}
return self;
}
- (int)sortOrder
{
/*-----------------------------------------------------------
Returns the sort order.
-----------------------------------------------------------*/
return sortOrder;
}
-setCaseSensitive:(BOOL)isIt
{
/*-----------------------------------------------------------
Whether or not compares on strings are case sensitive
-----------------------------------------------------------*/
caseSensitive = isIt;
return self;
}
- (BOOL)caseSensitive
{
return caseSensitive;
}
- setKeyDataType:(int)theKeyDataType
{
/*-----------------------------------------------------------
sets a flag that tells of the type of data contained the
list is sorted by. Right now this is DOUBLE, FLOAT, INT,
or ATOM (NXAtoms, the NeXT version of strings).
-----------------------------------------------------------*/
keyDataType = theKeyDataType;
return self;
}
- (int)keyDataType
{
/*-----------------------------------------------------------
Returns the type of data the list is sorted by.
-----------------------------------------------------------*/
return keyDataType;
}
- printKeyValues
{
/*-----------------------------------------------------------
Prints out the key values of the objects in the sortedList,
in the order they are stored in the list. This is really
just an internal debugging sort of thing, but most people
wind up using something like this sooner or later.
This method should not be called in any production code.
-----------------------------------------------------------*/
int count, i;
id listObject;
printf("---------------\n");
count = [self count];
for(i = 0; i < count; i++)
{
listObject = [self objectAt:i];
switch(keyDataType)
{
case DOUBLE:
printf("%d: %g, for object %p\n", i,
((double(*)())[listObject methodFor:keyMethod])(), listObject);
break;
case FLOAT:
printf("%d: %g, for object %p\n", i,
((float(*)())[listObject methodFor:keyMethod])(), listObject);
break;
case INT:
printf("%d: %d, for object %p\n", i,
((int(*)())[listObject methodFor:keyMethod])(), listObject);
break;
case UNSIGNED_LONG:
printf("%lx: %lx, for object %p\n", i,
((int(*)())[listObject methodFor:keyMethod])(), listObject);
break;
case ATOM: printf("%d: %s, for object %p\n", i,
(char *)[[self objectAt:i] perform:keyMethod], listObject);
break;
default: [self error:"attempt print contents of SortedList when the key value of object is of unknown type"];
break;
}
}
printf("---------------\n");
return self;
}
- addObject:anObject
{
/*-----------------------------------------------------------
Adds an object to the sortedList. Uses a binary search to
find the insert point.
By convention, the "top" of the list is at 0, and the "bottom"
of the list is at the last slot. Conceptually this is a
top-to bottom arrangement, a convention followed in naming
the variables here.
If the object does not respond to the accessor method, we
should catch it here and punt big-time.
-----------------------------------------------------------*/
int topPtr = 0, bottomPtr, pivot;
int compareResult;
bottomPtr = [self count] - 1;
pivot = (int)((topPtr + bottomPtr)/2);
//Make sure the new object can respond to the accessor
//method.
if(!([anObject respondsTo:keyMethod]))
{
[self error:"attempt to add object to SortedList without correct accesor method. The object was of Class %s\n", [anObject name]];
return nil;
}
//empty list; insert and get out of here
if(bottomPtr == -1)
{
[super insertObject:anObject at:0];
return self;
}
//The real interest. Do a binary search until the insertion pt
//is found.
compareResult = [self compare:[self objectAt:pivot] to:anObject];
do
{
if(compareResult > 0)
bottomPtr = pivot - 1;
else
topPtr = pivot + 1;
pivot = (int)((topPtr + bottomPtr)/2);
compareResult = [self compare:[self objectAt:pivot] to:anObject];
}
while ((compareResult != 0) && (topPtr < bottomPtr));
//Insert the new object
if(compareResult >= 0)
[super insertObject:anObject at:pivot];
else
[super insertObject:anObject at:pivot+1];
return self;
}
- addObjectIfAbsent:anObject
{
/*-----------------------------------------------------------
More overrides of List methods. We need to make sure all additions
are done through the addObject: method to ensure it all stays
sorted.
-----------------------------------------------------------*/
if([self indexOf:anObject] == NX_NOT_IN_LIST)
{
[self addObject:anObject];
}
return self;
}
- (BOOL)isEqual:anObject
{
/*-----------------------------------------------------------
Similar to the list op,which compares the to lists for equality.
We also need to check for the new instance vars declared
in this object, and make sure this is a SortedList rather
than just a List.
-----------------------------------------------------------*/
if([self class] != [anObject class])
return NO;
if(([anObject sortOrder] != [self sortOrder]) ||
([anObject keyMethod] != [self keyMethod]) ||
([anObject caseSensitive] != [self caseSensitive]) ||
([anObject keyDataType] != [self keyDataType]))
return NO;
return [super isEqual:anObject];
}
- (int)compare:thisObject to:thatObject
{
/*-----------------------------------------------------------
Compares the values of the keys of thisObject and thatObject.
returns a number larger than zero if the first object's key is
larger than the other object's, a number smaller than zero if
the first object is less than the second, and zero if they have
the same key values. For complex sorts, "larger" means that it
comes after the object when sorted in ascending order.
This can deal with ints, doubles, floats, and atoms at this point.
Feel free to expand it to other types.
There is a built-in capability to expand this to other comparision
(sorting) operations, perhaps with complex structs or multiple
keys. If the return type is not one of the pre-defined (and fairly
common) types such as int, double, or atom, the program
sends the SEL message to thisObject with an argument of thatObject.
The OBJECTS IN THE LIST should respond to this message and return
the results of a comparision operation. Eg,
result = [thisObject compareTo:thatObject];
return result;
where the compareTo: method takes the other object as an arg,
and does the possibly complex comparision. If thisObject is
"greater" than thatObject, by whatever criterion, the method
should return an int greater than zero. If thisObject is "less"
than thatObject, it should return a negative integer, and if the
two are equal zero should be returned.
The ATOM type is case sensitive by default. The default string
ordering table is used. You should be using NXUniqueString to to
the atoms before passing them in, and the should be null-terminated.
-----------------------------------------------------------*/
//protos for ptr to function that returns a <type> and takes the usual
//objc parameters: an id and a SEL.
typedef double (*keyValueFunctionDouble)(id, SEL);
typedef int (*keyValueFunctionInt)(id, SEL);
typedef NXAtom (*keyValueFunctionAtom)(id, SEL);
typedef float (*keyValueFunctionFloat)(id, SEL);
typedef unsigned long (*keyValueFunctionUnsignedLong)(id, SEL);
//pointer to key value function for each of the objects passed in.
//A function pointer for each type that the sortedList can hold.
keyValueFunctionDouble thisObjectKeyFunctionDouble,
thatObjectKeyFunctionDouble;
keyValueFunctionInt thisObjectKeyFunctionInt,
thatObjectKeyFunctionInt;
keyValueFunctionUnsignedLong thisObjectKeyFunctionUnsignedLong,
thatObjectKeyFunctionUnsignedLong;
keyValueFunctionFloat thisObjectKeyFunctionFloat,
thatObjectKeyFunctionFloat;
double compareResults; //difference between two numerics
int orderFlag;
//This can be either ascending or descending. To do with compares we'll
//just use a flag, -1 or 1, and multiply that by the integer result.
//that'll flip the comparision results depending on asc or desc.
orderFlag = (sortOrder == ASCENDING) ? 1 : -1;
switch(keyDataType)
{
case DOUBLE:
thisObjectKeyFunctionDouble = (keyValueFunctionDouble)[thisObject methodFor:keyMethod];
thatObjectKeyFunctionDouble = (keyValueFunctionDouble)[thatObject methodFor:keyMethod];
compareResults = ( thisObjectKeyFunctionDouble(thisObject, keyMethod) -
thatObjectKeyFunctionDouble(thatObject, keyMethod));
//return -1, 0, or 1.
if(compareResults < 0) return orderFlag * (-1);
if(compareResults > 0) return orderFlag * 1;
return 0;
break;
case FLOAT:
thisObjectKeyFunctionFloat = (keyValueFunctionFloat)[thisObject methodFor:keyMethod];
thatObjectKeyFunctionFloat = (keyValueFunctionFloat)[thatObject methodFor:keyMethod];
compareResults = (double)( thisObjectKeyFunctionFloat(thisObject, keyMethod) -
thatObjectKeyFunctionFloat(thatObject, keyMethod));
//return -1, 0, or 1.
if(compareResults < 0) return orderFlag * (-1);
if(compareResults > 0) return orderFlag * 1;
return 0;
break;
case INT:
thisObjectKeyFunctionInt = (keyValueFunctionInt)[thisObject methodFor:keyMethod];
thatObjectKeyFunctionInt = (keyValueFunctionInt)[thatObject methodFor:keyMethod];
compareResults = (double)( thisObjectKeyFunctionInt(thisObject, keyMethod) -
thatObjectKeyFunctionInt(thatObject, keyMethod));
//return -1, 0, or 1.
if(compareResults < 0) return orderFlag * (-1);
if(compareResults > 0) return orderFlag * 1;
return 0;
break;
case UNSIGNED_LONG:
thisObjectKeyFunctionUnsignedLong
= (keyValueFunctionUnsignedLong)[thisObject methodFor:keyMethod];
thatObjectKeyFunctionUnsignedLong
= (keyValueFunctionUnsignedLong)[thatObject methodFor:keyMethod];
//return -1, 0, or 1.
if(thisObjectKeyFunctionUnsignedLong(thisObject, keyMethod)
< thatObjectKeyFunctionUnsignedLong(thatObject, keyMethod))
return orderFlag * (-1);
if(thisObjectKeyFunctionUnsignedLong(thisObject, keyMethod)
> thatObjectKeyFunctionUnsignedLong(thatObject, keyMethod))
return orderFlag * 1;
return 0;
break;
case ATOM:
return orderFlag * NXOrderStrings((unsigned char*)[thisObject perform:keyMethod],
(unsigned char *)[thatObject perform:keyMethod],
caseSensitive, -1, NULL);
break;
case OTHER:
return orderFlag * (int)[thisObject perform:keyMethod with:thisObject];
break;
default: [self error:"unspecified type of comparision operator\n"];
}
return 0; //foo-faw to fool the compiler; should never get here
}
- insertionSort;
{
/*-----------------------------------------------------------
do a simple insertion sort. This is good for files that
are "alomst sorted", as I suspect that many data sets
will be in this application. Besides, it's easy to program
and I'm lazy right now :-)
I'm sure someone can do something more sophisticated
than this.
-----------------------------------------------------------*/
int i, j, dataSize, compareResult;
id listEl;
dataSize = [self count];
for(i = 1; i < dataSize; i++)
{
j = i-1;
listEl = [self objectAt:i];
while(((compareResult = [self compare:[self objectAt:j] to:listEl]) > 0) &&
(j >=1))
j--;
if(compareResult > 0)
{
[super removeObjectAt:i];
[super insertObject:listEl at:j];
}
}
return self;
}
-copy
{
/*-----------------------------------------------------------
An override to keep things hunky-dory with all the instance
vars.
-----------------------------------------------------------*/
id newList;
newList = [super copy];
[newList setKeyMethod: [self keyMethod]];
[newList setSortOrder: [self sortOrder]];
[newList setCaseSensitive: [self caseSensitive]];
[newList setKeyDataType: [self keyDataType]];
return newList;
}
-copyFromZone:(NXZone*)zone
{
/*-----------------------------------------------------------
Ditto above method.
-----------------------------------------------------------*/
id newList;
newList = [super copyFromZone:zone];
[newList setKeyMethod: [self keyMethod]];
[newList setSortOrder: [self sortOrder]];
[newList setCaseSensitive: [self caseSensitive]];
[newList setKeyDataType: [self keyDataType]];
return newList;
}
/*-----------------------------------------------------------
Methods that return a rutime error if called
-----------------------------------------------------------*/
- insertObject:anObject at:(unsigned int)index
{
[self error:" objects should not be sent insertObject:at: messages.\n"];
return self; //foo-faw to keep the compiler happy 'bout return types
}
- replaceObjectAt:(unsigned int)index with:newObject
{
[self error:"%s objects should not be sent replaceObjectAt:with: messages.\n"];
return self; //foo-faw to keep the compiler happy 'bout return types
}
- replaceObject:anObject with:newObject
{
[self error:"%s objects should not be sent replaceObject:with: messages.\n"];
return self; //foo-faw to keep the compiler happy 'bout return types
}
/*-----------------------------------------------------------
Archiving methods
-----------------------------------------------------------*/
-write:(NXTypedStream*)stream
{
/*-----------------------------------------------------------
Write out the instance variables and the superclass
object structure.
-----------------------------------------------------------*/
[super write:stream];
NXWriteTypes(stream, "ic:i", &sortOrder,
&caseSensitive, &keyMethod, &keyDataType);
return self;
}
- read:(NXTypedStream*)stream
{
/*-----------------------------------------------------------
Read the object back in
-----------------------------------------------------------*/
[super read:stream];
NXReadTypes(stream, "ic:i", &sortOrder,
&caseSensitive, &keyMethod, &keyDataType);
return self;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.