Files
@ r10696:8dfe83e30d01
Branch filter:
Location: cpp/openttd-patchpack/source/bin/ai/library/queue/binary_heap/main.nut - annotation
r10696:8dfe83e30d01
2.7 KiB
text/plain
(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
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 | /* $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;
}
|