SSJ
3.2.1
Stochastic Simulation in Java
|
This class implements the mapping of a Hilbert curve in the \(d\)-dimensional unit hypercube \([0,1)^d\). More...
Public Member Functions | |
HilbertCurveMap (int d, int m) | |
Constructs a HilbertCurveMap object that will use the first \(m\) bits of each of the first d coordinates to sort the points. More... | |
HilbertCurveMap (int d) | |
This constructor is similar to HilbertCurveMap(int,int), but the parameter \(m = \lfloor63/d\rfloor\). More... | |
int | dimension () |
Returns the dimension of the unit hypercube. | |
int | getM () |
Returns the number of bits \(m\) that is used to divide the axis of each coordinate. | |
void | indexToCoordinates (long r, int[] a) |
Takes as input the Hilbert index \(r\) of a subcube and returns in a[] its integer coordinates. More... | |
long | coordinatesToIndex (int a[]) |
Takes as input in a[] the integer coordinates of a subcube and returns the corresponding Hilbert index \(r\). | |
void | pointToCoordinates (double[] p, int[] a) |
Takes in p[] a point with real-valued coordinates and places in a[] the integer coordinates of the corresponding subcube. More... | |
Package Functions | |
void | initTables () |
Package Attributes | |
int | dimension |
int | m |
int | maxnbits |
int | maxlength |
int [] | p_to_s |
int [] | s_to_p |
int [] | p_to_J |
int [] | bit |
int [] | parity |
int [][] | circshift |
int [][] | bitof |
This class implements the mapping of a Hilbert curve in the \(d\)-dimensional unit hypercube \([0,1)^d\).
This mapping can be used for sorting algorithms.
This map (conceptually) divides the unit hypercube \([0,1)^d\) in \(2^{dm}\) subcubes of equal sizes, by dividing each axis in \(2^m\) equal parts, and uses the first \(m\) bits of each of the \(d\) coordinates to place each point in one of the subcubes. It then enumerates the subcubes in the same order as a Hilbert curve in \([0,1)^d\) would visit them, and orders the points accordingly. Each cube has an (integer) Hilbert index \(r\) from 0 to \(2^{dm}-1\) and the cubes (and points) are ordered according to this index. Two points that fall in the same subcube can be placed in an unspecified (arbitrary) order.
For the implementation of sorts based on the Hilbert curve (or Hilbert index), we identify and sort the subcubes by their Hilbert index, but it is also convenient to identify them (alternatively) with \(m\)-bit integer coordinates: The subcube with coordinates \((i_1,…,i_d)\) is defined as \(\prod_{j=0}^{d-1} [i_j 2^{-m}, (i_j+1) 2^{-m})\). Note that each interval is open on the right. That is, if we multiply the coordinates of a point in the subcube by \(2^m\) and truncate them to integers, we obtain the integer coordinates of the subcube. For example, if \(d=2\) and \(m=4\), we have \(2^8 = 256\) subcubes, whose integer coordinates go from 0 to 15, and the point \((0.1, 0.51)\) belongs to the subcube with integer coordinates \((1, 8)\).
For given \(d\) and \(m\), this class offers methods to compute the integer coordinates of the corresponding subcube from the real-valued coordinates of a point in \([0,1)^d\), as well as the Hilbert index of a subcube from its integer coordinates, and vice versa. The code that computes the latter correspondences is taken (with slight adaptations) from the hilbert.c
program of Spencer W. Thomas, University of Michigan, 1991.
HilbertCurveMap | ( | int | d, |
int | m | ||
) |
Constructs a HilbertCurveMap object that will use the first \(m\) bits of each of the first d
coordinates to sort the points.
In this implementation, one must have \(md \le63\).
d | maximum dimension |
m | number of bits used for each coordinate |
HilbertCurveMap | ( | int | d | ) |
This constructor is similar to HilbertCurveMap(int,int), but the parameter \(m = \lfloor63/d\rfloor\).
In this implementation, one must have \(md \le63\).
d | maximum dimension |
void indexToCoordinates | ( | long | r, |
int [] | a | ||
) |
Takes as input the Hilbert index \(r\) of a subcube and returns in a[]
its integer coordinates.
WARNING: This method currently works only for \(m \le9\). It is not used for the sort.
void pointToCoordinates | ( | double [] | p, |
int [] | a | ||
) |
Takes in p[]
a point with real-valued coordinates and places in a[]
the integer coordinates of the corresponding subcube.
The two arrays are assumed to have length \(d\).