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 sorts arrays.
  14 # In order to provide your own sort class you should define a subclass of `Comparator` with
  15 # a custom `Comparator::compare` function.
  16 module sorter
  17
  18 import array
  19
  20 # This abstract class generalizes ways to sort an array
  21 interface Comparator[E]
  22         # Compare `a` and `b`.
  23         # Returns:
  24         #       -1 if a < b
  25         #       0  if a = b
  26         #       1  if a > b
  27         fun compare(a: E, b: E): Int is abstract
  28
  29         # Sort `array` using the `compare` function.
  30         fun sort(array: Array[E]) do sub_sort(array, 0, array.length-1)
  31
  32         # Sort `array` between `from` and `to` indices
  33         private fun sub_sort(array: Array[E], from: Int, to: Int)
  34         do
  35                 if from >= to then
  36                         return
  37                 else if from + 7 < to then
  38                         quick_sort(array, from, to)
  39                 else
  40                         bubble_sort(array, from, to)
  41                 end
  42         end
  43
  44         # Quick-sort `array` between `from` and `to` indices
  45         private fun quick_sort(array: Array[E], from: Int, to: Int)
  46         do
  47                 var pivot = array[from]
  48                 var i = from
  49                 var j = to
  50                 while j > i do
  51                         while i <= to and compare(array[i], pivot) <= 0 do i += 1
  52                         while j > i and compare(array[j], pivot) >= 0 do j -= 1
  53                         if j > i then
  54                                 var t = array[i]
  55                                 array[i] = array[j]
  56                                 array[j] = t
  57                         end
  58                 end
  59                 array[from] = array[i-1]
  60                 array[i-1] = pivot
  61                 sub_sort(array, from, i-2)
  62                 sub_sort(array, i, to)
  63         end
  64
  65         # Bubble-sort `array` between `from` and `to` indices
  66         private fun bubble_sort(array: Array[E], from: Int, to: Int)
  67         do
  68                 var i = from
  69                 while i < to do
  70                         var min = i
  71                         var min_v = array[i]
  72                         var j = i
  73                         while j <= to do
  74                                 if compare(min_v, array[j]) > 0 then
  75                                         min = j
  76                                         min_v = array[j]
  77                                 end
  78                                 j += 1
  79                         end
  80                         if min != i then
  81                                 array[min] = array[i]
  82                                 array[i] = min_v
  83                         end
  84                         i += 1
  85                 end
  86         end
  87 end
  88
  89 # Deprecated class, use `Comparator` instead
  90 interface AbstractSorter[E]
  91         super Comparator[E]
  92 end
  93
  94 # This comparator uses the operator `<=>` to compare objects.
  95 class DefaultComparator[E: Comparable]
  96         super Comparator[E]
  97         # Return a <=> b
  98         redef fun compare(a, b) do return a <=> b
  99
 100         init do end
 101 end
 102
 103 # Deprecated class, use `DefaultComparator` instead
 104 class ComparableSorter[E: Comparable]
 105         super DefaultComparator[E]
 106 end