From 80beeeb187e84bda89cfe7390704f6a53406cad6 Mon Sep 17 00:00:00 2001 From: Waqas Hussain Date: Tue, 29 Sep 2020 21:27:16 -0500 Subject: util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value) --- spec/util_indexedbheap_spec.lua | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 spec/util_indexedbheap_spec.lua (limited to 'spec/util_indexedbheap_spec.lua') diff --git a/spec/util_indexedbheap_spec.lua b/spec/util_indexedbheap_spec.lua new file mode 100644 index 00000000..b10ee385 --- /dev/null +++ b/spec/util_indexedbheap_spec.lua @@ -0,0 +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 () + 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); -- cgit v1.2.3