bitvec-1.1.5.0: Space-efficient bit vectors
Copyright(c) 2019-2022 Andrew Lelechenko 2012-2016 James Cook
LicenseBSD3
MaintainerAndrew Lelechenko <andrew.lelechenko@gmail.com>
Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.Bit

Description

This module exposes an interface with non-thread-safe writes and flips. Additionally, concurrently modifying non-intersecting slices of the same underlying array may lead to unexpected results. Consider using Data.Bit.ThreadSafe, which is thread-safe, but slower (usually 10-20%, up to 50% for short vectors).

Since: 0.1

Synopsis

Documentation

newtype Bit Source #

A newtype wrapper with a custom instance for Data.Vector.Unboxed, which packs booleans as efficient as possible (8 values per byte). Unboxed vectors of Bit use 8x less memory than unboxed vectors of Bool (which store one value per byte), but random writes are slightly slower.

Since: 0.1

Constructors

Bit 

Fields

Instances

Instances details
Bits Bit Source # 
Instance details

Defined in Data.Bit.Internal

Methods

(.&.) :: Bit -> Bit -> Bit #

(.|.) :: Bit -> Bit -> Bit #

xor :: Bit -> Bit -> Bit #

complement :: Bit -> Bit #

shift :: Bit -> Int -> Bit #

rotate :: Bit -> Int -> Bit #

zeroBits :: Bit #

bit :: Int -> Bit #

setBit :: Bit -> Int -> Bit #

clearBit :: Bit -> Int -> Bit #

complementBit :: Bit -> Int -> Bit #

testBit :: Bit -> Int -> Bool #

bitSizeMaybe :: Bit -> Maybe Int #

bitSize :: Bit -> Int #

isSigned :: Bit -> Bool #

shiftL :: Bit -> Int -> Bit #

unsafeShiftL :: Bit -> Int -> Bit #

shiftR :: Bit -> Int -> Bit #

unsafeShiftR :: Bit -> Int -> Bit #

rotateL :: Bit -> Int -> Bit #

rotateR :: Bit -> Int -> Bit #

popCount :: Bit -> Int #

FiniteBits Bit Source #

Since: 0.2.0.0

Instance details

Defined in Data.Bit.Internal

Bounded Bit Source # 
Instance details

Defined in Data.Bit.Internal

Methods

minBound :: Bit #

maxBound :: Bit #

Enum Bit Source # 
Instance details

Defined in Data.Bit.Internal

Methods

succ :: Bit -> Bit #

pred :: Bit -> Bit #

toEnum :: Int -> Bit #

fromEnum :: Bit -> Int #

enumFrom :: Bit -> [Bit] #

enumFromThen :: Bit -> Bit -> [Bit] #

enumFromTo :: Bit -> Bit -> [Bit] #

enumFromThenTo :: Bit -> Bit -> Bit -> [Bit] #

Generic Bit Source # 
Instance details

Defined in Data.Bit.Internal

Associated Types

type Rep Bit :: Type -> Type #

Methods

from :: Bit -> Rep Bit x #

to :: Rep Bit x -> Bit #

Num Bit Source #

There is only one lawful Num instance possible with + = xor and fromInteger = Bit . odd.

Since: 1.0.1.0

Instance details

Defined in Data.Bit.Internal

Methods

(+) :: Bit -> Bit -> Bit #

(-) :: Bit -> Bit -> Bit #

(*) :: Bit -> Bit -> Bit #

negate :: Bit -> Bit #

abs :: Bit -> Bit #

signum :: Bit -> Bit #

fromInteger :: Integer -> Bit #

Read Bit Source # 
Instance details

Defined in Data.Bit.Internal

Fractional Bit Source #

Since: 1.0.1.0

Instance details

Defined in Data.Bit.Internal

Methods

(/) :: Bit -> Bit -> Bit #

recip :: Bit -> Bit #

fromRational :: Rational -> Bit #

Integral Bit Source #

Since: 1.0.1.0

Instance details

Defined in Data.Bit.Internal

Methods

quot :: Bit -> Bit -> Bit #

rem :: Bit -> Bit -> Bit #

div :: Bit -> Bit -> Bit #

mod :: Bit -> Bit -> Bit #

quotRem :: Bit -> Bit -> (Bit, Bit) #

divMod :: Bit -> Bit -> (Bit, Bit) #

toInteger :: Bit -> Integer #

Real Bit Source #

Since: 1.0.1.0

Instance details

Defined in Data.Bit.Internal

Methods

