|
SSJ V. labo. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectumontreal.iro.lecuyer.util.HilbertCurveBatchSort
public class HilbertCurveBatchSort
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. |
|
|
sort(T[] a)
Sorts the entire array. |
|
|
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 |
---|
public HilbertCurveBatchSort(int[] batches)
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
.
batches
- number of batches in each dimensionpublic HilbertCurveBatchSort(double[] batchesExponents)
HilbertCurveBatchSort
that will use
batchesExponents. Sum of batchesExponents must
equal 1 or an IllegalArgumentException
is thrown.
batchesExponents
- exponents to compute the batches sizesMethod Detail |
---|
public <T extends MultiDimComparable<? super T>> void sort(T[] a, int iMin, int iMax)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortiMin
- index of first element to sortiMax
- index of last element to sort is
public <T extends MultiDimComparable<? super T>> void sort(T[] a)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortpublic void sort(double[][] a, int iMin, int iMax)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortiMin
- index of first element to sortiMax
- index of last element to sort is
public void indexBatchsort(long[][] b, int iMin, int iMax)
public void sort(double[][] a)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortpublic int dimension()
MultiDimSort
dimension
in interface MultiDimSort
|
SSJ V. labo. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |