author | Kim Alvefur <zash@zash.se> |
Wed, 19 Oct 2022 16:25:05 +0200 | |
changeset 12785 | 22066b02887f |
parent 11119 | 7d4c292f178e |
permissions | -rw-r--r-- |
5876
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
1 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
2 |
local setmetatable = setmetatable; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
3 |
local math_floor = math.floor; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
4 |
local t_remove = table.remove; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
5 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
6 |
local function _heap_insert(self, item, sync, item2, index) |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
7 |
local pos = #self + 1; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
8 |
while true do |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
9 |
local half_pos = math_floor(pos / 2); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
10 |
if half_pos == 0 or item > self[half_pos] then break; end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
11 |
self[pos] = self[half_pos]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
12 |
sync[pos] = sync[half_pos]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
13 |
index[sync[pos]] = pos; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
14 |
pos = half_pos; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
15 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
16 |
self[pos] = item; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
17 |
sync[pos] = item2; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
18 |
index[item2] = pos; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
19 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
20 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
21 |
local function _percolate_up(self, k, sync, index) |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
22 |
local tmp = self[k]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
23 |
local tmp_sync = sync[k]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
24 |
while k ~= 1 do |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
25 |
local parent = math_floor(k/2); |
11119
7d4c292f178e
util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents:
8385
diff
changeset
|
26 |
if tmp >= self[parent] then break; end |
5876
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
27 |
self[k] = self[parent]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
28 |
sync[k] = sync[parent]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
29 |
index[sync[k]] = k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
30 |
k = parent; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
31 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
32 |
self[k] = tmp; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
33 |
sync[k] = tmp_sync; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
34 |
index[tmp_sync] = k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
35 |
return k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
36 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
37 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
38 |
local function _percolate_down(self, k, sync, index) |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
39 |
local tmp = self[k]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
40 |
local tmp_sync = sync[k]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
41 |
local size = #self; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
42 |
local child = 2*k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
43 |
while 2*k <= size do |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
44 |
if child ~= size and self[child] > self[child + 1] then |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
45 |
child = child + 1; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
46 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
47 |
if tmp > self[child] then |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
48 |
self[k] = self[child]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
49 |
sync[k] = sync[child]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
50 |
index[sync[k]] = k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
51 |
else |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
52 |
break; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
53 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
54 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
55 |
k = child; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
56 |
child = 2*k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
57 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
58 |
self[k] = tmp; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
59 |
sync[k] = tmp_sync; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
60 |
index[tmp_sync] = k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
61 |
return k; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
62 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
63 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
64 |
local function _heap_pop(self, sync, index) |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
65 |
local size = #self; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
66 |
if size == 0 then return nil; end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
67 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
68 |
local result = self[1]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
69 |
local result_sync = sync[1]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
70 |
index[result_sync] = nil; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
71 |
if size == 1 then |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
72 |
self[1] = nil; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
73 |
sync[1] = nil; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
74 |
return result, result_sync; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
75 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
76 |
self[1] = t_remove(self); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
77 |
sync[1] = t_remove(sync); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
78 |
index[sync[1]] = 1; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
79 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
80 |
_percolate_down(self, 1, sync, index); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
81 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
82 |
return result, result_sync; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
83 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
84 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
85 |
local indexed_heap = {}; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
86 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
87 |
function indexed_heap:insert(item, priority, id) |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
88 |
if id == nil then |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
89 |
id = self.current_id; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
90 |
self.current_id = id + 1; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
91 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
92 |
self.items[id] = item; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
93 |
_heap_insert(self.priorities, priority, self.ids, id, self.index); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
94 |
return id; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
95 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
96 |
function indexed_heap:pop() |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
97 |
local priority, id = _heap_pop(self.priorities, self.ids, self.index); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
98 |
if id then |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
99 |
local item = self.items[id]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
100 |
self.items[id] = nil; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
101 |
return priority, item, id; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
102 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
103 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
104 |
function indexed_heap:peek() |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
105 |
return self.priorities[1]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
106 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
107 |
function indexed_heap:reprioritize(id, priority) |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
108 |
local k = self.index[id]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
109 |
if k == nil then return; end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
110 |
self.priorities[k] = priority; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
111 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
112 |
k = _percolate_up(self.priorities, k, self.ids, self.index); |
8385
e5d00bf4a4d5
util: Various minor changes to please [luacheck]
Kim Alvefur <zash@zash.se>
parents:
6151
diff
changeset
|
113 |
_percolate_down(self.priorities, k, self.ids, self.index); |
5876
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
114 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
115 |
function indexed_heap:remove_index(k) |
6151
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
116 |
local result = self.priorities[k]; |
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
117 |
if result == nil then return; end |
5876
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
118 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
119 |
local result_sync = self.ids[k]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
120 |
local item = self.items[result_sync]; |
6151
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
121 |
local size = #self.priorities; |
5876
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
122 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
123 |
self.priorities[k] = self.priorities[size]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
124 |
self.ids[k] = self.ids[size]; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
125 |
self.index[self.ids[k]] = k; |
6151
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
126 |
|
5876
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
127 |
t_remove(self.priorities); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
128 |
t_remove(self.ids); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
129 |
|
6151
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
130 |
self.index[result_sync] = nil; |
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
131 |
self.items[result_sync] = nil; |
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
132 |
|
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
133 |
if size > k then |
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
134 |
k = _percolate_up(self.priorities, k, self.ids, self.index); |
8385
e5d00bf4a4d5
util: Various minor changes to please [luacheck]
Kim Alvefur <zash@zash.se>
parents:
6151
diff
changeset
|
135 |
_percolate_down(self.priorities, k, self.ids, self.index); |
6151
a34a14054532
util.indexedbheap: Fix a possible traceback when removing the last item.
Waqas Hussain <waqas20@gmail.com>
parents:
5876
diff
changeset
|
136 |
end |
5876
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
137 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
138 |
return result, item, result_sync; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
139 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
140 |
function indexed_heap:remove(id) |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
141 |
return self:remove_index(self.index[id]); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
142 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
143 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
144 |
local mt = { __index = indexed_heap }; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
145 |
|
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
146 |
local _M = { |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
147 |
create = function() |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
148 |
return setmetatable({ |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
149 |
ids = {}; -- heap of ids, sync'd with priorities |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
150 |
items = {}; -- map id->items |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
151 |
priorities = {}; -- heap of priorities |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
152 |
index = {}; -- map of id->index of id in ids |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
153 |
current_id = 1.5 |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
154 |
}, mt); |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
155 |
end |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
156 |
}; |
f62ad84811df
util.indexedbheap: A priority queue implementation with a reverse index with no per-entry memory allocation.
Waqas Hussain <waqas20@gmail.com>
parents:
diff
changeset
|
157 |
return _M; |