toRational :: Bit -> Rational #

Show Bit Source # 
Instance details

Defined in Data.Bit.Internal

Methods

showsPrec :: Int -> Bit -> ShowS #

show :: Bit -> String #

showList :: [Bit] -> ShowS #

NFData Bit Source #

Since: 1.0.1.0

Instance details

Defined in Data.Bit.Internal

Methods

rnf :: Bit -> () #

Eq Bit Source # 
Instance details

Defined in Data.Bit.Internal

Methods

(==) :: Bit -> Bit -> Bool #

(/=) :: Bit -> Bit -> Bool #

Ord Bit Source # 
Instance details

Defined in Data.Bit.Internal

Methods

compare :: Bit -> Bit -> Ordering #

(<) :: Bit -> Bit -> Bool #

(<=) :: Bit -> Bit -> Bool #

(>) :: Bit -> Bit -> Bool #

(>=) :: Bit -> Bit -> Bool #

max :: Bit -> Bit -> Bit #

min :: Bit -> Bit -> Bit #

Unbox Bit Source # 
Instance details

Defined in Data.Bit.Internal

Vector Vector Bit Source # 
Instance details

Defined in Data.Bit.Internal

MVector MVector Bit Source # 
Instance details

Defined in Data.Bit.Internal

Bits (Vector Bit) Source #

Note: For (.&.), (.|.) and xor, if one input is larger than the other, the remaining bits will be ignored. bitSize is undefined (throws an exception).

Instance details

Defined in Data.Bit.Immutable

type Rep Bit Source #

Since: 1.0.1.0

Instance details

Defined in Data.Bit.Internal

