diff options
author | truebrain <truebrain@openttd.org> | 2009-01-17 16:57:30 +0000 |
---|---|---|
committer | truebrain <truebrain@openttd.org> | 2009-01-17 16:57:30 +0000 |
commit | 84f0da74af2b76c40e0ff231697f963267a8f537 (patch) | |
tree | 2e2f1540060cc86996c72dc0afa421216320530b /bin/ai/library/queue/fibonacci_heap | |
parent | 72b0341ed01caed7053df6f2ca7f9530d1f67e40 (diff) | |
download | openttd-84f0da74af2b76c40e0ff231697f963267a8f537.tar.xz |
(svn r15128) -Remove: remove WrightAI and AI Libraries from SVN, as they are now available via the content service
Diffstat (limited to 'bin/ai/library/queue/fibonacci_heap')
-rw-r--r-- | bin/ai/library/queue/fibonacci_heap/library.nut | 14 | ||||
-rw-r--r-- | bin/ai/library/queue/fibonacci_heap/main.nut | 204 |
2 files changed, 0 insertions, 218 deletions
diff --git a/bin/ai/library/queue/fibonacci_heap/library.nut b/bin/ai/library/queue/fibonacci_heap/library.nut deleted file mode 100644 index 6cbd614da..000000000 --- a/bin/ai/library/queue/fibonacci_heap/library.nut +++ /dev/null @@ -1,14 +0,0 @@ -/* $Id$ */ - -class Fibonacci_Heap extends AILibrary { - function GetAuthor() { return "OpenTTD NoAI Developers Team"; } - function GetName() { return "Fibonacci Heap"; } - function GetShortName() { return "QUFH"; } - function GetDescription() { return "An implementation of a Fibonacci Heap"; } - function GetVersion() { return 1; } - function GetDate() { return "2008-08-22"; } - function CreateInstance() { return "Fibonacci_Heap"; } - function GetCategory() { return "Queue"; } -} - -RegisterLibrary(Fibonacci_Heap()); diff --git a/bin/ai/library/queue/fibonacci_heap/main.nut b/bin/ai/library/queue/fibonacci_heap/main.nut deleted file mode 100644 index 6be8bdd49..000000000 --- a/bin/ai/library/queue/fibonacci_heap/main.nut +++ /dev/null @@ -1,204 +0,0 @@ -/* $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 Fibonacci_Heap { - _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 Fibonacci_Heap::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 Fibonacci_Heap::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 Fibonacci_Heap::Peek() { - if (_count == 0) return null; - return _min.item; -} - -function Fibonacci_Heap::Count() { - return _count; -} - -function Fibonacci_Heap::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 Fibonacci_Heap::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 Fibonacci_Heap.Node { - degree = null; - child = null; - - item = null; - priority = null; - - constructor() { - child = []; - degree = 0; - } -}; |