prosody
6dde2c9fa272
util/indexedbheap.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Annotate

util/indexedbheap.lua @ 11169:6dde2c9fa272 0.11

util.strbitop: Create buffer in the correct size (optimization) This avoids dynamically growing the buffer as Lua does when luaL_addchar is used, thus saving on realloc calls.
author Kim Alvefur <zash@zash.se>
date Thu, 15 Oct 2020 16:43:30 +0200
parent 11115:7d4c292f178e
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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);
11115
7d4c292f178e util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
Waqas Hussain <waqas20@gmail.com>
parents: 8382
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);
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;