lib/core/collection/sorter.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2005-2008 Jean Privat <jean@pryen.org>
   4 #
   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
  11 # another product.
  12
  13 # This module contains classes used to compare things and sorts arrays.
  14 #
  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.
  17 module sorter
  18
  19 import range
  20 import array
  21
  22 # This abstract class generalizes ways to sort an array
  23 interface Comparator
  24         # What to compare to
  25         type COMPARED: nullable Object
  26
  27         # Compare `a` and `b`.
  28         #
  29         # Returns:
  30         #
  31         # * -1 if a < b
  32         # * 0  if a = b
  33         # * 1  if a > b
  34         fun compare(a: COMPARED, b: COMPARED): Int is abstract
  35
  36         # Is `seq` sorted?
  37         #
  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
  42         do
  43                 if seq.length <= 1 then return true
  44                 var prev = seq.first
  45                 for e in seq do
  46                         if compare(prev, e) > 0 then return false
  47                         prev = e
  48                 end
  49                 return true
  50         end
  51
  52         # Returns the minimum between `a` and `b`.
  53         #
  54         #     assert default_comparator.min(2,10) == 2
  55         #     assert alpha_comparator.min(2,10)   == 10
  56         #
  57         # If both are equivalent, then returns `a`.
  58         #
  59         #     var m = alpha_comparator.min(1, "1")
  60         #     assert m == 1
  61         #     assert m != "1"
  62         fun min(a,b: COMPARED): COMPARED
  63         do
  64                 if compare(a,b) > 0 then return b else return a
  65         end
  66
  67         # Returns the maximum between `a` and `b`.
  68         #
  69         #     assert default_comparator.max(2,10) == 10
  70         #     assert alpha_comparator.max(2,10)   == 2
  71         #
  72         # If both are equivalent, then returns `a`.
  73         #
  74         #     var m = alpha_comparator.max(1, "1")
  75         #     assert m == 1
  76         #     assert m != "1"
  77         fun max(a,b: COMPARED): COMPARED
  78         do
  79                 if compare(a,b) < 0 then return b else return a
  80         end
  81
  82         # Sort `array` using the `compare` function.
  83         #
  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)
  90
  91         # Sort `array` between `from` and `to` indices
  92         private fun sub_sort(array: Array[COMPARED], from: Int, to: Int)
  93         do
  94                 if from >= to then
  95                         return
  96                 else if from + 7 < to then
  97                         quick_sort(array, from, to)
  98                 else
  99                         bubble_sort(array, from, to)
 100                 end
 101         end
 102
 103         # Quick-sort `array` between `from` and `to` indices
 104         # Worst case: O(n^2), Average case: O(n lg n)
 105         #
 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]
 112         #     var a3 = [1]
 113         #     default_comparator.quick_sort(a3, 0, a3.length - 1)
 114         #     assert a3 == [1]
 115         fun quick_sort(array: Array[COMPARED], from: Int, to: Int) do
 116                 if from >= to then return
 117                 var pivot = array[from]
 118                 var i = from
 119                 var j = to
 120                 while j > i do
 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
 123                         if j > i then
 124                                 var t = array[i]
 125                                 array[i] = array[j]
 126                                 array[j] = t
 127                         end
 128                 end
 129                 array[from] = array[i-1]
 130                 array[i-1] = pivot
 131                 sub_sort(array, from, i-2)
 132                 sub_sort(array, i, to)
 133         end
 134
 135         # Bubble-sort `array` between `from` and `to` indices
 136         # Worst case: O(n^2), average case: O(n^2)
 137         #
 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)
 142         do
 143                 var i = from
 144                 while i < to do
 145                         var min = i
 146                         var min_v = array[i]
 147                         var j = i
 148                         while j <= to do
 149                                 if compare(min_v, array[j]) > 0 then
 150                                         min = j
 151                                         min_v = array[j]
 152                                 end
 153                                 j += 1
 154                         end
 155                         if min != i then
 156                                 array[min] = array[i]
 157                                 array[i] = min_v
 158                         end
 159                         i += 1
 160                 end
 161         end
 162
 163         # Insertion-sort `array` between `from` and `to` indices
 164         # Worst case: O(n^2), average case: O(n^2)
 165         #
 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
 171                         var j = i
 172                         while j > 0 and compare(array[j], array[j - 1]) < 0 do
 173                                 array.swap_at(j, j - 1)
 174                                 j -= 1
 175                         end
 176                 end
 177         end
 178
 179         # Merge-sort `array` between `from` and `to` indices
 180         # Worst case: O(n lg n), average: O(n lg n)
 181         #
 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)
 191         end
 192
 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]
 198                 var i = 0
 199                 var j = 0
 200                 for k in [from..to] do
 201                         if i >= l.length then
 202                                 array[k] = r[j]
 203                                 j += 1
 204                         else if j >= r.length then
 205                                 array[k] = l[i]
 206                                 i += 1
 207                         else if compare(l[i], r[j]) <= 0 then
 208                                 array[k] = l[i]
 209                                 i += 1
 210                         else
 211                                 array[k] = r[j]
 212                                 j += 1
 213                         end
 214                 end
 215         end
 216
 217         # Heap-sort `array` between `from` and `to` indices
 218         # Worst case: O(n lg n), average: O(n lg n)
 219         #
 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)
 227                         size -= 1
 228                         heapify(array, 0, size)
 229                 end
 230         end
 231
 232         private fun build_heap(array: Array[COMPARED]): Int do
 233                 var size = array.length - 1
 234                 var i = size / 2
 235                 while i >= 0 do
 236                         heapify(array, i, size)
 237                         i -= 1
 238                 end
 239                 return size
 240         end
 241
 242         private fun heapify(array: Array[COMPARED], from, to: Int) do
 243                 var l = from * 2
 244                 var r = l + 1
 245                 var largest: Int
 246                 if l < to and compare(array[l], array[from]) > 0 then
 247                         largest = l
 248                 else
 249                         largest = from
 250                 end
 251                 if r < to and compare(array[r], array[largest]) > 0 then
 252                         largest = r
 253                 end
 254                 if largest != from then
 255                         array.swap_at(from, largest)
 256                         heapify(array, largest, to)
 257                 end
 258         end
 259
 260 end
 261
 262 redef class MapRead[K,V]
 263         # Return an array of all values sorted with their keys using `comparator`.
 264         #
 265         # ~~~
 266         # var map = new HashMap[Int, String]
 267         # map[10] = "ten"
 268         # map[2]  = "two"
 269         # map[1]  = "one"
 270         # assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
 271         # assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
 272         # ~~~
 273         fun values_sorted_by_key(comparator: Comparator): Array[V]
 274         do
 275                 var keys = self.keys.to_a
 276                 comparator.sort(keys)
 277                 return [for k in keys do self[k]]
 278         end
 279
 280         # Return an array of all keys sorted with their values using `comparator`.
 281         #
 282         # ~~~
 283         # var map = new HashMap[String, Int]
 284         # map["ten"] = 10
 285         # map["two"] = 2
 286         # map["one"] = 1
 287         # assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
 288         # assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
 289         # ~~~
 290         #
 291         # See: `to_map_comparator` to get the comparator used internally.
 292         fun keys_sorted_by_values(comparator: Comparator): Array[K]
 293         do
 294                 var keys = self.keys.to_a
 295                 var map_cmp = to_map_comparator(comparator)
 296                 map_cmp.sort(keys)
 297                 return keys
 298         end
 299
 300         # A comparator that compares things with their values in self.
 301         #
 302         # See `MapComparator` for details.
 303         fun to_map_comparator(comparator: Comparator): MapComparator[K, V] do return new MapComparator[K,V](self, comparator)
 304 end
 305
 306 # A comparator that compares things with their values in a map.
 307 #
 308 # ~~~
 309 # var map = new HashMap[String, Int]
 310 # map["ten"] = 10
 311 # map["two"] = 2
 312 # map["one"] = 1
 313 #
 314 # var map_cmp = map.to_map_comparator(default_comparator)
 315 # var a = ["ten", "one", "two"]
 316 # map_cmp.sort(a)
 317 # assert a == ["one", "two", "ten"]
 318 # map_cmp = map.to_map_comparator(alpha_comparator)
 319 # map_cmp.sort(a)
 320 # assert a == ["one", "ten", "two"]
 321 # ~~~
 322 class MapComparator[K,V]
 323         super Comparator
 324
 325         # What is compared are the keys of the values
 326         redef type COMPARED: K
 327
 328         # The map that associates compared elements to the value used to compare them
 329         var map: MapRead[K,V]
 330
 331         # The comparator used to compare values
 332         var comparator: Comparator
 333
 334         redef fun compare(a,b) do return comparator.compare(map[a], map[b])
 335 end
 336
 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
 340         super Comparator
 341         redef type COMPARED: Comparable
 342         # Return a <=> b
 343         redef fun compare(a, b) do return a <=> b
 344 end
 345
 346 # This comparator uses the operator `<=>` to compare objects in a reverse order.
 347 #
 348 # See `default_reverse_comparator` for an easy-to-use general stateless reverse
 349 # default comparator.
 350 class DefaultReverseComparator
 351         super Comparator
 352
 353         redef type COMPARED: Comparable
 354
 355         # Returns `b <=> a`.
 356         redef fun compare(a, b) do return b <=> a
 357 end
 358
 359 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
 360 fun default_comparator: DefaultComparator do return once new DefaultComparator
 361
 362 # Easy-to-use general stateless default reverse comparator.
 363 #
 364 # Does the same as `default_comparator` but in reverse order.
 365 fun default_reverse_comparator: DefaultReverseComparator do
 366         return once new DefaultReverseComparator
 367 end