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 # This comparator uses the operator `<=>` to compare objects.
254 # see `default_comparator` for an easy-to-use general stateless default comparator.
255 class DefaultComparator
257 redef type COMPARED: Comparable
259 redef fun compare
(a
, b
) do return a
<=> b
262 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
263 fun default_comparator
: DefaultComparator do return once
new DefaultComparator