(svn r15027) -Merge: tomatos and bananas left to be, here is NoAI for all to see.

  NoAI is an API (a framework) to build your own AIs in. See:
   http://wiki.openttd.org/wiki/index.php/AI:Main_Page
 With many thanks to:
  - glx and Rubidium for their syncing, feedback and hard work
  - Yexo for his feedback, patches, and AIs which tested the system very deep
  - Morloth for his feedback and patches
  - TJIP for hosting a challenge which kept NoAI on track
  - All AI authors for testing our AI API, and all other people who helped in one way or another
-Remove: all old AIs and their cheats/hacks

1 files changed, 204 insertions, 0 deletions

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;
+	}
+};