DimensionalHash 0.0 → 0.1

raw patch · 2 files changed

+41/−30 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/DimensionalHash.hs +36/−25
• DimensionalHash.cabal +5/−5

@@ -1,37 +1,48 @@ --
 -- Morton number generator
--- Can be used as a 2 or 3 dimensional hash
+-- Can be used for n-dimensional hash
 
 module Data.DimensionalHash  
 (
   MortonNumber(..)
 ) where
 
-
 import Data.Bits
+import Data.Int
+import Data.Word
 
-class (Bits a) => (MortonNumber a) where
-	-- 3d morton number generation
-	toMortonNumber3d :: a -> a -> a -> a
-	toMortonNumber3d x y z =
-			x4 .|. (shift y 1) .|. (shift z 2)
-		where 
-			x1 = (x  .|. (shift x 16)) .&. 0x030000FF
-			x2 = (x1 .|. (shift x1 8)) .&. 0x0300F00F
-			x3 = (x2 .|. (shift x2 4)) .&. 0x030C30C3
-			x4 = (x3 .|. (shift x3 2)) .&. 0x09249249
+takeBitAt :: (Bits a) => a -> Int -> a
+takeBitAt x n = x .&. (shift 1 n)
 
-	-- 2d morton number generation		
-	toMortonNumber2d :: a -> a -> a
-	toMortonNumber2d x y = x4 .|. (shift y4 1)
-		where
-			x1 = (x  .|. (shift x  8)) .&. 0x00FF00FF
-			x2 = (x1 .|. (shift x1 4)) .&. 0x0F0F0F0F
-			x3 = (x2 .|. (shift x2 2)) .&. 0x33333333
-			x4 = (x3 .|. (shift x3 1)) .&. 0x55555555
-			y1 = (y  .|. (shift y  8)) .&. 0x00FF00FF
-			y2 = (y1 .|. (shift y1 4)) .&. 0x0F0F0F0F
-			y3 = (y2 .|. (shift y2 2)) .&. 0x33333333
-			y4 = (y3 .|. (shift y3 1)) .&. 0x55555555
+shiftElements :: (Bits a) => [a] -> Int -> [a]
+shiftElements [] n = []
+shiftElements (x:xs) n = [(shift x n)] ++ (shiftElements xs (n+1))
 
-instance MortonNumber Integer
+concatBits :: (Bits a) => [a] -> Int -> a
+concatBits list n = foldl (\acc x -> acc .|. x) 0 shiftedMap
+	where 	
+		shiftedMap = shiftElements mapList n
+		mapList = map (\x -> (takeBitAt x n)) list
+
+hash :: (Bits a) => [a] -> Int -> Int -> a
+hash list n precision
+	| n < precision = (concatBits list n) .|. (hash list (n + 1) precision)
+	| otherwise = concatBits list precision
+
+class (Bits a) => (MortonNumber a) where	
+	dimensionalHash :: (Bits a) => [a] -> a
+	dimensionalHash list = hash list 0 (bitSize (head list))
+
+instance MortonNumber Integer where
+	dimensionalHash list = hash list 0 32
+
+instance MortonNumber Int8
+instance MortonNumber Int32
+instance MortonNumber Int64
+
+instance MortonNumber Word
+instance MortonNumber Word8
+instance MortonNumber Word16
+instance MortonNumber Word32
+instance MortonNumber Word64
+

@@ -1,5 +1,5 @@ name:          DimensionalHash
-version:       0.0
+version:       0.1
 build-Type:    Simple
 cabal-version: >= 1.6
 tested-with:   GHC == 7.0.3
@@ -8,10 +8,10 @@ author:        Ghassen Hamrouni
 maintainer:    ghamrouni@iptechinside.com
 category:      Data, Algorithms
-synopsis:      2 and 3 dimensional hash using Morton numbers.
-description:   This library compute the Morton numbers in 2d and 3d. 
-			   It transforms integers x, y to a single integer z.
-               The hash z has the property : if (x, y) and (x2, y2) 
+synopsis:      An n-dimensional hash using Morton numbers.
+description:   This library compute an n-dimensional hash. 
+			   It transforms a list of integers [x .. y] to a single integer z.
+               The hash z has the property : if (x1 .. xn) and (y1 .. yn) 
                are close then their Morton numbers are close.
 library				
   build-Depends:  base >= 3 && < 5