prosody
d334f2bebe55
spec/util_indexedbheap_spec.lua

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

Software / code / prosody

Comparison

spec/util_indexedbheap_spec.lua @ 11116:d334f2bebe55

Merge 0.11->trunk
author Matthew Wild <mwild1@gmail.com>
date Wed, 30 Sep 2020 07:25:32 +0100
parent 10998:f3fc0f799dc4
parent 11115:7d4c292f178e
comparison
equal deleted inserted replaced
11114:6a608ecb3471 11116:d334f2bebe55
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);