//
//	MiscLinkedList.m -- an implementation of a doubly linked list
//		Written by Sean Luke (c) 1993, 1994 by Sean Luke.
//		Additional methods and editing by Don Yacktman.
//				Version 0.9.  All rights reserved.
//
//		This notice may not be removed from this source code.
//
//	This object is included in the MiscKit by permission from the author
//	and its use is governed by the MiscKit license, found in the file
//	"LICENSE.rtf" in the MiscKit distribution.  Please refer to that file
//	for a list of all applicable permissions and restrictions.
//	

// ***** make sure that the list insertion methods don't reverse the order
// of the inserted list!

// ***** finish writing the extra methods


#import <misckit/misckit.h>

@implementation MiscLinkedList

- init
	{
	return [self initForClass:[MiscLinkedListNode class]];
	}
	
- initForClass: this_class
	{
	id returnval=[super init];
	node_length=0;
	node_class=this_class;
	return returnval;
	}

- free
{
	[self freeNodes];
	return [super free];
}
	
- freeObjects
	{
	id temp;
	[self goFirst];
	while (node_length)
		{
		temp=[self deleteObject];
		if (temp!=nil) [[temp freeObject] free]; // deletes node AND object
		}
	return self;
	}

- freeNodes
	{
	id temp;
	[self goFirst];
	while (node_length)
		{
		temp=[self deleteObject];
		if (temp!=nil) [temp free]; // deletes node ONLY
		}
	return self;
	}

- goFirst
	{
	current_node=first_node;
	if (current_node==nil) return nil;
	return [current_node getObject];
	}
	
- goNext
 	{
	id new_node;
	if (current_node==nil) return nil;
	new_node=[current_node getNext];
	if (new_node==nil) return nil;
	current_node=new_node;
	return [current_node getObject];
	}
	
- goLast
	{
	current_node=last_node;
	if (current_node==nil) return nil;
	return [current_node getObject];
	}

- goPrevious
 	{
	id new_node;
	if (current_node==nil) return nil;
	new_node=[current_node getPrevious];
	if (new_node==nil) return nil;
	current_node=new_node;
	return [current_node getObject];
	}

- getNode
	{
	if (current_node==nil) return nil;
	return current_node;
	}

	
- getObject
	{
	if (current_node==nil) return nil;
	return [current_node getObject];
	}

- setObject:this_object
	{
	if (current_node==nil) return nil;
	return [current_node setObject:this_object];
	}
	
- insertObjectAfter: this_object
	{
	id new_node;
	if (this_object==nil) return nil;
	new_node=[[node_class alloc] initObject:this_object];
	if (node_length==0)					// node is both ends
		{
		first_node=new_node;
		last_node=new_node;
		current_node=new_node;
		}
	else if (current_node==last_node) 	// node is last end
		{
		[new_node setNext:nil];
		[new_node setPrevious:current_node];
		[current_node setNext:new_node];
		last_node=new_node;
		current_node=new_node;
		}
	else 								// node is in the middle
		{
		[new_node setNext:[current_node getNext]];
		[new_node setPrevious:current_node];
		[current_node setNext:new_node];
		[[new_node getNext] setPrevious:new_node];
		current_node=new_node;
		}
	node_length++;
//	printf ("Last Node: %d\n",(int)last_node);
	return this_object;
	}
	
- insertObjectBefore: this_object
	{
	id new_node;
	if (this_object==nil) return nil;
	new_node=[[node_class alloc] initObject:this_object];
	
	if (node_length==0)					// node is both ends
		{
		first_node=new_node;
		last_node=new_node;
		current_node=new_node;
		}
	else if (current_node==first_node) 	// node is first end
		{
		[new_node setPrevious:nil];
		[new_node setNext:current_node];
		[current_node setPrevious:new_node];
		first_node=new_node;
		current_node=new_node;
		}
	else 								// node is in the middle
		{
		[new_node setPrevious:[current_node getPrevious]];
		[new_node setNext:current_node];
		[current_node setPrevious:new_node];
		[[new_node getPrevious] setNext:new_node];
		current_node=new_node;
		}
	node_length++;
//	printf ("Last Node: %d\n",(int)last_node);
	return this_object;
	}
	
- deleteObject
	{
	id next_node, previous_node, the_object;
	if (current_node==nil) return nil;
	
	next_node=[current_node getNext];
	previous_node=[current_node getPrevious];
	the_object=[current_node getObject];
	[current_node free];
	node_length--;
	
	if (node_length==0)					// that was the last node!
		{
		first_node=nil;
		last_node=nil;
		current_node=nil;
		}
	else if (next_node==nil) 			// current node was last
		{
		last_node=previous_node;
		[previous_node setNext:nil];
		current_node=previous_node;
		}
	else if (previous_node==nil)		// current node was first
		{
		first_node=next_node;
		[next_node setPrevious:nil];
		current_node=next_node;
		}
	else								// node is in the center
		{
		[next_node setPrevious:previous_node];
		[previous_node setNext:next_node];
		current_node=previous_node;    		// (default)
		}
//	printf ("Deleting Last Node: %d\n",(int)last_node);
	
	return the_object;
	}

