# HG changeset patch
# User Matthew Wild <mwild1@gmail.com>
# Date 1601455590 -3600
# Node ID 590ac42d81c534b306140e48c4a046619eb656e6
# Parent  7d4c292f178e8e6fb1981c5851e1760d715de0b6# Parent  10301c214f4e2406ac42038750f81dc56f06f2ef
Merge

diff -r 10301c214f4e -r 590ac42d81c5 spec/util_indexedbheap_spec.lua
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/spec/util_indexedbheap_spec.lua	Wed Sep 30 09:46:30 2020 +0100
@@ -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 -r 10301c214f4e -r 590ac42d81c5 util/indexedbheap.lua
--- a/util/indexedbheap.lua	Tue Sep 29 15:18:32 2020 +0100
+++ b/util/indexedbheap.lua	Wed Sep 30 09:46:30 2020 +0100
@@ -23,7 +23,7 @@
 	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;