This is ObjectList.m in view mode; [Download] [Up]
#import "ObjectList.h"
#import <appkit/appkit.h>
#ifdef DEBUG
# define LOCAL static
#else
# define LOCAL volatile
#endif
@implementation ObjectList
static Storage *gSortMethods;
static id delegate;
const char *methodNames[] = {"insertionSort", "shellSort", "heapSort",
"quickSort", "mergeSort"};
/*\ ---------------------- Initialization Methods ---------------------- \*/
+ initialize
{
int methodID;
SEL theMethod;
if ( gSortMethods == nil )
{ /* Initialize our class variables */
gSortMethods = [[Storage alloc] initCount: 0
elementSize: sizeof(SEL) description: ":"];
for(methodID = eFirstID; methodID < eLastID; methodID ++)
{
theMethod = sel_getUid(methodNames[methodID]);
[gSortMethods addElement: &theMethod];
}
}
return self;
}
+ (int) addSortMethod:(SEL) theMethod delegate: selDelegate
{
int methodID;
if( delegate != nil && delegate != selDelegate )
return INVALID_SORTMETHODID;
delegate = selDelegate;
methodID = [gSortMethods count];
[gSortMethods addElement: &theMethod];
return methodID;
} // End addSortMethod: delegate:
+ setDelegate: selDelegate
{
delegate = selDelegate;
return self;
} // End setDelegate:
+ (BOOL) isValidSortMethod:(int) methodID
{
if( methodID < [gSortMethods count] )
return YES;
return NO;
} // End isValidSortMethod:
- initCount:(int) count sortAlgorithm:(int) algorithm
{
/* --- MethodDescription
ReturnValue: self if successful, [self free] otherwise;
Description: Initializes a newly allocated ObjectList using our
initCount:sortAlgorithm:uniform: with a NO argument for
the uniform: arg;
Args:
count: The initial size of the list;
sortAlgorithm: A int indicating which sort method to use.
It must be one of the symbolic constants defined by
the class (e.q. eInsertionSort), or a value returned
by addSortMethod:delegate. Any other value results in
the ObjectList being freed and nil returned.;
*/
return [self initCount: count sortAlgorithm: algorithm
typeID: eVoidType size: 0 keyMethod: NULL];
}
- initCount:(int) count sortAlgorithm:(int) algorithm
typeID:(int) typeID keyMethod:(SEL) keyMethod
{
return [self initCount: count sortAlgorithm: algorithm
typeID: typeID size: 0 keyMethod: keyMethod];
}
- initCount:(int) count sortAlgorithm:(int) algorithm
typeID:(int) typeID size:(int) tSize keyMethod:(SEL) keyMethod
{
/* --- MethodDescription
ReturnValue: self if successful, [self free] otherwise;
Description: Initializes a newly allocated ObjectList to
hold count items, sort itself using method associated
with algorithm. If objClass is not NIL, The ObjectList
is created as a homogeneous list of objClass objects.;
Args:
count: The initial size of the list;
sortAlgorithm: A int indicating which sort method to use.
It must be one of the symbolic constants defined by
the class (e.q. eInsertionSort), or a value returned
by addSortMethod:delegate. Any other value results in
the ObjectList being freed and nil returned.;
keyMethod: The key method the objects should use to perform
comparisons;
*/
[super initCount: count];
switch( algorithm )
{
case eInsertionSort:
case eShellSort:
case eHeapSort:
case eQuickSort:
case eMergeSort:
sortAlgorithm = algorithm;
break;
default:
if( [ObjectList isValidSortMethod: algorithm] == NO )
return [self free];
/* Algorithm was previously added by addSortMethod:delegate: */
sortAlgorithm = algorithm;
break;
}
theKeyMethod = keyMethod;
methodTypeID = typeID;
typeSize = tSize;
sortDirection = eSmallToLarge;
isHomogeneous = (keyMethod != NULL);
return self;
} // End initCount: sortAlgorithm: keyMethod: typeID:
- (BOOL) isHomogeneous
{
return isHomogeneous;
}
/*\ ---------------------- Sort Methods ---------------------- \*/
- sort
{
return [self sortAtLevel: 0];
}
- sortAtLevel:(int) level
{
SEL sortMethod;
if( level != 0 )
[self notImplemented:_cmd];
if( isSorted == YES )
return self;
sortMethod = *(SEL *)[gSortMethods elementAt: sortAlgorithm];
if( sortMethod == 0 )
{ /* Internal error */
[self error: INTERNAL_ERROR method:_cmd
key:"Failed to find method for methodID %d", sortAlgorithm];
return nil;
}
if( sortAlgorithm < eLastID )
[self perform: sortMethod];
else if( delegate != nil )
[delegate perform: sortMethod with: self];
else
{
[self error: "Invalid delegate for sortMethod: %s",
sel_getName(sortMethod)];
}
isSorted = YES;
return self;
}
- sortAtLevel:(int) level reportTime:(long *) runTime
reportCompares:(int *) comparisons
{
long startTime, endTime;
if( level != 0 )
[self notImplemented:_cmd];
time(&startTime);
comparisonCount = 0;
[self sortAtLevel: level];
time(&endTime);
*runTime = endTime - startTime;
*comparisons = comparisonCount;
return self;
}
- (BOOL) isSorted
{
return isSorted;
}
- (BOOL) setSortDirection:(int) direction
{
if( direction != sortDirection )
isSorted = NO;
sortDirection = direction;
return isSorted;
}
- (int) sortDirection
{
return sortDirection;
}
- changeKeyMethod:(SEL) keyMethod typeID:(int) typeID
{
[self changeKeyMethod: keyMethod typeID: typeID size: 0
dir: sortDirection];
return self;
} // End changeKeyMethod: typeID:
- changeKeyMethod:(SEL) keyMethod typeID:(int) typeID size:(int) tSize
dir:(int) direction
{
theKeyMethod = keyMethod;
methodTypeID = typeID;
typeSize = tSize;
isSorted = NO;
sortDirection = direction;
[self sortAtLevel: 0];
return self;
} // End changeKeyMethod: typeID: size:
/*\ ---------------------- Manipulation Methods ---------------------- \*/
- (int) insertObject: anObject
{
/* --- MethodDescription
ReturnValue: The index at which the object was inserted;
Description: Insert the object into the list using a binary search.
A check is made to ensure the list is sorted and if it is not,
an assertion error is logged and the list is sorted.;
Args:
anObject: the object to insert into the list;
*/
int insertionIndex;
if( isSorted == NO && numElements > 0 )
[self sort];
insertionIndex = [self binarySearch: anObject canFail: YES];
if( [super insertObject: anObject at: insertionIndex] == nil )
insertionIndex = NX_NOT_IN_LIST;
return insertionIndex;
}
- appendObject: anObject
{
[super addObject : anObject];
isSorted = NO;
return self;
}
- addObject: anObject
{
return [self appendObject: anObject];
}
/*\ ------------------------- Search Methods ------------------------- \*/
- findObject: theObject
{
int objIndex;
objIndex = [self binarySearch: theObject canFail: NO];
/* binarySearch returns the index just after the object
if the object was found so we decrement it */
objIndex --;
theObject = [super objectAt: objIndex];
return theObject;
} // End findObject:
- findObjectWithData:(void *) data
{
int objIndex;
id theObject;
objIndex = [self binarySearchUsing: data canFail: NO];
/* binarySearchUsing returns the index just after the object
if the object was found so we decrement it */
objIndex --;
theObject = [super objectAt: objIndex];
return theObject;
} // End findObjectWithData:
- findObjectWithData:(void *) data typeString:(const char *) typeString
{
[self notImplemented:_cmd];
return self;
} // End findObjectWithData: typeString:
/*\ ---------------------- Setting the Sort Method ---------------------- \*/
- setSortMethod:(int) methodID
{
if( sortAlgorithm >= [gSortMethods count] )
return nil;
sortAlgorithm = methodID;
return self;
} // End setSortMethod:
- (int) binarySearch: anObject canFail:(BOOL) canFail
{
/* --- MethodDescription
ReturnValue: The index of the last object whose compareTo:typeID:keyMethod:.
If canFail is YES, it returns the index at which the object associated
with data should be placed. If canFail is NO and an object is not found
-1 is returned;
Description: This method performs a binary search using the
list objects compareTo:typeID:size:keyMethod:;
Args:
anObject: The object to search for;
canFail: A flag indicating if an index value should be returned
if the method fails to locate an object which equates
to data;
*/
int first, last, middle, midTest;
BOOL found;
id object;
first = 0;
last = numElements - 1;
middle = 0;
found = NO;
while( found == NO && first <= last )
{
middle = (first + last) >> 1;
object = [super objectAt: middle];
/* Compare the object at middle against the object we are
looking for */
midTest = [object compare: anObject typeID: methodTypeID
size: typeSize keyMethod: theKeyMethod];
if( midTest == 0 )
{
found = YES;
break;
}
else if( first == last )
{ /* anObject's key value has been smaller(larger) than every
object's value in the list excluding the first object
We make a last comparison to determine if the
anObject should be the first or second element. */
switch( sortDirection )
{
case eSmallToLarge:
/* If the first object is less than anObject, inc
middle to insert anObject in position 2 */
if( midTest < 0 )
middle ++;
break;
case eLargeToSmall:
/* If the first object is greater than anObject, inc
middle to insert anObject in position 2 */
if( midTest > 0 )
middle ++;
break;
}
break;
}
switch( sortDirection )
{
case eSmallToLarge:
/* If the middle comparison is < 0, anObject > object
so we continue searching in the second half of the list */
if( midTest < 0 )
first = middle + 1;
else
last = middle - 1; // Look in first half
break;
case eLargeToSmall:
/* If the middle comparison is > 0, anObject < object
so we continue searching in the second half of the list */
if( midTest > 0 )
first = middle + 1;
else
last = middle - 1; // Look in first half
break;
}
} // End while( found == NO && first <= last )
/* If items with the same value exist, place the new item
after the items already in the list */
if( found == YES )
{
do
{
middle ++;
object = [super objectAt: middle] ;
midTest = [object compare: anObject typeID: methodTypeID
size: typeSize keyMethod: theKeyMethod];
} while( object != nil && midTest == 0 );
}
else if( canFail == NO )
return -1;
return middle;
} // End binarySearch: canFail:
- (int) binarySearchUsing:(void *) data canFail:(BOOL) canFail
{
/* --- MethodDescription
ReturnValue: The index of the last object whose compareTo:typeID:keyMethod:.
If canFail is YES, it returns the index at which the object associated
with data should be placed. If canFail is NO and an object is not found
-1 is returned;
Description: This method performs a binary search using the
list objects compareTo:typeID:keyMethod:;
Args:
data: The data used to generate comparison values. It
is the data argument passed to compareTo:typeID:keyMethod:;
canFail: A flag indicating if an index value should be returned
if the method fails to locate an object which equates
to data;
*/
int first, last, middle, midTest;
BOOL found;
id object;
first = 0;
last = numElements - 1;
middle = 0;
found = NO;
while( found == NO && first <= last )
{
middle = (first + last) >> 1;
object = [super objectAt : middle];
midTest = [object compareTo: data typeID: methodTypeID
size: typeSize keyMethod: theKeyMethod];
if( midTest == 0 )
{
found = YES;
break;
}
else if( first == last )
{ /* anObject's key value has been smaller(larger) than every
object's value in the list excluding the first object
We make a last comparison to determine if the
anObject should be the first or second element. */
switch( sortDirection )
{
case eSmallToLarge:
/* If the first object is less than anObject, inc
middle to insert anObject in position 2 */
if( midTest < 0 )
middle ++;
break;
case eLargeToSmall:
/* If the first object is greater than anObject, inc
middle to insert anObject in position 2 */
if( midTest > 0 )
middle ++;
break;
}
break;
}
switch( sortDirection )
{
case eSmallToLarge:
/* If the middle comparison is < 0, anObject > object
so we continue searching in the second half of the list */
if( midTest < 0 )
first = middle + 1;
else
last = middle - 1; // Look in first half
break;
case eLargeToSmall:
/* If the middle comparison is > 0, anObject < object
so we continue searching in the second half of the list */
if( midTest > 0 )
first = middle + 1;
else
last = middle - 1; // Look in first half
break;
}
} // End while( found == NO && first <= last )
/* If items with the same value exist, place the new item
after the items in the list */
if( found == YES )
{
do
{
middle ++;
object = [super objectAt: middle] ;
midTest = [object compareTo: data typeID: methodTypeID
size: typeSize keyMethod: theKeyMethod];
} while( object != nil && midTest == 0 );
}
else if( canFail == NO )
return -1;
return middle;
} // End binarySearchUsing: typeID: keyMethod: canFail:
/*\ ---------------------- Sort Methods ---------------------- \*/
- insertionSort
{
return [self insertionSort: 0 inc: 1];
}
- insertionSort:(int) first inc:(int) step
{
LOCAL int insertPt, unSorted, compareValue;
LOCAL id obj1, obj2;
LOCAL BOOL found;
obj1 = [super objectAt: first];
for(unSorted = first+step; unSorted < numElements; unSorted += step)
{
obj2 = [self objectAt: unSorted];
compareValue = [obj2 compare: obj1 typeID: methodTypeID
size: typeSize keyMethod: theKeyMethod];
switch( sortDirection )
{
case eSmallToLarge:
/* If obj2 < obj1, insert obj2 into the sorted
first of the list */
if( compareValue < 0 )
{
[super removeObjectAt: unSorted];
/* Search for the position to insert this object */
insertPt = unSorted - step; // The last sorted object, obj1
do
{
insertPt -= step;
if( insertPt < 0 )
found = YES;
else
{
obj1 = [super objectAt: insertPt];
compareValue = [obj2 compare: obj1
typeID: methodTypeID size: typeSize
keyMethod: theKeyMethod];
/* When obj2 >= obj1, can place obj2 after obj1 */
found = (compareValue >= 0);
}
} while( found == NO );
/* Insert obj2 into the list and set update the
last sorted object, obj1 */
[super insertObject: obj2 at: insertPt+step];
obj1 = [self objectAt: unSorted];
}
else
obj1 = obj2;
break;
case eLargeToSmall:
/* If obj2 > obj1, insert obj2 into the sorted
first of the list */
if( compareValue > 0 )
{
[super removeObjectAt: unSorted];
/* Search for the position to insert this object */
insertPt = unSorted - step; // The last sorted object, obj1
do
{
insertPt -= step;
if( insertPt < 0 )
found = YES;
else
{
obj1 = [super objectAt: insertPt];
compareValue = [obj2 compare: obj1
typeID: methodTypeID size: typeSize
keyMethod: theKeyMethod];
/* When obj2 <= obj1, can place obj2 after obj1 */
found = (compareValue <= 0);
}
} while( found == NO );
/* Insert obj2 into the list and set update the
last sorted object, obj1 */
[super insertObject: obj2 at: insertPt+step];
obj1 = [self objectAt: unSorted];
}
else
obj1 = obj2;
break;
}
}
isSorted = YES;
return self;
}
/* Perform insertion sort on the ObjectList starting at first using
elements first, first + step, first + 2step, ... first + n step;
n <= numElements / step */
- shellSort
{
int first,increment;
increment = numElements;
do
{
increment = increment / 3 + 1;
for(first = 0; first < increment; first ++)
[self insertionSort: first inc: increment];
} while(increment > 1);
return self;
}
- heapSort
{
int i,heapSize;
id rootObj,obj;
/* Build the heap */
heapSize = numElements - 1;
for(i = (numElements-1)/2; i >= 0; i --)
{
rootObj = [super objectAt: i];
[self insertHeap: rootObj : i : heapSize];
}
/* Repeatedly remove the root and and rearrange the heap */
for(heapSize = numElements-1; heapSize >= 1; heapSize --)
{ /* Move root object to end of heap and reinsert the
object it replaces */
rootObj = [super objectAt: 0];
obj = [super replaceObjectAt: heapSize with: rootObj];
[self insertHeap: obj : 0 : heapSize-1];
}
isSorted = YES;
return self;
}
/* fixHeap implementation */
- (void) insertHeap: keyObj :(int) root :(int) bound
{
int index, compareValue;
id leftChild, rightChild, childToPromote;
index = 2*root + 1;
while( index <= bound )
{ /* Determine the child to promote. Intially assume the leftChild
is the one to promote. */
childToPromote = leftChild = [super objectAt: index];
rightChild = [super objectAt: index + 1];
compareValue = [rightChild compare: leftChild typeID: methodTypeID
size: typeSize keyMethod: theKeyMethod];
if( index < bound )
{
switch( sortDirection )
{
case eLargeToSmall:
/* Promote the smallest child */
if( compareValue < 0 )
{
index ++;
childToPromote = rightChild;
}
break;
case eSmallToLarge:
/* Promote the largest child */
if( compareValue > 0 )
{
index ++;
childToPromote = rightChild;
}
break;
}
}
/* Compare the object being inserted with the current
child node object */
compareValue = [keyObj compare: childToPromote typeID: methodTypeID
size: typeSize keyMethod: theKeyMethod];
if( sortDirection == eSmallToLarge && compareValue >= 0 )
break; // Insert keyObj at current root index
if( sortDirection == eLargeToSmall && compareValue <= 0 )
break; // Insert keyObj at current root index
else
{ /* Promote the child */
[self replaceObjectAt: root with: childToPromote];
root = index;
index = 2*root + 1;
}
}
[super replaceObjectAt: root with: keyObj];
}
- quickSort
{
[self notImplemented : _cmd];
return self;
}
- mergeSort
{
[self notImplemented : _cmd];
return self;
}
- print
{
[self makeObjectsPerform : @selector(print)];
return self;
}
- printVerbose
{
int i;
for(i = 0; i < numElements; i ++)
{
printf("Element %d = ",i);
[[self objectAt : i] perform : @selector(print)];
}
return self;
}
- printHeap
{
/*
// node0
printf("\t\t\t%d\n", (int) [[self objectAt: 0] perform: keyValue]);
// nodes 1,2
printf("\t%d\t\t\t\t%d\n", (int)[[self objectAt: 1] perform: keyValue],
(int) [[self objectAt : 2] perform: keyValue]);
// nodes 3,4,5
printf("%d\t\t%d\t\t%d\n", (int)[[self objectAt: 3] perform: keyValue],
(int)[[self objectAt: 4] perform: keyValue],
(int)[[self objectAt: 5] perform: keyValue]);
*/
return self;
}
/*\ ---------------------- ObjectArchival Protocol ---------------------- \*/
static inline char *ClassName() { return "ObjectList"; }
static inline long ArchiveVersion()
{
/* --- MethodDescription
ReturnValue: Current ObjectArchival version of object;
Description: This routine returns the current version number of
the methods associated with the ObjectArchival protocol for
this object. This value should be written to the archive
stream to indicate the archive structure.;
*/
long version;
version = 1000 * OBJECTLIST_VERS + 10 * OBJECTLIST_SUBVERS +
OBJECTLIST_TYPE;
return version;
}
- initFromTStream:(NXTypedStream *) stream
{
/* --- MethodDescription
ReturnValue: self;
Description: This method sends the init message to super,
unarchives the instance information from the typed
stream by messaging self with readFromTStream:, and finishes
initializing of the instance;
Args:
stream: The typed stream from which the object is to be unarchived;
*/
[super initCount: 0];
if( [self readFromTStream: stream] == nil )
return nil;
return self;
}
- readFromTStream:(NXTypedStream *) stream
{
/* --- MethodDescription
ReturnValue: self;
Description: This method unarchives the information necessary to
reconstruct an object instance. The information unarchived
is the same as archived by the writeToTStream: method.;
Args:
stream: The typed stream from which the object is to be unarchived;
*/
long version;
const char *className;
void *data1 = NULL, *data2 = NULL;
NX_DURING
[self debug: MAX_DEBUG method: _cmd, "class = %s; superclass = %s\n",
[[self class] name], [[self superclass] name]];
[self debug: MAX_DEBUG method: _cmd, "\tinstance = %s\n", ClassName()];
/* Unarchive our super class */
[super readFromTStream: stream];
/* First read the class name & archive version */
NXReadTypes(stream, "*i", &className, &version);
if( strcmp(className, ClassName()) != 0 )
{
NXAllocErrorData(strlen(className)+1, &data1);
NXAllocErrorData(strlen(ClassName())+1, &data2);
strcpy(data1, className);
strcpy(data2, ClassName());
NX_RAISE(eWrongClassName, data1, data2);
}
/* Unarchive this version format */
switch( version )
{
case OBJECTLIST_VERSION_0:
/* Unarchive the sort algorithm type */
NXReadType(stream, "i", &sortAlgorithm);
/* Unarchive the key method info */
NXReadTypes(stream, ":ii", &theKeyMethod, &methodTypeID, &typeSize);
/* Unarchive the flags */
NXReadTypes(stream, "cc", &isHomogeneous, &isSorted);
break;
default:
NXAllocErrorData(strlen([[self class] name])+1, &data1);
NXAllocErrorData(sizeof(long), &data2);
strcpy(data1, [[self class] name]);
*((long *) data2) = version;
NX_RAISE(eBadObjVersion, data1, data2);
break;
}
NX_HANDLER
[self free];
NX_RERAISE();
NX_ENDHANDLER
return self;
}
- writeToTStream:(NXTypedStream *) stream
{
/* --- MethodDescription
ReturnValue: self;
Description: This method archives the information necessary to
reconstruct an object instance.;
Args:
stream: The typed stream to which the object is to be archived;
*/
long version;
const char *className;
NX_DURING
[self debug: MAX_DEBUG method: _cmd, "class = %s; superclass = %s\n",
[[self class] name], [[self superclass] name]];
[self debug: MAX_DEBUG method: _cmd, "\tinstance = %s\n", ClassName()];
/* Archive our super class */
[super writeToTStream: stream];
/* First write the class name & archive version */
className = ClassName();
version = ArchiveVersion();
NXWriteTypes(stream, "*i", &className, &version);
/* Archive the sort algorithm type */
NXWriteType(stream, "i", &sortAlgorithm);
/* Archive the key method info */
NXWriteTypes(stream, ":ii", &theKeyMethod, &methodTypeID, &typeSize);
/* Archive the flags */
NXWriteTypes(stream, "cc", &isHomogeneous, &isSorted);
NX_HANDLER
NX_RERAISE();
NX_ENDHANDLER
return self;
}
@end
/* RCS Information:
$Author: me $;
$Date: 93/02/23 02:01:46 $;
$Source: /usr1/me/NeXTSrc/MyClasses/RCS/ObjectList.m,v $;
$Revision: 1.1 $;
$Log: ObjectList.m,v $
Revision 1.1 93/02/23 02:01:46 me
Begin RCS logging.
;
*/
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.