- (int) getLength
	{
	return node_length;
	}
	
- read: (NXTypedStream*) stream
	{
	int x;
	id temp=nil;
	id previous=nil;
	
	[super read:stream];
	NXReadTypes(stream, "i", &node_length);
	// others don't matter, since they'll be different anyhow.
	
	first_node=temp;
	current_node=temp;
	for (x=1;x<=node_length;x++)
		{
		temp=NXReadObject(stream);
		if (previous==nil) 
			{
			first_node=temp;				// only read one!
			current_node=temp;
			[temp setPrevious: nil];		// just in case
			}
		else
			{
			[temp setPrevious:previous];
			[previous setNext:temp];
			}
		previous=temp;
		}
	last_node=temp;
	[temp setNext:nil];					// just in case
	node_class=[temp class]; // assume that all nodes are same class.
	return self;
	}
	
- insertList: this_list
	{ // ***** need a version that will insert objects from a NeXT List too
	// inserts this_list into the beginning of the list
	
	if ([this_list getLength])			// not empty
		{
		[this_list goFirst];
		do
			{
			[self insertObjectBefore: [this_list getObject]];
			}
		while ([this_list goNext]!=nil);
		}
	return self;
	}



- insertListAtFront: this_list
	{ // ***** need a version that will insert objects from a NeXT List too
	// inserts this_list into the beginning of the list
	
	if ([this_list getLength])			// not empty
		{
		[this_list goFirst];
		[self goFirst];
		do
			{
			[self insertObjectBefore: [this_list getObject]];
			}
		while ([this_list goNext]!=nil);
		}
	return self;
	}



- appendList: this_list
	{ // ***** need a version that will insert objects from a NeXT List too
	// appends this_list onto the end of the list
	
	if ([this_list getLength])			// not empty
		{
		[this_list goFirst];
		[self goLast];
		do
			{
			[self insertObjectAfter: [this_list getObject]];
			}
		while ([this_list goNext]!=nil);
		}
	return self;
	}



- write: (NXTypedStream*) stream	
	{
	int x;
	id temp;
	
	[super write:stream];
	NXWriteTypes(stream, "i", (const int*) &node_length);
	temp=first_node;
	for (x=1;x<=node_length;x++)
		{
		NXWriteObject(stream,temp);
		temp=[temp getNext];
		}
	return self;
	}

- swapWithNext
	{
	id farnext;
	id farprevious;
	id swapnode;
	
	if (current_node==nil) return nil;					// node doesn't exist
	if ([current_node getNext]==nil) return nil;		// no node with which to swap
	
	farnext=[[current_node getNext] getNext];
	farprevious=[current_node getPrevious];
	swapnode=[current_node getNext];
	
	[swapnode setPrevious: farprevious];
	[swapnode setNext: current_node];
	[current_node setPrevious: swapnode];
	[current_node setNext: farnext];
	
	if (farnext!=nil)										// swapping doesn't move node to back
		{
		[farnext setPrevious: current_node];
		}
	if (farprevious!=nil)									// swapping doesn't move node from front
		{
		[farprevious setNext: swapnode];
		}
	return self;
	}
	
- swapWithPrevious
	{
	id farnext;
	id farprevious;
	id swapnode;
	
	if (current_node==nil) return nil;					// node doesn't exist
	if ([current_node getPrevious]==nil) return nil;	// no node with which to swap
	
	farnext=[current_node getNext];
	farprevious=[[current_node getPrevious] getPrevious];
	swapnode=[current_node getPrevious];
	
	[swapnode setNext: farnext];
	[swapnode setPrevious: current_node];
	[current_node setNext: swapnode];
	[current_node setPrevious: farprevious];
	
	if (farnext!=nil)										// swapping doesn't move node from back
		{
		[farnext setPrevious: swapnode];
		}
	if (farprevious!=nil)									// swapping doesn't move node to front
		{
		[farprevious setNext: current_node];
		}
	return self;
	}
	

- moveToFirst
	{
	id next_node;
	id previous_node;
	
	if (current_node==nil) return nil;
	
	next_node=[current_node getNext];
	previous_node=[current_node getPrevious];
	
	if (next_node!=nil) [next_node setPrevious: previous_node];
	if (previous_node!=nil) [previous_node setNext: next_node];
	[first_node setPrevious:current_node];
	[current_node setNext:first_node];
	[current_node setPrevious:nil];
	first_node=current_node;
	return self;
	}
	

- moveToLast
	{
	id next_node;
	id previous_node;
	
	if (current_node==nil) return nil;
	
	next_node=[current_node getNext];
	previous_node=[current_node getPrevious];
	
	if (next_node!=nil) [next_node setPrevious: previous_node];
	if (previous_node!=nil) [previous_node setNext: next_node];
	[last_node setNext:current_node];
	[current_node setPrevious:last_node];
	[current_node setNext:nil];
	last_node=current_node;
	return self;
	}

