diff options
Diffstat (limited to 'bin/ai/library/queue/binary_heap/main.nut')
-rw-r--r-- | bin/ai/library/queue/binary_heap/main.nut | 131 |
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; +} |