jhplot.math
Class SortUtils

java.lang.Object
  extended by jhplot.math.SortUtils

public class SortUtils
extends java.lang.Object

Utility class providing some useful static sort methods. The sort routines all return index permutations p such that data[p[0]],..,data[p[data.length-1]] is in sorted order. The data array itself is not modified. To actually rearrange the array elements, the inverse of p can be used to permute the array, such that data[0],..,data[data.length-1] is in sorted order. Use getIterator(p, data) to iterate in sorted order. A code example may show you what to do next:

 String[] colors = { "red", "green", "blue" };
 int[] p = SortUtils.sort(colors, new StringComparator());
 // --> (colors[p[0]], colors[p[1]], colors[p[2]]) == ("blue","green","red")
 Iterator iter = SortUtils.getIterator(p, colors)
 // --> (iter.next(), iter.next(), iter.next()) == ("blue","green","red")
 SortUtils.permute(SortUtils.inverse(p), colors, true);
 // --> (colors[0], colors[1], colors[2]) == ("blue","green","red")
 
Stable sorts (preserving order of equal elements) are supported. Sorting is done using quick-sort mith median of 3 (and insertion-sort for small ranges).


Constructor Summary
SortUtils()
           
 
Method Summary
static java.util.Iterator getIterator(int[] p, java.util.List data)
          Answer iterator, which iterates over specified data list according to the specified permutation, that is data.get(p[0]),..,data.get(p[data.length-1])
static java.util.Iterator getIterator(int[] p, java.lang.Object[] data)
          Answer iterator, which iterates over specified data array according to the specified permutation, that is data[p[0]],..,data[p[data.length-1]]
static int[] identity(int n)
          Create identity permutation, that is {0, 1, ..., n}
static int[] inverse(int[] p)
          Compute inverse permutation
static void main(java.lang.String[] args)
          Test method
static java.lang.Object[] permute(int[] p, java.lang.Object[] data, boolean clone)
          Rearrange the specified data according to the specified permutation.
static int[] reverse(int n)
          Create reverse permutation, that is {n-1, ....
static void sort(int[] indices, java.lang.Object[] data, java.util.Comparator comparator)
          Do an unstable sort.
static void sort(int[] indices, java.lang.Object[] data, java.util.Comparator comparator, boolean stable)
          Do a sort on indices.
static int[] sort(java.lang.Object[] data, java.util.Comparator comparator)
          Do an unstable sort.
static int[] sort(java.lang.Object[] data, java.util.Comparator comparator, boolean stable)
          Do a sort on indices.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SortUtils

public SortUtils()
Method Detail

identity

public static int[] identity(int n)
Create identity permutation, that is {0, 1, ..., n}


reverse

public static int[] reverse(int n)
Create reverse permutation, that is {n-1, .... 1, 0}


inverse

public static int[] inverse(int[] p)
Compute inverse permutation


permute

public static java.lang.Object[] permute(int[] p,
                                         java.lang.Object[] data,
                                         boolean clone)
Rearrange the specified data according to the specified permutation. That is, the array is rearranged, such that data_after[p[i]] == data_before[i].

Parameters:
data - data to be permuted
p - the permutation
clone - if true, rearrange a clone instead of the original data;
Returns:
the permuted array (which is the original reference if clone == false)

getIterator

public static java.util.Iterator getIterator(int[] p,
                                             java.lang.Object[] data)
Answer iterator, which iterates over specified data array according to the specified permutation, that is data[p[0]],..,data[p[data.length-1]]


getIterator

public static java.util.Iterator getIterator(int[] p,
                                             java.util.List data)
Answer iterator, which iterates over specified data list according to the specified permutation, that is data.get(p[0]),..,data.get(p[data.length-1])


sort

public static void sort(int[] indices,
                        java.lang.Object[] data,
                        java.util.Comparator comparator,
                        boolean stable)
Do a sort on indices.

Parameters:
data - data to be sorted
comparator - comparator to use
stable - do a stable sort iff true
indices - into data (any permutation of 0,..data.length-1).

sort

public static int[] sort(java.lang.Object[] data,
                         java.util.Comparator comparator,
                         boolean stable)
Do a sort on indices.

Parameters:
data - data to be sorted
comparator - comparator to use
stable - do a stable sort iff true
Returns:
permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order

sort

public static int[] sort(java.lang.Object[] data,
                         java.util.Comparator comparator)
Do an unstable sort.

Parameters:
data - data to be sorted
comparator - comparator to use
Returns:
permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order

sort

public static void sort(int[] indices,
                        java.lang.Object[] data,
                        java.util.Comparator comparator)
Do an unstable sort.

Parameters:
data - data to be sorted
indices - into data (permutation of 0,..data.length-1).

main

public static void main(java.lang.String[] args)
Test method



jHepWork 2.8 (©) S.Chekanov