type Rep Bit = D1 ('MetaData "Bit" "Data.Bit.Internal" "bitvec-1.1.5.0-6f2gROHOhn4BLl7RQND7hM" 'True) (C1 ('MetaCons "Bit" 'PrefixI 'True) (S1 ('MetaSel ('Just "unBit") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Bool)))
data Vector Bit Source # 
Instance details

Defined in Data.Bit.Internal

data MVector s Bit Source # 
Instance details

Defined in Data.Bit.Internal

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

Flip the bit at the given position. No bound checks are performed. Equivalent to flip unsafeModify complement, but up to 2x faster.

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).

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify (`unsafeFlipBit` 2) [1,1,1,1]
[1,1,0,1]

Since: 1.0.0.0

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 2x faster.

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).

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify (`flipBit` 2) [1,1,1,1]
[1,1,0,1]

Since: 1.0.0.0

Immutable conversions

castFromWords :: Vector Word -> Vector Bit Source #

Cast an unboxed vector of words to an unboxed vector of bits. Cf. castFromWordsM.

>>> :set -XOverloadedLists
>>> castFromWords [123]
[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]

Since: 1.0.0.0

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

Try to cast an unboxed vector of bits to an unboxed vector of words. It succeeds if the vector of bits is aligned. Use cloneToWords otherwise. Cf. castToWordsM.

castToWords (castFromWords v) == Just v

Since: 1.0.0.0

cloneToWords :: Vector Bit -> Vector Word Source #

Clone an unboxed 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.

>>> :set -XOverloadedLists
>>> cloneToWords [1,1,0,1,1,1,1]
[123]

Since: 1.0.0.0

castFromWords8 :: Vector Word8 -> Vector Bit Source #

Cast an unboxed vector of Word8 to an unboxed vector of bits.

On big-endian architectures castFromWords8 resorts to copying instead of aliasing the underlying array.

>>> :set -XOverloadedLists
>>> castFromWords8 [123]
[1,1,0,1,1,1,1,0]

Since: 1.0.3.0

castToWords8 :: Vector Bit -> Maybe (Vector Word8) Source #

Try to cast an unboxed vector of bits to an unboxed vector of Word8. It succeeds if the vector of bits is aligned. Use cloneToWords8 otherwise.

castToWords8 (castFromWords8 v) == Just v

Since: 1.0.3.0

cloneToWords8 :: Vector Bit -> Vector Word8 Source #

Clone an unboxed vector of bits to a new unboxed vector of Word8. If the bits don't completely fill the bytes, the last Word8 will be zero-padded.

>>> :set -XOverloadedLists
>>> cloneToWords8 [1,1,0,1,1,1,1]
[123]

Since: 1.0.3.0

cloneFromByteString :: ByteString -> Vector Bit Source #

Clone a ByteString to a new unboxed vector of bits.

>>> :set -XOverloadedStrings
>>> cloneFromByteString "abc"
[1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

Since: 1.1.0.0

cloneToByteString :: Vector Bit -> ByteString Source #

Clone an unboxed vector of bits to a new ByteString. If the bits don't completely fill the bytes, the last character will be zero-padded.

>>> :set -XOverloadedLists
>>> cloneToByteString [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1]
"ab#"

Since: 1.1.0.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 3500x (!) faster.

Note: If one input is larger than the other, the remaining bits will be ignored.

For sufficiently dense sets, represented as bitmaps, zipBits is up to 64x faster than union, intersection, etc.

The function passed to zipBits may only use the following Bits methods:

.&., .|., xor, complement, zeroBits, and (likely uselessly) bitSizeMaybe and isSigned.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> zipBits (.&.) [1,1,0] [0,1,1] -- intersection
[0,1,0]
>>> zipBits (.|.) [1,1,0] [0,1,1] -- union
[1,1,1]
>>> zipBits (\x y -> x .&. complement y) [1,1,0] [0,1,1] -- difference
[1,0,0]
>>> zipBits xor [1,1,0] [0,1,1] -- symmetric difference
[1,0,1]

Since: 1.0.0.0

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

Map a vectors with the given function. Similar to map, but faster.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> mapBits complement [0,1,1]
[1,0,0]

Since: 1.1.0.0

invertBits :: Vector Bit -> Vector Bit Source #

Invert (flip) all bits.

>>> :set -XOverloadedLists
>>> invertBits [0,1,0,1,0]
[1,0,1,0,1]

Since: 1.0.1.0

reverseBits :: Vector Bit -> Vector Bit Source #

Reverse the order of bits.

>>> :set -XOverloadedLists
>>> reverseBits [1,1,0,1,0]
[0,1,0,1,1]

Consider using the vector-rotcev package to reverse vectors in O(1) time.

Since: 1.0.1.0

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.

>>> :set -XOverloadedLists
>>> bitIndex 1 [0,0,1,0,1]
Just 2
>>> bitIndex 1 [0,0,0,0,0]
Nothing
bitIndex bit == nthBitIndex bit 1

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

import Data.Maybe
isAnyBitSet   = isJust    . bitIndex 1
areAllBitsSet = isNothing . bitIndex 0

Since: 1.0.0.0

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.

>>> :set -XOverloadedLists
>>> nthBitIndex 1 2 [0,1,0,1,1,1,0] -- 2nd occurence of 1
Just 3
>>> nthBitIndex 1 5 [0,1,0,1,1,1,0] -- 5th occurence of 1
Nothing

One can use nthBitIndex to implement to implement select{0,1} queries for succinct dictionaries.

Since: 1.0.0.0

countBits :: Vector Bit -> Int Source #

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

>>> :set -XOverloadedLists
>>> countBits [1,1,0,1,0,1]
4

One can combine countBits with take to implement rank{0,1} queries for succinct dictionaries.

Since: 0.1

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

Return 0-based indices of set bits in a vector.

>>> :set -XOverloadedLists
>>> listBits [1,1,0,1,0,1]
[0,1,3,5]

Since: 0.1

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

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

Note: If one input is larger than the other, the remaining bits will be ignored.

>>> :set -XOverloadedLists
>>> selectBits [0,1,0,1,1] [1,1,0,0,1]
[1,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))

Since: 0.1

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

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

Note: If one input is larger than the other, the remaining bits will be ignored.

>>> :set -XOverloadedLists
>>> excludeBits [0,1,0,1,1] [1,1,0,0,1]
[1,0]

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))

Since: 0.1

Mutable conversions

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

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

Since: 1.0.0.0

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

Try to cast a vector of bits to a vector of words. It succeeds if the vector of bits is aligned. Use cloneToWordsM otherwise. Cf. castToWords.

Since: 1.0.0.0

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.

Since: 1.0.0.0

Mutable operations

zipInPlace :: forall m. 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 the contents of the second argument. Cf. zipBits.

Note: If one input is larger than the other, the remaining bits will be ignored.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> Data.Vector.Unboxed.modify (zipInPlace (.&.) [1,1,0]) [0,1,1]
[0,1,0]

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

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> Data.Vector.Unboxed.modify (zipInPlace (.&.) [1,1,0]) [0,1,1,1,1,1]
[0,1,0,1,1,1] -- note trailing garbage

Since: 1.0.0.0

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

