# This abstract class generalizes ways to sort an array
interface Comparator
	# What to compare to
	type COMPARED: nullable Object

	# Compare `a` and `b`.
	#
	# Returns:
	#
	# * -1 if a < b
	# * 0  if a = b
	# * 1  if a > b
	fun compare(a: COMPARED, b: COMPARED): Int is abstract

	# Is `seq` sorted?
	#
	#     assert default_comparator.is_sorted([1,2,2,3])   == true
	#     assert default_comparator.is_sorted([1,10,2,3])  == false
	#     assert alpha_comparator.is_sorted([1,10,2,3])    == true
	fun is_sorted(seq: SequenceRead[COMPARED]): Bool
	do
		if seq.length <= 1 then return true
		var prev = seq.first
		for e in seq do
			if compare(prev, e) > 0 then return false
			prev = e
		end
		return true
	end

	# Returns the minimum between `a` and `b`.
	#
	#     assert default_comparator.min(2,10) == 2
	#     assert alpha_comparator.min(2,10)   == 10
	#
	# If both are equivalent, then returns `a`.
	#
	#     var m = alpha_comparator.min(1, "1")
	#     assert m == 1
	#     assert m != "1"
	fun min(a,b: COMPARED): COMPARED
	do
		if compare(a,b) > 0 then return b else return a
	end

	# Returns the maximum between `a` and `b`.
	#
	#     assert default_comparator.max(2,10) == 10
	#     assert alpha_comparator.max(2,10)   == 2
	#
	# If both are equivalent, then returns `a`.
	#
	#     var m = alpha_comparator.max(1, "1")
	#     assert m == 1
	#     assert m != "1"
	fun max(a,b: COMPARED): COMPARED
	do
		if compare(a,b) < 0 then return b else return a
	end

	# Sort `array` using the `compare` function.
	#
	#     var a = [10, 2, 3, 1, 4]
	#     default_comparator.sort(a)
	#     assert a == [1, 2, 3, 4, 10]
	#     alpha_comparator.sort(a)
	#     assert a == [1, 10, 2, 3, 4]
	fun sort(array: Array[COMPARED]) do sub_sort(array, 0, array.length-1)

	# Sort `array` between `from` and `to` indices
	private fun sub_sort(array: Array[COMPARED], from: Int, to: Int)
	do
		if from >= to then
			return
		else if from + 7 < to then
			quick_sort(array, from, to)
		else
			bubble_sort(array, from, to)
		end
	end

	# Quick-sort `array` between `from` and `to` indices
	# Worst case: O(n^2), Average case: O(n lg n)
	#
	#     var a = [5, 2, 3, 1, 4]
	#     default_comparator.quick_sort(a, 0, a.length - 1)
	#     assert a == [1, 2, 3, 4, 5]
	#     var a2 = new Array[Int]
	#     default_comparator.quick_sort(a2, 0, a2.length - 1)
	#     assert a2 == new Array[Int]
	#     var a3 = [1]
	#     default_comparator.quick_sort(a3, 0, a3.length - 1)
	#     assert a3 == [1]
	fun quick_sort(array: Array[COMPARED], from: Int, to: Int) do
		if from >= to then return
		var pivot = array[from]
		var i = from
		var j = to
		while j > i do
			while i <= to and compare(array[i], pivot) <= 0 do i += 1
			while j > i and compare(array[j], pivot) >= 0 do j -= 1
			if j > i then
				var t = array[i]
				array[i] = array[j]
				array[j] = t
			end
		end
		array[from] = array[i-1]
		array[i-1] = pivot
		sub_sort(array, from, i-2)
		sub_sort(array, i, to)
	end

	# Bubble-sort `array` between `from` and `to` indices
	# Worst case: O(n^2), average case: O(n^2)
	#
	#     var a = [5, 2, 3, 1, 4]
	#     default_comparator.bubble_sort(a, 0, a.length - 1)
	#     assert a == [1, 2, 3, 4, 5]
	fun bubble_sort(array: Array[COMPARED], from: Int, to: Int)
	do
		var i = from
		while i < to do
			var min = i
			var min_v = array[i]
			var j = i
			while j <= to do
				if compare(min_v, array[j]) > 0 then
					min = j
					min_v = array[j]
				end
				j += 1
			end
			if min != i then
				array[min] = array[i]
				array[i] = min_v
			end
			i += 1
		end
	end

	# Insertion-sort `array` between `from` and `to` indices
	# Worst case: O(n^2), average case: O(n^2)
	#
	#     var a = [5, 2, 3, 1, 4]
	#     default_comparator.insertion_sort(a, 0, a.length - 1)
	#     assert a == [1, 2, 3, 4, 5]
	fun insertion_sort(array: Array[COMPARED], from: Int, to: Int) do
		for i in [from..to] do
			var j = i
			while j > 0 and compare(array[j], array[j - 1]) < 0 do
				array.swap_at(j, j - 1)
				j -= 1
			end
		end
	end

	# Merge-sort `array` between `from` and `to` indices
	# Worst case: O(n lg n), average: O(n lg n)
	#
	#     var a = [5, 2, 3, 1, 4]
	#     default_comparator.merge_sort(a, 0, a.length - 1)
	#     assert a == [1, 2, 3, 4, 5]
	fun merge_sort(array: Array[COMPARED], from, to: Int) do
		if from >= to then return
		var mid = (to + from) / 2
		merge_sort(array, from, mid)
		merge_sort(array, mid + 1, to)
		merge(array, from, mid, to)
	end

	private fun merge(array: Array[COMPARED], from, mid, to: Int) do
		var l = new Array[COMPARED]
		for i in [from..mid] do l.add array[i]
		var r = new Array[COMPARED]
		for i in [mid + 1..to] do r.add array[i]
		var i = 0
		var j = 0
		for k in [from..to] do
			if i >= l.length then
				array[k] = r[j]
				j += 1
			else if j >= r.length then
				array[k] = l[i]
				i += 1
			else if compare(l[i], r[j]) <= 0 then
				array[k] = l[i]
				i += 1
			else
				array[k] = r[j]
				j += 1
			end
		end
	end

	# Heap-sort `array` between `from` and `to` indices
	# Worst case: O(n lg n), average: O(n lg n)
	#
	#     var a = [5, 2, 3, 1, 4]
	#     default_comparator.heap_sort(a, 0, a.length - 1)
	#     assert a == [1, 2, 3, 4, 5]
	fun heap_sort(array: Array[COMPARED], from, to: Int) do
		var size = build_heap(array)
		for j in [from..to[ do
			array.swap_at(0, size)
			size -= 1
			heapify(array, 0, size)
		end
	end

	private fun build_heap(array: Array[COMPARED]): Int do
		var size = array.length - 1
		var i = size / 2
		while i >= 0 do
			heapify(array, i, size)
			i -= 1
		end
		return size
	end

	private fun heapify(array: Array[COMPARED], from, to: Int) do
		var l = from * 2
		var r = l + 1
		var largest: Int
		if l < to and compare(array[l], array[from]) > 0 then
			largest = l
		else
			largest = from
		end
		if r < to and compare(array[r], array[largest]) > 0 then
			largest = r
		end
		if largest != from then
			array.swap_at(from, largest)
			heapify(array, largest, to)
		end
	end

end