Copyright | (C) 2013 Edward Kmett |
---|---|
License | BSD-style (see the file LICENSE) |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Stability | experimental |
Portability | non-portable |
Safe Haskell | None |
Language | Haskell98 |
Keys in Morton order
This module provides combinators for shuffling together the bits of two key components to get a key that is based on their interleaved bits.
See http://en.wikipedia.org/wiki/Z-order_curve for more information about Morton order.
How to perform the comparison without interleaving is described in
https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-2
Keys in Morton order
Key i j
logically orders the keys as if the bits of the keys i
and j
were interleaved. This is equivalent to storing the keys in "Morton Order".
>>>
Key 100 200 ^. _1
100
>>>
Key 100 200 ^. _2
200
Eq Key | |
Ord Key | |
Read Key | |
Show Key | |
Unbox Key | |
Arrayed Key | |
Vector Vector Key | |
FunctorWithIndex Key Heap | |
FoldableWithIndex Key Heap | |
TraversableWithIndex Key Heap | |
MVector MVector Key | |
((~) * a Word, (~) * b Word) => Field1 Key Key a b | |
((~) * a Word, (~) * b Word) => Field2 Key Key a b | |
data Vector Key = V_Key !Int !(Vector Word) !(Vector Word) | |
type Arr Key = Vector | |
data MVector s Key = MV_Key !Int !(MVector s Word) !(MVector s Word) |
Most significant bit comparisons
compares :: Word -> Word -> Ordering Source
compare the position of the most significant bit of two words
>>>
compares 4 7
EQ
>>>
compares 7 9
LT
>>>
compares 9 7
GT
Unboxed vector constructors
data family MVector s a
data family Vector a