1 files changed, 131 insertions, 0 deletions
diff --git a/bin/ai/library/queue/binary_heap/main.nut b/bin/ai/library/queue/binary_heap/main.nut
new file mode 100644
index 000000000..1bbb3914f
--- /dev/null
+++ b/bin/ai/library/queue/binary_heap/main.nut
@@ -0,0 +1,131 @@
+/* $Id$ */
+
+/**
+ * Binary Heap.
+ *  Peek and Pop always return the current lowest value in the list.
+ *  Sort is done on insertion and on deletion.
+ */
+class BinaryHeap
+{
+	_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 BinaryHeap::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 BinaryHeap::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 BinaryHeap::Peek()
+{
+	if (_count == 0) return null;
+
+	return _queue[0][0];
+}
+
+function BinaryHeap::Count()
+{
+	return _count;
+}
+
+function BinaryHeap::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 BinaryHeap::_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;
+}