-- 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 3500x faster.
--   
--   The vector package represents unboxed arrays of Bools
--   spending 1 byte (8 bits) per boolean. This library provides a newtype
--   wrapper Bit and a custom instance of an unboxed Vector,
--   which packs bits densely, achieving an 8x smaller 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 3500x faster than Vector Bool.
--   
--   
Thread safety
--   
--   
--   
- Data.Bit is faster, but writes and flips are not
--   thread-safe. This is because naive updates are not atomic: they read
--   the whole word from memory, then modify a bit, then write the whole
--   word back. Concurrently modifying non-intersecting slices of the same
--   underlying array may also lead to unexpected results, since they can
--   share a word in memory.
--   
- Data.Bit.ThreadSafe is slower (usually 10-20%), but writes
--   and flips are thread-safe. Additionally, concurrently modifying
--   non-intersecting slices of the same underlying array works as
--   expected. However, operations that affect multiple elements are not
--   guaranteed to be atomic.
--   
--   
--   
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.5.0

-- | This module exposes an interface with thread-safe writes and flips.
--   Additionally, concurrently modifying non-intersecting slices of the
--   same underlying array works as expected. However, operations that
--   affect multiple elements are not guaranteed to be atomic. Consider
--   using Data.Bit, which is faster (usually 10-20%, up to 50% for
--   short vectors), but not thread-safe.
module Data.Bit.ThreadSafe

-- | 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.
newtype Bit
Bit :: Bool -> Bit

[unBit] :: Bit -> Bool

-- | Flip the bit at the given position. No bound 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 the 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 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]
--   
castFromWords8 :: Vector Word8 -> Vector Bit

-- | 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
--   
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 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]
--   
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.
--   
--   
--   >>> :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 the 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).
--   
--   
--   >>> :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, 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))
--   
selectBits :: Vector Bit -> Vector Bit -> Vector Bit

-- | 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))
--   
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 the
--   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 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
--   
zipInPlace :: 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 the vector-rotcev package to reverse vectors in
--   O(1) time.
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

-- | 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]
--   
selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int

-- | 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]
--   
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.
--   
--   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
--   
data F2Poly

-- | Convert an 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 an 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
--   <math>.
--   
--   
--   >>> :set -XBinaryLiterals
--   
--   >>> gcdExt 0b101 0b0101
--   (0b101,0b0)
--   
--   >>> gcdExt 0b11 0b111
--   (0b1,0b10)
--   
gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)

-- | 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).
module Data.Bit

-- | 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.
newtype Bit
Bit :: Bool -> Bit

[unBit] :: Bit -> Bool

-- | 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]
--   
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 the 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 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]
--   
castFromWords8 :: Vector Word8 -> Vector Bit

-- | 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
--   
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 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]
--   
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.
--   
--   
--   >>> :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 the 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).
--   
--   
--   >>> :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, 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))
--   
selectBits :: Vector Bit -> Vector Bit -> Vector Bit

-- | 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))
--   
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 the
--   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 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
--   
zipInPlace :: 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 the vector-rotcev package to reverse vectors in
--   O(1) time.
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

-- | 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]
--   
selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int

-- | 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]
--   
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.
--   
--   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
--   
data F2Poly

-- | Convert an 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 an 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
--   <math>.
--   
--   
--   >>> :set -XBinaryLiterals
--   
--   >>> gcdExt 0b101 0b0101
--   (0b101,0b0)
--   
--   >>> gcdExt 0b11 0b111
--   (0b1,0b10)
--   
gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)
