diff options
Diffstat (limited to 'spec')
| -rw-r--r-- | spec/util_indexedbheap_spec.lua | 20 |
1 files changed, 19 insertions, 1 deletions
diff --git a/spec/util_indexedbheap_spec.lua b/spec/util_indexedbheap_spec.lua index a76f94cb..b10ee385 100644 --- a/spec/util_indexedbheap_spec.lua +++ b/spec/util_indexedbheap_spec.lua @@ -1,15 +1,33 @@ local ibh = require"util.indexedbheap"; + +local function verify_heap_property(priorities) + for k in ipairs(priorities) do + local parent = priorities[k]; + local childA = priorities[2*k]; + local childB = priorities[2*k+1]; + -- print("-", parent, childA, childB) + assert(childA == nil or childA > parent, "heap property violated"); + assert(childB == nil or childB > parent, "heap property violated"); + end +end + local h setup(function () h = ibh.create(); end) describe("util.indexedbheap", function () - pending("item can be moved from end to top", function () + it("item can be moved from end to top", function () + verify_heap_property(h); h:insert("a", 1); + verify_heap_property(h); h:insert("b", 2); + verify_heap_property(h); h:insert("c", 3); + verify_heap_property(h); local id = h:insert("*", 10); + verify_heap_property(h); h:reprioritize(id, 0); + verify_heap_property(h); assert.same({ 0, "*", id }, { h:pop() }); end) end); |