{-# LANGUAGE CPP #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE TypeApplications #-}

-- |
-- Module:      Data.Chimera.ContinuousMapping
-- Copyright:   (c) 2017 Andrew Lelechenko
-- Licence:     BSD3
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Helpers for continuous mappings, useful to memoize
-- functions on 'Int' (instead of 'Word' only) and
-- functions over two and three arguments.
--
-- __Example 1__
--
-- Imagine writing a program to simulate
-- <https://en.wikipedia.org/wiki/Rule_90 Rule 90>.
-- This is a cellular automaton,
-- which consists of an infinite one-dimensional line of cells,
-- each being either dead ('False') or alive ('True').
-- If two neighbours of a cell are equal,
-- it becomes dead on the next step, otherwise alive.
--
-- Usually cellular automata are modelled by a finite vector.
-- This is a bit suboptimal, because cellular automata
-- may grow in different directions over time, but with
-- a finite vector one has to define a bounding segment well beforehand.
-- Moreover, what if we are interested to explore
-- an evolution of an essentially infinite initial configuration?
--
-- It would be natural to encode an initial configuration
-- as a function 'Int' @->@ 'Bool', which takes a coordinate
-- and returns the status of the corresponding cell. Define
-- a function, which translates the automaton to the next step:
--
-- > step :: (Int -> Bool) -> (Int -> Bool)
-- > step current = \n -> current (n - 1) /= current (n + 1)
--
-- Unfortunately, iterating @step@ would be extremely slow
-- because of branching recursion. One
-- could suggest to introduce a caching layer:
--
-- > step :: (Int -> Bool) -> (Int -> Bool)
-- > step current = \n -> current' (n - 1) /= current' (n + 1)
-- >   where
-- >     current' = memoize (current . fromIntegral) . fromIntegral
--
-- Unfortunately, it would not work well,
-- because 'fromIntegral' @::@ 'Int' @->@ 'Word'
-- maps @-1@ to 'maxBound' and it would take ages to memoize
-- everything up to 'maxBound'.
-- But continuous mappings 'intToWord' and 'wordToInt' avoid this issue:
--
-- > step :: (Int -> Bool) -> (Int -> Bool)
-- > step current = \n -> current' (n - 1) /= current' (n + 1)
-- >   where
-- >     current' = memoize (current . wordToInt) . intToWord
--
-- __Example 2__
--
-- What about another famous cellular automaton:
-- <https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life Conway's Game of Life>?
-- It is two-dimensional, so its state can be represented as
-- a function 'Int' @->@ 'Int' @->@ 'Bool'. Following the approach above,
-- we would like to memoize such functions.
-- Namely, cast the state to 'Word' @->@ 'Bool', ready for memoization:
--
-- > cast :: (Int -> Int -> Bool) -> (Word -> Bool)
-- > cast f = \n -> let (x, y) = fromZCurve n in f (fromHalf x) (fromHalf y)
-- >   where
-- >     fromHalf :: HalfWord -> Int
-- >     fromHalf = wordToInt . fromIntegral @HalfWord @Word
--
-- and then back:
--
-- > uncast :: (Word -> Bool) -> (Int -> Int -> Bool)
-- > uncast g = \x y -> g (toZCurve (toHalf x) (toHalf y))
-- >   where
-- >     toHalf :: Int -> HalfWord
-- >     toHalf = fromIntegral @Word @HalfWord . intToWord
module Data.Chimera.ContinuousMapping (
  intToWord,
  wordToInt,
  HalfWord,
  toZCurve,
  fromZCurve,
  throughZCurveFix,
  ThirdWord,
  toZCurve3,
  fromZCurve3,
  throughZCurveFix3,
) where

import Data.Bifunctor
import Data.Bits
import Data.Chimera.FromIntegral
import Data.Coerce
import Data.Word

#include "MachDeps.h"

-- | Total map, which satisfies
--
-- prop> abs (intToWord x - intToWord y) <= 2 * abs (x - y)
--
-- Note that usual 'fromIntegral' @::@ 'Int' @->@ 'Word' does not
-- satisfy this inequality,
-- because it has a discontinuity between −1 and 0.
--
-- >>> map intToWord [-5..5]
-- [9,7,5,3,1,0,2,4,6,8,10]
--
-- @since 0.2.0.0
intToWord :: Int -> Word
intToWord :: Int -> Word
intToWord Int
i = (if Word
sign Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0 then Word -> Word
forall a. a -> a
id else Word -> Word
forall a. Bits a => a -> a
complement) (Int -> Word
int2word Int
i) Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
sign
  where
    sign :: Word
sign = Int -> Word
int2word Int
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` (Int -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
{-# INLINE intToWord #-}

-- | Inverse for 'intToWord'.
--
-- >>> map wordToInt [0..10]
-- [0,-1,1,-2,2,-3,3,-4,4,-5,5]
--
-- @since 0.2.0.0
wordToInt :: Word -> Int
wordToInt :: Word -> Int
wordToInt Word
w = Word -> Int
word2int (Word -> Int) -> Word -> Int
forall a b. (a -> b) -> a -> b
$ (if Word
w Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0 then Word -> Word
forall a. a -> a
id else Word -> Word
forall a. Bits a => a -> a
complement) (Word
w Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
1)
{-# INLINE wordToInt #-}

-- | 32 bits on 64-bit architecture, 16 bits on 32-bit architecture.
--
-- To create a value of type 'HalfWord' use 'fromIntegral'.
--
-- @since 0.4.0.0
#if WORD_SIZE_IN_BITS == 64
newtype HalfWord = HalfWord Word32
  deriving newtype (HalfWord -> HalfWord -> Bool
(HalfWord -> HalfWord -> Bool)
-> (HalfWord -> HalfWord -> Bool) -> Eq HalfWord
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: HalfWord -> HalfWord -> Bool
== :: HalfWord -> HalfWord -> Bool
$c/= :: HalfWord -> HalfWord -> Bool
/= :: HalfWord -> HalfWord -> Bool
Eq, Eq HalfWord
Eq HalfWord =>
(HalfWord -> HalfWord -> Ordering)
-> (HalfWord -> HalfWord -> Bool)
-> (HalfWord -> HalfWord -> Bool)
-> (HalfWord -> HalfWord -> Bool)
-> (HalfWord -> HalfWord -> Bool)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> Ord HalfWord
HalfWord -> HalfWord -> Bool
HalfWord -> HalfWord -> Ordering
HalfWord -> HalfWord -> HalfWord
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: HalfWord -> HalfWord -> Ordering
compare :: HalfWord -> HalfWord -> Ordering
$c< :: HalfWord -> HalfWord -> Bool
< :: HalfWord -> HalfWord -> Bool
$c<= :: HalfWord -> HalfWord -> Bool
<= :: HalfWord -> HalfWord -> Bool
$c> :: HalfWord -> HalfWord -> Bool
> :: HalfWord -> HalfWord -> Bool
$c>= :: HalfWord -> HalfWord -> Bool
>= :: HalfWord -> HalfWord -> Bool
$cmax :: HalfWord -> HalfWord -> HalfWord
max :: HalfWord -> HalfWord -> HalfWord
$cmin :: HalfWord -> HalfWord -> HalfWord
min :: HalfWord -> HalfWord -> HalfWord
Ord, Int -> HalfWord -> ShowS
[HalfWord] -> ShowS
HalfWord -> String
(Int -> HalfWord -> ShowS)
-> (HalfWord -> String) -> ([HalfWord] -> ShowS) -> Show HalfWord
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> HalfWord -> ShowS
showsPrec :: Int -> HalfWord -> ShowS
$cshow :: HalfWord -> String
show :: HalfWord -> String
$cshowList :: [HalfWord] -> ShowS
showList :: [HalfWord] -> ShowS
Show, ReadPrec [HalfWord]
ReadPrec HalfWord
Int -> ReadS HalfWord
ReadS [HalfWord]
(Int -> ReadS HalfWord)
-> ReadS [HalfWord]
-> ReadPrec HalfWord
-> ReadPrec [HalfWord]
-> Read HalfWord
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: Int -> ReadS HalfWord
readsPrec :: Int -> ReadS HalfWord
$creadList :: ReadS [HalfWord]
readList :: ReadS [HalfWord]
$creadPrec :: ReadPrec HalfWord
readPrec :: ReadPrec HalfWord
$creadListPrec :: ReadPrec [HalfWord]
readListPrec :: ReadPrec [HalfWord]
Read, Eq HalfWord
HalfWord
Eq HalfWord =>
(HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> HalfWord
-> (Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> Bool)
-> (HalfWord -> Maybe Int)
-> (HalfWord -> Int)
-> (HalfWord -> Bool)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int -> HalfWord)
-> (HalfWord -> Int)
-> Bits HalfWord
Int -> HalfWord
HalfWord -> Bool
HalfWord -> Int
HalfWord -> Maybe Int
HalfWord -> HalfWord
HalfWord -> Int -> Bool
HalfWord -> Int -> HalfWord
HalfWord -> HalfWord -> HalfWord
forall a.
Eq a =>
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> a
-> (Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> Bool)
-> (a -> Maybe Int)
-> (a -> Int)
-> (a -> Bool)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int)
-> Bits a
$c.&. :: HalfWord -> HalfWord -> HalfWord
.&. :: HalfWord -> HalfWord -> HalfWord
$c.|. :: HalfWord -> HalfWord -> HalfWord
.|. :: HalfWord -> HalfWord -> HalfWord
$cxor :: HalfWord -> HalfWord -> HalfWord
xor :: HalfWord -> HalfWord -> HalfWord
$ccomplement :: HalfWord -> HalfWord
complement :: HalfWord -> HalfWord
$cshift :: HalfWord -> Int -> HalfWord
shift :: HalfWord -> Int -> HalfWord
$crotate :: HalfWord -> Int -> HalfWord
rotate :: HalfWord -> Int -> HalfWord
$czeroBits :: HalfWord
zeroBits :: HalfWord
$cbit :: Int -> HalfWord
bit :: Int -> HalfWord
$csetBit :: HalfWord -> Int -> HalfWord
setBit :: HalfWord -> Int -> HalfWord
$cclearBit :: HalfWord -> Int -> HalfWord
clearBit :: HalfWord -> Int -> HalfWord
$ccomplementBit :: HalfWord -> Int -> HalfWord
complementBit :: HalfWord -> Int -> HalfWord
$ctestBit :: HalfWord -> Int -> Bool
testBit :: HalfWord -> Int -> Bool
$cbitSizeMaybe :: HalfWord -> Maybe Int
bitSizeMaybe :: HalfWord -> Maybe Int
$cbitSize :: HalfWord -> Int
bitSize :: HalfWord -> Int
$cisSigned :: HalfWord -> Bool
isSigned :: HalfWord -> Bool
$cshiftL :: HalfWord -> Int -> HalfWord
shiftL :: HalfWord -> Int -> HalfWord
$cunsafeShiftL :: HalfWord -> Int -> HalfWord
unsafeShiftL :: HalfWord -> Int -> HalfWord
$cshiftR :: HalfWord -> Int -> HalfWord
shiftR :: HalfWord -> Int -> HalfWord
$cunsafeShiftR :: HalfWord -> Int -> HalfWord
unsafeShiftR :: HalfWord -> Int -> HalfWord
$crotateL :: HalfWord -> Int -> HalfWord
rotateL :: HalfWord -> Int -> HalfWord
$crotateR :: HalfWord -> Int -> HalfWord
rotateR :: HalfWord -> Int -> HalfWord
$cpopCount :: HalfWord -> Int
popCount :: HalfWord -> Int
Bits, Bits HalfWord
Bits HalfWord =>
(HalfWord -> Int)
-> (HalfWord -> Int) -> (HalfWord -> Int) -> FiniteBits HalfWord
HalfWord -> Int
forall b.
Bits b =>
(b -> Int) -> (b -> Int) -> (b -> Int) -> FiniteBits b
$cfiniteBitSize :: HalfWord -> Int
finiteBitSize :: HalfWord -> Int
$ccountLeadingZeros :: HalfWord -> Int
countLeadingZeros :: HalfWord -> Int
$ccountTrailingZeros :: HalfWord -> Int
countTrailingZeros :: HalfWord -> Int
FiniteBits, HalfWord
HalfWord -> HalfWord -> Bounded HalfWord
forall a. a -> a -> Bounded a
$cminBound :: HalfWord
minBound :: HalfWord
$cmaxBound :: HalfWord
maxBound :: HalfWord
Bounded, Int -> HalfWord
HalfWord -> Int
HalfWord -> [HalfWord]
HalfWord -> HalfWord
HalfWord -> HalfWord -> [HalfWord]
HalfWord -> HalfWord -> HalfWord -> [HalfWord]
(HalfWord -> HalfWord)
-> (HalfWord -> HalfWord)
-> (Int -> HalfWord)
-> (HalfWord -> Int)
-> (HalfWord -> [HalfWord])
-> (HalfWord -> HalfWord -> [HalfWord])
-> (HalfWord -> HalfWord -> [HalfWord])
-> (HalfWord -> HalfWord -> HalfWord -> [HalfWord])
-> Enum HalfWord
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
$csucc :: HalfWord -> HalfWord
succ :: HalfWord -> HalfWord
$cpred :: HalfWord -> HalfWord
pred :: HalfWord -> HalfWord
$ctoEnum :: Int -> HalfWord
toEnum :: Int -> HalfWord
$cfromEnum :: HalfWord -> Int
fromEnum :: HalfWord -> Int
$cenumFrom :: HalfWord -> [HalfWord]
enumFrom :: HalfWord -> [HalfWord]
$cenumFromThen :: HalfWord -> HalfWord -> [HalfWord]
enumFromThen :: HalfWord -> HalfWord -> [HalfWord]
$cenumFromTo :: HalfWord -> HalfWord -> [HalfWord]
enumFromTo :: HalfWord -> HalfWord -> [HalfWord]
$cenumFromThenTo :: HalfWord -> HalfWord -> HalfWord -> [HalfWord]
enumFromThenTo :: HalfWord -> HalfWord -> HalfWord -> [HalfWord]
Enum, Integer -> HalfWord
HalfWord -> HalfWord
HalfWord -> HalfWord -> HalfWord
(HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord)
-> (HalfWord -> HalfWord)
-> (HalfWord -> HalfWord)
-> (Integer -> HalfWord)
-> Num HalfWord
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
$c+ :: HalfWord -> HalfWord -> HalfWord
+ :: HalfWord -> HalfWord -> HalfWord
$c- :: HalfWord -> HalfWord -> HalfWord
- :: HalfWord -> HalfWord -> HalfWord
$c* :: HalfWord -> HalfWord -> HalfWord
* :: HalfWord -> HalfWord -> HalfWord
$cnegate :: HalfWord -> HalfWord
negate :: HalfWord -> HalfWord
$cabs :: HalfWord -> HalfWord
abs :: HalfWord -> HalfWord
$csignum :: HalfWord -> HalfWord
signum :: HalfWord -> HalfWord
$cfromInteger :: Integer -> HalfWord
fromInteger :: Integer -> HalfWord
Num, Enum HalfWord
Real HalfWord
(Real HalfWord, Enum HalfWord) =>
(HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> HalfWord)
-> (HalfWord -> HalfWord -> (HalfWord, HalfWord))
-> (HalfWord -> HalfWord -> (HalfWord, HalfWord))
-> (HalfWord -> Integer)
-> Integral HalfWord
HalfWord -> Integer
HalfWord -> HalfWord -> (HalfWord, HalfWord)
HalfWord -> HalfWord -> HalfWord
forall a.
(Real a, Enum a) =>
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> (a, a))
-> (a -> a -> (a, a))
-> (a -> Integer)
-> Integral a
$cquot :: HalfWord -> HalfWord -> HalfWord
quot :: HalfWord -> HalfWord -> HalfWord
$crem :: HalfWord -> HalfWord -> HalfWord
rem :: HalfWord -> HalfWord -> HalfWord
$cdiv :: HalfWord -> HalfWord -> HalfWord
div :: HalfWord -> HalfWord -> HalfWord
$cmod :: HalfWord -> HalfWord -> HalfWord
mod :: HalfWord -> HalfWord -> HalfWord
$cquotRem :: HalfWord -> HalfWord -> (HalfWord, HalfWord)
quotRem :: HalfWord -> HalfWord -> (HalfWord, HalfWord)
$cdivMod :: HalfWord -> HalfWord -> (HalfWord, HalfWord)
divMod :: HalfWord -> HalfWord -> (HalfWord, HalfWord)
$ctoInteger :: HalfWord -> Integer
toInteger :: HalfWord -> Integer
Integral, Num HalfWord
Ord HalfWord
(Num HalfWord, Ord HalfWord) =>
(HalfWord -> Rational) -> Real HalfWord
HalfWord -> Rational
forall a. (Num a, Ord a) => (a -> Rational) -> Real a
$ctoRational :: HalfWord -> Rational
toRational :: HalfWord -> Rational
Real)
#else
newtype HalfWord = HalfWord Word16
  deriving newtype (Eq, Ord, Show, Read, Bits, FiniteBits, Bounded, Enum, Num, Integral, Real)
#endif

-- | Total map from plain to line, continuous almost everywhere.
-- See <https://en.wikipedia.org/wiki/Z-order_curve Z-order curve>.
--
-- >>> [ toZCurve x y | x <- [0..3], y <- [0..3] ]
-- [0,2,8,10,1,3,9,11,4,6,12,14,5,7,13,15]
--
-- @since 0.2.0.0
toZCurve :: HalfWord -> HalfWord -> Word
toZCurve :: HalfWord -> HalfWord -> Word
toZCurve HalfWord
x HalfWord
y = HalfWord -> Word
part1by1 HalfWord
y Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. HalfWord -> Word
part1by1 HalfWord
x

-- | Inverse for 'toZCurve'.
-- See <https://en.wikipedia.org/wiki/Z-order_curve Z-order curve>.
--
-- >>> map fromZCurve [0..15]
-- [(0,0),(1,0),(0,1),(1,1),(2,0),(3,0),(2,1),(3,1),(0,2),(1,2),(0,3),(1,3),(2,2),(3,2),(2,3),(3,3)]
--
-- @since 0.2.0.0
fromZCurve :: Word -> (HalfWord, HalfWord)
fromZCurve :: Word -> (HalfWord, HalfWord)
fromZCurve Word
z = (Word -> HalfWord
compact1by1 Word
z, Word -> HalfWord
compact1by1 (Word
z Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
1))

-- | Convert a function of two 'HalfWord's to a function of one 'Word'.
contramapFromZCurve
  :: (HalfWord -> HalfWord -> a)
  -> (Word -> a)
contramapFromZCurve :: forall a. (HalfWord -> HalfWord -> a) -> Word -> a
contramapFromZCurve HalfWord -> HalfWord -> a
f = (HalfWord -> HalfWord -> a) -> (HalfWord, HalfWord) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry HalfWord -> HalfWord -> a
f ((HalfWord, HalfWord) -> a)
-> (Word -> (HalfWord, HalfWord)) -> Word -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> (HalfWord, HalfWord)
fromZCurve

-- | Convert a function of one 'Word' to a function of two 'HalfWord's.
contramapToZCurve
  :: (Word -> a)
  -> (HalfWord -> HalfWord -> a)
contramapToZCurve :: forall a. (Word -> a) -> HalfWord -> HalfWord -> a
contramapToZCurve Word -> a
f = (Word -> a
f (Word -> a) -> (HalfWord -> Word) -> HalfWord -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((HalfWord -> Word) -> HalfWord -> a)
-> (HalfWord -> HalfWord -> Word) -> HalfWord -> HalfWord -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HalfWord -> HalfWord -> Word
toZCurve

-- | For an input function @f@ return function @g@ such that
-- 'Data.Function.fix' @f@ = ('Data.Function.fix' @g@ '.') '.' 'toZCurve'.
--
-- @since 0.4.0.0
throughZCurveFix
  :: ((HalfWord -> HalfWord -> a) -> (HalfWord -> HalfWord -> a))
  -> (Word -> a)
  -> (Word -> a)
throughZCurveFix :: forall a.
((HalfWord -> HalfWord -> a) -> HalfWord -> HalfWord -> a)
-> (Word -> a) -> Word -> a
throughZCurveFix (HalfWord -> HalfWord -> a) -> HalfWord -> HalfWord -> a
f = (HalfWord -> HalfWord -> a) -> Word -> a
forall a. (HalfWord -> HalfWord -> a) -> Word -> a
contramapFromZCurve ((HalfWord -> HalfWord -> a) -> Word -> a)
-> ((Word -> a) -> HalfWord -> HalfWord -> a)
-> (Word -> a)
-> Word
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (HalfWord -> HalfWord -> a) -> HalfWord -> HalfWord -> a
f ((HalfWord -> HalfWord -> a) -> HalfWord -> HalfWord -> a)
-> ((Word -> a) -> HalfWord -> HalfWord -> a)
-> (Word -> a)
-> HalfWord
-> HalfWord
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> a) -> HalfWord -> HalfWord -> a
forall a. (Word -> a) -> HalfWord -> HalfWord -> a
contramapToZCurve

-- | 21 bits on 64-bit architecture, 10 bits on 32-bit architecture.
--
-- To create a value of type 'ThirdWord' use 'fromIntegral'.
--
-- @since 0.4.0.0
newtype ThirdWord = ThirdWord Word32
  deriving newtype (ThirdWord -> ThirdWord -> Bool
(ThirdWord -> ThirdWord -> Bool)
-> (ThirdWord -> ThirdWord -> Bool) -> Eq ThirdWord
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: ThirdWord -> ThirdWord -> Bool
== :: ThirdWord -> ThirdWord -> Bool
$c/= :: ThirdWord -> ThirdWord -> Bool
/= :: ThirdWord -> ThirdWord -> Bool
Eq, Eq ThirdWord
Eq ThirdWord =>
(ThirdWord -> ThirdWord -> Ordering)
-> (ThirdWord -> ThirdWord -> Bool)
-> (ThirdWord -> ThirdWord -> Bool)
-> (ThirdWord -> ThirdWord -> Bool)
-> (ThirdWord -> ThirdWord -> Bool)
-> (ThirdWord -> ThirdWord -> ThirdWord)
-> (ThirdWord -> ThirdWord -> ThirdWord)
-> Ord ThirdWord
ThirdWord -> ThirdWord -> Bool
ThirdWord -> ThirdWord -> Ordering
ThirdWord -> ThirdWord -> ThirdWord
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: ThirdWord -> ThirdWord -> Ordering
compare :: ThirdWord -> ThirdWord -> Ordering
$c< :: ThirdWord -> ThirdWord -> Bool
< :: ThirdWord -> ThirdWord -> Bool
$c<= :: ThirdWord -> ThirdWord -> Bool
<= :: ThirdWord -> ThirdWord -> Bool
$c> :: ThirdWord -> ThirdWord -> Bool
> :: ThirdWord -> ThirdWord -> Bool
$c>= :: ThirdWord -> ThirdWord -> Bool
>= :: ThirdWord -> ThirdWord -> Bool
$cmax :: ThirdWord -> ThirdWord -> ThirdWord
max :: ThirdWord -> ThirdWord -> ThirdWord
$cmin :: ThirdWord -> ThirdWord -> ThirdWord
min :: ThirdWord -> ThirdWord -> ThirdWord
Ord, Int -> ThirdWord -> ShowS
[ThirdWord] -> ShowS
ThirdWord -> String
(Int -> ThirdWord -> ShowS)
-> (ThirdWord -> String)
-> ([ThirdWord] -> ShowS)
-> Show ThirdWord
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> ThirdWord -> ShowS
showsPrec :: Int -> ThirdWord -> ShowS
$cshow :: ThirdWord -> String
show :: ThirdWord -> String
$cshowList :: [ThirdWord] -> ShowS
showList :: [ThirdWord] -> ShowS
Show)

mkThirdWord :: Word32 -> ThirdWord
mkThirdWord :: Word32 -> ThirdWord
mkThirdWord Word32
n = ThirdWord
t
  where
    t :: ThirdWord
t = Word32 -> ThirdWord
ThirdWord (Word32
n Word32 -> Word32 -> Word32
forall a. Bits a => a -> a -> a
.&. ((Word32
1 Word32 -> Int -> Word32
forall a. Bits a => a -> Int -> a
`shiftL` ThirdWord -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize ThirdWord
t) Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
- Word32
1))

instance Read ThirdWord where
  readsPrec :: Int -> ReadS ThirdWord
readsPrec = (((Word32, String) -> (ThirdWord, String))
-> [(Word32, String)] -> [(ThirdWord, String)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Word32 -> ThirdWord) -> (Word32, String) -> (ThirdWord, String)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Word32 -> ThirdWord
mkThirdWord) ([(Word32, String)] -> [(ThirdWord, String)])
-> ReadS Word32 -> ReadS ThirdWord
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) (ReadS Word32 -> ReadS ThirdWord)
-> (Int -> ReadS Word32) -> Int -> ReadS ThirdWord
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> ReadS Word32
forall a. Read a => Int -> ReadS a
readsPrec

instance Bits ThirdWord where
  .&. :: ThirdWord -> ThirdWord -> ThirdWord
(.&.) = (Word32 -> Word32 -> Word32) -> ThirdWord -> ThirdWord -> ThirdWord
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> a -> a
(.&.) @Word32)
  .|. :: ThirdWord -> ThirdWord -> ThirdWord
(.|.) = (Word32 -> Word32 -> Word32) -> ThirdWord -> ThirdWord -> ThirdWord
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> a -> a
(.|.) @Word32)
  xor :: ThirdWord -> ThirdWord -> ThirdWord
xor = (Word32 -> Word32 -> Word32) -> ThirdWord -> ThirdWord -> ThirdWord
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> a -> a
xor @Word32)
  complement :: ThirdWord -> ThirdWord
complement (ThirdWord Word32
n) = Word32 -> ThirdWord
mkThirdWord (Word32 -> Word32
forall a. Bits a => a -> a
complement Word32
n)
  shift :: ThirdWord -> Int -> ThirdWord
shift (ThirdWord Word32
n) Int
k = Word32 -> ThirdWord
mkThirdWord (Word32 -> Int -> Word32
forall a. Bits a => a -> Int -> a
shift Word32
n Int
k)
  bitSize :: ThirdWord -> Int
bitSize = ThirdWord -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize
  bitSizeMaybe :: ThirdWord -> Maybe Int
bitSizeMaybe = Int -> Maybe Int
forall a. a -> Maybe a
Just (Int -> Maybe Int) -> (ThirdWord -> Int) -> ThirdWord -> Maybe Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ThirdWord -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize
  isSigned :: ThirdWord -> Bool
isSigned = (Word32 -> Bool) -> ThirdWord -> Bool
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> Bool
isSigned @Word32)
  testBit :: ThirdWord -> Int -> Bool
testBit = (Word32 -> Int -> Bool) -> ThirdWord -> Int -> Bool
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> Int -> Bool
testBit @Word32)
  bit :: Int -> ThirdWord
bit = Word32 -> ThirdWord
mkThirdWord (Word32 -> ThirdWord) -> (Int -> Word32) -> Int -> ThirdWord
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word32
forall a. Bits a => Int -> a
bit
  popCount :: ThirdWord -> Int
popCount = (Word32 -> Int) -> ThirdWord -> Int
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> Int
popCount @Word32)

  rotate :: ThirdWord -> Int -> ThirdWord
rotate ThirdWord
t Int
k'
    | Int
k Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = ThirdWord
t
    | Bool
otherwise = (ThirdWord
t ThirdWord -> Int -> ThirdWord
forall a. Bits a => a -> Int -> a
`shiftL` Int
k) ThirdWord -> ThirdWord -> ThirdWord
forall a. Bits a => a -> a -> a
.|. (ThirdWord
t ThirdWord -> Int -> ThirdWord
forall a. Bits a => a -> Int -> a
`shiftR` (Int
fbs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
k))
    where
      fbs :: Int
fbs = ThirdWord -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize ThirdWord
t
      k :: Int
k = Int
k' Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
fbs

instance FiniteBits ThirdWord where
  finiteBitSize :: ThirdWord -> Int
finiteBitSize = Int -> ThirdWord -> Int
forall a b. a -> b -> a
const (Int -> ThirdWord -> Int) -> Int -> ThirdWord -> Int
forall a b. (a -> b) -> a -> b
$ Word -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Word
0 :: Word) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
3

instance Bounded ThirdWord where
  minBound :: ThirdWord
minBound = Word32 -> ThirdWord
mkThirdWord Word32
forall a. Bounded a => a
minBound
  maxBound :: ThirdWord
maxBound = Word32 -> ThirdWord
mkThirdWord Word32
forall a. Bounded a => a
maxBound

instance Enum ThirdWord where
  toEnum :: Int -> ThirdWord
toEnum = Word32 -> ThirdWord
mkThirdWord (Word32 -> ThirdWord) -> (Int -> Word32) -> Int -> ThirdWord
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Word32
forall a. Enum a => Int -> a
toEnum
  fromEnum :: ThirdWord -> Int
fromEnum = (Word32 -> Int) -> ThirdWord -> Int
forall a b. Coercible a b => a -> b
coerce (forall a. Enum a => a -> Int
fromEnum @Word32)

instance Num ThirdWord where
  ThirdWord Word32
x + :: ThirdWord -> ThirdWord -> ThirdWord
+ ThirdWord Word32
y = Word32 -> ThirdWord
mkThirdWord (Word32
x Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
+ Word32
y)
  ThirdWord Word32
x * :: ThirdWord -> ThirdWord -> ThirdWord
* ThirdWord Word32
y = Word32 -> ThirdWord
mkThirdWord (Word32
x Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
* Word32
y)
  negate :: ThirdWord -> ThirdWord
negate (ThirdWord Word32
x) = Word32 -> ThirdWord
mkThirdWord (Word32 -> Word32
forall a. Num a => a -> a
negate Word32
x)
  abs :: ThirdWord -> ThirdWord
abs = (Word32 -> Word32) -> ThirdWord -> ThirdWord
forall a b. Coercible a b => a -> b
coerce (forall a. Num a => a -> a
abs @Word32)
  signum :: ThirdWord -> ThirdWord
signum = (Word32 -> Word32) -> ThirdWord -> ThirdWord
forall a b. Coercible a b => a -> b
coerce (forall a. Num a => a -> a
signum @Word32)
  fromInteger :: Integer -> ThirdWord
fromInteger = Word32 -> ThirdWord
mkThirdWord (Word32 -> ThirdWord)
-> (Integer -> Word32) -> Integer -> ThirdWord
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Word32
forall a. Num a => Integer -> a
fromInteger

instance Real ThirdWord where
  toRational :: ThirdWord -> Rational
toRational = (Word32 -> Rational) -> ThirdWord -> Rational
forall a b. Coercible a b => a -> b
coerce (forall a. Real a => a -> Rational
toRational @Word32)

instance Integral ThirdWord where
  quotRem :: ThirdWord -> ThirdWord -> (ThirdWord, ThirdWord)
quotRem = (Word32 -> Word32 -> (Word32, Word32))
-> ThirdWord -> ThirdWord -> (ThirdWord, ThirdWord)
forall a b. Coercible a b => a -> b
coerce (forall a. Integral a => a -> a -> (a, a)
quotRem @Word32)
  toInteger :: ThirdWord -> Integer
toInteger = (Word32 -> Integer) -> ThirdWord -> Integer
forall a b. Coercible a b => a -> b
coerce (forall a. Integral a => a -> Integer
toInteger @Word32)

-- | Total map from space to line, continuous almost everywhere.
-- See <https://en.wikipedia.org/wiki/Z-order_curve Z-order curve>.
--
-- >>> [ toZCurve3 x y z | x <- [0..3], y <- [0..3], z <- [0..3] ]
-- [0,4,32,36,2,6,34,38,16,20,48,52,18,22,50,54,1,5,33,37,3,7,35,39,17,21,49,53,19,23,51,55,
-- 8,12,40,44,10,14,42,46,24,28,56,60,26,30,58,62,9,13,41,45,11,15,43,47,25,29,57,61,27,31,59,63]
--
-- @since 0.2.0.0
toZCurve3 :: ThirdWord -> ThirdWord -> ThirdWord -> Word
toZCurve3 :: ThirdWord -> ThirdWord -> ThirdWord -> Word
toZCurve3 ThirdWord
x ThirdWord
y ThirdWord
z = ThirdWord -> Word
part1by2 ThirdWord
z Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
2 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. ThirdWord -> Word
part1by2 ThirdWord
y Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. ThirdWord -> Word
part1by2 ThirdWord
x

-- | Inverse for 'toZCurve3'.
-- See <https://en.wikipedia.org/wiki/Z-order_curve Z-order curve>.
--
-- >>> map fromZCurve3 [0..63]
-- [(0,0,0),(1,0,0),(0,1,0),(1,1,0),(0,0,1),(1,0,1),(0,1,1),(1,1,1),(2,0,0),(3,0,0),(2,1,0),(3,1,0),(2,0,1),(3,0,1),(2,1,1),(3,1,1),
--  (0,2,0),(1,2,0),(0,3,0),(1,3,0),(0,2,1),(1,2,1),(0,3,1),(1,3,1),(2,2,0),(3,2,0),(2,3,0),(3,3,0),(2,2,1),(3,2,1),(2,3,1),(3,3,1),
--  (0,0,2),(1,0,2),(0,1,2),(1,1,2),(0,0,3),(1,0,3),(0,1,3),(1,1,3),(2,0,2),(3,0,2),(2,1,2),(3,1,2),(2,0,3),(3,0,3),(2,1,3),(3,1,3),
--  (0,2,2),(1,2,2),(0,3,2),(1,3,2),(0,2,3),(1,2,3),(0,3,3),(1,3,3),(2,2,2),(3,2,2),(2,3,2),(3,3,2),(2,2,3),(3,2,3),(2,3,3),(3,3,3)]
--
-- @since 0.2.0.0
fromZCurve3 :: Word -> (ThirdWord, ThirdWord, ThirdWord)
fromZCurve3 :: Word -> (ThirdWord, ThirdWord, ThirdWord)
fromZCurve3 Word
z = (Word -> ThirdWord
compact1by2 Word
z, Word -> ThirdWord
compact1by2 (Word
z Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
1), Word -> ThirdWord
compact1by2 (Word
z Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
2))

-- | Convert a function of two 'ThirdWord's to a function of one 'Word'.
contramapFromZCurve3
  :: (ThirdWord -> ThirdWord -> ThirdWord -> a)
  -> (Word -> a)
contramapFromZCurve3 :: forall a. (ThirdWord -> ThirdWord -> ThirdWord -> a) -> Word -> a
contramapFromZCurve3 ThirdWord -> ThirdWord -> ThirdWord -> a
f = (ThirdWord -> ThirdWord -> ThirdWord -> a)
-> (ThirdWord, ThirdWord, ThirdWord) -> a
forall {t} {t} {t} {t}. (t -> t -> t -> t) -> (t, t, t) -> t
uncurry3 ThirdWord -> ThirdWord -> ThirdWord -> a
f ((ThirdWord, ThirdWord, ThirdWord) -> a)
-> (Word -> (ThirdWord, ThirdWord, ThirdWord)) -> Word -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> (ThirdWord, ThirdWord, ThirdWord)
fromZCurve3
  where
    uncurry3 :: (t -> t -> t -> t) -> (t, t, t) -> t
uncurry3 t -> t -> t -> t
func (t
a, t
b, t
c) = t -> t -> t -> t
func t
a t
b t
c

-- | Convert a function of one 'Word' to a function of two 'ThirdWord's.
contramapToZCurve3
  :: (Word -> a)
  -> (ThirdWord -> ThirdWord -> ThirdWord -> a)
contramapToZCurve3 :: forall a. (Word -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a
contramapToZCurve3 Word -> a
f = ((Word -> a
f (Word -> a) -> (ThirdWord -> Word) -> ThirdWord -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((ThirdWord -> Word) -> ThirdWord -> a)
-> (ThirdWord -> ThirdWord -> Word) -> ThirdWord -> ThirdWord -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((ThirdWord -> ThirdWord -> Word) -> ThirdWord -> ThirdWord -> a)
-> (ThirdWord -> ThirdWord -> ThirdWord -> Word)
-> ThirdWord
-> ThirdWord
-> ThirdWord
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ThirdWord -> ThirdWord -> ThirdWord -> Word
toZCurve3

-- | For an input function @f@ return function @g@ such that
-- 'Data.Function.fix' @f@ = (('Data.Function.fix' @g@ '.') '.') '.' 'toZCurve3'.
--
-- @since 0.4.0.0
throughZCurveFix3
  :: ((ThirdWord -> ThirdWord -> ThirdWord -> a) -> (ThirdWord -> ThirdWord -> ThirdWord -> a))
  -> (Word -> a)
  -> (Word -> a)
throughZCurveFix3 :: forall a.
((ThirdWord -> ThirdWord -> ThirdWord -> a)
 -> ThirdWord -> ThirdWord -> ThirdWord -> a)
-> (Word -> a) -> Word -> a
throughZCurveFix3 (ThirdWord -> ThirdWord -> ThirdWord -> a)
-> ThirdWord -> ThirdWord -> ThirdWord -> a
f = (ThirdWord -> ThirdWord -> ThirdWord -> a) -> Word -> a
forall a. (ThirdWord -> ThirdWord -> ThirdWord -> a) -> Word -> a
contramapFromZCurve3 ((ThirdWord -> ThirdWord -> ThirdWord -> a) -> Word -> a)
-> ((Word -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a)
-> (Word -> a)
-> Word
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ThirdWord -> ThirdWord -> ThirdWord -> a)
-> ThirdWord -> ThirdWord -> ThirdWord -> a
f ((ThirdWord -> ThirdWord -> ThirdWord -> a)
 -> ThirdWord -> ThirdWord -> ThirdWord -> a)
-> ((Word -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a)
-> (Word -> a)
-> ThirdWord
-> ThirdWord
-> ThirdWord
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a
forall a. (Word -> a) -> ThirdWord -> ThirdWord -> ThirdWord -> a
contramapToZCurve3

-- Inspired by https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
part1by1 :: HalfWord -> Word
part1by1 :: HalfWord -> Word
part1by1 HalfWord
x = Word64 -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
x5 :: Word64)
  where
    x0 :: Word64
x0 = HalfWord -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral HalfWord
x Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00000000ffffffff
    x1 :: Word64
x1 = (Word64
x0 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x0 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
16)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x0000ffff0000ffff
    x2 :: Word64
x2 = (Word64
x1 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
8)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00ff00ff00ff00ff
    x3 :: Word64
x3 = (Word64
x2 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x2 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
4)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x0f0f0f0f0f0f0f0f
    x4 :: Word64
x4 = (Word64
x3 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x3 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
2)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x3333333333333333
    x5 :: Word64
x5 = (Word64
x4 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x4 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
1)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x5555555555555555

-- Inspired by https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
part1by2 :: ThirdWord -> Word
part1by2 :: ThirdWord -> Word
part1by2 ThirdWord
x = Word64 -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
x5 :: Word64)
  where
    x0 :: Word64
x0 = ThirdWord -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral ThirdWord
x Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00000000ffffffff
    x1 :: Word64
x1 = (Word64
x0 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x0 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
32)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffff00000000ffff
    x2 :: Word64
x2 = (Word64
x1 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
16)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00ff0000ff0000ff
    x3 :: Word64
x3 = (Word64
x2 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x2 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
8)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xf00f00f00f00f00f
    x4 :: Word64
x4 = (Word64
x3 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x3 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
4)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x30c30c30c30c30c3
    x5 :: Word64
x5 = (Word64
x4 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x4 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftL` Int
2)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x1249249249249249

