lib/standard/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         # Returns:
  29         #       -1 if a < b
  30         #       0  if a = b
  31         #       1  if a > b
  32         fun compare(a: COMPARED, b: COMPARED): Int is abstract
  33
  34         # Is `seq` sorted?
  35         #
  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
  40         do
  41                 if seq.length <= 1 then return true
  42                 var prev = seq.first
  43                 for e in seq do
  44                         if compare(prev, e) > 0 then return false
  45                         prev = e
  46                 end
  47                 return true
  48         end
  49
  50         # Returns the minimum between `a` and `b`.
  51         #
  52         #     assert default_comparator.min(2,10) == 2
  53         #     assert alpha_comparator.min(2,10)   == 10
  54         #
  55         # If both are equivalent, then returns `a`.
  56         #
  57         #     var m = alpha_comparator.min(1, "1")
  58         #     assert m == 1
  59         #     assert m != "1"
  60         fun min(a,b: COMPARED): COMPARED
  61         do
  62                 if compare(a,b) > 0 then return b else return a
  63         end
  64
  65         # Returns the maximum between `a` and `b`.
  66         #
  67         #     assert default_comparator.max(2,10) == 10
  68         #     assert alpha_comparator.max(2,10)   == 2
  69         #
  70         # If both are equivalent, then returns `a`.
  71         #
  72         #     var m = alpha_comparator.max(1, "1")
  73         #     assert m == 1
  74         #     assert m != "1"
  75         fun max(a,b: COMPARED): COMPARED
  76         do
  77                 if compare(a,b) < 0 then return b else return a
  78         end
  79
  80         # Sort `array` using the `compare` function.
  81         #
  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)
  88
  89         # Sort `array` between `from` and `to` indices
  90         private fun sub_sort(array: Array[COMPARED], from: Int, to: Int)
  91         do
  92                 if from >= to then
  93                         return
  94                 else if from + 7 < to then
  95                         quick_sort(array, from, to)
  96                 else
  97                         bubble_sort(array, from, to)
  98                 end
  99         end
 100
 101         # Quick-sort `array` between `from` and `to` indices
 102         # Worst case: O(n^2), Average case: O(n lg n)
 103         #
 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]
 109                 var i = from
 110                 var j = to
 111                 while j > i do
 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
 114                         if j > i then
 115                                 var t = array[i]
 116                                 array[i] = array[j]
 117                                 array[j] = t
 118                         end
 119                 end
 120                 array[from] = array[i-1]
 121                 array[i-1] = pivot
 122                 sub_sort(array, from, i-2)
 123                 sub_sort(array, i, to)
 124         end
 125
 126         # Bubble-sort `array` between `from` and `to` indices
 127         # Worst case: O(n^2), average case: O(n^2)
 128         #
 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)
 133         do
 134                 var i = from
 135                 while i < to do
 136                         var min = i
 137                         var min_v = array[i]
 138                         var j = i
 139                         while j <= to do
 140                                 if compare(min_v, array[j]) > 0 then
 141                                         min = j
 142                                         min_v = array[j]
 143                                 end
 144                                 j += 1
 145                         end
 146                         if min != i then
 147                                 array[min] = array[i]
 148                                 array[i] = min_v
 149                         end
 150                         i += 1
 151                 end
 152         end
 153
 154         # Insertion-sort `array` between `from` and `to` indices
 155         # Worst case: O(n^2), average case: O(n^2)
 156         #
 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
 162                         var j = i
 163                         while j > 0 and compare(array[j], array[j - 1]) < 0 do
 164                                 array.swap_at(j, j - 1)
 165                                 j -= 1
 166                         end
 167                 end
 168         end
 169
 170         # Merge-sort `array` between `from` and `to` indices
 171         # Worst case: O(n lg n), average: O(n lg n)
 172         #
 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)
 182         end
 183
 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]
 189                 var i = 0
 190                 var j = 0
 191                 for k in [from..to] do
 192                         if i >= l.length then
 193                                 array[k] = r[j]
 194                                 j += 1
 195                         else if j >= r.length then
 196                                 array[k] = l[i]
 197                                 i += 1
 198                         else if compare(l[i], r[j]) <= 0 then
 199                                 array[k] = l[i]
 200                                 i += 1
 201                         else
 202                                 array[k] = r[j]
 203                                 j += 1
 204                         end
 205                 end
 206         end
 207
 208         # Heap-sort `array` between `from` and `to` indices
 209         # Worst case: O(n lg n), average: O(n lg n)
 210         #
 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)
 218                         size -= 1
 219                         heapify(array, 0, size)
 220                 end
 221         end
 222
 223         private fun build_heap(array: Array[COMPARED]): Int do
 224                 var size = array.length - 1
 225                 var i = size / 2
 226                 while i >= 0 do
 227                         heapify(array, i, size)
 228                         i -= 1
 229                 end
 230                 return size
 231         end
 232
 233         private fun heapify(array: Array[COMPARED], from, to: Int) do
 234                 var l = from * 2
 235                 var r = l + 1
 236                 var largest: Int
 237                 if l < to and compare(array[l], array[from]) > 0 then
 238                         largest = l
 239                 else
 240                         largest = from
 241                 end
 242                 if r < to and compare(array[r], array[largest]) > 0 then
 243                         largest = r
 244                 end
 245                 if largest != from then
 246                         array.swap_at(from, largest)
 247                         heapify(array, largest, to)
 248                 end
 249         end
 250
 251 end
 252
 253 redef class MapRead[K,V]
 254         # Return an array of all values sorted with their keys using `comparator`.
 255         #
 256         # ~~~
 257         # var map = new HashMap[Int, String]
 258         # map[10] = "ten"
 259         # map[2]  = "two"
 260         # map[1]  = "one"
 261         # assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
 262         # assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
 263         # ~~~
 264         fun values_sorted_by_key(comparator: Comparator): Array[V]
 265         do
 266                 var keys = self.keys.to_a
 267                 comparator.sort(keys)
 268                 return [for k in keys do self[k]]
 269         end
 270
 271         # Return an array of all keys sorted with their values using `comparator`.
 272         #
 273         # ~~~
 274         # var map = new HashMap[String, Int]
 275         # map["ten"] = 10
 276         # map["two"] = 2
 277         # map["one"] = 1
 278         # assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
 279         # assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
 280         # ~~~
 281         #
 282         # See: `to_map_comparator` to get the comparator used internally.
 283         fun keys_sorted_by_values(comparator: Comparator): Array[K]
 284         do
 285                 var keys = self.keys.to_a
 286                 var map_cmp = to_map_comparator(comparator)
 287                 map_cmp.sort(keys)
 288                 return keys
 289         end
 290
 291         # A comparator that compares things with their values in self.
 292         #
 293         # See `MapComparator` for details.
 294         fun to_map_comparator(comparator: Comparator): MapComparator[K, V] do return new MapComparator[K,V](self, comparator)
 295 end
 296
 297 # A comparator that compares things with their values in a map.
 298 #
 299 # ~~~
 300 # var map = new HashMap[String, Int]
 301 # map["ten"] = 10
 302 # map["two"] = 2
 303 # map["one"] = 1
 304 #
 305 # var map_cmp = map.to_map_comparator(default_comparator)
 306 # var a = ["ten", "one", "two"]
 307 # map_cmp.sort(a)
 308 # assert a == ["one", "two", "ten"]
 309 # map_cmp = map.to_map_comparator(alpha_comparator)
 310 # map_cmp.sort(a)
 311 # assert a == ["one", "ten", "two"]
 312 # ~~~
 313 class MapComparator[K,V]
 314         super Comparator
 315
 316         # What is compared are the keys of the values
 317         redef type COMPARED: K
 318
 319         # The map that associates compared elements to the value used to compare them
 320         var map: MapRead[K,V]
 321
 322         # The comparator used to compare values
 323         var comparator: Comparator
 324
 325         redef fun compare(a,b) do return comparator.compare(map[a], map[b])
 326 end
 327
 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
 331         super Comparator
 332         redef type COMPARED: Comparable
 333         # Return a <=> b
 334         redef fun compare(a, b) do return a <=> b
 335 end
 336
 337 # This comparator uses the operator `<=>` to compare objects in a reverse order.
 338 #
 339 # See `default_reverse_comparator` for an easy-to-use general stateless reverse
 340 # default comparator.
 341 class DefaultReverseComparator
 342         super Comparator
 343
 344         redef type COMPARED: Comparable
 345
 346         # Returns `b <=> a`.
 347         redef fun compare(a, b) do return b <=> a
 348 end
 349
 350 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
 351 fun default_comparator: DefaultComparator do return once new DefaultComparator
 352
 353 # Easy-to-use general stateless default reverse comparator.
 354 #
 355 # Does the same as `default_comparator` but in reverse order.
 356 fun default_reverse_comparator: DefaultReverseComparator do
 357         return once new DefaultReverseComparator
 358 end