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