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

#import <Cocoa/Cocoa.h>

@class OCLinkedListNode;

/*!
    @class
    @abstract		OCLinkedList is an implementation of a linked list.
    @discussion		This is an unremarkable implementation of a linked list
					in Objective-C.  The maximum capacity is the value of the
					largest unsigned integer.  No convenience methods, coders,
					enumerators, or the like are included.
					Also, not extremely optimized in terms of message passing.
					However, no autorelease pools are required for operation and
					exception handling is not supported, (hopefully) improving
					performance.
*/

@interface OCLinkedList : NSObject {
	@protected
		// listHead is a sentinel node for the head of the list.
		OCLinkedListNode* listHead;
		// listTail is a sentinel node for the end of the list.
		OCLinkedListNode* listTail;
		// count is the number of items in the list.
		unsigned int count;
}
/*!
    @method     
    @abstract				Insert a new object at an arbitrary position in the receiver.
    @discussion				Requires: insertionIndex is less than or equal to count and
							is greater than or equal to zero, and that the number of items
							in the list can be expressed by an unsigned	integer.
							
							Guarantees: anObject will be inserted at index insertionIndex.
							Objects with an index less than insertionIndex will retain their
							current index while those at and following this point will have their
							index increased by one.
							
	@param anObject			The object to be inserted.
	@param insertionIndex	The zero-based index at which the object is to be inserted.
*/
-(void) insertObject:(id) anObject atIndex:(unsigned int) insertionIndex;

/*!
    @method     
    @abstract				Append a new object to the end of the receiver.
    @discussion				Requires: The number of items in the list can be expressed by
							an unsigned integer.
							
							Guarantees: anObject will be appended to the last position in the
							linked list.  The effect is the same as performing an insertion at
							the last position.
							
	@param anObject			The object to be inserted.
*/
-(void) addObject:(id) anObject;

/*!
    @method     
    @abstract				Append a new object to the end of the receiver.
    @discussion				Requires: The number of items in the list can be expressed
							by an unsigned integer.
							
							Guarantees: anObject will be inserted at the beginning of the
							linked list.  The effect is the same as performing an insertion at
							the beginning using insertObject:atIndex:.
							
	@param anObject			The object to be inserted.
*/
-(void) addObjectAtBeginning:(id) anObject;

/*!
    @method     
    @abstract				Remove an object from an arbitrary position in the receiver.
    @discussion				Requires: The removalIndex is a non-negative integer that is
							strictly less than count.
							
							Guarantees: The object with a zero-based index of removalIndex is removed
							with all subsequent objects having their indices decremented by one.
							
	@param removalIndex		The zero-based index at which an object is to be deleted.
*/
-(void) removeFromIndex:(unsigned int) removalIndex;

/*!
    @method     
    @abstract				Remove the first object in the reciever.
    @discussion				Requires: None.
							
							Guarantees: The object with a zero-based index of 0 is removed
							with all subsequent objects having their indices decremented by one.
							If no such object exists, nil is returned.
*/
-(void) removeFirstObject;

/*!
    @method     
    @abstract				Remove the last object in the receiver.
    @discussion				Requires: There must be at least one object on the list.
							
							Guarantees: The last object in the list is removed.
							If no such object exists, nil is returned.							
*/
-(void) removeLastObject;

/*!
    @method     
    @abstract				Returns the number of objects currently in the receiver.
    @discussion				Requires: None.
							
							Guarantees: The object count is correctly returned.
							
	@returns				The number of objects currently in the receiver.
*/
-(unsigned int) count;

/*!
    @method     
    @abstract				Returns a specified item from the receiver.
    @discussion				Requires: The index is a non-negative number that is strictly less than
							the number of objects in the receiver.
							
							Guarantees: The object with the corresponding index is correctly returned.
	@param	fetchIndex		The index of the item to be returned.
	@returns				The object with the requested index.
*/
-(id) objectAtIndex:(unsigned int) fetchIndex;


/*!
    @method     
    @abstract				Returns an NSEnumerator to iterate over objects in this list.
    @discussion				Requires: None.
							
							Guarantees: An NSEnumerator is returned that iterates over all objects
										if the list is not modified during traversal.
	@returns				An NSEnumerator.
*/
-(NSEnumerator*) objectEnumerator;
@end