Data.Algorithm.Hilbert.Utility

The following module implements Compact Hilbert Indices - Technical Report -- CS-2006-07 by Chris Hamilton. At the time of writing this comment, the document is found at: https://www.cs.dal.ca/sites/default/files/technical_reports/CS-2006-07.pdf

Gray code

grayCode :: PrecisionNum -> PrecisionNum

Generate the ith binary reflected graycode given i. See Theorem 2.1 of Hamilton.

grayCodeInverse :: PrecisionNum -> PrecisionNum

Generate i given the ith binary reflected graycode.

Bit operations

trailingSetBits :: PrecisionNum -> PrecisionNum

Lemma 2.3 of Hamilton's paper deals with the dimension of the gray code change at any point in the sequence it depends on the number of bits that are set in the item of the sequence just before that point. For example, in the sequence below, the value in the trailingSetBits column for each entry predicts the position of the bracketed, changed number in the following row.

  i   | grayCode i | trailingSetBits i   
  ------------------------------------ 
  0   | 000        |  0 
  1   | 00(1)      |  1 
  2   | 0(1)1      |  0  
  3   | 01(0)      |  2 
  4   | (1)10      |  0   

convertPointToHypercube :: [PrecisionNum] -> Maybe [PrecisionNum]

convertPointToHypercube relates to s 2.1.4 Algorithms of Hamilton, and specifically the transformation of p (a vector of points) into l, by a formula l_(m-1) = [bit (p_(n-1), m - 1) ... bit (p_0, m - 1)]

An example is perhaps helpful in understanding what it does.

Given a list of n integers: [1, 2, 3], their binary representation is

| 0 0 1 | 
| 0 1 0 | 
| 0 1 1 | 

Transpose the above representation, to form a row from each column,

| 0 0 0 | 
| 0 1 1 | 
| 1 0 1 | 

The transposed representation is converted back to a list of integers [ 0, 3, 5] Eg:

convertPointToHypercube ([1, 2, 3]) 3 
= [0, 3, 5] 

Each integer in the list successively identifies a subhypercube in which our original point exists. That is, to calculate the Hilbert index of the point [1, 2, 3], we traverse subhypercubes identified by [0, 3, 5]

Each subhypercube co-ordinate is large enough to uniquely identify any vertex. This depends only on the dimension When convertPointToHypercube is called from pointToIndex, it is passed in the Hilbert curve order as the number of bits, and a list representing a point on the curve as the vector p.

In that situation it will return a list having a length equal to the order of the Hilbert curve, in which each element of the list is representable in less than 2^dimension.

convertInteger :: PrecisionNum -> Int -> Int -> Maybe [PrecisionNum]

numToBool :: PrecisionNum -> [Bool]

Convert an integer to a list of Bools corresponding to its binary representation. For example, to represent the integer 3 in 4 bits:

numToBool (3::Int) 4
= [True,True,False,False]

boolToNum :: [Bool] -> Maybe PrecisionNum

Convert a list of Bool representation of an integer to an integer. For example, to obtain an integer from its binary representation: Assumes that the precision of the returned value should be equal to the number of bits that were provided. > boolToNum [False, True, True, True] > = 14

entryPoint :: PrecisionNum -> PrecisionNum

Calculate entry point for hypercube based on index. Referred to as e(i) in Hamilton. Is the return type here just a [Hypercube a]?

exitPoint :: PrecisionNum -> PrecisionNum -> PrecisionNum

Calculate exit point for hypercube based on index. Referred to as f(i) in Hamilton.

direction :: PrecisionNum -> PrecisionNum -> PrecisionNum

Lemma 2.8 Calculate the direction in the hypercube. Referred to as the intra sub-hypercube dimension, d(i) Note that n doesn't come into play as long as i < 2^n - 1 - which means that we really need to consider whether its worth passing n, or just limiting i in the beginning.

inverseTransform :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum

See Section 2.1.3 of Hamilton, 'Rotations and Reflections', which describes transformation of entry and exit points.

transform :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum

See Section 2.1.3 of Hamilton, 'Rotations and Reflections', which describes transformation of entry and exit points. The rotation in this function needs to be performed with a bit size equal to the dimension of the problem. assert(b < 2^dimension && e < 2^dimension)

toParameters :: (Ord a, Num a, Integral a) => Int -> Int -> [a] -> Maybe (PrecisionNum, PrecisionNum, [PrecisionNum])