lib: new API for Comparator

Also remove old deprecated classes.

Signed-off-by: Jean Privat <jean@pryen.org>

diff --git a/contrib/nitcc/src/autom.nit b/contrib/nitcc/src/autom.nit
index 86f25b3..8825b01 100644 (file)
--- a/contrib/nitcc/src/autom.nit
+++ b/contrib/nitcc/src/autom.nit
@@ -536,7 +536,7 @@ class Automaton
 
                        # From the important values, build a sequence of TSymbols
                        var a = alphabet.to_a
-                       (new ComparableSorter[Int]).sort(a)
+                       default_comparator.sort(a)
                        var tsyms = new Array[TSymbol]
                        var last = 0
                        for i in a do

diff --git a/examples/mnit_dino/src/game_logic.nit b/examples/mnit_dino/src/game_logic.nit
index 1df0119..8d1a849 100644 (file)
--- a/examples/mnit_dino/src/game_logic.nit
+++ b/examples/mnit_dino/src/game_logic.nit
@@ -386,7 +386,8 @@ class Bush super Entity end
 
 # Sort entities on screen in order of Y, entities in the back are drawn first
 class EntitiesSorter
-       super AbstractSorter[Entity]
+       super Comparator
+       redef type COMPARED: Entity
 
        redef fun compare(a, b) do return b.pos.y <=> a.pos.y
 end

diff --git a/lib/ai/search.nit b/lib/ai/search.nit
index f279d4f..21a349d 100644 (file)
--- a/lib/ai/search.nit
+++ b/lib/ai/search.nit
@@ -608,7 +608,8 @@ end
 # Used to compare nodes with their score.
 # Smaller is score, smaller is the node.
 private class NodeComparator[S: Object, A]
-       super Comparator[SearchNode[S, A]]
+       super Comparator
+       redef type COMPARED: SearchNode[S, A]
        redef fun compare(a,b) do return a.score <=> b.score
 end
 

diff --git a/lib/counter.nit b/lib/counter.nit
index 75278d2..670fc59 100644 (file)
--- a/lib/counter.nit
+++ b/lib/counter.nit
@@ -174,7 +174,8 @@ class Counter[E: Object]
 end
 
 private class CounterComparator[E: Object]
-       super Comparator[E]
+       super Comparator
+       redef type COMPARED: E
        var counter: Counter[E]
        redef fun compare(a,b) do return self.counter.map[a] <=> self.counter.map[b]
 end

diff --git a/lib/ordered_tree.nit b/lib/ordered_tree.nit
index f6cd69a..91f8e63 100644 (file)
--- a/lib/ordered_tree.nit
+++ b/lib/ordered_tree.nit
@@ -80,7 +80,7 @@ class OrderedTree[E: Object]
 
        # Sort roots and other elements using a comparator method
        # This method basically sorts roots then each group of children
-       fun sort_with(comparator: Comparator[E])
+       fun sort_with(comparator: Comparator)
        do
                comparator.sort(roots)
                for a in sub.values do

diff --git a/lib/pipeline.nit b/lib/pipeline.nit
index da1b4c4..31d007b 100644 (file)
--- a/lib/pipeline.nit
+++ b/lib/pipeline.nit
@@ -35,7 +35,7 @@ redef interface Iterator[E]
 
        # Filter: sort with a given `comparator`.
        # Important: require O(n) memory.
-       fun sort_with(comparator: Comparator[E]): Iterator[E]
+       fun sort_with(comparator: Comparator): Iterator[E]
        do
                var a = self.to_a
                comparator.sort(a)

diff --git a/lib/poset.nit b/lib/poset.nit
index 3149b21..7a26f90 100644 (file)
--- a/lib/poset.nit
+++ b/lib/poset.nit
@@ -24,7 +24,9 @@ module poset
 #  * transitivity: `(self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)`
 class POSet[E: Object]
        super Collection[E]
-       super Comparator[E]
+       super Comparator
+
+       redef type COMPARED: E is fixed
 
        redef fun iterator do return elements.keys.iterator
 

diff --git a/lib/standard/collection/sorter.nit b/lib/standard/collection/sorter.nit
index b6319e1..7c311b0 100644 (file)
--- a/lib/standard/collection/sorter.nit
+++ b/lib/standard/collection/sorter.nit
@@ -19,24 +19,29 @@ import range
 import array
 
 # This abstract class generalizes ways to sort an array
