module Data.DimensionalHash
(
MortonNumber(..)
) where
import Data.Bits
import Data.Int
import Data.Word
import Control.Exception
import Data.Typeable
class (Bits a, Integral a) => (MortonNumber a) where
dimensionalHash :: (Bits a) => [a] -> a
dimensionalHash [] = 0
dimensionalHash list = hash list 0 (bitSize (head list))
maxBitSize :: (Bits a) => [a] -> Int
maxBitSize list = div (bitSize (head list)) (length list)
maxSize :: (Bits a) => [a] -> Int
maxSize list = 2 ^ (maxBitSize list)
isHashable :: (Bits a) => [a] -> Bool
isHashable [x] = True
isHashable list = (length filteredList) == 0
where
filteredList = filter (\x -> (fromIntegral x) > (maxSize list)) list
instance MortonNumber Integer where
dimensionalHash list = hash list 0 32
maxBitSize list = div 32 (length list)
instance MortonNumber Int8
instance MortonNumber Int32
instance MortonNumber Int64
instance MortonNumber Word
instance MortonNumber Word8
instance MortonNumber Word16
instance MortonNumber Word32
instance MortonNumber Word64
hash :: (Bits a) => [a] -> Int -> Int -> a
hash list n precision
| length list == 1 = head list
| n < precision = (concatBits list n) .|. (hash list (n + 1) precision)
| otherwise = 0
concatBits :: (Bits a) => [a] -> Int -> a
concatBits list n = foldl (\acc x -> acc .|. x) 0 shiftedMap
where
shiftedMap = shiftElements mapList (n * ((length list) 1))
mapList = map (\x -> (takeBitAt x n)) list
shiftElements :: (Bits a) => [a] -> Int -> [a]
shiftElements [] n = []
shiftElements (x:xs) n = [(shiftL x n)] ++ (shiftElements xs (n+1))
takeBitAt :: (Bits a) => a -> Int -> a
takeBitAt x n = x .&. (shiftL 1 n)