aboutsummaryrefslogtreecommitdiffstats
path: root/spec/util_indexedbheap_spec.lua
diff options
context:
space:
mode:
authorMatthew Wild <mwild1@gmail.com>2020-09-30 07:25:32 +0100
committerMatthew Wild <mwild1@gmail.com>2020-09-30 07:25:32 +0100
commitb80ff2ae4f86aa26e055890a8284b55170ef2056 (patch)
tree3a37db7b805b1555d08cc61c7938cf512ff35ce0 /spec/util_indexedbheap_spec.lua
parentbff06592c76b5c441f05280e6d3ece1381ad429a (diff)
parent80beeeb187e84bda89cfe7390704f6a53406cad6 (diff)
downloadprosody-b80ff2ae4f86aa26e055890a8284b55170ef2056.tar.gz
prosody-b80ff2ae4f86aa26e055890a8284b55170ef2056.zip
Merge 0.11->trunk
Diffstat (limited to 'spec/util_indexedbheap_spec.lua')
-rw-r--r--spec/util_indexedbheap_spec.lua20
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);