Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
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
- grayCode :: PrecisionNum -> PrecisionNum
- grayCodeInverse :: PrecisionNum -> PrecisionNum
- trailingSetBits :: PrecisionNum -> PrecisionNum
- convertPointToHypercube :: [PrecisionNum] -> Maybe [PrecisionNum]
- convertInteger :: PrecisionNum -> Int -> Int -> Maybe [PrecisionNum]
- numToBool :: PrecisionNum -> [Bool]
- boolToNum :: [Bool] -> Maybe PrecisionNum
- entryPoint :: PrecisionNum -> PrecisionNum
- exitPoint :: PrecisionNum -> PrecisionNum -> PrecisionNum
- direction :: PrecisionNum -> PrecisionNum -> PrecisionNum
- inverseTransform :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum
- transform :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum
- toParameters :: (Ord a, Num a, Integral a) => Int -> Int -> [a] -> Maybe (PrecisionNum, PrecisionNum, [PrecisionNum])
Gray code
grayCode :: PrecisionNum -> PrecisionNum Source
Generate the ith binary reflected graycode given i. See Theorem 2.1 of Hamilton.
grayCodeInverse :: PrecisionNum -> PrecisionNum Source
Generate i given the ith binary reflected graycode.
Bit operations
trailingSetBits :: PrecisionNum -> PrecisionNum Source
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] Source
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] Source
numToBool :: PrecisionNum -> [Bool] Source
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 Source
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 Source
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 Source
Calculate exit point for hypercube based on index. Referred to as f(i) in Hamilton.
direction :: PrecisionNum -> PrecisionNum -> PrecisionNum Source
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 Source
See Section 2.1.3 of Hamilton, 'Rotations and Reflections', which describes transformation of entry and exit points.
transform :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum Source
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]) Source