Software /
code /
prosody
Annotate
util/indexedbheap.lua @ 8742:71939a65961e
Merge 0.10->trunk
author | Kim Alvefur <zash@zash.se> |
---|---|
date | Tue, 10 Apr 2018 20:23:54 +0200 (2018-04-10) |
parent | 8382:e5d00bf4a4d5 |
child | 11115:7d4c292f178e |
rev | line source |
---|---|
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); |
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
|
26 if tmp < self[parent] 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
|
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); |
8382
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); |
8382
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; |