-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Space-efficient bit vectors
--
-- A newtype over Bool with a better Vector instance: 8x
-- less memory, up to 1000x faster.
--
-- The vector package represents unboxed arrays of Bool
-- spending 1 byte (8 bits) per boolean. This library provides a newtype
-- wrapper Bit and a custom instance of unboxed Vector,
-- which packs bits densely, achieving 8x less memory footprint.
-- The performance stays mostly the same; the most significant
-- degradation happens for random writes (up to 10% slower). On the other
-- hand, for certain bulk bit operations Vector Bit is up
-- to 1000x faster than Vector Bool.
--
-- Thread safety
--
--
-- - Data.Bit is faster, but writes and flips are thread-unsafe.
-- This is because naive updates are not atomic: read the whole word from
-- memory, then modify a bit, then write the whole word back.
-- - Data.Bit.ThreadSafe is slower (up to 20%), but writes and
-- flips are thread-safe.
--
--
-- Similar packages
--
--
-- - bv and bv-little do not offer mutable vectors.
-- - array is memory-efficient for Bool, but lacks a
-- handy Vector interface and is not thread-safe.
--
@package bitvec
@version 1.1.2.0
-- | This module exposes an interface with thread-safe writes and flips.
-- Consider using Data.Bit, which is faster (up to 20%), but
-- thread-unsafe.
module Data.Bit.ThreadSafe
-- | 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.
newtype Bit
Bit :: Bool -> Bit
[unBit] :: Bit -> Bool
-- | 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).
--
--
-- >>> Data.Vector.Unboxed.modify (\v -> unsafeFlipBit v 1) (read "[1,1,1]")
-- [1,0,1]
--
unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()
-- | 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).
--
--
-- >>> Data.Vector.Unboxed.modify (\v -> flipBit v 1) (read "[1,1,1]")
-- [1,0,1]
--
flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()
-- | 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]
--
castFromWords :: Vector Word -> Vector Bit
-- | Try to cast an unboxed vector of bits to an unboxed vector of words.
-- It succeeds if a vector of bits is aligned. Use cloneToWords
-- otherwise. Cf. castToWordsM.
--
--
-- castToWords (castFromWords v) == Just v
--
castToWords :: Vector Bit -> Maybe (Vector Word)
-- | 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]
--
cloneToWords :: Vector Bit -> Vector Word
-- | Cast a unboxed vector of Word8 to an unboxed vector of bits.
--
-- On big-endian architectures castFromWords8 resorts to copying
-- instead of aliasing underlying arrays.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> castFromWords8 [123]
-- [1,1,0,1,1,1,1,0]
--
castFromWords8 :: Vector Word8 -> Vector Bit
-- | Try to cast an unboxed vector of bits to an unboxed vector of
-- Word8. It succeeds if a vector of bits is aligned. Use
-- cloneToWords8 otherwise.
--
--
-- castToWords8 (castFromWords8 v) == Just v
--
castToWords8 :: Vector Bit -> Maybe (Vector Word8)
-- | 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]
--
cloneToWords8 :: Vector Bit -> Vector Word8
-- | 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]
--
cloneFromByteString :: ByteString -> Vector Bit
-- | 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#"
--
cloneToByteString :: Vector Bit -> ByteString
-- | Zip two vectors with the given function. Similar to zipWith,
-- but up to 1000x (!) faster.
--
-- For sufficiently dense sets, represented as bitmaps, zipBits is
-- up to 32x faster than union, intersection, etc.
--
-- Users are strongly encouraged to enable flag libgmp for the
-- ultimate performance of zipBits.
--
--
-- >>> :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]
--
zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit
-- | 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]
--
mapBits :: (forall a. Bits a => a -> a) -> Vector Bit -> Vector Bit
-- | Invert (flip) all bits.
--
-- Users are strongly encouraged to enable flag libgmp for the
-- ultimate performance of invertBits.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> invertBits [0,1,0,1,0]
-- [1,0,1,0,1]
--
invertBits :: Vector Bit -> Vector Bit
-- | Reverse the order of bits.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> reverseBits [1,1,0,1,0]
-- [0,1,0,1,1]
--
--
-- Consider using vector-rotcev package to reverse vectors in
-- O(1) time.
reverseBits :: Vector Bit -> Vector Bit
-- | 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
--
bitIndex :: Bit -> Vector Bit -> Maybe Int
-- | 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.
nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int
-- | Return the number of set bits in a vector (population count,
-- popcount).
--
-- Users are strongly encouraged to enable flag libgmp for the
-- ultimate performance of countBits.
--
--
-- >>> :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.
countBits :: Vector Bit -> Int
-- | Return 0-based indices of set bits in a vector.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> listBits [1,1,0,1,0,1]
-- [0,1,3,5]
--
listBits :: Vector Bit -> [Int]
-- | 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).
--
--
-- >>> :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))
--
selectBits :: Vector Bit -> Vector Bit -> Vector Bit
-- | For each unset bit of the first argument, deposit the corresponding
-- bit of the second argument to the result.
--
--
-- >>> :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))
--
excludeBits :: Vector Bit -> Vector Bit -> Vector Bit
-- | Cast a vector of words to a vector of bits. Cf. castFromWords.
castFromWordsM :: MVector s Word -> MVector s Bit
-- | 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.
castToWordsM :: MVector s Bit -> Maybe (MVector s Word)
-- | 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.
cloneToWordsM :: PrimMonad m => MVector (PrimState m) Bit -> m (MVector (PrimState m) Word)
-- | Zip two vectors with the given function. rewriting contents of the
-- second argument. Cf. zipBits.
--
--
-- >>> :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 a 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
--
zipInPlace :: forall m. PrimMonad m => (forall a. Bits a => a -> a -> a) -> Vector Bit -> MVector (PrimState m) Bit -> m ()
-- | 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]
--
mapInPlace :: PrimMonad m => (forall a. Bits a => a -> a) -> MVector (PrimState m) Bit -> m ()
-- | Invert (flip) all bits in-place.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> Data.Vector.Unboxed.modify invertInPlace [0,1,0,1,0]
-- [1,0,1,0,1]
--
invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()
-- | 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 vector-rotcev package to reverse vectors in
-- O(1) time.
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()
-- | Same as selectBits, but deposit selected bits in-place. Returns
-- a number of selected bits. It is caller's responsibility to trim the
-- result to this number.
--
--
-- >>> :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]
--
selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int
-- | Same as excludeBits, but deposit excluded bits in-place.
-- Returns a number of excluded bits. It is caller's responsibility to
-- trim the result to this number.
--
--
-- >>> :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]
--
excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int
-- | Binary polynomials of one variable, backed by an unboxed Vector
-- Bit.
--
-- Polynomials are stored normalized, without leading zero coefficients.
--
-- 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
--
data F2Poly
-- | Convert F2Poly to a vector of coefficients (first element
-- corresponds to a constant term).
--
--
-- >>> :set -XBinaryLiterals
--
-- >>> unF2Poly 0b1101
-- [1,0,1,1]
--
unF2Poly :: F2Poly -> Vector Bit
-- | Make F2Poly from a list of coefficients (first element
-- corresponds to a constant term).
--
--
-- >>> :set -XOverloadedLists
--
-- >>> toF2Poly [1,0,1,1,0,0]
-- 0b1101
--
toF2Poly :: Vector Bit -> F2Poly
-- | Execute the extended Euclidean algorithm. For polynomials a
-- and b, compute their unique greatest common divisor
-- g and the unique coefficient polynomial s satisfying
-- as + bt = g.
--
--
-- >>> :set -XBinaryLiterals
--
-- >>> gcdExt 0b101 0b0101
-- (0b101,0b0)
--
-- >>> gcdExt 0b11 0b111
-- (0b1,0b10)
--
gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)
-- | This module exposes an interface with thread-unsafe writes and flips.
-- Consider using Data.Bit.ThreadSafe, which is thread-safe, but
-- slower (up to 20%).
module Data.Bit
-- | 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 10% slower.
newtype Bit
Bit :: Bool -> Bit
[unBit] :: Bit -> Bool
-- | Flip the bit at the given position. No bounds 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]
--
unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()
-- | 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]
--
flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()
-- | 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]
--
castFromWords :: Vector Word -> Vector Bit
-- | Try to cast an unboxed vector of bits to an unboxed vector of words.
-- It succeeds if a vector of bits is aligned. Use cloneToWords
-- otherwise. Cf. castToWordsM.
--
--
-- castToWords (castFromWords v) == Just v
--
castToWords :: Vector Bit -> Maybe (Vector Word)
-- | 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]
--
cloneToWords :: Vector Bit -> Vector Word
-- | Cast a unboxed vector of Word8 to an unboxed vector of bits.
--
-- On big-endian architectures castFromWords8 resorts to copying
-- instead of aliasing underlying arrays.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> castFromWords8 [123]
-- [1,1,0,1,1,1,1,0]
--
castFromWords8 :: Vector Word8 -> Vector Bit
-- | Try to cast an unboxed vector of bits to an unboxed vector of
-- Word8. It succeeds if a vector of bits is aligned. Use
-- cloneToWords8 otherwise.
--
--
-- castToWords8 (castFromWords8 v) == Just v
--
castToWords8 :: Vector Bit -> Maybe (Vector Word8)
-- | 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]
--
cloneToWords8 :: Vector Bit -> Vector Word8
-- | 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]
--
cloneFromByteString :: ByteString -> Vector Bit
-- | 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#"
--
cloneToByteString :: Vector Bit -> ByteString
-- | Zip two vectors with the given function. Similar to zipWith,
-- but up to 1000x (!) faster.
--
-- For sufficiently dense sets, represented as bitmaps, zipBits is
-- up to 32x faster than union, intersection, etc.
--
-- Users are strongly encouraged to enable flag libgmp for the
-- ultimate performance of zipBits.
--
--
-- >>> :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]
--
zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit
-- | 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]
--
mapBits :: (forall a. Bits a => a -> a) -> Vector Bit -> Vector Bit
-- | Invert (flip) all bits.
--
-- Users are strongly encouraged to enable flag libgmp for the
-- ultimate performance of invertBits.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> invertBits [0,1,0,1,0]
-- [1,0,1,0,1]
--
invertBits :: Vector Bit -> Vector Bit
-- | Reverse the order of bits.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> reverseBits [1,1,0,1,0]
-- [0,1,0,1,1]
--
--
-- Consider using vector-rotcev package to reverse vectors in
-- O(1) time.
reverseBits :: Vector Bit -> Vector Bit
-- | 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
--
bitIndex :: Bit -> Vector Bit -> Maybe Int
-- | 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.
nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int
-- | Return the number of set bits in a vector (population count,
-- popcount).
--
-- Users are strongly encouraged to enable flag libgmp for the
-- ultimate performance of countBits.
--
--
-- >>> :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.
countBits :: Vector Bit -> Int
-- | Return 0-based indices of set bits in a vector.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> listBits [1,1,0,1,0,1]
-- [0,1,3,5]
--
listBits :: Vector Bit -> [Int]
-- | 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).
--
--
-- >>> :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))
--
selectBits :: Vector Bit -> Vector Bit -> Vector Bit
-- | For each unset bit of the first argument, deposit the corresponding
-- bit of the second argument to the result.
--
--
-- >>> :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))
--
excludeBits :: Vector Bit -> Vector Bit -> Vector Bit
-- | Cast a vector of words to a vector of bits. Cf. castFromWords.
castFromWordsM :: MVector s Word -> MVector s Bit
-- | 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.
castToWordsM :: MVector s Bit -> Maybe (MVector s Word)
-- | 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.
cloneToWordsM :: PrimMonad m => MVector (PrimState m) Bit -> m (MVector (PrimState m) Word)
-- | Zip two vectors with the given function. rewriting contents of the
-- second argument. Cf. zipBits.
--
--
-- >>> :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 a 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
--
zipInPlace :: forall m. PrimMonad m => (forall a. Bits a => a -> a -> a) -> Vector Bit -> MVector (PrimState m) Bit -> m ()
-- | 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]
--
mapInPlace :: PrimMonad m => (forall a. Bits a => a -> a) -> MVector (PrimState m) Bit -> m ()
-- | Invert (flip) all bits in-place.
--
--
-- >>> :set -XOverloadedLists
--
-- >>> Data.Vector.Unboxed.modify invertInPlace [0,1,0,1,0]
-- [1,0,1,0,1]
--
invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()
-- | 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 vector-rotcev package to reverse vectors in
-- O(1) time.
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()
-- | Same as selectBits, but deposit selected bits in-place. Returns
-- a number of selected bits. It is caller's responsibility to trim the
-- result to this number.
--
--
-- >>> :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]
--
selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int
-- | Same as excludeBits, but deposit excluded bits in-place.
-- Returns a number of excluded bits. It is caller's responsibility to
-- trim the result to this number.
--
--
-- >>> :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]
--
excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int
-- | Binary polynomials of one variable, backed by an unboxed Vector
-- Bit.
--
-- Polynomials are stored normalized, without leading zero coefficients.
--
-- 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
--
data F2Poly
-- | Convert F2Poly to a vector of coefficients (first element
-- corresponds to a constant term).
--
--
-- >>> :set -XBinaryLiterals
--
-- >>> unF2Poly 0b1101
-- [1,0,1,1]
--
unF2Poly :: F2Poly -> Vector Bit
-- | Make F2Poly from a list of coefficients (first element
-- corresponds to a constant term).
--
--
-- >>> :set -XOverloadedLists
--
-- >>> toF2Poly [1,0,1,1,0,0]
-- 0b1101
--
toF2Poly :: Vector Bit -> F2Poly
-- | Execute the extended Euclidean algorithm. For polynomials a
-- and b, compute their unique greatest common divisor
-- g and the unique coefficient polynomial s satisfying
-- as + bt = g.
--
--
-- >>> :set -XBinaryLiterals
--
-- >>> gcdExt 0b101 0b0101
-- (0b101,0b0)
--
-- >>> gcdExt 0b11 0b111
-- (0b1,0b10)
--
gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)