Apply a function to a mutable vector bitwise, rewriting its contents. Cf. mapBits.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> Data.Vector.Unboxed.modify (mapInPlace complement) [0,1,1]
[1,0,0]

Since: 1.1.0.0

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

Invert (flip) all bits in-place.

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify invertInPlace [0,1,0,1,0]
[1,0,1,0,1]

Since: 0.1

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

Reverse the order of bits in-place.

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify reverseInPlace [1,1,0,1,0]
[0,1,0,1,1]

Consider using the vector-rotcev package to reverse vectors in O(1) time.

Since: 0.1

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

Same as selectBits, but extract selected bits in-place. Returns the number of selected bits. It is the caller's responsibility to trim the result to this number.

Note: If one input is larger than the other, the remaining bits will be ignored.

>>> :set -XOverloadedLists
>>> import Control.Monad.ST (runST)
>>> import qualified Data.Vector.Unboxed as U
>>> runST $ do { vec <- U.unsafeThaw [1,1,0,0,1]; n <- selectBitsInPlace [0,1,0,1,1] vec; U.take n <$> U.unsafeFreeze vec }
[1,0,1]

Since: 0.1

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

Same as excludeBits, but extract excluded bits in-place. Returns the number of excluded bits. It is the caller's responsibility to trim the result to this number.

Note: If one input is larger than the other, the remaining bits will be ignored.

>>> :set -XOverloadedLists
>>> import Control.Monad.ST (runST)
>>> import qualified Data.Vector.Unboxed as U
>>> runST $ do { vec <- U.unsafeThaw [1,1,0,0,1]; n <- excludeBitsInPlace [0,1,0,1,1] vec; U.take n <$> U.unsafeFreeze vec }
[1,0]

Since: 0.1

Binary polynomials

data F2Poly Source #

Binary polynomials of one variable, backed by an unboxed Vector Bit.

Polynomials are stored normalized, without leading zero coefficients.

The Ord instance does not make much sense mathematically, it is defined only for the sake of Set, Map, etc.

>>> :set -XBinaryLiterals
>>> -- (1 + x) * (1 + x + x^2) = 1 + x^3 (mod 2)
>>> 0b11 * 0b111 :: F2Poly
0b1001

Since: 1.0.1.0

Instances

Instances details
Enum F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

Generic F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

Associated Types

type Rep F2Poly :: Type -> Type #

Methods

from :: F2Poly -> Rep F2Poly x #

to :: Rep F2Poly x -> F2Poly #

Num F2Poly Source #

Addition and multiplication are evaluated modulo 2.

abs = id and signum = const 1.

fromInteger converts a binary polynomial, encoded as Integer, to F2Poly encoding.

Instance details

Defined in Data.Bit.F2Poly

Integral F2Poly Source #

toInteger converts a binary polynomial, encoded as F2Poly, to an Integer encoding.

Instance details

Defined in Data.Bit.F2Poly

Real F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

Show F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

NFData F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

Methods

rnf :: F2Poly -> () #

Eq F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

Methods

(==) :: F2Poly -> F2Poly -> Bool #

(/=) :: F2Poly -> F2Poly -> Bool #

Ord F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

type Rep F2Poly Source # 
Instance details

Defined in Data.Bit.F2Poly

type Rep F2Poly = D1 ('MetaData "F2Poly" "Data.Bit.F2Poly" "bitvec-1.1.5.0-6f2gROHOhn4BLl7RQND7hM" 'True) (C1 ('MetaCons "F2Poly" 'PrefixI 'True) (S1 ('MetaSel ('Just "unF2Poly") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Vector Bit))))

unF2Poly :: F2Poly -> Vector Bit Source #

Convert an F2Poly to a vector of coefficients (first element corresponds to a constant term).

>>> :set -XBinaryLiterals
>>> unF2Poly 0b1101
[1,0,1,1]

Since: 1.0.1.0

toF2Poly :: Vector Bit -> F2Poly Source #

Make an F2Poly from a list of coefficients (first element corresponds to a constant term).

>>> :set -XOverloadedLists
>>> toF2Poly [1,0,1,1,0,0]
0b1101

Since: 1.0.1.0

gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly) Source #

Execute the extended Euclidean algorithm. For polynomials a and b, compute their unique greatest common divisor g and the unique coefficient polynomial s satisfying \( a \cdot s + b \cdot t = g \).

>>> :set -XBinaryLiterals
>>> gcdExt 0b101 0b0101
(0b101,0b0)
>>> gcdExt 0b11 0b111
(0b1,0b10)

Since: 1.0.2.0