#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.
;
*/
