SSJ
V. labo.

umontreal.iro.lecuyer.util
Class HilbertCurveBatchSort

java.lang.Object
  extended by umontreal.iro.lecuyer.util.HilbertCurveBatchSort
All Implemented Interfaces:
MultiDimSort

public class HilbertCurveBatchSort
extends Object
implements MultiDimSort

This sort is similar to BatchSort, except that when applying the batch sort, the objects are also given labels that map them to the d-dimensional unit hypercube [0, 1)d as explained below, and then re-ordered by following a Hilbert curve as in the HilbertCurveSort. The user specifies n1,..., nd, where each nj must be a power of 2, say nj = 2ej, and one must have n = n1n2 ... nd = 2e where e = e1 + ... + ed.

During the batch sort of n objects, the entire space is split into n rectangular boxes, with exactly one object per box, by separating the objects into n1 batches of equal size using the first coordinate, then each batch into n2 batches of equal size using the second coordinate, and so on, until each batch has a single object.

Conceptually, each box is given a d-dimensional label, in which coordinate j is represented by a binary string of length ej, which represents the number of the batch that the objects in that box fell in when they were sorted according to coordinate j. At first, each string is empty. Then, whenever a box is split in nj parts according to coordinate j, for each sub-box we set the string of ej bits for coordinate j to the number of the sub-box, for all objects in that sub-box.

At the end, we interpret these strings as fractional binary expansions of new coordinates in [0, 1)d. This labeling maps the points to the unit hypercube. After that labeling, we sort the points exactly as in HilbertCurveSort.


Constructor Summary
HilbertCurveBatchSort(double[] batchesExponents)
          Constructs a HilbertCurveBatchSort that will use batchesExponents.
HilbertCurveBatchSort(int[] batches)
          Constructs a HilbertCurveBatchSort that will use batches.
 
Method Summary
 int dimension()
          Returns the greatest dimension used in the sort.
 void indexBatchsort(long[][] b, int iMin, int iMax)
           
 void sort(double[][] a)
          Sorts the entire array.
 void sort(double[][] a, int iMin, int iMax)
          Sorts the subarray of a made of the elements with indices from iMin to iMax-1.
<T extends MultiDimComparable<? super T>>
void
sort(T[] a)
          Sorts the entire array.
<T extends MultiDimComparable<? super T>>
void
sort(T[] a, int iMin, int iMax)
          Sorts the subarray of a made of the elements with indices from iMin to iMax-1.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

HilbertCurveBatchSort

public HilbertCurveBatchSort(int[] batches)
Constructs a HilbertCurveBatchSort that will use batches. The product of elements in batches must equal the size of the arrays to sort; it is verified in sort.

Parameters:
batches - number of batches in each dimension

HilbertCurveBatchSort

public HilbertCurveBatchSort(double[] batchesExponents)
Constructs a HilbertCurveBatchSort that will use batchesExponents. Sum of batchesExponents must equal 1 or an IllegalArgumentException is thrown.

Parameters:
batchesExponents - exponents to compute the batches sizes
Method Detail

sort

public <T extends MultiDimComparable<? super T>> void sort(T[] a,
                                                           int iMin,
                                                           int iMax)
Description copied from interface: MultiDimSort
Sorts the subarray of a made of the elements with indices from iMin to iMax-1.

Specified by:
sort in interface MultiDimSort
Parameters:
a - array to sort
iMin - index of first element to sort
iMax - index of last element to sort is iMax - 1

sort

public <T extends MultiDimComparable<? super T>> void sort(T[] a)
Description copied from interface: MultiDimSort
Sorts the entire array.

Specified by:
sort in interface MultiDimSort
Parameters:
a - array to sort

sort

public void sort(double[][] a,
                 int iMin,
                 int iMax)
Description copied from interface: MultiDimSort
Sorts the subarray of a made of the elements with indices from iMin to iMax-1.

Specified by:
sort in interface MultiDimSort
Parameters:
a - array to sort
iMin - index of first element to sort
iMax - index of last element to sort is iMax - 1

indexBatchsort

public void indexBatchsort(long[][] b,
                           int iMin,
                           int iMax)

sort

public void sort(double[][] a)
Description copied from interface: MultiDimSort
Sorts the entire array.

Specified by:
sort in interface MultiDimSort
Parameters:
a - array to sort

dimension

public int dimension()
Description copied from interface: MultiDimSort
Returns the greatest dimension used in the sort.

Specified by:
dimension in interface MultiDimSort
Returns:
greatest dimension used for the sort

SSJ
V. labo.

To submit a bug or ask questions, send an e-mail to Pierre L'Ecuyer.