// List 0.0.1
// requires: nothing
// 
// protected by creative commons deed
// under the following conditions: Attribution, Share Alike
// http://creativecommons.org/licenses/by-sa/2.5/
// 
// queue implementation
//
// API:
// int List.length
// Array List.toArray([boolean dense = false])
// mixed List.get([int index])
// boolean List.contains(mixed item, [boolean exact = true])
// List List.insert(mixed item, [int index])
// List List.remove(index)
// List List.add(Array arr)
// List List.filter(Function fn, object context, [Array arg])
// List List.undo([int steps = 1])
// List List.apply(Function fn, object context, [Array arg])

var List = function () {
	
	// private properties
	
	var data = [];
	
	var rollbackData = [];
	
	
	
	
	// private methods
	
	var getEmptyIndex = function (index) {
		// finds first index where an item could be placed
		var result = data.length;
		var i, l;
		if (
			(typeof index == "number") && 
			(index > 0) && 
			(index < data.length) && 
			(typeof data[index] == "undefined")
		) { // index is correct
			result = index;
		} else {
			findHole: for (i = 0, l = data.length; i < l; i++) {
				if (typeof data[i] == "undefined") {
					result = i;
					break findHole;
				}
			}
		}
		return result;
	};
	
	var updateLength = function () {
		var index = data.length - 1;
		while (typeof data[index] == "undefined") {
			index--;
		}
		this.length = index + 1;
		data.length = this.length;
		return true;
	};
	
	var addRollback = function (undoMethod, undoArguments) {
		rollbackData[rollbackData.length] = [undoMethod, undoArguments];
		return true;
	};
	
	var setItem = function (item, index) {
		data[index] = item;
		updateLength.apply(this, []);
		return true;
	};
	
	var removeItem = function (index) {
		if (
			(typeof index == "number") && 
			(index >= 0) && 
			(index < data.length)
		) {
			delete data[index];
			updateLength.apply(this, []);
		} else {
			throw "List.remove: index out of bounds";
		}
		return true;
	};
	
	
	
	
	// public properties
	this.length = 0;
	
	
	
	
	// public methods - getters
	
	this.toArray = function (dense) {
		// returns the content as sparse or dense array
		var result = [];
		var i, l;
		for (i = 0, l = data.length; i < l; i++) {
			if (dense) {
				result[result.length] = data[i];
			} else {
				result[i] = data[i];
			}
		}
		return result;
	};
	
	this.toString = function () {
		return data.join();
	};
	
	this.get = function (index) {
		var result = null;
		if (
			(typeof index == "number") && 
			(index >= 0) && 
			(index < data.length) && 
			(data[index] != "undefined")
		) {
			result = data[index];
		} else {
			result = this.toArray();
		}
		return result;
	};
	
	this.contains = function (item, exact) {
		// tests if this list contains item. By default, use == for test, if exact is true use === . Not a deep testing.
		if (typeof exact != "boolean") {
			exact = true; // exact search by default
		}
		var itemFound = false;
		var i, l;
		searchForItem:
			for (i = 0, l = data.length; i < l; i++) {
				if (exact) {
					if (data[i] === item) {
						itemFound = true;
						break searchForItem;
					}
				} else if (data[i] == item) {
					itemFound = true;
					break searchForItem;
				}
			}
		return itemFound;
	};
	
	// public methods - reversible
	
	this.insert = function (item, index) {
		index = getEmptyIndex.apply(this, [index]);
		if (setItem.apply(this, [item, index])) {
			addRollback.apply(this, [removeItem, [index]]);
		}
		return this;
	};
	
	this.remove = function (index) {
		var rollbackData = data[index];
		if ( removeItem.apply(this, [index]) ) {
			addRollback.apply(this, [setItem, [rollbackData, index]]);
		}
		return this;
	};
	
	this.add = function (arr) {
		// adds all items from array arr to the list
		var i, l;
		var insertCount = 0;
		if (arr && (typeof arr.length == "number")) {
			for (i = 0, l = arr.length; i < l; i++) {
				if (typeof arr[i] != "undefined") {
					this.insert(arr[i]);
					insertCount++;
				}
			}
		}
		if (insertCount > 0) {
			addRollback.apply(this.undo, [insertCount]);
		}
		return this;
	};
	
	this.filter = function (fn, context, arg) {
		// callback function is called on all data items.
		// if any callback returns false, the item is removed
		// call: context.fn(item, arg)
		var removeCount = 0;
		var i, l;
		for (i = 0, l = data.length - 1; i < l; i++) {
			if (false === fn.apply(context, [data[i], arg])) {
				this.remove(i);
				removeCount++;
			}
		}
		if (removeCount > 0) {
			addRollback.apply(this.undo, [removeCount]);
		}
		return this;
	};
	
	// public methods - ireversible
	
	this.undo = function (steps) {
		if (
			(typeof steps != "number") || 
			(steps < 0)
		) {
			steps = 1; // default number of undo steps
		}
		result = this;
		var i, rollbackItem;
		if (rollbackData.length >= steps) {
			for (i = 0; i < steps; i++) {
				rollbackItem = rollbackData[rollbackData.length - 1];
				result = rollbackItem[0].apply(this, rollbackItem[1]);
				delete rollbackData[rollbackData.length - 1];
				rollbackData.length--;
			}
		} else {
			throw("Undo failed, insufficient number of entries in undo history");
		}
		return result;
	};
	
	this.apply = function (fn, context, arg) {
		// callback function is applied on all data items
		// call: context.fn(item, arg)
		var i, l;
		for (i = 0, l = data.length - 1; i < l; i++) {
			data[data.length] = fn.apply(context, [data[i], arg]);
		}
		return this;
	};
	
	
	
	
	// run this as init code
	
	this.add.apply(this, arguments);
};