//
//  OCLinkedList.m
//  LinkedList
//
//  Created by Jonathan Lung on 02/03/07.
//  Copyright 2007 Jonathan Lung. All rights reserved.
//	http://www.cs.toronto.edu/~lungj
//

#import "OCLinkedList.h"

@interface OCLinkedListNode : NSObject {
	OCLinkedListNode* next;
	OCLinkedListNode* previous;
	id value;
}

// Get the value stored in this node.
-(id) getValue;

// Set the value stored in this node.
-(void) setValue:(id) newValue;

// Set the pointer to the next node.
-(void) setNext:(OCLinkedListNode *) newNext;

// Set the pointer to the previous node.
-(void) setPrevious:(OCLinkedListNode *) newPrevious;

// Get the pointer to the next node.
-(OCLinkedListNode *) getNext;

// Get the pointer to the previous node.
-(OCLinkedListNode *) getPrevious;

@end

#pragma mark -

@interface OCLinkedListEnumerator : NSEnumerator {
	OCLinkedListNode* lastNode;
}

-(id) initWithLinkedList:(OCLinkedList*) linkedList;
@end

#pragma mark -

@implementation OCLinkedList

#pragma mark Some helper methods
// Helper method for getting the node with the specified node number.
// This implementation goes from the front or the end, depending on which is closer.
// Assumes a valid node number.  -1 for listHead and count for listTail.
-(OCLinkedListNode *) getNode:(unsigned int) nodeNumber {
	SEL traversalMethod;
	unsigned int nodes;
	OCLinkedListNode* currentNode;
	
	// count >> 1 is the half-way point; -1U is the head.
	if (nodeNumber < (count >> 1) || nodeNumber == -1) {
		// We're closer to the front.  Go forwards.
		traversalMethod = @selector(getNext);
		currentNode = listHead;
		
		// +1 correction is to include the beginning sentinel.
		nodes = nodeNumber + 1;
		
	} else {
		// We're closer to the rear.  Go backwards.
		traversalMethod = @selector(getPrevious);
		currentNode = listTail;
		
		// Get the number of nodes to traverse.
		nodes = (count - nodeNumber);
		
	}
	
	while(nodes--) {
		currentNode = objc_msgSend(currentNode, traversalMethod);
	}
	
	return currentNode;
}

#pragma mark Accessor methods
-(id) objectAtIndex:(unsigned int) fetchIndex {
	return [[self getNode:fetchIndex] getValue];
}

-(NSEnumerator*) objectEnumerator {
	return [[OCLinkedListEnumerator alloc] initWithLinkedList:self];
}

#pragma mark Bookkeeping methods

-(unsigned int) count {
	return count;
}

#pragma mark Methods for adding objects. 

// Helper method that inserts a new node after the preceeding node specified.
-(void) insert:(OCLinkedListNode*) newNode after:(OCLinkedListNode*) preceedingNode {
	OCLinkedListNode* proceedingNode = [preceedingNode getNext];
	// Set up the new node's pointers.
	[newNode setNext:proceedingNode];
	[newNode setPrevious:preceedingNode];
	// Set up the surrounding pointers.
	[proceedingNode setPrevious:newNode];
	[preceedingNode setNext:newNode];
	
	// Update count of objects in list.
	count++;

}

-(void) insertObject:(id) anObject atIndex:(unsigned int) insertionIndex {
	// Initialize the node to be inserted.
	OCLinkedListNode* newNode = [[OCLinkedListNode alloc] init];
	[newNode setValue:anObject];
	
	// We need to insert at insertionIndex - 1.
	OCLinkedListNode* insertionPoint = [self getNode:(insertionIndex - 1)];
	[self insert:newNode after:insertionPoint];
	
	// Not to worry...  newNode already retained by the OCLinkedListNode.
	[newNode release];
}

-(void) addObjectAtBeginning:(id) anObject {
	// Initialize the node to be inserted.
	OCLinkedListNode* newNode = [[OCLinkedListNode alloc] init];
	[newNode setValue:anObject];
	
	[self insert:newNode after:listHead];
	
	// Not to worry...  newNode already retained by the OCLinkedListNode.
	[newNode release];
}


