6 files changed, 486 insertions, 0 deletions
diff --git a/bin/ai/library/queue/binary_heap/library.nut b/bin/ai/library/queue/binary_heap/library.nut
new file mode 100644
index 000000000..3a96617a9
--- /dev/null
+++ b/bin/ai/library/queue/binary_heap/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class BinaryHeap extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Binary Heap"; }
+	function GetDescription() { return "An implementation of a Binary Heap"; }
+	function GetVersion()     { return 1; }
+	function GetDate()        { return "2008-06-10"; }
+	function CreateInstance() { return "BinaryHeap"; }
+}
+
+RegisterLibrary(BinaryHeap());
diff --git a/bin/ai/library/queue/binary_heap/main.nut b/bin/ai/library/queue/binary_heap/main.nut
new file mode 100644
index 000000000..1bbb3914f
--- /dev/null
+++ b/bin/ai/library/queue/binary_heap/main.nut
@@ -0,0 +1,131 @@
+/* $Id$ */
+
+/**
+ * Binary Heap.
+ *  Peek and Pop always return the current lowest value in the list.
+ *  Sort is done on insertion and on deletion.
+ */
+class BinaryHeap
+{
+	_queue = null;
+	_count = 0;
+
+	constructor()
+	{
+		_queue = [];
+	}
+
+	/**
+	 * Insert a new entry in the list.
+	 *  The complexity of this operation is O(ln n).
+	 * @param item The item to add to the list.
+	 * @param priority The priority this item has.
+	 */
+	function Insert(item, priority);
+
+	/**
+	 * Pop the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(ln n).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Pop();
+
+	/**
+	 * Peek the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Peek();
+
+	/**
+	 * Get the amount of current items in the list.
+	 *  The complexity of this operation is O(1).
+	 * @return The amount of items currently in the list.
+	 */
+	function Count();
+
+	/**
+	 * Check if an item exists in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to check for.
+	 * @return True if the item is already in the list.
+	 */
+	function Exists(item);
+};
+
+function BinaryHeap::Insert(item, priority)
+{
+	/* Append dummy entry */
+	_queue.append(0);
+	_count++;
+
+	local hole;
+	/* Find the point of insertion */
+	for (hole = _count - 1; hole > 0 && priority <= _queue[hole / 2][1]; hole /= 2)
+		_queue[hole] = _queue[hole / 2];
+	/* Insert new pair */
+	_queue[hole] = [item, priority];
+
+	return true;
+}
+
+function BinaryHeap::Pop()
+{
+	if (_count == 0) return null;
+
+	local node = _queue[0];
+	/* Remove the item from the list by putting the last value on top */
+	_queue[0] = _queue[_count - 1];
+	_queue.pop();
+	_count--;
+	/* Bubble down the last value to correct the tree again */
+	_BubbleDown();
+
+	return node[0];
+}
+
+function BinaryHeap::Peek()
+{
+	if (_count == 0) return null;
+
+	return _queue[0][0];
+}
+
+function BinaryHeap::Count()
+{
+	return _count;
+}
+
+function BinaryHeap::Exists(item)
+{
+	/* Brute-force find the item (there is no faster way, as we don't have the priority number) */
+	foreach (node in _queue) {
+		if (node[0] == item) return true;
+	}
+
+	return false;
+}
+
+
+
+function BinaryHeap::_BubbleDown()
+{
+	if (_count == 0) return;
+
+	local hole = 1;
+	local tmp = _queue[0];
+
+	/* Start switching parent and child until the tree is restored */
+	while (hole * 2 < _count + 1) {
+		local child = hole * 2;
+		if (child != _count && _queue[child][1] <= _queue[child - 1][1]) child++;
+		if (_queue[child - 1][1] > tmp[1]) break;
+
+		_queue[hole - 1] = _queue[child - 1];
+		hole = child;
+	}
+	/* The top value is now at his new place */
+	_queue[hole - 1] = tmp;
+}
diff --git a/bin/ai/library/queue/fibonacci_heap/library.nut b/bin/ai/library/queue/fibonacci_heap/library.nut
new file mode 100644
index 000000000..1ea7260e0
--- /dev/null
+++ b/bin/ai/library/queue/fibonacci_heap/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class FibonacciHeap extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Fibonacci Heap"; }
+	function GetDescription() { return "An implementation of a Fibonacci Heap"; }
+	function GetVersion()     { return 1; }
+	function GetDate()        { return "2008-08-22"; }
+	function CreateInstance() { return "FibonacciHeap"; }
+}
+
+RegisterLibrary(FibonacciHeap());
diff --git a/bin/ai/library/queue/fibonacci_heap/main.nut b/bin/ai/library/queue/fibonacci_heap/main.nut
new file mode 100644
index 000000000..7c6b3ece2
--- /dev/null
+++ b/bin/ai/library/queue/fibonacci_heap/main.nut
@@ -0,0 +1,204 @@
+/* $Id$ */
+
+/**
+ * Fibonacci heap.
+ *  This heap is heavily optimized for the Insert and Pop functions.
+ *  Peek and Pop always return the current lowest value in the list.
+ *  Insert is implemented as a lazy insert, as it will simply add the new
+ *  node to the root list. Sort is done on every Pop operation.
+ */
+class FibonacciHeap {
+	_min = null;
+	_min_index = 0;
+	_min_priority = 0;
+	_count = 0;
+	_root_list = null;
+
+	/**
+	 * Create a new fibonacci heap.
+	 * http://en.wikipedia.org/wiki/Fibonacci_heap
+	 */
+	constructor() {
+		_count = 0;
+		_min = Node();
+		_min.priority = 0x7FFFFFFF;
+		_min_index = 0;
+		_min_priority = 0x7FFFFFFF;
+		_root_list = [];
+	}
+
+	/**
+	 * Insert a new entry in the heap.
+	 *  The complexity of this operation is O(1).
+	 * @param item The item to add to the list.
+	 * @param priority The priority this item has.
+	 */
+	function Insert(item, priority);
+
+	/**
+	 * Pop the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(ln n).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Pop();
+
+	/**
+	 * Peek the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Peek();
+
+	/**
+	 * Get the amount of current items in the list.
+	 *  The complexity of this operation is O(1).
+	 * @return The amount of items currently in the list.
+	 */
+	function Count();
+
+	/**
+	 * Check if an item exists in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to check for.
+	 * @return True if the item is already in the list.
+	 */
+	function Exists(item);
+};
+
+function FibonacciHeap::Insert(item, priority) {
+	/* Create a new node instance to add to the heap. */
+	local node = Node();
+	/* Changing params is faster than using constructor values */
+	node.item = item;
+	node.priority = priority;
+
+	/* Update the reference to the minimum node if this node has a
+	 * smaller priority. */
+	if (_min_priority > priority) {
+		_min = node;
+		_min_index = _root_list.len();
+		_min_priority = priority;
+	}
+
+	_root_list.append(node);
+	_count++;
+}
+
+function FibonacciHeap::Pop() {
+
+	if (_count == 0) return null;
+
+	/* Bring variables from the class scope to this scope explicitly to
+	 * optimize variable lookups by Squirrel. */
+	local z = _min;
+	local tmp_root_list = _root_list;
+
+	/* If there are any children, bring them all to the root level. */
+	tmp_root_list.extend(z.child);
+
+	/* Remove the minimum node from the rootList. */
+	tmp_root_list.remove(_min_index);
+	local root_cache = {};
+
+	/* Now we decrease the number of nodes on the root level by
+	 * merging nodes which have the same degree. The node with
+	 * the lowest priority value will become the parent. */
+	foreach(x in tmp_root_list) {
+		local y;
+
+		/* See if we encountered a node with the same degree already. */
+		while (y = root_cache.rawdelete(x.degree)) {
+			/* Check the priorities. */
+			if (x.priority > y.priority) {
+				local tmp = x;
+				x = y;
+				y = tmp;
+			}
+
+			/* Make y a child of x. */
+			x.child.append(y);
+			x.degree++;
+		}
+
+		root_cache[x.degree] <- x;
+	}
+
+	/* The root_cache contains all the nodes which will form the
+	 *  new rootList. We reset the priority to the maximum number
+	 *  for a 32 signed integer to find a new minumum. */
+	tmp_root_list.resize(root_cache.len());
+	local i = 0;
+	local tmp_min_priority = 0x7FFFFFFF;
+
+	/* Now we need to find the new minimum among the root nodes. */
+	foreach (val in root_cache) {
+		if (val.priority < tmp_min_priority) {
+			_min = val;
+			_min_index = i;
+			tmp_min_priority = val.priority;
+		}
+
+		tmp_root_list[i++] = val;
+	}
+
+	/* Update global variables. */
+	_min_priority = tmp_min_priority;
+
+	_count--;
+	return z.item;
+}
+
+function FibonacciHeap::Peek() {
+	if (_count == 0) return null;
+	return _min.item;
+}
+
+function FibonacciHeap::Count() {
+	return _count;
+}
+
+function FibonacciHeap::Exists(item) {
+	return ExistsIn(_root_list, item);
+}
+
+/**
+ * Auxilary function to search through the whole heap.
+ * @param list The list of nodes to look through.
+ * @param item The item to search for.
+ * @return True if the item is found, false otherwise.
+ */
+function FibonacciHeap::ExistsIn(list, item) {
+
+	foreach (val in list) {
+		if (val.item == item) {
+			return true;
+		}
+
+		foreach (c in val.child) {
+			if (ExistsIn(c, item)) {
+				return true;
+			}
+		}
+	}
+
+	/* No luck, item doesn't exists in the tree rooted under list. */
+	return false;
+}
+
+/**
+ * Basic class the fibonacci heap is composed of.
+ */
+class FibonacciHeap.Node {
+	degree = null;
+	child = null;
+
+	item = null;
+	priority = null;
+
+	constructor() {
+		child = [];
+		degree = 0;
+	}
+};
diff --git a/bin/ai/library/queue/priority_queue/library.nut b/bin/ai/library/queue/priority_queue/library.nut
new file mode 100644
index 000000000..a8c615ed1
--- /dev/null
+++ b/bin/ai/library/queue/priority_queue/library.nut
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class PriorityQueue extends AILibrary {
+	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }
+	function GetName()        { return "Priority Queue"; }
+	function GetDescription() { return "An implementation of a Priority Queue"; }
+	function GetVersion()     { return 2; }
+	function GetDate()        { return "2008-06-10"; }
+	function CreateInstance() { return "PriorityQueue"; }
+}
+
+RegisterLibrary(PriorityQueue());
diff --git a/bin/ai/library/queue/priority_queue/main.nut b/bin/ai/library/queue/priority_queue/main.nut
new file mode 100644
index 000000000..bafc93ac5
--- /dev/null
+++ b/bin/ai/library/queue/priority_queue/main.nut
@@ -0,0 +1,115 @@
+/* $Id$ */
+
+/**
+ * Priority Queue.
+ *  Peek and Pop always return the current lowest value in the list.
+ *  Sort is done on insertion only.
+ */
+class PriorityQueue
+{
+	_queue = null;
+	_count = 0;
+
+	constructor()
+	{
+		_count = 0;
+		_queue = [];
+	}
+
+	/**
+	 * Insert a new entry in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to add to the list.
+	 * @param priority The priority this item has.
+	 */
+	function Insert(item, priority);
+
+	/**
+	 * Pop the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Pop();
+
+	/**
+	 * Peek the first entry of the list.
+	 *  This is always the item with the lowest priority.
+	 *  The complexity of this operation is O(1).
+	 * @return The item of the entry with the lowest priority.
+	 */
+	function Peek();
+
+	/**
+	 * Get the amount of current items in the list.
+	 *  The complexity of this operation is O(1).
+	 * @return The amount of items currently in the list.
+	 */
+	function Count();
+
+	/**
+	 * Check if an item exists in the list.
+	 *  The complexity of this operation is O(n).
+	 * @param item The item to check for.
+	 * @return True if the item is already in the list.
+	 */
+	function Exists(item);
+};
+
+function PriorityQueue::Insert(item, priority)
+{
+	/* Append dummy entry */
+	_queue.append(0);
+	_count++;
+
+	local i;
+	/* Find the point of insertion */
+	for (i = _count - 2; i >= 0; i--) {
+		if (priority > _queue[i][1]) {
+			/* All items bigger move one place to the right */
+			_queue[i + 1] = _queue[i];
+		} else if (item == _queue[i][0]) {
+			/* Same item, ignore insertion */
+			return false;
+		} else {
+			/* Found place to insert at */
+			break;
+		}
+	}
+	/* Insert new pair */
+	_queue[i + 1] = [item, priority];
+
+	return true;
+}
+
+function PriorityQueue::Pop()
+{
+	if (_count == 0) return null;
+
+	local node = _queue.pop();
+	_count--;
+
+	return node[0];
+}
+
+function PriorityQueue::Peek()
+{
+	if (_count == 0) return null;
+
+	return _queue[_count - 1][0];
+}
+
+function PriorityQueue::Count()
+{
+	return _count;
+}
+
+function PriorityQueue::Exists(item)
+{
+	/* Brute-force find the item (there is no faster way, as we don't have the priority number) */
+	foreach (node in _queue) {
+		if (node[0] == item) return true;
+	}
+
+	return false;
+}