/* SortedList.m
 * Written By:  Thomas Burkholder
 *
 * 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.
 */

#import "SortedList.h"

@implementation SortedList:List

- initCount:(unsigned)numSlots
{
	[super initCount:numSlots];
	agent = nil;
	return self;
}

- setAgent:anObject
{
	agent = anObject;
	return self;
}

- agent
{
	return agent;
}

- (id)subdirectoryForObjectAt:(int)at
{
	if (agent && [agent respondsTo:@selector(subdirectoryFor:sender:)])
		return [agent subdirectoryFor:[self objectAt:at] sender:self];
	return nil;  // default is no entries.
}

- (BOOL)isLeafAt:(int)at
{
	if (agent && [agent respondsTo:@selector(isLeaf:sender:)])
		return [agent isLeaf:[self objectAt:at] sender:self];
	return YES;  // default is YES.
}

- (const char *)displayStringForObjectAt:(int)at
{
	if (agent && [agent respondsTo:@selector(displayStringFor:sender:)])
		return [agent displayStringFor:[self objectAt:at] sender:self];
	return NULL;  // default is YES.
}

- (int)compareObjectAt:(int)at with:object
{
	if (agent && [agent respondsTo:@selector(compare:with:sender:)])
		return [agent compare:[self objectAt:at] with:object sender:self];
	return 1;  //By default, it's smaller, so it get's appended.
}

- (int)browser:sender fillMatrix:matrix inColumn:(int)column
{
	id c;
	int i,n;
	id candidate = self;

	if (column != 0) {
		for(i=0;(i<column);i++) {
			candidate = [candidate subdirectoryForObjectAt:[[sender matrixInColumn:i] selectedRow]];
			if ((!candidate) || (![candidate isKindOf:[SortedList class]])) return 0;
		}
	}

	for(i=0,n=[candidate count];i<n;i++) {
		[matrix addRow];
		c = [matrix cellAt:i :0];
		[c setLeaf:[candidate isLeafAt:i]];
		[c setLoaded:YES];
		[c setStringValue:[candidate displayStringForObjectAt:i]];
	}
	return i;
}

- (const char *)browser:sender titleOfColumn:(int)column
{
	return [agent titleOfColumn:column];
}

- binaryInsert:anObject between:(int)lower and:(int)upper
{
	int r,c = lower + (1+upper-lower)/2;

	if (lower == upper) {  
		if ([self compareObjectAt:lower with:anObject]>0) // insert before
			return [super insertObject:anObject at:lower];
		else  // insert after
			return [super insertObject:anObject at:lower+1];
	}

	r = [self compareObjectAt:c with:anObject];
	if (r>0)  // Recursion is Good.
		return [self binaryInsert:anObject between:lower and:c-1];
	else if (r<0)  // In fact, Recursion is Holy.
		return [self binaryInsert:anObject between:c and:upper];
	else  // if equal insert right now.
		return [super insertObject:anObject at:c];
}

- addObject:anObject  // Assumes sorted list
{
	// Binary insertion...
	if (![self count])
		return [super addObject:anObject];
	[self binaryInsert:anObject between:0 and:[self count]-1];
	return self;
}

- sort:sender
{
	id l = [[List alloc] init];
	int i, n;

	// move our elements into plain old list.
	for(i=0,n=[self count];(i<n);i++)
		[l addObject:[self objectAt:i]];
	[self empty];


	// re-insert everything.
	for(i=0,n=[l count];(i<n);i++)
		[self addObject:[l objectAt:i]];
	[l empty];
	[l free];
	return self;
}

- read:(NXTypedStream *)stream
{
	[super read:stream];
	agent = NXReadObject(stream);
	return self;
}

- awakeFromNib
{
	// This won't be called in Test Interface mode.
	[self sort:self];
	return self;
}

- write:(NXTypedStream *)stream
{
	[super write:stream];
	NXWriteObject(stream,agent);
	return self;
}

@end