diff options
| -rw-r--r-- | spec/util_indexedbheap_spec.lua | 20 | ||||
| -rw-r--r-- | util/indexedbheap.lua | 2 |
2 files changed, 20 insertions, 2 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); diff --git a/util/indexedbheap.lua b/util/indexedbheap.lua index 7f193d54..45830673 100644 --- a/util/indexedbheap.lua +++ b/util/indexedbheap.lua @@ -23,7 +23,7 @@ local function _percolate_up(self, k, sync, index) local tmp_sync = sync[k]; while k ~= 1 do local parent = math_floor(k/2); - if tmp < self[parent] then break; end + if tmp >= self[parent] then break; end self[k] = self[parent]; sync[k] = sync[parent]; index[sync[k]] = k; |