// Creates a link list in javascript.

//----------------------------------------------------------------------------
// Description:
//		Constructs a list item.
// Parameters:
//		value        - value to store in the list.
//		previousItem - reference to the previous item in the list.
//		nextItem     - reference to the next item in the list.
//----------------------------------------------------------------------------
function ListItem(value, previousItem, nextItem)
{
	this.value = value;
	this.previousItem = previousItem;
	this.nextItem = nextItem;
}

//----------------------------------------------------------------------------
// Description:
//		Creates a double-link list.
// Parameters:
//		n/a.
//----------------------------------------------------------------------------
function List()
{
	this.headItem = null;
	this.tailItem = null;
	this.length = 0;
}

//----------------------------------------------------------------------------
// Description:
//		Adds an item to the end of the list.
// Parameters:
//		value - value to add to list.
//----------------------------------------------------------------------------
List.prototype.addItem = function(value)
{
	// Is this first item in list?
	if (this.headItem == null)
	{
		var item = new ListItem(value, null, null);
		this.headItem = item;
		this.tailItem = item;
		this.length = 1;
	}
	else
	{
		var item = new ListItem(value, this.tailItem, null);
		this.tailItem.nextItem = item;
		this.tailItem = item;
		this.length++;
	}
}

//----------------------------------------------------------------------------
// Description:
//		Removes head item from list and returns its value.
// Parameters:
//		n/a.
//----------------------------------------------------------------------------
List.prototype.removeHead = function()
{
	var value = null;
	// If this is the tail item, clear out the list.
	if (this.headItem != null)
	{
		value = this.headItem.value;
		if (this.headItem.nextItem == null)
		{
			this.headItem = null;
			this.tailItem = null;
		}
		else
		{
			var oldHead = this.headItem;
			this.headItem = this.headItem.nextItem;
			this.headItem.previousItem = null;
			oldHead.nextItem = null;
			oldHead.previousItem = null;
			oldHead = null;
		}
		this.length--;
	}
	return value;
}

//----------------------------------------------------------------------------
// Description:
//		Removes tail item from list and returns its value.
// Parameters:
//		n/a.
//----------------------------------------------------------------------------
List.prototype.removeTail = function()
{
	var value = null;
	if (this.tailItem != null)
	{
		value = this.tailItem.value;
		// If this is the head item, clear the list out.
		if (this.tailItem.previousItem == null)
		{
			this.headItem = null;
			this.tailItem = null;
		}
		else
		{
			var oldTail = this.tailItem;
			this.tailItem = this.tailItem.previousItem;
			this.tailItem.nextItem = null;
			oldTail.nextItem = null;
			oldTail.previousItem = null;
			oldTail = null;
		}
		this.length--;
	}
	return value;
}

//----------------------------------------------------------------------------
// Description:
//		Clears down the list.
// Parameters:
//		n/a.
//----------------------------------------------------------------------------

List.prototype.clear = function()
{
	while (this.headItem != null)
	{
		this.removeHead();
	}
	this.length = 0;
}

//----------------------------------------------------------------------------
// Description:
//		Returns the value stored in the item at the given index.
// Parameters:
//		index - index of item required.
//----------------------------------------------------------------------------
List.prototype.getAtIndex = function(index)
{
	if (this.headItem != null)
	{
		var count = 0;
		var item = this.headItem;
		
		for (var i = 0; i < this.length; i++)
		{
			if (i == index)
			{
				return item.value;
			}
			item = item.nextItem;
		}
	}
	return null;
}

//----------------------------------------------------------------------------
// Description:
//		Searches for an item with a given value.
//		Returns index in list of that item, or -1 if not found.
// Parameters:
//		value - value to search for.
//----------------------------------------------------------------------------
List.prototype.indexOf = function(value)
{
	if (this.headItem != null)
	{
		if (this.headItem.value == value)
		{
			return 0;
		}
		else if (this.tailItem.value == value)
		{
			return (this.length - 1);
		}
		else
		{
			var count = 0;
			var item = this.headItem.nextItem;
			while (item != null)
			{
				count++;
				if (item.value == value)
				{
					return count;
				}
				item = item.nextItem;
			}
		}
	}
	return (-1);
}

//----------------------------------------------------------------------------
// Description:
//		Removes an item at a given index and returns the value of it.
// Parameters:
//		index - index of item to remove.
//----------------------------------------------------------------------------
List.prototype.removeAt = function(index)
{
	if (this.headItem != null)
	{
		var count = 0;
		var item = this.headItem;
		while (count < index)
		{
			if (item == null)
			{
				return null;
			}
			item = item.nextItem;
			count++;
		}
		// Detach item from list.
		// Does it have a previous item?
		if (item.previousItem != null)
		{
			item.previousItem.nextItem = item.nextItem;
		}
		// Does it have a next item?
		if (item.nextItem != null)
		{
			item.nextItem.previousItem = item.previousItem;
		}
		this.length--;
			
		// Now set the head and tail items accordingly.
		if (this.length == 0)
		{
			this.headItem = null;
			this.tailItem = null;
		}
		else
		{
			// Was this the head item?
			if (this.headItem == item)
			{
				this.headItem = item.nextItem;
			}
			// Was this the tail item?
			if (this.tailItem == item)
			{
				this.tailItem = item.previousItem;
			}
		}
		var val = item.value;
		item.nextItem = null;
		item.previousItem = null;
		item = null;
		return val;
	}
}

//----------------------------------------------------------------------------
// Description:
//		Useful debug method to alert all items in list.
// Parameters:
//		n/a.
//----------------------------------------------------------------------------
List.prototype.printContents = function()
{
	var strContents = '';
	var item = this.headItem;
	while (item != null)
	{
		strContents += item.value + ', ';
		item = item.nextItem;
	}
	alert(strContents);
}