diff options
author | truebrain <truebrain@openttd.org> | 2009-01-12 17:11:45 +0000 |
---|---|---|
committer | truebrain <truebrain@openttd.org> | 2009-01-12 17:11:45 +0000 |
commit | a3dd7506d377b1434f913bd65c019eed52b64b6e (patch) | |
tree | ced1a262eb143ad6e64ec02f4a4c89835c0c32fd /bin/ai/library/queue/priority_queue | |
parent | 9294f9616866b9778c22076c19b5a32b4f85f788 (diff) | |
download | openttd-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/priority_queue')
-rw-r--r-- | bin/ai/library/queue/priority_queue/library.nut | 12 | ||||
-rw-r--r-- | bin/ai/library/queue/priority_queue/main.nut | 115 |
2 files changed, 127 insertions, 0 deletions
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; +} |