-- Inspired by https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
compact1by1 :: Word -> HalfWord
compact1by1 :: Word -> HalfWord
compact1by1 Word
x = Word64 -> HalfWord
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
x5 :: Word64)
  where
    x0 :: Word64
x0 = Word -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
x Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x5555555555555555
    x1 :: Word64
x1 = (Word64
x0 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x0 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
1)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x3333333333333333
    x2 :: Word64
x2 = (Word64
x1 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
2)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x0f0f0f0f0f0f0f0f
    x3 :: Word64
x3 = (Word64
x2 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x2 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
4)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00ff00ff00ff00ff
    x4 :: Word64
x4 = (Word64
x3 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x3 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
8)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x0000ffff0000ffff
    x5 :: Word64
x5 = (Word64
x4 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x4 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
16)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00000000ffffffff

-- Inspired by https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/
compact1by2 :: Word -> ThirdWord
compact1by2 :: Word -> ThirdWord
compact1by2 Word
x = Word64 -> ThirdWord
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
x5 :: Word64)
  where
    x0 :: Word64
x0 = Word -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word
x Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x1249249249249249
    x1 :: Word64
x1 = (Word64
x0 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x0 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
2)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x30c30c30c30c30c3
    x2 :: Word64
x2 = (Word64
x1 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x1 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
4)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xf00f00f00f00f00f
    x3 :: Word64
x3 = (Word64
x2 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x2 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
8)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00ff0000ff0000ff
    x4 :: Word64
x4 = (Word64
x3 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x3 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
16)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffff00000000ffff
    x5 :: Word64
x5 = (Word64
x4 Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
`xor` (Word64
x4 Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
`shiftR` Int
32)) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0x00000000ffffffff