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         fun quick_sort(array: Array[COMPARED], from: Int, to: Int) do
 110                 var pivot = array[from]
 111                 var i = from
 112                 var j = to
 113                 while j > i do
 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
 116                         if j > i then
 117                                 var t = array[i]
 118                                 array[i] = array[j]
 119                                 array[j] = t
 120                         end
 121                 end
 122                 array[from] = array[i-1]
 123                 array[i-1] = pivot
 124                 sub_sort(array, from, i-2)
 125                 sub_sort(array, i, to)
 126         end
 127
 128         # Bubble-sort `array` between `from` and `to` indices
 129         # Worst case: O(n^2), average case: O(n^2)
 130         #
 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)
 135         do
 136                 var i = from
 137                 while i < to do
 138                         var min = i
 139                         var min_v = array[i]
 140                         var j = i
 141                         while j <= to do
 142                                 if compare(min_v, array[j]) > 0 then
 143                                         min = j
 144                                         min_v = array[j]
 145                                 end
 146                                 j += 1
 147                         end
 148                         if min != i then
 149                                 array[min] = array[i]
 150                                 array[i] = min_v
 151                         end
 152                         i += 1
 153                 end
 154         end
 155
 156         # Insertion-sort `array` between `from` and `to` indices
 157         # Worst case: O(n^2), average case: O(n^2)
 158         #
 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
 164                         var j = i
 165                         while j > 0 and compare(array[j], array[j - 1]) < 0 do
 166                                 array.swap_at(j, j - 1)
 167                                 j -= 1
 168                         end
 169                 end
 170         end
 171
 172         # Merge-sort `array` between `from` and `to` indices
 173         # Worst case: O(n lg n), average: O(n lg n)
 174         #
 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)
 184         end
 185
 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]
 191                 var i = 0
 192                 var j = 0
 193                 for k in [from..to] do
 194                         if i >= l.length then
 195                                 array[k] = r[j]
 196                                 j += 1
 197                         else if j >= r.length then
 198                                 array[k] = l[i]
 199                                 i += 1
 200                         else if compare(l[i], r[j]) <= 0 then
 201                                 array[k] = l[i]
 202                                 i += 1
 203                         else
 204                                 array[k] = r[j]
 205                                 j += 1
 206                         end
 207                 end
 208         end
 209
 210         # Heap-sort `array` between `from` and `to` indices
 211         # Worst case: O(n lg n), average: O(n lg n)
 212         #
 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)
 220                         size -= 1
 221                         heapify(array, 0, size)
 222                 end
 223         end
 224
 225         private fun build_heap(array: Array[COMPARED]): Int do
 226                 var size = array.length - 1
 227                 var i = size / 2
 228                 while i >= 0 do
 229                         heapify(array, i, size)
 230                         i -= 1
 231                 end
 232                 return size
 233         end
 234
 235         private fun heapify(array: Array[COMPARED], from, to: Int) do
 236                 var l = from * 2
 237                 var r = l + 1
 238                 var largest: Int
 239                 if l < to and compare(array[l], array[from]) > 0 then
 240                         largest = l
 241                 else
 242                         largest = from
 243                 end
 244                 if r < to and compare(array[r], array[largest]) > 0 then
 245                         largest = r
 246                 end
 247                 if largest != from then
 248                         array.swap_at(from, largest)
 249                         heapify(array, largest, to)
 250                 end
 251         end
 252
 253 end
 254
 255 redef class MapRead[K,V]
 256         # Return an array of all values sorted with their keys using `comparator`.
 257         #
 258         # ~~~
 259         # var map = new HashMap[Int, String]
 260         # map[10] = "ten"
 261         # map[2]  = "two"
 262         # map[1]  = "one"
 263         # assert map.values_sorted_by_key(default_comparator) == ["one", "two", "ten"]
 264         # assert map.values_sorted_by_key(alpha_comparator) == ["one", "ten", "two"]
 265         # ~~~
 266         fun values_sorted_by_key(comparator: Comparator): Array[V]
 267         do
 268                 var keys = self.keys.to_a
 269                 comparator.sort(keys)
 270                 return [for k in keys do self[k]]
 271         end
 272
 273         # Return an array of all keys sorted with their values using `comparator`.
 274         #
 275         # ~~~
 276         # var map = new HashMap[String, Int]
 277         # map["ten"] = 10
 278         # map["two"] = 2
 279         # map["one"] = 1
 280         # assert map.keys_sorted_by_values(default_comparator) == ["one", "two", "ten"]
 281         # assert map.keys_sorted_by_values(alpha_comparator) == ["one", "ten", "two"]
 282         # ~~~
 283         #
 284         # See: `to_map_comparator` to get the comparator used internally.
 285         fun keys_sorted_by_values(comparator: Comparator): Array[K]
 286         do
 287                 var keys = self.keys.to_a
 288                 var map_cmp = to_map_comparator(comparator)
 289                 map_cmp.sort(keys)
 290                 return keys
 291         end
 292
 293         # A comparator that compares things with their values in self.
 294         #
 295         # See `MapComparator` for details.
 296         fun to_map_comparator(comparator: Comparator): MapComparator[K, V] do return new MapComparator[K,V](self, comparator)
 297 end
 298
 299 # A comparator that compares things with their values in a map.
 300 #
 301 # ~~~
 302 # var map = new HashMap[String, Int]
 303 # map["ten"] = 10
 304 # map["two"] = 2
 305 # map["one"] = 1
 306 #
 307 # var map_cmp = map.to_map_comparator(default_comparator)
 308 # var a = ["ten", "one", "two"]
 309 # map_cmp.sort(a)
 310 # assert a == ["one", "two", "ten"]
 311 # map_cmp = map.to_map_comparator(alpha_comparator)
 312 # map_cmp.sort(a)
 313 # assert a == ["one", "ten", "two"]
 314 # ~~~
 315 class MapComparator[K,V]
 316         super Comparator
 317
 318         # What is compared are the keys of the values
 319         redef type COMPARED: K
 320
 321         # The map that associates compared elements to the value used to compare them
 322         var map: MapRead[K,V]
 323
 324         # The comparator used to compare values
 325         var comparator: Comparator
 326
 327         redef fun compare(a,b) do return comparator.compare(map[a], map[b])
 328 end
 329
 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
 333         super Comparator
 334         redef type COMPARED: Comparable
 335         # Return a <=> b
 336         redef fun compare(a, b) do return a <=> b
 337 end
 338
 339 # This comparator uses the operator `<=>` to compare objects in a reverse order.
 340 #
 341 # See `default_reverse_comparator` for an easy-to-use general stateless reverse
 342 # default comparator.
 343 class DefaultReverseComparator
 344         super Comparator
 345
 346         redef type COMPARED: Comparable
 347
 348         # Returns `b <=> a`.
 349         redef fun compare(a, b) do return b <=> a
 350 end
 351
 352 # Easy-to-use general stateless default comparator that uses `<=>` to compare things.
 353 fun default_comparator: DefaultComparator do return once new DefaultComparator
 354
 355 # Easy-to-use general stateless default reverse comparator.
 356 #
 357 # Does the same as `default_comparator` but in reverse order.
 358 fun default_reverse_comparator: DefaultReverseComparator do
 359         return once new DefaultReverseComparator
 360 end