HilbertCurveBatchSort< T extends MultiDimComparable<? super T > Class Template Reference

This sort is similar to BatchSortPow2, except that after applying the batch sort, the objects are 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. More...

Inheritance diagram for HilbertCurveBatchSort< T extends MultiDimComparable<? super T >:

Collaboration diagram for HilbertCurveBatchSort< T extends MultiDimComparable<? super T >:

Public Member Functions
	HilbertCurveBatchSort (double[] batchExponents, int m)
	Constructs a HilbertCurveBatchSort that will use the \(\alpha_j\) specified in batchesExponents for the batch sort. More...
	HilbertCurveBatchSort (double[] batchExponents, int m, HilbertCurveMap map)
	This constructor is similar to #HilbertCurveBatchSort(double[],int) except that the mapping object is given by the user. More...
void	computeIndexH (int n)
	For the given \(n\), \(e_j\)’s, and \(m\), computes and sort the table that gives the Hilbert index \(r\) of each object from its position after the batch sort. More...
void	sort (T[] a, int iMin, int iMax)
	Sorts the subarray a[iMin..iMax-1] of MultiDimComparable<T> objects with this sort.
void	sort (T[] a)
	Sorts the entire array.
void	sort (double[][] a, int iMin, int iMax)
void	sort (double[][] a)
int	dimension ()
	Returns the dimension of the unit hypercube.
HilbertCurveMap	getHilbertCurveMap ()
	Returns the HilbertCurveMap used for the mapping.

Package Attributes
int	dimension
int	m
HilbertCurveMap	hcMap
BatchSortPow2	bsort
long [][]	indexH
int	nSavedIndex = 0

Detailed Description

This sort is similar to BatchSortPow2, except that after applying the batch sort, the objects are 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 batch sort uses positive integers \(n_0, …, n_{d-1}\), where each \(n_j\) must be a power of 2, say \(n_j = 2^{e_j}\), and one has \(p = n_0 n_1 \cdots n_{d-1} = 2^e \ge n\) where \(n\) is the number of objects to be sorted, \(e = e_0 + \cdots+ e_{d-1}\), and the \(e_j\) are non-negative integers. During the batch sort of \(n\) objects, the entire space is split into \(p = 2^e \ge n\) rectangular boxes, where \(e\) is selected as in BatchSortPow2. The batch sort then places at most one object per box, by separating the objects into \(n_0\) batches using the first coordinate, then each batch into \(n_1\) batches using the second coordinate, and so on.

Each object is then mapped to a point in \([0,1)^d\), and we perform a HilbertCurveSort with \(m = \max(e_0,…,e_{d-1})\), as follows. When separating a batch with respect to coordinate \(j\), the \(n_j\) sub-batches are numbered from 0 to \(n_j-1\), which are \(e_j\)-bit numbers. We multiply them by \(2^{m-e_j}\) to obtain \(m\)-bit numbers which are interpreted as the integer coordinates of the subcubes to which the corresponding points belong for the Hilbert sort. All the objects have distinct vectors of integer coordinates after the batch sort. We then compute the Hilbert index of each subcube as explained in the HilbertCurveSort class, and we sort the points as in HilbertCurveSort.

The latter is implemented by using an index that maps the position (in the array) of an object after the batch sort to its final position after the Hilbert curve sort. For any given \(n\), this mapping is always the same, so it is computed once for all and saved in an index which is used to made the sort. This index is recomputed only when a sort is invoked with a new value of \(n\).

Constructor & Destructor Documentation

HilbertCurveBatchSort() [1/2]

HilbertCurveBatchSort	(	double []	batchExponents,
		int	m
	)

Constructs a HilbertCurveBatchSort that will use the \(\alpha_j\) specified in batchesExponents for the batch sort.

They must be non-negative numbers and their sum must equal 1. The dimension \(d\) of this array will be the dimension for the sort. The Hilbert sort will use \(m\) bits in each coordinate, and thus \(2^{dm}\) subcubes. The constructor will initialize a HilbertCurveMap, which can be accessed with getHilbertCurveMap.

Parameters

batchExponents	proportion exponents \(\alpha_j\) to compute the batches sizes
m	the number of bits for each coordinate

HilbertCurveBatchSort() [2/2]

HilbertCurveBatchSort	(	double []	batchExponents,
		int	m,
		HilbertCurveMap	map
	)

This constructor is similar to #HilbertCurveBatchSort(double[],int) except that the mapping object is given by the user.

This given HilbertCurveMap instance must have the same number of dimensions (which is the value of batchExponents.length) and same number of bits \(m\).

Parameters

batchExponents	proportion exponents \(\alpha_j\) to compute the batches sizes
m	the number of bits for each coordinate
map	the mapping object to use

Member Function Documentation

computeIndexH()

void computeIndexH

(

int

n

)

For the given \(n\), \(e_j\)’s, and \(m\), computes and sort the table that gives the Hilbert index \(r\) of each object from its position after the batch sort.

This index table has size \(n\) by 2, and it is constructed so its row \(i\) contains \(i\) in the first entry and the Hilbert index of object \(i\) (for the given \(m\)) in the second entry. This table is then sorted by the second coordinate and saved.

Parameters

n	number of objects

---

The documentation for this class was generated from the following file:

• HilbertCurveBatchSort.java