SSJ
V. labo.

umontreal.iro.lecuyer.util
Class HilbertCurveSplitSort

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

public class HilbertCurveSplitSort
extends Object
implements MultiDimSort

HilbertCurveSplitSort

This sort sort is similar to SplitSort, except that when applying the split sort, the elements are also mapped to the d-dimensional unit hypercube [0, 1)d as explained below, and then re-ordered by following a Hilbert curve. During the split sort, the entire space is actually split into n rectangular boxes, with exactly one point per box. Each box is given a d-dimensional number (or label), as follows, where each coordinate is represented by a binary string. At first, each string is empty. Then, each time a box is split in two according to coordinate j, we add a 0 on the right of the string of coordinate j for the lower box and a 1 for the upper box. At the end, we interpret these strings as fractional binary expansions of new coordinates in [0, 1)d. That is, this labeling maps the points to the unit hypercube. After this labeling, we sort the points exactly as in HilbertCurveSort.

The implementation notes in HilbertCurveBatchSort also apply here.


Constructor Summary
HilbertCurveSplitSort(int d)
          .
 
Method Summary
 int dimension()
          Returns the greatest dimension used in the sort.
 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

HilbertCurveSplitSort

public HilbertCurveSplitSort(int d)
. \begin{tabb}
 Constructs a \class{HilbertCurveSplitSort} that will use the first
 \texttt{d} dimensions to sort.
 \end{tabb}
dmaximum dimension to use for the sort

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

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.