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 | ee1310af719fdf9db650a8855c5726f3819ff78e (patch) | |
tree | 2e2f1540060cc86996c72dc0afa421216320530b /bin/ai/library/queue | |
parent | 3a13b75e37b5642de3c1e89cf6ab3bf860b76375 (diff) | |
download | openttd-ee1310af719fdf9db650a8855c5726f3819ff78e.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')
-rw-r--r-- | bin/ai/library/queue/binary_heap/library.nut | 14 | ||||
-rw-r--r-- | bin/ai/library/queue/binary_heap/main.nut | 131 | ||||
-rw-r--r-- | bin/ai/library/queue/fibonacci_heap/library.nut | 14 | ||||
-rw-r--r-- | bin/ai/library/queue/fibonacci_heap/main.nut | 204 | ||||
-rw-r--r-- | bin/ai/library/queue/priority_queue/library.nut | 14 | ||||
-rw-r--r-- | bin/ai/library/queue/priority_queue/main.nut | 115 |
6 files changed, 0 insertions, 492 deletions
diff --git a/bin/ai/library/queue/binary_heap/library.nut b/bin/ai/library/queue/binary_heap/library.nut deleted file mode 100644 index 5216fb588..000000000 --- a/bin/ai/library/queue/binary_heap/library.nut +++ /dev/null @@ -1,14 +0,0 @@ -/* $Id$ */ - -class Binary_Heap extends AILibrary { - function GetAuthor() { return "OpenTTD NoAI Developers Team"; } - function GetName() { return "Binary Heap"; } - function GetShortName() { return "QUBH"; } - function GetDescription() { return "An implementation of a Binary Heap"; } - function GetVersion() { return 1; } - function GetDate() { return "2008-06-10"; } - function CreateInstance() { return "Binary_Heap"; } - function GetCategory() { return "Queue"; } -} - -RegisterLibrary(Binary_Heap()); diff --git a/bin/ai/library/queue/binary_heap/main.nut b/bin/ai/library/queue/binary_heap/main.nut deleted file mode 100644 index 05fd452f3..000000000 --- a/bin/ai/library/queue/binary_heap/main.nut +++ /dev/null @@ -1,131 +0,0 @@ -/* $Id$ */ - -/** - * Binary Heap. - * Peek and Pop always return the current lowest value in the list. - * Sort is done on insertion and on deletion. - */ -class Binary_Heap -{ - _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 Binary_Heap::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 Binary_Heap::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 Binary_Heap::Peek() -{ - if (_count == 0) return null; - - return _queue[0][0]; -} - -function Binary_Heap::Count() -{ - return _count; -} - -function Binary_Heap::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 Binary_Heap::_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 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; - } -}; diff --git a/bin/ai/library/queue/priority_queue/library.nut b/bin/ai/library/queue/priority_queue/library.nut deleted file mode 100644 index 1559393ee..000000000 --- a/bin/ai/library/queue/priority_queue/library.nut +++ /dev/null @@ -1,14 +0,0 @@ -/* $Id$ */ - -class Priority_Queue extends AILibrary { - function GetAuthor() { return "OpenTTD NoAI Developers Team"; } - function GetName() { return "Priority Queue"; } - function GetShortName() { return "QUPQ"; } - function GetDescription() { return "An implementation of a Priority Queue"; } - function GetVersion() { return 2; } - function GetDate() { return "2008-06-10"; } - function CreateInstance() { return "Priority_Queue"; } - function GetCategory() { return "Queue"; } -} - -RegisterLibrary(Priority_Queue()); diff --git a/bin/ai/library/queue/priority_queue/main.nut b/bin/ai/library/queue/priority_queue/main.nut deleted file mode 100644 index feda89559..000000000 --- a/bin/ai/library/queue/priority_queue/main.nut +++ /dev/null @@ -1,115 +0,0 @@ -/* $Id$ */ - -/** - * Priority Queue. - * Peek and Pop always return the current lowest value in the list. - * Sort is done on insertion only. - */ -class Priority_Queue -{ - _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 Priority_Queue::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 Priority_Queue::Pop() -{ - if (_count == 0) return null; - - local node = _queue.pop(); - _count--; - - return node[0]; -} - -function Priority_Queue::Peek() -{ - if (_count == 0) return null; - - return _queue[_count - 1][0]; -} - -function Priority_Queue::Count() -{ - return _count; -} - -function Priority_Queue::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; -} |