(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

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