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 fun quick_sort
(array
: Array[COMPARED], from
: Int, to
: Int) do
110 var pivot
= array
[from
]
114 while i
<= to
and compare
(array
[i
], pivot
) <= 0 do i
+= 1
115 while j
> i
and compare
(array
[j
], pivot
) >= 0 do j
-= 1
122 array
[from
] = array
[i-1
]
124 sub_sort
(array
, from
, i-2
)
125 sub_sort
(array
, i
, to
)
128 # Bubble-sort `array` between `from` and `to` indices
129 # Worst case: O(n^2), average case: O(n^2)
131 # var a = [5, 2, 3, 1, 4]
132 # default_comparator.bubble_sort(a, 0, a.length - 1)
133 # assert a == [1, 2, 3, 4, 5]
134 fun bubble_sort
(array
: Array[COMPARED], from
: Int, to
: Int)
142 if compare
(min_v
, array
[j
]) > 0 then
149 array
[min
] = array
[i
]
156 # Insertion-sort `array` between `from` and `to` indices
157 # Worst case: O(n^2), average case: O(n^2)
159 # var a = [5, 2, 3, 1, 4]
160 # default_comparator.insertion_sort(a, 0, a.length - 1)
161 # assert a == [1, 2, 3, 4, 5]
162 fun insertion_sort
(array
: Array[COMPARED], from
: Int, to
: Int) do
163 for i
in [from
..to
] do
165 while j
> 0 and compare
(array
[j
], array
[j
- 1]) < 0 do
166 array
.swap_at
(j
, j
- 1)
172 # Merge-sort `array` between `from` and `to` indices
173 # Worst case: O(n lg n), average: O(n lg n)
175 # var a = [5, 2, 3, 1, 4]
176 # default_comparator.merge_sort(a, 0, a.length - 1)
177 # assert a == [1, 2, 3, 4, 5]
178 fun merge_sort
(array
: Array[COMPARED], from
, to
: Int) do
179 if from
>= to
then return
180 var mid
= (to
+ from
) / 2
181 merge_sort
(array
, from
, mid
)
182 merge_sort
(array
, mid
+ 1, to
)
183 merge
(array
, from
, mid
, to
)
186 private fun merge
(array
: Array[COMPARED], from
, mid
, to
: Int) do
187 var l
= new Array[COMPARED]
188 for i
in [from
..mid
] do l
.add array
[i
]
189 var r
= new Array[COMPARED]
190 for i
in [mid
+ 1..to
] do r
.add array
[i
]
193 for k
in [from
..to
] do
194 if i
>= l
.length
then
197 else if j
>= r
.length
then
200 else if compare
(l
[i
], r
[j
]) <= 0 then
210 # Heap-sort `array` between `from` and `to` indices
211 # Worst case: O(n lg n), average: O(n lg n)
213 # var a = [5, 2, 3, 1, 4]
214 # default_comparator.heap_sort(a, 0, a.length - 1)
215 # assert a == [1, 2, 3, 4, 5]
216 fun heap_sort
(array
: Array[COMPARED], from
, to
: Int) do
217 var size
= build_heap
(array
)
218 for j
in [from
..to
[ do
219 array
.swap_at
(0, size
)
221 heapify
(array
, 0, size
)
225 private fun build_heap
(array
: Array[COMPARED]): Int do
226 var size
= array
.length
- 1
229 heapify
(array
, i
, size
)
235 private fun heapify
(array
: Array[COMPARED], from
, to
: Int) do
239 if l
< to
and compare
(array
[l
], array
[from
]) > 0 then
244 if r
< to
and compare
(array
[r
], array
[largest
]) > 0 then
247 if largest
!= from
then
248 array
.swap_at
(from
, largest
)
249 heapify
(array
, largest
, to
)
255 redef class MapRead[K
,V
]
256 # Return an array of all values sorted with their keys using `comparator`.
259 # var map = new HashMap[Int, String]
263 # assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
264 # assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
266 fun values_sorted_by_key
(comparator
: Comparator): Array[V
]
268 var keys
= self.keys
.to_a
269 comparator
.sort
(keys
)
270 return [for k
in keys
do self[k
]]
273 # Return an array of all keys sorted with their values using `comparator`.
276 # var map = new HashMap[String, Int]
280 # assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
281 # assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
284 # See: `to_map_comparator` to get the comparator used internally.
285 fun keys_sorted_by_values
(comparator
: Comparator): Array[K
]
287 var keys
= self.keys
.to_a
288 var map_cmp
= to_map_comparator
(comparator
)
293 # A comparator that compares things with their values in self.
295 # See `MapComparator` for details.
296 fun to_map_comparator
(comparator
: Comparator): MapComparator[K
, V
] do return new MapComparator[K
,V
](self, comparator
)
299 # A comparator that compares things with their values in a map.
302 # var map = new HashMap[String, Int]
307 # var map_cmp = map.to_map_comparator(default_comparator)
308 # var a = ["ten", "one", "two"]
310 # assert a == ["one", "two", "ten"]
311 # map_cmp = map.to_map_comparator(alpha_comparator)
313 # assert a == ["one", "ten", "two"]
315 class MapComparator[K
,V
]
318 # What is compared are the keys of the values
319 redef type COMPARED: K
321 # The map that associates compared elements to the value used to compare them
322 var map
: MapRead[K
,V
]
324 # The comparator used to compare values
325 var comparator
: Comparator
327 redef fun compare
(a
,b
) do return comparator
.compare
(map
[a
], map
[b
])
330 # This comparator uses the operator `<=>` to compare objects.
331 # see `default_comparator` for an easy-to-use general stateless default comparator.
332 class DefaultComparator
334 redef type COMPARED: Comparable
336 redef fun compare
(a
, b
) do return a
<=> b
339 # This comparator uses the operator `<=>` to compare objects in a reverse order.
341 # See `default_reverse_comparator` for an easy-to-use general stateless reverse
342 # default comparator.
343 class DefaultReverseComparator
346 redef type COMPARED: Comparable
349 redef fun compare
(a
, b
) do return b
<=> a
352 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
353 fun default_comparator
: DefaultComparator do return once
new DefaultComparator
355 # Easy-to-use general stateless default reverse comparator.
357 # Does the same as `default_comparator` but in reverse order.
358 fun default_reverse_comparator
: DefaultReverseComparator do
359 return once
new DefaultReverseComparator