# 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
# This abstract class generalizes ways to sort an array
interface Comparator
# What to compare to
- #
- # The type is virtual, instead of generic, to allow a contravariant
- # subtyping of the comparator.
type COMPARED: nullable Object
# Compare `a` and `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 = [5, 2, 3, 1, 4]
+ # var a = [10, 2, 3, 1, 4]
# default_comparator.sort(a)
- # assert a == [1, 2, 3, 4, 5]
+ # 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
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
+
+# 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
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
+
+ # 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
nitlanguage / nit.git / blobdiff