Copyright | (c) 2019 Andrew Lelechenko 2012-2016 James Cook |
---|---|

License | BSD3 |

Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |

Safe Haskell | None |

Language | Haskell2010 |

This module exposes an interface with thread-safe writes and flips. Consider using Data.Bit, which is faster (up to 20%), but thread-unsafe.

## Synopsis

- newtype Bit = Bit {}
- unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()
- flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()
- castFromWords :: Vector Word -> Vector Bit
- castToWords :: Vector Bit -> Maybe (Vector Word)
- cloneToWords :: Vector Bit -> Vector Word
- zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit
- bitIndex :: Bit -> Vector Bit -> Maybe Int
- nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int
- countBits :: Vector Bit -> Int
- listBits :: Vector Bit -> [Int]
- selectBits :: Vector Bit -> Vector Bit -> Vector Bit
- excludeBits :: Vector Bit -> Vector Bit -> Vector Bit
- castFromWordsM :: MVector s Word -> MVector s Bit
- castToWordsM :: MVector s Bit -> Maybe (MVector s Word)
- cloneToWordsM :: PrimMonad m => MVector (PrimState m) Bit -> m (MVector (PrimState m) Word)
- invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()
- zipInPlace :: PrimMonad m => (forall a. Bits a => a -> a -> a) -> Vector Bit -> MVector (PrimState m) Bit -> m ()
- selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int
- excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int
- reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

# Documentation

A newtype wrapper with a custom instance
of Data.Vector.Unboxed, which packs booleans
as efficient as possible (8 values per byte).
Vectors of `Bit`

use 8x less memory
than vectors of `Bool`

(which stores one value per byte).
but random writes are up to 20% slower.

## Instances

unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m () Source #

Flip the bit at the given position.
No bounds checks are performed.
Equivalent to `flip`

`unsafeModify`

`complement`

,
but up to 33% faster and atomic.

In general there is no reason to `unsafeModify`

bit vectors:
either you modify it with `id`

(which is `id`

altogether)
or with `complement`

(which is `unsafeFlipBit`

).

`>>>`

[1,0,1]`Data.Vector.Unboxed.modify (\v -> unsafeFlipBit v 1) (read "[1,1,1]")`

flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m () Source #

Flip the bit at the given position.
Equivalent to `flip`

`modify`

`complement`

,
but up to 33% faster and atomic.

In general there is no reason to `modify`

bit vectors:
either you modify it with `id`

(which is `id`

altogether)
or with `complement`

(which is `flipBit`

).

`>>>`

[1,0,1]`Data.Vector.Unboxed.modify (\v -> flipBit v 1) (read "[1,1,1]")`

# Immutable conversions

castFromWords :: Vector Word -> Vector Bit Source #

Cast a vector of words to a vector of bits.
Cf. `castFromWordsM`

.

`>>>`

[1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]`castFromWords (Data.Vector.Unboxed.singleton 123)`

castToWords :: Vector Bit -> Maybe (Vector Word) Source #

Try to cast a vector of bits to a vector of words.
It succeeds if a vector of bits is aligned.
Use `cloneToWords`

otherwise.
Cf. `castToWordsM`

.

castToWords (castFromWords v) == Just v

cloneToWords :: Vector Bit -> Vector Word Source #

Clone a vector of bits to a new unboxed vector of words.
If the bits don't completely fill the words, the last word will be zero-padded.
Cf. `cloneToWordsM`

.

`>>>`

[123]`cloneToWords (read "[1,1,0,1,1,1,1,0]")`

# Immutable operations

zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit Source #

Zip two vectors with the given function.
Similar to `zipWith`

, but up to 16x faster.

`>>>`

`import Data.Bits`

`>>>`

[0,1,0]`zipBits (.&.) (read "[1,1,0]") (read "[0,1,1]") -- intersection`

`>>>`

[1,1,1]`zipBits (.|.) (read "[1,1,0]") (read "[0,1,1]") -- union`

`>>>`

[1,0,0]`zipBits (\x y -> x .&. complement y) (read "[1,1,0]") (read "[0,1,1]") -- difference`

`>>>`

[1,0,1]`zipBits xor (read "[1,1,0]") (read "[0,1,1]") -- symmetric difference`

bitIndex :: Bit -> Vector Bit -> Maybe Int Source #

Return the index of the first bit in the vector
with the specified value, if any.
Similar to `elemIndex`

, but up to 64x faster.

`>>>`

