# A min-heap implemented over an array
#
# The order is given by the `comparator`.
#
# ~~~
# var a = [3,4,1,2]
# var h = new MinHeap[Int].default
# h.add_all(a)
# assert h.peek == 1
# var b = h.take_all
# assert b == [1, 2, 3, 4]
# ~~~
class MinHeap[E: Object]
	super Queue[E]

	private var items = new Array[E]

	# The comparator used to order the Heap
	var comparator: Comparator

	# Use the `default_comparator` on Comparable elements
	#
	# Require self isa MinHeap[Comparable]
	init default
	do
		assert self isa MinHeap[Comparable]
		init(default_comparator)
	end

	redef fun is_empty do return items.is_empty
	redef fun length do return items.length
	redef fun iterator do return items.iterator
	redef fun clear do items.clear

	redef fun peek do return items.first
	redef fun add(e)
	do
		#assert assert_best else print "try to add {e}"
		#var ol = length
		var ei = items.length + 1
		while ei > 1 do
			var pi = ei/2
			var p = items[pi-1]
			if comparator.compare(p, e) <= 0 then break

			# bubble-up
			items[ei-1] = p

			# next
			ei = pi
		end
		items[ei-1] = e
		#assert length == ol + 1
		#assert assert_best else print "added {e}"
	end

	redef fun take do
		#assert assert_best else print "tri to take"
		#var ol = length
		if length < 2 then return items.pop

		var res = items.first
		var ei = 1
		var e = items.pop

		var last = items.length
		loop
			# Check first child
			var ci = ei*2
			if ci > last then break # no children
			var c = items[ci-1]
			var upc = comparator.compare(e, c) > 0

			# Check second child
			var c2i = ci + 1
			if c2i <= last then do
				var c2 = items[c2i-1]
				# possibility to bubble-down to c2, or not?
				if comparator.compare(e, c2) <= 0 then break label
				# c2 is a better path, or not?
				if upc and comparator.compare(c2, c) > 0 then break label
				# goes to c2 path
				upc = true
				c = c2
				ci = c2i
			end label

			# bubble-down?
			if not upc then break

			items[ei-1] = c
			ei = ci
		end
		items[ei-1] = e
		#assert length == ol - 1 else print "is {length}, expected {ol - 1}"
		#assert assert_best else print "dequed {res}"
		return res
	end

	# Used internally do debug the Heap.
	# Not removed because this can still be useful.
	private fun assert_best: Bool
	do
		if is_empty then return true
		var b = peek
		for i in self do if comparator.compare(b, i) > 0 then
			#print "  peek is {b} but better found {i}"
			for j in self do
				#print "   {j}"
			end
			return false
		end
		return true
	end
end