-(void) addObject:(id) anObject {
	// Initialize the node to be inserted.
	OCLinkedListNode* newNode = [[OCLinkedListNode alloc] init];
	[newNode setValue:anObject];
	
	// Could have an insert before method, but at the expense of code duplication.
	[self insert:newNode after:[listTail getPrevious]];
	
	// Not to worry...  newNode already retained by the OCLinkedListNode.
	[newNode release];
}

#pragma mark Methods for removing objects.

-(void) remove:(OCLinkedListNode*) nodeToBeRemoved {
	OCLinkedListNode* previous = [nodeToBeRemoved getPrevious];
	OCLinkedListNode* next = [nodeToBeRemoved getNext];
	
	// Change pointers around
	[previous setNext:next];
	// nodeToBeRemoved automatically released by setPrevious:.
	[next setPrevious:previous];
	
	// Update count of list length.
	count--;
}

-(void) removeFromIndex:(unsigned int) removalIndex {
	// Get the node to be removed...
	OCLinkedListNode* nodeToBeRemoved = [self getNode:removalIndex];
	
	[self remove:nodeToBeRemoved];
}

-(void) removeLastObject {
	[self remove:[listTail getPrevious]];
}

-(void) removeFirstObject {
	[self remove:[listHead getNext]];
}

#pragma mark Init/release routines

-(id) init {
	self = [super init];
	// Initialize the head and tail of the linked list to be sentinels
	listHead = [[OCLinkedListNode alloc] init];
	listTail = [[OCLinkedListNode alloc] init];
	
	[listHead setNext:listTail];
	[listTail setPrevious:listHead];
	
	// count is set to 0 by alloc
	
	// Initialization done, so just return self.
	return self;
}

-(void) dealloc {
	// Deallocate all items.
	while(count) {
		[self remove:[listHead getNext]];
	};
	
	[listHead release];
	[listTail release];
		
	[super dealloc];
}

@end


#pragma mark -

@implementation OCLinkedListNode
#pragma mark Value setter and getter
-(id) getValue {
	return value;
}

-(void) setValue:(id) newValue {
	// Avoid using autorelease by doing manual check
	// for equality.
	if (value != newValue) {
		// Avoid requiring nil message handling
		if (value != nil) {
			[value release];
		}
		value = newValue;
		// Avoid requiring nil message handling
		if (newValue != nil) {
			[newValue retain];
		}
		
	}
}
#pragma mark Previous setter and getter
-(OCLinkedListNode *) getPrevious {
	return previous;
}

-(void) setPrevious:(OCLinkedListNode *) newPrevious {
	// Avoid autoreleasing
	if (previous != newPrevious) {
	
		[previous release];
		[newPrevious retain];
		previous = newPrevious;
		
	}
}

#pragma mark Next setter and getter
-(void) setNext:(OCLinkedListNode *) newNext {
	// Avoid autoreleasing
	if (next != newNext) {
	
		[next release];
		[newNext retain];
		next = newNext;
		
	}
}

-(OCLinkedListNode *) getNext {
	return next;
}

#pragma mark Bookkeeping methods
-(void) dealloc {
	if (value != nil) {
		[value release];
	}
	[super dealloc];
}


@end

#pragma mark -

@implementation OCLinkedListEnumerator
-(id) initWithLinkedList:(OCLinkedList*) linkedList {
	self = [super init];

	// Only deal with the linked list at the time of instantiation.
	
	// Peek into private method to get first non-sentinel node.
	lastNode = [linkedList getNode:0];
	[lastNode retain];
		
	return self;
}
-(void) dealloc {
	[lastNode release];
	[super dealloc];
}
-(id) nextObject {
	OCLinkedListNode* nextNode = [lastNode getNext];
	
	// See if there are any more nodes left to traverse.
	if (nextNode == nil) {
		return nil;
	}

	// Store return value.
	id returnValue = [lastNode getValue];
	if (returnValue != nil) {
		[[returnValue retain] autorelease];
	}
	
	// Make sure access to lastNode is guaranteed on next iteration.
	[nextNode retain];
	[lastNode release];
	
	// Update node pointer
	lastNode = nextNode;
	
	return returnValue;
}

-(NSArray*) allObjects {
	NSMutableArray* objectArray = [[[NSMutableArray alloc] init] autorelease];

	while ([lastNode getNext] != nil) {
		[objectArray addObject:[self nextObject]];
	}
	
	return objectArray;
}
@end