/**
 * Doubly linked list implementation.
 *
 * See: <a href="http://en.wikipedia.org/wiki/Linked_list">Linked_list</a>
 *
 * @author ddjohnson
 * @version 1.0
 */

function LinkedList()
{
	this.header = new LinkedList.Entry(null,null,null);
	this.header.next = this.header.previous = this.header;
}

LinkedList.Entry = function(element,next,previous)
{
	this.element = element;
	this.next = next;
	this.previous = previous;
}

LinkedList.prototype =
{
	size: 0,

	add: function(e)
	{
		this.addBefore(e,this.header);
	},

	clear: function()
	{
		var e = this.header.next;
		while(e != this.header)
		{
			var next = e.next;
			e.next = e.previous = null;
			e.element = null;
			e = next;
		}
		this.header.next = this.header.previous = this.header;
		this.size = 0;
	},

	addBefore: function(e, entry)
	{
		var newEntry = new LinkedList.Entry(e,entry,entry.previous);
		newEntry.previous.next = newEntry;
		newEntry.next.previous = newEntry;
		this.size++;
		return newEntry;
	},

	getFirst: function()
	{
		if(this.size == 0)
			return null;
		return this.header.next.element;
	},

	getLast: function()
	{
		if(this.size == 0)
			return null;
		return this.header.previous.element;
	},

	iterator: function()
	{
		var _self = this;
		var el = this.header;
		var index = 0;
		return ({
			hasNext: function()
			{
				return index < _self.size;
			},
			next: function()
			{
				index++;
				return (el = el.next).element;
			}
		});
	},

	get: function(index)
	{
		if(index < 0 || index >= this.size)
			return null;
		var e = this.header;
		if(index < (this.size >> 1))
		{
			for(var i=0; i <= index; i++)
				e = e.next;
		}
		else
		{
			for(var i=this.size; i > index; i--)
				e = e.previous;
		}
		return e.element;
	},

	toString: function()
	{
		var str = "";
		var e = this.header.next;
		var c = 0;
		do
		{
			if(c!=0)
				str += ', ';
			str += e.element;
			e = e.next;
		}
		while(++c < this.size);

		return str;
	}
}