summaryrefslogtreecommitdiff
path: root/bin/ai/library/queue/fibonacci_heap
diff options
context:
space:
mode:
authortruebrain <truebrain@openttd.org>2009-01-12 17:11:45 +0000
committertruebrain <truebrain@openttd.org>2009-01-12 17:11:45 +0000
commita3dd7506d377b1434f913bd65c019eed52b64b6e (patch)
treeced1a262eb143ad6e64ec02f4a4c89835c0c32fd /bin/ai/library/queue/fibonacci_heap
parent9294f9616866b9778c22076c19b5a32b4f85f788 (diff)
downloadopenttd-a3dd7506d377b1434f913bd65c019eed52b64b6e.tar.xz
(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
Diffstat (limited to 'bin/ai/library/queue/fibonacci_heap')
-rw-r--r--bin/ai/library/queue/fibonacci_heap/library.nut12
-rw-r--r--bin/ai/library/queue/fibonacci_heap/main.nut204
2 files changed, 216 insertions, 0 deletions
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;
+ }
+};