1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2005-2008 Jean Privat <jean@pryen.org>
5 # This file is free software, which comes along with NIT. This software is
6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
7 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
8 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
9 # is kept unaltered, and a notification of the changes is added.
10 # You are allowed to redistribute it and sell it, alone or is a part of
13 # This module contains classes used to compare things and sorts arrays.
15 # In order to provide your own sort class you should define a subclass of `Comparator` with
16 # a custom `Comparator::compare` function and a specific `COMPARED` virtual type.
22 # This abstract class generalizes ways to sort an array
25 type COMPARED: nullable Object
27 # Compare `a` and `b`.
34 fun compare
(a
: COMPARED, b
: COMPARED): Int is abstract
38 # assert default_comparator.is_sorted([1,2,2,3]) == true
39 # assert default_comparator.is_sorted([1,10,2,3]) == false
40 # assert alpha_comparator.is_sorted([1,10,2,3]) == true
41 fun is_sorted
(seq
: SequenceRead[COMPARED]): Bool
43 if seq
.length
<= 1 then return true
46 if compare
(prev
, e
) > 0 then return false
52 # Returns the minimum between `a` and `b`.
54 # assert default_comparator.min(2,10) == 2
55 # assert alpha_comparator.min(2,10) == 10
57 # If both are equivalent, then returns `a`.
59 # var m = alpha_comparator.min(1, "1")
62 fun min
(a
,b
: COMPARED): COMPARED
64 if compare
(a
,b
) > 0 then return b
else return a
67 # Returns the maximum between `a` and `b`.
69 # assert default_comparator.max(2,10) == 10
70 # assert alpha_comparator.max(2,10) == 2
72 # If both are equivalent, then returns `a`.
74 # var m = alpha_comparator.max(1, "1")
77 fun max
(a
,b
: COMPARED): COMPARED
79 if compare
(a
,b
) < 0 then return b
else return a
82 # Sort `array` using the `compare` function.
84 # var a = [10, 2, 3, 1, 4]
85 # default_comparator.sort(a)
86 # assert a == [1, 2, 3, 4, 10]
87 # alpha_comparator.sort(a)
88 # assert a == [1, 10, 2, 3, 4]
89 fun sort
(array
: Array[COMPARED]) do sub_sort
(array
, 0, array
.length-1
)
91 # Sort `array` between `from` and `to` indices
92 private fun sub_sort
(array
: Array[COMPARED], from
: Int, to
: Int)
96 else if from
+ 7 < to
then
97 quick_sort
(array
, from
, to
)
99 bubble_sort
(array
, from
, to
)
103 # Quick-sort `array` between `from` and `to` indices
104 # Worst case: O(n^2), Average case: O(n lg n)
106 # var a = [5, 2, 3, 1, 4]
107 # default_comparator.quick_sort(a, 0, a.length - 1)
108 # assert a == [1, 2, 3, 4, 5]
109 # var a2 = new Array[Int]
110 # default_comparator.quick_sort(a2, 0, a2.length - 1)
111 # assert a2 == new Array[Int]
113 # default_comparator.quick_sort(a3, 0, a3.length - 1)
115 fun quick_sort
(array
: Array[COMPARED], from
: Int, to
: Int) do
116 if from
>= to
then return
117 var pivot
= array
[from
]
121 while i
<= to
and compare
(array
[i
], pivot
) <= 0 do i
+= 1
122 while j
> i
and compare
(array
[j
], pivot
) >= 0 do j
-= 1
129 array
[from
] = array
[i-1
]
131 sub_sort
(array
, from
, i-2
)
132 sub_sort
(array
, i
, to
)
135 # Bubble-sort `array` between `from` and `to` indices
136 # Worst case: O(n^2), average case: O(n^2)
138 # var a = [5, 2, 3, 1, 4]
139 # default_comparator.bubble_sort(a, 0, a.length - 1)
140 # assert a == [1, 2, 3, 4, 5]
141 fun bubble_sort
(array
: Array[COMPARED], from
: Int, to
: Int)
149 if compare
(min_v
, array
[j
]) > 0 then
156 array
[min
] = array
[i
]
163 # Insertion-sort `array` between `from` and `to` indices
164 # Worst case: O(n^2), average case: O(n^2)
166 # var a = [5, 2, 3, 1, 4]
167 # default_comparator.insertion_sort(a, 0, a.length - 1)
168 # assert a == [1, 2, 3, 4, 5]
169 fun insertion_sort
(array
: Array[COMPARED], from
: Int, to
: Int) do
170 for i
in [from
..to
] do
172 while j
> 0 and compare
(array
[j
], array
[j
- 1]) < 0 do
173 array
.swap_at
(j
, j
- 1)
179 # Merge-sort `array` between `from` and `to` indices
180 # Worst case: O(n lg n), average: O(n lg n)
182 # var a = [5, 2, 3, 1, 4]
183 # default_comparator.merge_sort(a, 0, a.length - 1)
184 # assert a == [1, 2, 3, 4, 5]
185 fun merge_sort
(array
: Array[COMPARED], from
, to
: Int) do
186 if from
>= to
then return
187 var mid
= (to
+ from
) / 2
188 merge_sort
(array
, from
, mid
)
189 merge_sort
(array
, mid
+ 1, to
)
190 merge
(array
, from
, mid
, to
)
193 private fun merge
(array
: Array[COMPARED], from
, mid
, to
: Int) do
194 var l
= new Array[COMPARED]
195 for i
in [from
..mid
] do l
.add array
[i
]
196 var r
= new Array[COMPARED]
197 for i
in [mid
+ 1..to
] do r
.add array
[i
]
200 for k
in [from
..to
] do
201 if i
>= l
.length
then
204 else if j
>= r
.length
then
207 else if compare
(l
[i
], r
[j
]) <= 0 then
217 # Heap-sort `array` between `from` and `to` indices
218 # Worst case: O(n lg n), average: O(n lg n)
220 # var a = [5, 2, 3, 1, 4]
221 # default_comparator.heap_sort(a, 0, a.length - 1)
222 # assert a == [1, 2, 3, 4, 5]
223 fun heap_sort
(array
: Array[COMPARED], from
, to
: Int) do
224 var size
= build_heap
(array
)
225 for j
in [from
..to
[ do
226 array
.swap_at
(0, size
)
228 heapify
(array
, 0, size
)
232 private fun build_heap
(array
: Array[COMPARED]): Int do
233 var size
= array
.length
- 1
236 heapify
(array
, i
, size
)
242 private fun heapify
(array
: Array[COMPARED], from
, to
: Int) do
246 if l
< to
and compare
(array
[l
], array
[from
]) > 0 then
251 if r
< to
and compare
(array
[r
], array
[largest
]) > 0 then
254 if largest
!= from
then
255 array
.swap_at
(from
, largest
)
256 heapify
(array
, largest
, to
)
262 redef class MapRead[K
,V
]
263 # Return an array of all values sorted with their keys using `comparator`.
266 # var map = new HashMap[Int, String]
270 # assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
271 # assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
273 fun values_sorted_by_key
(comparator
: Comparator): Array[V
]
275 var keys
= self.keys
.to_a
276 comparator
.sort
(keys
)
277 return [for k
in keys
do self[k
]]
280 # Return an array of all keys sorted with their values using `comparator`.
283 # var map = new HashMap[String, Int]
287 # assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
288 # assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
291 # See: `to_map_comparator` to get the comparator used internally.
292 fun keys_sorted_by_values
(comparator
: Comparator): Array[K
]
294 var keys
= self.keys
.to_a
295 var map_cmp
= to_map_comparator
(comparator
)
300 # A comparator that compares things with their values in self.
302 # See `MapComparator` for details.
303 fun to_map_comparator
(comparator
: Comparator): MapComparator[K
, V
] do return new MapComparator[K
,V
](self, comparator
)
306 # A comparator that compares things with their values in a map.
309 # var map = new HashMap[String, Int]
314 # var map_cmp = map.to_map_comparator(default_comparator)
315 # var a = ["ten", "one", "two"]
317 # assert a == ["one", "two", "ten"]
318 # map_cmp = map.to_map_comparator(alpha_comparator)
320 # assert a == ["one", "ten", "two"]
322 class MapComparator[K
,V
]
325 # What is compared are the keys of the values
326 redef type COMPARED: K
328 # The map that associates compared elements to the value used to compare them
329 var map
: MapRead[K
,V
]
331 # The comparator used to compare values
332 var comparator
: Comparator
334 redef fun compare
(a
,b
) do return comparator
.compare
(map
[a
], map
[b
])
337 # This comparator uses the operator `<=>` to compare objects.
338 # see `default_comparator` for an easy-to-use general stateless default comparator.
339 class DefaultComparator
341 redef type COMPARED: Comparable
343 redef fun compare
(a
, b
) do return a
<=> b
346 # This comparator uses the operator `<=>` to compare objects in a reverse order.
348 # See `default_reverse_comparator` for an easy-to-use general stateless reverse
349 # default comparator.
350 class DefaultReverseComparator
353 redef type COMPARED: Comparable
356 redef fun compare
(a
, b
) do return b
<=> a
359 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
360 fun default_comparator
: DefaultComparator do return once
new DefaultComparator
362 # Easy-to-use general stateless default reverse comparator.
364 # Does the same as `default_comparator` but in reverse order.
365 fun default_reverse_comparator
: DefaultReverseComparator do
366 return once
new DefaultReverseComparator