diff options
| -rw-r--r-- | spec/util_indexedbheap_spec.lua | 33 | ||||
| -rw-r--r-- | util/indexedbheap.lua | 2 |
2 files changed, 34 insertions, 1 deletions
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); 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; |