-interface Comparator[E]
+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`.
        # 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
 
        # Sort `array` using the `compare` function.
        #
-       #     var s = new DefaultComparator[Int]
        #     var a = [5, 2, 3, 1, 4]
-       #     s.sort(a)
+       #     default_comparator.sort(a)
        #     assert a == [1, 2, 3, 4, 5]
-       fun sort(array: Array[E]) do sub_sort(array, 0, array.length-1)
+       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 +55,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 +80,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 +108,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 +124,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 +135,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 +162,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 +174,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 +184,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 +204,14 @@ interface Comparator[E]
 
 end
 
-# Deprecated class, use `Comparator` instead
-interface AbstractSorter[E]
-       super Comparator[E]
-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]
 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

diff --git a/lib/standard/queue.nit b/lib/standard/queue.nit
index c4cce96..ceab407 100644 (file)
--- a/lib/standard/queue.nit
+++ b/lib/standard/queue.nit
@@ -47,7 +47,7 @@ interface Queue[E]
        # assert a.take == 2
        # assert a.take == 1
        #
-       # var h = new MinHeapCmp[Int]
+       # var h = new MinHeap[Int].default
        # h.add 2
        # h.add 1
        # h.add 10
@@ -206,11 +206,10 @@ end
 # A min-heap implemented over an array
 #
 # The order is given by the `comparator`.
-# If `E` is Comparable, then the subclass `MinHeapCmp` can be used instead.
 #
 # ~~~
 # var a = [3,4,1,2]
-# var h = new MinHeap[Int](new DefaultComparator[Int])
+# var h = new MinHeap[Int].default
 # h.add_all(a)
 # assert h.peek == 1
 # var b = h.take_all
@@ -220,7 +219,20 @@ class MinHeap[E: Object]
        super Queue[E]
 
        private var items = new Array[E]
-       var comparator: Comparator[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
+
+       init(comparator: Comparator) do self.comparator = comparator
 
        redef fun is_empty do return items.is_empty
        redef fun length do return items.length
@@ -307,18 +319,3 @@ class MinHeap[E: Object]
                return true
        end
 end
-
-# A `MinHeap` for `Comparable` that does not need a specific `Comparator`
-#
-# ~~~
-# var a = [3,4,1,2]
-# var h = new MinHeapCmp[Int]
-# h.add_all(a)
-# assert h.peek == 1
-# var b = h.take_all
-# assert b == [1, 2, 3, 4]
-# ~~~
-class MinHeapCmp[E: Comparable]
-       super MinHeap[E]
-       init is old_style_init do super(new DefaultComparator[E])
-end

diff --git a/lib/standard/string.nit b/lib/standard/string.nit
index 3eede86..0529b60 100644 (file)
--- a/lib/standard/string.nit
+++ b/lib/standard/string.nit
@@ -2119,7 +2119,8 @@ end
 #
 # Note: it caching is not usefull, see `alpha_comparator`
 class CachedAlphaComparator
-       super Comparator[Object]
+       super Comparator
+       redef type COMPARED: Object
 
        private var cache = new HashMap[Object, String]
 
@@ -2137,7 +2138,7 @@ end
 
 # see `alpha_comparator`
 private class AlphaComparator
-       super Comparator[Object]
+       super Comparator
        redef fun compare(a, b) do return a.to_s <=> b.to_s
 end
 
@@ -2149,7 +2150,7 @@ end
 #     var a = [1, 2, 3, 10, 20]
 #     alpha_comparator.sort(a)
 #     assert a == [1, 10, 2, 20, 3]
-fun alpha_comparator: Comparator[Object] do return once new AlphaComparator
+fun alpha_comparator: Comparator do return once new AlphaComparator
 
 # The arguments of the program as given by the OS
 fun args: Sequence[String]

diff --git a/src/doc/doc_templates.nit b/src/doc/doc_templates.nit
index 200e650..516b17e 100644 (file)
--- a/src/doc/doc_templates.nit
+++ b/src/doc/doc_templates.nit
@@ -240,7 +240,9 @@ end
 
 # Comparator used to sort boxes by order
 private class OrderComparator
-       super Comparator[TplSidebarElt]
+       super Comparator
+
+       redef type COMPARED: TplSidebarElt
 
        redef fun compare(a, b) do
                if a.order < b.order then return -1

diff --git a/src/model/model.nit b/src/model/model.nit
index f989302..eab60f7 100644 (file)
--- a/src/model/model.nit
+++ b/src/model/model.nit
@@ -293,7 +293,8 @@ redef class MModule
 end
 
 private class MClassDefSorter
-       super AbstractSorter[MClassDef]
+       super Comparator
+       redef type COMPARED: MClassDef
        var mmodule: MModule
        redef fun compare(a, b)
        do
@@ -305,7 +306,8 @@ private class MClassDefSorter
 end
 
 private class MPropDefSorter
-       super AbstractSorter[MPropDef]
+       super Comparator
+       redef type COMPARED: MPropDef
        var mmodule: MModule
        redef fun compare(pa, pb)
        do

diff --git a/src/model/model_viz.nit b/src/model/model_viz.nit
index bc324b7..f8c0016 100644 (file)
--- a/src/model/model_viz.nit
+++ b/src/model/model_viz.nit
@@ -62,7 +62,10 @@ end
 # Compare modules and groups using the
 # FIXME do not use Object, but a better common interface of MModule and MGroup
 private class LinexComparator
-       super Comparator[Object]
+       super Comparator
+
+       redef type COMPARED: Object
+
        var mins = new HashMap [MGroup, nullable MModule]
        var maxs = new HashMap [MGroup, nullable MModule]
        fun min(o: Object): nullable MModule do

diff --git a/src/model_utils.nit b/src/model_utils.nit
index ff1a8d9..3153274 100644 (file)
--- a/src/model_utils.nit
+++ b/src/model_utils.nit
@@ -525,7 +525,8 @@ end
 
 # Sort mentities by their name
 class MEntityNameSorter
-       super AbstractSorter[MEntity]
+       super Comparator
+       redef type COMPARED: MEntity
        redef fun compare(a, b) do return a.name <=> b.name
        init do end
 end
@@ -540,7 +541,8 @@ end
 # If both `a` and `b` have the same ranking,
 # ordering is based on lexicographic comparison of `a.name` and `b.name`
 class MConcernRankSorter
-       super AbstractSorter[MConcern]
+       super Comparator
+       redef type COMPARED: MConcern
 
        init do end
 

diff --git a/src/toolcontext.nit b/src/toolcontext.nit
index 33322d2..893a843 100644 (file)
--- a/src/toolcontext.nit
+++ b/src/toolcontext.nit
@@ -103,7 +103,7 @@ class ToolContext
 
        # Messages
        private var messages = new Array[Message]
-       private var message_sorter = new ComparableSorter[Message]
+       private var message_sorter: Comparator = default_comparator
 
        # Output all current stacked messages.
        # If some errors occurred, exits the program.

diff --git a/tests/bench_complex_sort.nit b/tests/bench_complex_sort.nit
index 116d7d7..2eef2cb 100644 (file)
--- a/tests/bench_complex_sort.nit
+++ b/tests/bench_complex_sort.nit
@@ -74,8 +74,9 @@ class E
 end
 
 class EltComparator
-       super Comparator[Elt]
-       redef fun compare(a: Elt, b: Elt): Int
+       super Comparator
+       redef type COMPARED: Elt
+       redef fun compare(a, b)
        do
                if _is_val1 then
                        return a.val1 <=> b.val1

diff --git a/tests/example_sorter.nit b/tests/example_sorter.nit
index 32b661c..ae839ed 100644 (file)
--- a/tests/example_sorter.nit
+++ b/tests/example_sorter.nit
@@ -16,7 +16,8 @@
 
 
 class BackIntComparator
-       super Comparator[Int]
+       super Comparator
+       redef type COMPARED: Int
        redef fun compare(a: Int, b: Int): Int
        do
                return b <=> a
@@ -26,7 +27,8 @@ class BackIntComparator
 end
 
 class DecimalComparator
-       super Comparator[Int]
+       super Comparator
+       redef type COMPARED: Int
        redef fun compare(a: Int, b: Int): Int
        do
                return (a%10) <=> (b%10)
@@ -51,7 +53,7 @@ end
 
 var q = get_an_array(50)
 print(q.join(" "))
-(new DefaultComparator[Int]).sort(q)
+(default_comparator).sort(q)
 print(q.join(" "))
 (new DecimalComparator).sort(q)
 print(q.join(" "))