/***********************************************************************************************************
// Doubly Linked List and Node objects that also suport slow indexed access.
// Thanks to RadicalCongruency... http://www.radicalcongruency.com/20060511-javascript-doubly-linked-list //
// Copyright 2007-2008 Collaborative Bike Map Project
************************************************************************************************************/
// Constructor/template
function LinkedList() {
	this.firstnode = null;
	this.lastnode = null;
	this.length = 0;      
}

// Insert after node
LinkedList.prototype.insertAfter = function (node, newNode) {
	newNode.prev = node;
	newNode.next = node.next;

	if (node.next == null) 
		this.lastnode = newNode;
	else 
		node.next.prev = newNode;
	node.next = newNode;
	this.length++;
}

// Insert before node
LinkedList.prototype.insertBefore = function (node, newNode) {
	newNode.prev = node.prev;
	newNode.next = node;

	if (node.prev == null) 
		this.firstnode = newNode;
	else 
		node.prev.next = newNode;
	node.prev = newNode;
	this.length++;
}

// Insert at beginning
LinkedList.prototype.insertBeginning = function (newNode) {
	if (this.firstnode == null) {
		this.firstnode = newNode;
		this.lastnode  = newNode;
		newNode.prev = null;
		newNode.next = null;
		this.length = 1;
	}
	else 
		this.insertBefore(this.firstnode, newNode)
}

// Append to end
LinkedList.prototype.insertEnd = function (newNode) {
	if (this.lastnode == null) 
		this.insertBeginning(newNode);
	else 
		this.insertAfter(this.lastnode, newNode);
}

// Remove node
LinkedList.prototype.remove = function (node) {
	if (node.prev == null)
		this.firstnode = node.next;
	else 
		node.prev.next = node.next;

	if (node.next == null) 
		this.lastnode = node.prev;
	else 
		node.next.prev = node.prev;
	this.length--;

	node.next = node.prev = null;    // do for proper garbage collection
}

// Remove all nodes (doesn't delete node objects but does set prev/next pointers to null to ensure garbage collection)
LinkedList.prototype.removeAll = function () {
	var nextnode;
	var n;
	// debugger;
	n = this.firstnode;
	while (n != null) {
		nextnode = n.next;
		n.next = n.prev = null;
		n = nextnode;
	}
	this.firstnode = this.lastnode = null;
	this.length = 0;
}

// Get node at index (zero-based) - Added by Jack
// Returns null if index < 0 or past end of list
LinkedList.prototype.getByIndex = function (index) {
	var i = 0;
	var node = this.firstnode;
	if (index < 0)
		return null;
	else {
		while (i<index && node != null) {
			node = node.next; 
			i++;
		}
		return (node);
	}
}

// Get index of specified node (zero-based) - Added by Jack
// Returns null if node is not in the list
LinkedList.prototype.getIndex = function (node) {
	var i = 0;
	var n = this.firstnode;
	while (n != null && n != node) {
		i++;
		n = n.next;
	}
	return (n == null ? null : i);
}

// Check if specified node is in the list
LinkedList.prototype.check = function (seeknode) {
	var found = false;
	var node = this.firstnode;
	while (!found && node != null) {
		if (node == seeknode)
			found = true;
		else
			node = node.next;
	}
	return (found);
}

// Return list node with specified unique ID.  Return null if ID not found.
// The ID field must be defined in the class derived from LinkedList or null will be returned.
LinkedList.prototype.getById = function (id) {
	var found = false;
	var node = null;
	if (this.id != undefined) {
		node = this.firstnode;
		while (!found && node != null) {
			if (node.id == id)
				found = true;
			else
				node = node.next;
		}
	}
	return (node);
}

// Generate unique ID within linked list (id > 1).  New ID not necessarily sequential.
// The ID field must be defined in the class derived from LinkedList or null will be returned.
// It computes  maximum id already in use in the list and returns max + 1.
// To improve performance it can be called once to get an initial unique id value,
// then that value can be incrememented to get successive unique ids.
LinkedList.prototype.genUniqueListId = function () {        
	var max_id = 0;	
	var node = this.firstnode;
	if (node != null && node.id != undefined) {
		while (node != null) {
			if (node.id > max_id)
				max_id = node.id;
			node = node.next;
		}
		return (max_id + 1);
	}
	else
		return null;
}

// Create array from LinkedList.  Returns the array.
LinkedList.prototype.toArray = function () {
	var arr = new Array ();
	// if route has any points (otherwise do nothing)
	var n = this.firstnode;
	while (n != null) {
		arr.push (n);
		n = n.next;
	}
	return arr;
}


/***********************************************************************************************************
// Node object type
************************************************************************************************************/
/* Generic node object type */
function Node() {
	this.next = null;
	this.prev = null;
}