--
-- Morton number generator
-- Can be used as a 2 or 3 dimensional hash

module Data.DimensionalHash  
(
  MortonNumber(..)
) where


import Data.Bits

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

	-- 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

instance MortonNumber Integer