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`.
32 fun compare
(a
: COMPARED, b
: COMPARED): Int is abstract
36 # assert default_comparator.is_sorted([1,2,2,3]) == true
37 # assert default_comparator.is_sorted([1,10,2,3]) == false
38 # assert alpha_comparator.is_sorted([1,10,2,3]) == true
39 fun is_sorted
(seq
: SequenceRead[COMPARED]): Bool
41 if seq
.length
<= 1 then return true
44 if compare
(prev
, e
) > 0 then return false
50 # Returns the minimum between `a` and `b`.
52 # assert default_comparator.min(2,10) == 2
53 # assert alpha_comparator.min(2,10) == 10
55 # If both are equivalent, then returns `a`.
57 # var m = alpha_comparator.min(1, "1")
60 fun min
(a
,b
: COMPARED): COMPARED
62 if compare
(a
,b
) > 0 then return b
else return a
65 # Returns the maximum between `a` and `b`.
67 # assert default_comparator.max(2,10) == 10
68 # assert alpha_comparator.max(2,10) == 2
70 # If both are equivalent, then returns `a`.
72 # var m = alpha_comparator.max(1, "1")
75 fun max
(a
,b
: COMPARED): COMPARED
77 if compare
(a
,b
) < 0 then return b
else return a
80 # Sort `array` using the `compare` function.
82 # var a = [10, 2, 3, 1, 4]
83 # default_comparator.sort(a)
84 # assert a == [1, 2, 3, 4, 10]
85 # alpha_comparator.sort(a)
86 # assert a == [1, 10, 2, 3, 4]
87 fun sort
(array
: Array[COMPARED]) do sub_sort
(array
, 0, array
.length-1
)
89 # Sort `array` between `from` and `to` indices
90 private fun sub_sort
(array
: Array[COMPARED], from
: Int, to
: Int)
94 else if from
+ 7 < to
then
95 quick_sort
(array
, from
, to
)
97 bubble_sort
(array
, from
, to
)
101 # Quick-sort `array` between `from` and `to` indices
102 # Worst case: O(n^2), Average case: O(n lg n)
104 # var a = [5, 2, 3, 1, 4]
105 # default_comparator.quick_sort(a, 0, a.length - 1)
106 # assert a == [1, 2, 3, 4, 5]
107 fun quick_sort
(array
: Array[COMPARED], from
: Int, to
: Int) do
108 var pivot
= array
[from
]
112 while i
<= to
and compare
(array
[i
], pivot
) <= 0 do i
+= 1
113 while j
> i
and compare
(array
[j
], pivot
) >= 0 do j
-= 1
120 array
[from
] = array
[i-1
]
122 sub_sort
(array
, from
, i-2
)
123 sub_sort
(array
, i
, to
)
126 # Bubble-sort `array` between `from` and `to` indices
127 # Worst case: O(n^2), average case: O(n^2)
129 # var a = [5, 2, 3, 1, 4]
130 # default_comparator.bubble_sort(a, 0, a.length - 1)
131 # assert a == [1, 2, 3, 4, 5]
132 fun bubble_sort
(array
: Array[COMPARED], from
: Int, to
: Int)
140 if compare
(min_v
, array
[j
]) > 0 then
147 array
[min
] = array
[i
]
154 # Insertion-sort `array` between `from` and `to` indices
155 # Worst case: O(n^2), average case: O(n^2)
157 # var a = [5, 2, 3, 1, 4]
158 # default_comparator.insertion_sort(a, 0, a.length - 1)
159 # assert a == [1, 2, 3, 4, 5]
160 fun insertion_sort
(array
: Array[COMPARED], from
: Int, to
: Int) do
161 for i
in [from
..to
] do
163 while j
> 0 and compare
(array
[j
], array
[j
- 1]) < 0 do
164 array
.swap_at
(j
, j
- 1)
170 # Merge-sort `array` between `from` and `to` indices
171 # Worst case: O(n lg n), average: O(n lg n)
173 # var a = [5, 2, 3, 1, 4]
174 # default_comparator.merge_sort(a, 0, a.length - 1)
175 # assert a == [1, 2, 3, 4, 5]
176 fun merge_sort
(array
: Array[COMPARED], from
, to
: Int) do
177 if from
>= to
then return
178 var mid
= (to
+ from
) / 2
179 merge_sort
(array
, from
, mid
)
180 merge_sort
(array
, mid
+ 1, to
)
181 merge
(array
, from
, mid
, to
)
184 private fun merge
(array
: Array[COMPARED], from
, mid
, to
: Int) do
185 var l
= new Array[COMPARED]
186 for i
in [from
..mid
] do l
.add array
[i
]
187 var r
= new Array[COMPARED]
188 for i
in [mid
+ 1..to
] do r
.add array
[i
]
191 for k
in [from
..to
] do
192 if i
>= l
.length
then
195 else if j
>= r
.length
then
198 else if compare
(l
[i
], r
[j
]) <= 0 then
208 # Heap-sort `array` between `from` and `to` indices
209 # Worst case: O(n lg n), average: O(n lg n)
211 # var a = [5, 2, 3, 1, 4]
212 # default_comparator.heap_sort(a, 0, a.length - 1)
213 # assert a == [1, 2, 3, 4, 5]
214 fun heap_sort
(array
: Array[COMPARED], from
, to
: Int) do
215 var size
= build_heap
(array
)
216 for j
in [from
..to
[ do
217 array
.swap_at
(0, size
)
219 heapify
(array
, 0, size
)
223 private fun build_heap
(array
: Array[COMPARED]): Int do
224 var size
= array
.length
- 1
227 heapify
(array
, i
, size
)
233 private fun heapify
(array
: Array[COMPARED], from
, to
: Int) do
237 if l
< to
and compare
(array
[l
], array
[from
]) > 0 then
242 if r
< to
and compare
(array
[r
], array
[largest
]) > 0 then
245 if largest
!= from
then
246 array
.swap_at
(from
, largest
)
247 heapify
(array
, largest
, to
)
253 redef class MapRead[K
,V
]
254 # Return an array of all values sorted with their keys using `comparator`.
257 # var map = new HashMap[Int, String]
261 # assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
262 # assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
264 fun values_sorted_by_key
(comparator
: Comparator): Array[V
]
266 var keys
= self.keys
.to_a
267 comparator
.sort
(keys
)
268 return [for k
in keys
do self[k
]]
271 # Return an array of all keys sorted with their values using `comparator`.
274 # var map = new HashMap[String, Int]
278 # assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
279 # assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
282 # See: `to_map_comparator` to get the comparator used internally.
283 fun keys_sorted_by_values
(comparator
: Comparator): Array[K
]
285 var keys
= self.keys
.to_a
286 var map_cmp
= to_map_comparator
(comparator
)
291 # A comparator that compares things with their values in self.
293 # See `MapComparator` for details.
294 fun to_map_comparator
(comparator
: Comparator): MapComparator[K
, V
] do return new MapComparator[K
,V
](self, comparator
)
297 # A comparator that compares things with their values in a map.
300 # var map = new HashMap[String, Int]
305 # var map_cmp = map.to_map_comparator(default_comparator)
306 # var a = ["ten", "one", "two"]
308 # assert a == ["one", "two", "ten"]
309 # map_cmp = map.to_map_comparator(alpha_comparator)
311 # assert a == ["one", "ten", "two"]
313 class MapComparator[K
,V
]
316 # What is compared are the keys of the values
317 redef type COMPARED: K
319 # The map that associates compared elements to the value used to compare them
320 var map
: MapRead[K
,V
]
322 # The comparator used to compare values
323 var comparator
: Comparator
325 redef fun compare
(a
,b
) do return comparator
.compare
(map
[a
], map
[b
])
328 # This comparator uses the operator `<=>` to compare objects.
329 # see `default_comparator` for an easy-to-use general stateless default comparator.
330 class DefaultComparator
332 redef type COMPARED: Comparable
334 redef fun compare
(a
, b
) do return a
<=> b
337 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
338 fun default_comparator
: DefaultComparator do return once
new DefaultComparator