1 local ibh = require"util.indexedbheap"; |
1 local ibh = require"util.indexedbheap"; |
|
2 |
|
3 local function verify_heap_property(priorities) |
|
4 for k in ipairs(priorities) do |
|
5 local parent = priorities[k]; |
|
6 local childA = priorities[2*k]; |
|
7 local childB = priorities[2*k+1]; |
|
8 -- print("-", parent, childA, childB) |
|
9 assert(childA == nil or childA > parent, "heap property violated"); |
|
10 assert(childB == nil or childB > parent, "heap property violated"); |
|
11 end |
|
12 end |
|
13 |
2 local h |
14 local h |
3 setup(function () |
15 setup(function () |
4 h = ibh.create(); |
16 h = ibh.create(); |
5 end) |
17 end) |
6 describe("util.indexedbheap", function () |
18 describe("util.indexedbheap", function () |
7 pending("item can be moved from end to top", function () |
19 it("item can be moved from end to top", function () |
|
20 verify_heap_property(h); |
8 h:insert("a", 1); |
21 h:insert("a", 1); |
|
22 verify_heap_property(h); |
9 h:insert("b", 2); |
23 h:insert("b", 2); |
|
24 verify_heap_property(h); |
10 h:insert("c", 3); |
25 h:insert("c", 3); |
|
26 verify_heap_property(h); |
11 local id = h:insert("*", 10); |
27 local id = h:insert("*", 10); |
|
28 verify_heap_property(h); |
12 h:reprioritize(id, 0); |
29 h:reprioritize(id, 0); |
|
30 verify_heap_property(h); |
13 assert.same({ 0, "*", id }, { h:pop() }); |
31 assert.same({ 0, "*", id }, { h:pop() }); |
14 end) |
32 end) |
15 end); |
33 end); |