X-Git-Url: http://nitlanguage.org

diff --git a/lib/standard/collection/sorter.nit b/lib/standard/collection/sorter.nit
index 0b4cd39..ca16460 100644
--- a/lib/standard/collection/sorter.nit
+++ b/lib/standard/collection/sorter.nit
@@ -4,34 +4,90 @@
 #
 # This file is free software, which comes along with NIT.  This software is
 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
-# without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A 
+# without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
 # is kept unaltered, and a notification of the changes is added.
 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
 # another product.
 
-# This module contains classes used to sorts arrays.
-# In order to provide your own sort class you should define a subclass of AbstractSorter with
-# a custom `compare' function.
-package sorter
+# This module contains classes used to compare things and sorts arrays.
+#
+# In order to provide your own sort class you should define a subclass of `Comparator` with
+# a custom `Comparator::compare` function and a specific `COMPARED` virtual type.
+module sorter
 
+import range
 import array
 
 # This abstract class generalizes ways to sort an array
-# TODO: rename *Sorter to *Comparator
-interface AbstractSorter[E]
-	# Compare `a' and `b'.
+interface Comparator
+	# What to compare to
+	type COMPARED: nullable Object
+
+	# Compare `a` and `b`.
 	# Returns:
-	# 	-1 if a < b
+	#	-1 if a < b
 	#	0  if a = b
 	#	1  if a > b
-	fun compare(a: E, b: E): Int is abstract
+	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.
-	fun sort(array: Array[E]) do sub_sort(array, 0, array.length-1)
+	# 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[E], from: Int, to: Int)
+	# Sort `array` between `from` and `to` indices
+	private fun sub_sort(array: Array[COMPARED], from: Int, to: Int)
 	do
 		if from >= to then
 			return
@@ -42,9 +98,13 @@ interface AbstractSorter[E]
 		end
 	end
 
-	# Quick-sort `array' between `from' and `to' indices
-	private fun quick_sort(array: Array[E], from: Int, to: Int)
-	do
+	# 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]
+	fun quick_sort(array: Array[COMPARED], from: Int, to: Int) do
 		var pivot = array[from]
 		var i = from
 		var j = to
@@ -62,9 +122,14 @@ interface AbstractSorter[E]
 		sub_sort(array, from, i-2)
 		sub_sort(array, i, to)
 	end
-	
-	# Bubble-sort `array' between `from' and `to' indices
-	private fun bubble_sort(array: Array[E], from: Int, to: Int)
+
+	# 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
@@ -85,15 +150,209 @@ interface AbstractSorter[E]
 			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
+
+redef class MapRead[K,V]
+	# Return an array of all values sorted with their keys using `comparator`.
+	#
+	# ~~~
+	# var map = new HashMap[Int, String]
+	# map[10] = "ten"
+	# map[2]  = "two"
+	# map[1]  = "one"
+	# assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
+	# assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
+	# ~~~
+	fun values_sorted_by_key(comparator: Comparator): Array[V]
+	do
+		var keys = self.keys.to_a
+		comparator.sort(keys)
+		return [for k in keys do self[k]]
+	end
+
+	# Return an array of all keys sorted with their values using `comparator`.
+	#
+	# ~~~
+	# var map = new HashMap[String, Int]
+	# map["ten"] = 10
+	# map["two"] = 2
+	# map["one"] = 1
+	# assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
+	# assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
+	# ~~~
+	#
+	# See: `to_map_comparator` to get the comparator used internally.
+	fun keys_sorted_by_values(comparator: Comparator): Array[K]
+	do
+		var keys = self.keys.to_a
+		var map_cmp = to_map_comparator(comparator)
+		map_cmp.sort(keys)
+		return keys
+	end
+
+	# A comparator that compares things with their values in self.
+	#
+	# See `MapComparator` for details.
+	fun to_map_comparator(comparator: Comparator): MapComparator[K, V] do return new MapComparator[K,V](self, comparator)
 end
 
-# This class uses the operator <=> to sort arrays.
-# You can also use the `sort' method of the `Array' class.
-class ComparableSorter[E: Comparable]
-	super AbstractSorter[E]
+# A comparator that compares things with their values in a map.
+#
+# ~~~
+# var map = new HashMap[String, Int]
+# map["ten"] = 10
+# map["two"] = 2
+# map["one"] = 1
+#
+# var map_cmp = map.to_map_comparator(default_comparator)
+# var a = ["ten", "one", "two"]
+# map_cmp.sort(a)
+# assert a == ["one", "two", "ten"]
+# map_cmp = map.to_map_comparator(alpha_comparator)
+# map_cmp.sort(a)
+# assert a == ["one", "ten", "two"]
+# ~~~
+class MapComparator[K,V]
+	super Comparator
+
+	# What is compared are the keys of the values
+	redef type COMPARED: K
+
+	# The map that associates compared elements to the value used to compare them
+	var map: MapRead[K,V]
+
+	# The comparator used to compare values
+	var comparator: Comparator
+
+	redef fun compare(a,b) do return comparator.compare(map[a], map[b])
+end
+
+# This comparator uses the operator `<=>` to compare objects.
+# see `default_comparator` for an easy-to-use general stateless default comparator.
+class DefaultComparator
+	super Comparator
+	redef type COMPARED: Comparable
 	# Return a <=> b
 	redef fun compare(a, b) do return a <=> b
+end
+
+# This comparator uses the operator `<=>` to compare objects in a reverse order.
+#
+# See `default_reverse_comparator` for an easy-to-use general stateless reverse
+# default comparator.
+class DefaultReverseComparator
+	super Comparator
+
+	redef type COMPARED: Comparable
 
-	init do end
+	# Returns `b <=> a`.
+	redef fun compare(a, b) do return b <=> a
 end
 
+# Easy-to-use general stateless default comparator that uses `<=>` to compare things.
+fun default_comparator: DefaultComparator do return once new DefaultComparator
+
+# Easy-to-use general stateless default reverse comparator.
+#
+# Does the same as `default_comparator` but in reverse order.
+fun default_reverse_comparator: DefaultReverseComparator do
+	return once new DefaultReverseComparator
+end