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