Just 2`bitIndex (Bit True) (read "[0,0,1,0,1]")`

`>>>`

Nothing`bitIndex (Bit True) (read "[0,0,0,0,0]")`

bitIndex bit == nthBitIndex bit 1

One can also use it to reduce a vector with disjunction or conjunction:

`>>>`

`import Data.Maybe`

`>>>`

`isAnyBitSet = isJust . bitIndex (Bit True)`

`>>>`

`areAllBitsSet = isNothing . bitIndex (Bit False)`

nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int Source #

Return the index of the `n`

-th bit in the vector
with the specified value, if any.
Here `n`

is 1-based and the index is 0-based.
Non-positive `n`

results in an error.

`>>>`

Just 3`nthBitIndex (Bit True) 2 (read "[0,1,0,1,1,1,0]")`

`>>>`

Nothing`nthBitIndex (Bit True) 5 (read "[0,1,0,1,1,1,0]")`

One can use `nthBitIndex`

to implement
to implement `select{0,1}`

queries
for succinct dictionaries.

countBits :: Vector Bit -> Int Source #

Return the number of set bits in a vector (population count, popcount).

`>>>`

4`countBits (read "[1,1,0,1,0,1]")`

One can combine `countBits`

with `take`

to implement `rank{0,1}`

queries
for succinct dictionaries.

listBits :: Vector Bit -> [Int] Source #

Return the indices of set bits in a vector.

`>>>`

[0,1,3,5]`listBits (read "[1,1,0,1,0,1]")`

selectBits :: Vector Bit -> Vector Bit -> Vector Bit Source #

For each set bit of the first argument, deposit the corresponding bit of the second argument to the result. Similar to the parallel deposit instruction (PDEP).

`>>>`

[1,0,1]`selectBits (read "[0,1,0,1,1]") (read "[1,1,0,0,1]")`

Here is a reference (but slow) implementation:

import qualified Data.Vector.Unboxed as U selectBits mask ws == U.map snd (U.filter (unBit . fst) (U.zip mask ws))

excludeBits :: Vector Bit -> Vector Bit -> Vector Bit Source #

For each unset bit of the first argument, deposit the corresponding bit of the second argument to the result.

`>>>`

[1,0]`excludeBits (read "[0,1,0,1,1]") (read "[1,1,0,0,1]")`

Here is a reference (but slow) implementation:

import qualified Data.Vector.Unboxed as U excludeBits mask ws == U.map snd (U.filter (not . unBit . fst) (U.zip mask ws))

# Mutable conversions

castFromWordsM :: MVector s Word -> MVector s Bit Source #

Cast a vector of words to a vector of bits.
Cf. `castFromWords`

.

castToWordsM :: MVector s Bit -> Maybe (MVector s Word) Source #

Try to cast a vector of bits to a vector of words.
It succeeds if a vector of bits is aligned.
Use `cloneToWordsM`

otherwise.
Cf. `castToWords`

.

cloneToWordsM :: PrimMonad m => MVector (PrimState m) Bit -> m (MVector (PrimState m) Word) Source #

Clone a vector of bits to a new unboxed vector of words.
If the bits don't completely fill the words, the last word will be zero-padded.
Cf. `cloneToWords`

.

# Mutable operations

invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m () Source #

Invert (flip) all bits in-place.

Combine with `modify`

or simply resort to `map`

`complement`

to operate on immutable vectors.

`>>>`

[1,0,1,0,1]`Data.Vector.Unboxed.modify invertInPlace (read "[0,1,0,1,0]")`

zipInPlace :: PrimMonad m => (forall a. Bits a => a -> a -> a) -> Vector Bit -> MVector (PrimState m) Bit -> m () Source #

Zip two vectors with the given function.
rewriting contents of the second argument.
Cf. `zipBits`

.

`>>>`

`import Data.Bits`

`>>>`

[0,1,0]`modify (zipInPlace (.&.) (read "[1,1,0]")) (read "[0,1,1]")`

**Warning**: if the immutable vector is shorter than the mutable one,
it is a caller's responsibility to trim the result:

`>>>`

`import Data.Bits`

`>>>`

[0,1,0,1,1,1] -- note trailing garbage`modify (zipInPlace (.&.) (read "[1,1,0]")) (read "[0,1,1,1,1,1]")`

selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int Source #

Same as `selectBits`

, but deposit
selected bits in-place. Returns a number of selected bits.
It is caller's resposibility to trim the result to this number.