local o=require("\046\047\105\110\105\116")local f=function(f)local D=f.describe local H=f.test local P=f.expect D("\080\117\115\104",function()H("\115\104\111\117\108\100 \105\110\115\101\114\116 \101\108\101\109\101\110\116\115 \105\110 \099\111\114\114\101\099\116 \111\114\100\101\114 \102\111\114 \109\105\110\072\101\097\112",function()local f=o.min()f:Push(5)f:Push(2)f:Push(8);(P(f:Peek())).is(2)end)H("\115\104\111\117\108\100 \105\110\115\101\114\116 \101\108\101\109\101\110\116\115 \105\110 \099\111\114\114\101\099\116 \111\114\100\101\114 \102\111\114 \109\097\120\072\101\097\112",function()local f=o.max()f:Push(5)f:Push(2)f:Push(8);(P(f:Peek())).is(8)end)end)D("\080\111\112",function()H("\115\104\111\117\108\100 \114\101\109\111\118\101 \097\110\100 \114\101\116\117\114\110 \101\108\101\109\101\110\116\115 \105\110 \099\111\114\114\101\099\116 \111\114\100\101\114 \102\111\114 \109\105\110\072\101\097\112",function()local f=o.min()f:Push(3)f:Push(1)f:Push(4);(P(f:Pop())).is(1);(P(f:Pop())).is(3);(P(f:Pop())).is(4)end)H("\115\104\111\117\108\100 \114\101\109\111\118\101 \097\110\100 \114\101\116\117\114\110 \101\108\101\109\101\110\116\115 \105\110 \099\111\114\114\101\099\116 \111\114\100\101\114 \102\111\114 \109\097\120\072\101\097\112",function()local f=o.max()f:Push(3)f:Push(1)f:Push(4);(P(f:Pop())).is(4);(P(f:Pop())).is(3);(P(f:Pop())).is(1)end)end)D("\080\101\101\107",function()H("\115\104\111\117\108\100 \114\101\116\117\114\110 \116\111\112 \101\108\101\109\101\110\116 \119\105\116\104\111\117\116 \114\101\109\111\118\105\110\103 \105\116",function()local f=o.min()f:Push(7)f:Push(2);(P(f:Peek())).is(2);(P(#f)).is(2)end)end)D("\082\101\109\111\118\101\070\105\114\115\116\079\099\099\117\114\114\101\110\099\101",function()H("\115\104\111\117\108\100 \114\101\109\111\118\101 \116\104\101 \102\105\114\115\116 \111\099\099\117\114\114\101\110\099\101 \111\102 \097 \118\097\108\117\101",function()local f=o.min()f:Push(5)f:Push(3)f:Push(8)f:Push(3);(P(f:RemoveFirstOccurrence(3))).is(true);(P(f:RemoveFirstOccurrence(3))).is(true);(P(f:RemoveFirstOccurrence(3))).is(false)end)H("\115\104\111\117\108\100 \109\097\105\110\116\097\105\110 \104\101\097\112 \111\114\100\101\114 \097\102\116\101\114 \114\101\109\111\118\097\108\115",function()local f=o.min()f:Push(5)f:Push(3)f:Push(8)f:Push(3)f:Push(10)f:RemoveFirstOccurrence(3);(P(f:Peek())).is(3)f:RemoveFirstOccurrence(3);(P(f:Peek())).is(5)end)end)D("\082\101\109\111\118\101\065\108\108\079\099\099\117\114\114\101\110\099\101\115",function()H("\115\104\111\117\108\100 \114\101\109\111\118\101 \097\108\108 \111\099\099\117\114\114\101\110\099\101\115 \111\102 \097 \118\097\108\117\101",function()local f=o.min()f:Push(5)f:Push(3)f:Push(8)f:Push(3)f:Push(3)f:Push(10);(P(f:RemoveAllOccurrences(3))).is(3);(P(#f)).is(3);(P(f:RemoveAllOccurrences(3))).is(0);(P(#f)).is(3)end)end)D("\095\095\108\101\110",function()H("\115\104\111\117\108\100 \114\101\116\117\114\110 \099\111\114\114\101\099\116 \110\117\109\098\101\114 \111\102 \101\108\101\109\101\110\116\115",function()local f=o.min()f:Push(5)f:Push(10);(P(#f)).is(2)f:Pop();(P(#f)).is(1)f:Pop();(P(#f)).is(0)f:Pop();(P(#f)).is(0)f:Push(20);(P(#f)).is(1)end)end)D("\095\095\116\111\115\116\114\105\110\103",function()H("\115\104\111\117\108\100 \114\101\116\117\114\110 \097 \115\116\114\105\110\103 \114\101\112\114\101\115\101\110\116\097\116\105\111\110 \111\102 \116\104\101 \104\101\097\112",function()local f=o.min()for o=1,10,1 do f:Push(math.random(1,10))end local D=tostring(f);(P(D:find("\072\101\097\112\058"))).never_is(nil)end)end)D("\076\097\114\103\101 \068\097\116\097\115\101\116 \084\101\115\116",function()local f=o.min()local D=100000 local P=99900 H("\073\110\115\101\114\116\105\111\110\058 "..(D.." \073\116\101\109\115"),function()for o=1,D,1 do f:Push(math.random(1,100))end end)H("\082\101\109\111\118\097\108 \111\102 \111\110\101 \105\116\101\109",function()f:Pop()end)H("\082\101\109\111\118\097\108\058 "..(P.." \073\116\101\109\115"),function()for o=1,P,1 do f:Pop()end end)end)end return f
local Heap = require("./init")

local test_suite = function(tiniest)
	local describe = tiniest.describe
	local test = tiniest.test
	local expect = tiniest.expect

	describe("Push", function()
		test("should insert elements in correct order for minHeap", function()
			local minHeap = Heap.min()
			minHeap:Push(5)
			minHeap:Push(2)
			minHeap:Push(8)
			expect(minHeap:Peek()).is(2)
		end)

		test("should insert elements in correct order for maxHeap", function()
			local maxHeap = Heap.max()
			maxHeap:Push(5)
			maxHeap:Push(2)
			maxHeap:Push(8)
			expect(maxHeap:Peek()).is(8)
		end)
	end)

	describe("Pop", function()
		test("should remove and return elements in correct order for minHeap", function()
			local minHeap = Heap.min()
			minHeap:Push(3)
			minHeap:Push(1)
			minHeap:Push(4)
			expect(minHeap:Pop()).is(1)
			expect(minHeap:Pop()).is(3)
			expect(minHeap:Pop()).is(4)
		end)

		test("should remove and return elements in correct order for maxHeap", function()
			local maxHeap = Heap.max()
			maxHeap:Push(3)
			maxHeap:Push(1)
			maxHeap:Push(4)
			expect(maxHeap:Pop()).is(4)
			expect(maxHeap:Pop()).is(3)
			expect(maxHeap:Pop()).is(1)
		end)
	end)

	describe("Peek", function()
		test("should return top element without removing it", function()
			local minHeap = Heap.min()
			minHeap:Push(7)
			minHeap:Push(2)
			expect(minHeap:Peek()).is(2)
			expect(#minHeap).is(2)
		end)
	end)

	describe("RemoveFirstOccurrence", function()
		test("should remove the first occurrence of a value", function()
			local minHeap = Heap.min()
			minHeap:Push(5)
			minHeap:Push(3)
			minHeap:Push(8)
			minHeap:Push(3)
			expect(minHeap:RemoveFirstOccurrence(3)).is(true)
			expect(minHeap:RemoveFirstOccurrence(3)).is(true)
			expect(minHeap:RemoveFirstOccurrence(3)).is(false)
		end)

		test("should maintain heap order after removals", function()
			local minHeap = Heap.min()
			minHeap:Push(5)
			minHeap:Push(3)
			minHeap:Push(8)
			minHeap:Push(3)
			minHeap:Push(10)
			minHeap:RemoveFirstOccurrence(3)
			expect(minHeap:Peek()).is(3)
			minHeap:RemoveFirstOccurrence(3)
			expect(minHeap:Peek()).is(5)
		end)
	end)

	describe("RemoveAllOccurrences", function()
		test("should remove all occurrences of a value", function()
			local minHeap = Heap.min()
			minHeap:Push(5)
			minHeap:Push(3)
			minHeap:Push(8)
			minHeap:Push(3)
			minHeap:Push(3)
			minHeap:Push(10)
			expect(minHeap:RemoveAllOccurrences(3)).is(3)
			expect(#minHeap).is(3)
			expect(minHeap:RemoveAllOccurrences(3)).is(0)
			expect(#minHeap).is(3)
		end)
	end)

	describe("__len", function()
		test("should return correct number of elements", function()
			local minHeap = Heap.min()
			minHeap:Push(5)
			minHeap:Push(10)
			expect(#minHeap).is(2)
			minHeap:Pop()
			expect(#minHeap).is(1)
			minHeap:Pop()
			expect(#minHeap).is(0)
			minHeap:Pop()
			expect(#minHeap).is(0)
			minHeap:Push(20)
			expect(#minHeap).is(1)
		end)
	end)

	describe("__tostring", function()
		test("should return a string representation of the heap", function()
			local minHeap = Heap.min()
			for i = 1, 10 do
				minHeap:Push(math.random(1, 10))
			end
			
			local heapStr = tostring(minHeap)
			expect(heapStr:find("Heap:")).never_is(nil)
		end)
	end)

	describe("Large Dataset Test", function()
		local minHeap = Heap.min()
		local elementsToInsert = 100000
		local elementsToRemove = 99900

		test("Insertion: "..elementsToInsert.." Items", function()
			for i = 1, elementsToInsert do
				minHeap:Push(math.random(1, 100))
			end
		end)

		test("Removal of one item", function()
			minHeap:Pop()
		end)

		test("Removal: "..elementsToRemove.." Items", function()
			for i = 1, elementsToRemove do
				minHeap:Pop()
			end
		end)
	end)
end

return test_suite