X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/collection/sorter.nit b/lib/standard/collection/sorter.nit index b6319e1..ca16460 100644 --- a/lib/standard/collection/sorter.nit +++ b/lib/standard/collection/sorter.nit @@ -10,33 +10,84 @@ # 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. +# 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. +# 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 -interface Comparator[E] +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: 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. # - # var s = new DefaultComparator[Int] - # var a = [5, 2, 3, 1, 4] - # s.sort(a) - # assert a == [1, 2, 3, 4, 5] - fun sort(array: Array[E]) do sub_sort(array, 0, array.length-1) + # 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) + private fun sub_sort(array: Array[COMPARED], from: Int, to: Int) do if from >= to then return @@ -50,11 +101,10 @@ interface Comparator[E] # Quick-sort `array` between `from` and `to` indices # Worst case: O(n^2), Average case: O(n lg n) # - # var s = new DefaultComparator[Int] # var a = [5, 2, 3, 1, 4] - # s.quick_sort(a, 0, a.length - 1) + # default_comparator.quick_sort(a, 0, a.length - 1) # assert a == [1, 2, 3, 4, 5] - fun quick_sort(array: Array[E], from: Int, to: Int) do + fun quick_sort(array: Array[COMPARED], from: Int, to: Int) do var pivot = array[from] var i = from var j = to @@ -76,11 +126,10 @@ interface Comparator[E] # Bubble-sort `array` between `from` and `to` indices # Worst case: O(n^2), average case: O(n^2) # - # var s = new DefaultComparator[Int] # var a = [5, 2, 3, 1, 4] - # s.bubble_sort(a, 0, a.length - 1) + # default_comparator.bubble_sort(a, 0, a.length - 1) # assert a == [1, 2, 3, 4, 5] - fun bubble_sort(array: Array[E], from: Int, to: Int) + fun bubble_sort(array: Array[COMPARED], from: Int, to: Int) do var i = from while i < to do @@ -105,12 +154,10 @@ interface Comparator[E] # Insertion-sort `array` between `from` and `to` indices # Worst case: O(n^2), average case: O(n^2) # - # var s = new DefaultComparator[Int] # var a = [5, 2, 3, 1, 4] - # s.insertion_sort(a, 0, a.length - 1) + # default_comparator.insertion_sort(a, 0, a.length - 1) # assert a == [1, 2, 3, 4, 5] - fun insertion_sort(array: Array[E], from: Int, to: Int) do - var last = array.length + 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 @@ -123,11 +170,10 @@ interface Comparator[E] # Merge-sort `array` between `from` and `to` indices # Worst case: O(n lg n), average: O(n lg n) # - # var s = new DefaultComparator[Int] # var a = [5, 2, 3, 1, 4] - # s.merge_sort(a, 0, a.length - 1) + # default_comparator.merge_sort(a, 0, a.length - 1) # assert a == [1, 2, 3, 4, 5] - fun merge_sort(array: Array[E], from, to: Int) do + 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) @@ -135,10 +181,10 @@ interface Comparator[E] merge(array, from, mid, to) end - private fun merge(array: Array[E], from, mid, to: Int) do - var l = new Array[E] + 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[E] + var r = new Array[COMPARED] for i in [mid + 1..to] do r.add array[i] var i = 0 var j = 0 @@ -162,11 +208,10 @@ interface Comparator[E] # Heap-sort `array` between `from` and `to` indices # Worst case: O(n lg n), average: O(n lg n) # - # var s = new DefaultComparator[Int] # var a = [5, 2, 3, 1, 4] - # s.heap_sort(a, 0, a.length - 1) + # default_comparator.heap_sort(a, 0, a.length - 1) # assert a == [1, 2, 3, 4, 5] - fun heap_sort(array: Array[E], from, to: Int) do + 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) @@ -175,7 +220,7 @@ interface Comparator[E] end end - private fun build_heap(array: Array[E]): Int do + private fun build_heap(array: Array[COMPARED]): Int do var size = array.length - 1 var i = size / 2 while i >= 0 do @@ -185,7 +230,7 @@ interface Comparator[E] return size end - private fun heapify(array: Array[E], from, to: Int) do + private fun heapify(array: Array[COMPARED], from, to: Int) do var l = from * 2 var r = l + 1 var largest: Int @@ -205,25 +250,109 @@ interface Comparator[E] end -# Deprecated class, use `Comparator` instead -interface AbstractSorter[E] - super Comparator[E] +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 + +# 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[E: Comparable] - super Comparator[E] +class DefaultComparator + super Comparator + redef type COMPARED: Comparable # Return a <=> b redef fun compare(a, b) do return a <=> b - - init do end end -# Deprecated class, use `DefaultComparator` instead -class ComparableSorter[E: Comparable] - super DefaultComparator[E] +# 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 + + # 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: Comparator[Comparable] do return once new DefaultComparator[Comparable] +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