// We guess in the -read method and choose for the node class the
// node at the end of the list...likely to be more correct than
// simply setting the default class, and means that whomever un-archives
// the list doesn't have to worry as much about making sure the class
// is the right one.  Of course, the archiver has to make sure that
// the last node is representative of what we want, but that is
// not likely to be a problem, since typically all nodes will be of
// the same class.
/*- awake
	{
	[super awake];
	node_class=[MiscLinkedListNode class];
	return self;
	}*/

- empty
{
	return [self freeNodes];
}

- (BOOL)isEqual:anObject;
{
	id temp2, temp = first_node;
	
	// first, a few shortcuts to speed up common cases
	if (anObject == self) return YES;	// same object
	if ([anObject class] != [self class]) return NO; // different classes
	if ([anObject count] != [self count]) return NO; // different lengths
	
	[anObject goFirst];
	temp2 = [anObject getNode];
	while (temp && temp2) { // check each object against counterpart in other
		if (![[temp getObject] isEqual:[temp2 getObject]]) return NO; // diff!
		temp = [temp getNext];
		temp2 = [temp2 getNext];
	}
	if (temp || temp2) return NO; // different lengths (shouldn't happen)
	return YES;
}


- makeObjectsPerform:(SEL)aSelector;
{
	id temp = first_node;
	while (temp) {
		id tobj = [temp getObject];
		if ([tobj respondsTo:aSelector]) {
			[tobj perform:aSelector];
		}
		temp = [temp getNext];
	}
	return self;
}

- makeObjectsPerform:(SEL)aSelector with:anObject
{
	id temp = first_node;
	while (temp) {
		id tobj = [temp getObject];
		if ([tobj respondsTo:aSelector]) {
			[tobj perform:aSelector with:anObject];
		}
		temp = [temp getNext];
	}
	return self;
}

- replaceObject:anObject with:newObject; // return anObject
{
	id temp = first_node;
	while (temp) {
		if ([temp getObject] == anObject) {
			return [temp setObject:newObject];
		}
		temp = [temp getNext];
	}
	return nil;
}

- removeObject:anObject; // return anObject
{
	current_node = first_node;
	while (current_node) {
		if ([current_node getObject] == anObject) {
			return [self deleteObject];
		}
		current_node = [current_node getNext];
	}
	return nil;
}

- addObjectIfAbsent:anObject; // appends it
{
	id temp = first_node;
	while (temp) {
		if ([temp getObject] == anObject) return nil; // found it!
		temp = [temp getNext];
	}
	return [self addObject:anObject];
}

// these four are obvious:
- removeLastObject
{
	id the_object = [last_node getObject];
	id new_last = [last_node getPrevious];
	if (!last_node) return nil;
	node_length--;
	[last_node free];
	last_node = new_last;
	[last_node setNext:nil];
	return the_object;
}
- lastObject
{
	return [last_node getObject];
}

- removeFirstObject
{
	id the_object = [first_node getObject];
	id new_first = [first_node getNext];
	if (!first_node) return nil;
	node_length--;
	[first_node free];
	first_node = new_first;
	[first_node setPrevious:nil];
	return the_object;
}

- firstObject
{
	return [first_node getObject];
}

- (unsigned int)count // same as -getLength
{
	return (unsigned int)node_length;
}

- addObject:anObject // appends object to list
{
	id new_node = [[node_class alloc] initObject:anObject];
	
	[last_node setNext:new_node];
	[new_node setPrevious:last_node];
	[new_node setNext:nil];
	last_node = new_node;
	if (!first_node) first_node = new_node;
	node_length++;
	return self;
}

// NXTransport protocol implementation:
- encodeUsing:(id <NXEncoding>)portal
{
	int i; id temp;
	[portal encodeData:&node_length ofType:"i"];
	[portal encodeObjectBycopy:node_class];
	temp = first_node;
	for (i=1; i<=node_length; i++) {
		[portal encodeObjectBycopy:temp];
		temp=[temp getNext];
	}
	return self;
}

- decodeUsing:(id <NXDecoding>)portal
{
	int x; id temp = nil; id previous = nil;
	[portal decodeData:&node_length ofType:"i"];
	first_node = temp;
	current_node = temp;
	node_class = [portal decodeObject];
	for (x=1; x<=node_length; x++) {
		temp = [portal decodeObject];
		if (previous == nil) {
			first_node = temp;				// only read one!
			current_node = temp;
			[temp setPrevious: nil];		// just in case
		} else {
			[temp setPrevious:previous];
			[previous setNext:temp];
		}
		previous = temp;
	}
	last_node = temp;
	[temp setNext:nil];					// just in case
	return self;
}

- encodeRemotelyFor:(NXConnection *)connection
	freeAfterEncoding:(BOOL *)flagp isBycopy:(BOOL)isByCopy
{
	if (isByCopy) {
		*flagp = NO; // object will copy.
		return self; //encode object (copy it)
	}
	*flagp = NO; // object will copy.
	// super will encode the proxy otherwise
	return [super encodeRemotelyFor:connection
				freeAfterEncoding:flagp isBycopy:isByCopy];
}

@end
