Sparse.Matrix.Internal.Key

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

data Key

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

Constructors

Key !Word !Word

Instances

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

swap :: Key -> Key

Swaps the key components around

>>> swap (Key 100 200)
Key 200 100

Most significant bit comparisons

compares :: Word -> Word -> Ordering

compare the position of the most significant bit of two words

>>> compares 4 7
EQ

>>> compares 7 9
LT

>>> compares 9 7
GT

lts :: Word -> Word -> Bool

lts a b returns True when the position of the most significant bit of a is less than the position of the most signficant bit of b.

>>> lts 4 10
True

>>> lts 4 7
False

>>> lts 7 8
True

les :: Word -> Word -> Bool

les a b returns True when the position of the most significant bit of a is less than or equal to the position of the most signficant bit of b.

>>> les 4 10
True

>>> les 4 7
True

>>> les 7 4
True

>>> les 10 4
False

eqs :: Word -> Word -> Bool

eqs a b returns True when the position of the most significant bit of a is equal to the position of the most signficant bit of b.

>>> eqs 4 7
True

>>> eqs 4 8
False

>>> eqs 7 4
True

>>> eqs 8 4
False

nes :: Word -> Word -> Bool

nes a b returns True when the position of the most significant bit of a is not equal to the position of the most signficant bit of b.

>>> nes 4 7
False

>>> nes 4 8
True

>>> nes 7 4
False

>>> nes 8 4
True

ges :: Word -> Word -> Bool

gts a b returns True when the position of the most significant bit of a is greater than or equal to the position of the most signficant bit of b.

>>> ges 4 10
False

>>> ges 4 7
True

>>> ges 7 4
True

>>> ges 10 4
True

gts :: Word -> Word -> Bool

gts a b returns True when the position of the most significant bit of a is greater than to the position of the most signficant bit of b.

>>> gts 4 10
False

>>> gts 4 7
False

>>> gts 7 4
False

>>> gts 10 4
True

Unboxed vector constructors

data family MVector s a

data family Vector a