Files
@ r10759:b4c7c8262caf
Branch filter:
Location: cpp/openttd-patchpack/source/bin/ai/library/queue/fibonacci_heap/main.nut - annotation
r10759:b4c7c8262caf
4.6 KiB
text/plain
(svn r15092) -Fix [NoAI]: make the library internal class name consistant with their directory name
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 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 | r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10759:b4c7c8262caf 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 r10759:b4c7c8262caf 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 r10759:b4c7c8262caf 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 r10759:b4c7c8262caf r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10759:b4c7c8262caf r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10759:b4c7c8262caf r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10759:b4c7c8262caf 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 r10759:b4c7c8262caf r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 r10696:8dfe83e30d01 | /* $Id$ */
/**
* Fibonacci heap.
* This heap is heavily optimized for the Insert and Pop functions.
* Peek and Pop always return the current lowest value in the list.
* Insert is implemented as a lazy insert, as it will simply add the new
* node to the root list. Sort is done on every Pop operation.
*/
class Fibonacci_Heap {
_min = null;
_min_index = 0;
_min_priority = 0;
_count = 0;
_root_list = null;
/**
* Create a new fibonacci heap.
* http://en.wikipedia.org/wiki/Fibonacci_heap
*/
constructor() {
_count = 0;
_min = Node();
_min.priority = 0x7FFFFFFF;
_min_index = 0;
_min_priority = 0x7FFFFFFF;
_root_list = [];
}
/**
* Insert a new entry in the heap.
* The complexity of this operation is O(1).
* @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 Fibonacci_Heap::Insert(item, priority) {
/* Create a new node instance to add to the heap. */
local node = Node();
/* Changing params is faster than using constructor values */
node.item = item;
node.priority = priority;
/* Update the reference to the minimum node if this node has a
* smaller priority. */
if (_min_priority > priority) {
_min = node;
_min_index = _root_list.len();
_min_priority = priority;
}
_root_list.append(node);
_count++;
}
function Fibonacci_Heap::Pop() {
if (_count == 0) return null;
/* Bring variables from the class scope to this scope explicitly to
* optimize variable lookups by Squirrel. */
local z = _min;
local tmp_root_list = _root_list;
/* If there are any children, bring them all to the root level. */
tmp_root_list.extend(z.child);
/* Remove the minimum node from the rootList. */
tmp_root_list.remove(_min_index);
local root_cache = {};
/* Now we decrease the number of nodes on the root level by
* merging nodes which have the same degree. The node with
* the lowest priority value will become the parent. */
foreach(x in tmp_root_list) {
local y;
/* See if we encountered a node with the same degree already. */
while (y = root_cache.rawdelete(x.degree)) {
/* Check the priorities. */
if (x.priority > y.priority) {
local tmp = x;
x = y;
y = tmp;
}
/* Make y a child of x. */
x.child.append(y);
x.degree++;
}
root_cache[x.degree] <- x;
}
/* The root_cache contains all the nodes which will form the
* new rootList. We reset the priority to the maximum number
* for a 32 signed integer to find a new minumum. */
tmp_root_list.resize(root_cache.len());
local i = 0;
local tmp_min_priority = 0x7FFFFFFF;
/* Now we need to find the new minimum among the root nodes. */
foreach (val in root_cache) {
if (val.priority < tmp_min_priority) {
_min = val;
_min_index = i;
tmp_min_priority = val.priority;
}
tmp_root_list[i++] = val;
}
/* Update global variables. */
_min_priority = tmp_min_priority;
_count--;
return z.item;
}
function Fibonacci_Heap::Peek() {
if (_count == 0) return null;
return _min.item;
}
function Fibonacci_Heap::Count() {
return _count;
}
function Fibonacci_Heap::Exists(item) {
return ExistsIn(_root_list, item);
}
/**
* Auxilary function to search through the whole heap.
* @param list The list of nodes to look through.
* @param item The item to search for.
* @return True if the item is found, false otherwise.
*/
function Fibonacci_Heap::ExistsIn(list, item) {
foreach (val in list) {
if (val.item == item) {
return true;
}
foreach (c in val.child) {
if (ExistsIn(c, item)) {
return true;
}
}
}
/* No luck, item doesn't exists in the tree rooted under list. */
return false;
}
/**
* Basic class the fibonacci heap is composed of.
*/
class Fibonacci_Heap.Node {
degree = null;
child = null;
item = null;
priority = null;
constructor() {
child = [];
degree = 0;
}
};
|