-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Space-efficient bit vectors
--   
--   A newtype over <a>Bool</a> with a better <a>Vector</a> instance: 8x
--   less memory, up to 3500x faster.
--   
--   The <a>vector</a> package represents unboxed arrays of <a>Bool</a>s
--   spending 1 byte (8 bits) per boolean. This library provides a newtype
--   wrapper <a>Bit</a> and a custom instance of an unboxed <a>Vector</a>,
--   which packs bits densely, achieving an <b>8x smaller memory
--   footprint.</b> 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 <a>Vector</a>
--   <a>Bit</a> is up to 3500x faster than <a>Vector</a> <a>Bool</a>.
--   
--   <h3>Thread safety</h3>
--   
--   <ul>
--   <li><a>Data.Bit</a> 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.</li>
--   <li><a>Data.Bit.ThreadSafe</a> 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.</li>
--   </ul>
--   
--   <h3>Similar packages</h3>
--   
--   <ul>
--   <li><a>bv</a> and <a>bv-little</a> do not offer mutable vectors.</li>
--   <li><a>array</a> is memory-efficient for <a>Bool</a>, but lacks a
--   handy <a>Vector</a> interface and is not thread-safe.</li>
--   </ul>
@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 <a>Data.Bit</a>, 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
--   <a>Data.Vector.Unboxed</a>, which packs booleans as efficient as
--   possible (8 values per byte). Unboxed vectors of <a>Bit</a> use 8x
--   less memory than unboxed vectors of <a>Bool</a> (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 <a>flip</a> <a>unsafeModify</a> <a>complement</a>, but
--   up to 33% faster and atomic.
--   
--   In general there is no reason to <a>unsafeModify</a> bit vectors:
--   either you modify it with <a>id</a> (which is <a>id</a> altogether) or
--   with <a>complement</a> (which is <a>unsafeFlipBit</a>).
--   
--   <pre>
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (\v -&gt; unsafeFlipBit v 1) (read "[1,1,1]")
--   [1,0,1]
--   </pre>
unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()

-- | Flip the bit at the given position. Equivalent to <a>flip</a>
--   <a>modify</a> <a>complement</a>, but up to 33% faster and atomic.
--   
--   In general there is no reason to <a>modify</a> bit vectors: either you
--   modify it with <a>id</a> (which is <a>id</a> altogether) or with
--   <a>complement</a> (which is <a>flipBit</a>).
--   
--   <pre>
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (\v -&gt; flipBit v 1) (read "[1,1,1]")
--   [1,0,1]
--   </pre>
flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()

-- | Cast an unboxed vector of words to an unboxed vector of bits. Cf.
--   <a>castFromWordsM</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>cloneToWords</a>
--   otherwise. Cf. <a>castToWordsM</a>.
--   
--   <pre>
--   castToWords (castFromWords v) == Just v
--   </pre>
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. <a>cloneToWordsM</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; cloneToWords [1,1,0,1,1,1,1]
--   [123]
--   </pre>
cloneToWords :: Vector Bit -> Vector Word

-- | Cast an unboxed vector of <a>Word8</a> to an unboxed vector of bits.
--   
--   On big-endian architectures <a>castFromWords8</a> resorts to copying
--   instead of aliasing the underlying array.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; castFromWords8 [123]
--   [1,1,0,1,1,1,1,0]
--   </pre>
castFromWords8 :: Vector Word8 -> Vector Bit

-- | Try to cast an unboxed vector of bits to an unboxed vector of
--   <a>Word8</a>. It succeeds if the vector of bits is aligned. Use
--   <a>cloneToWords8</a> otherwise.
--   
--   <pre>
--   castToWords8 (castFromWords8 v) == Just v
--   </pre>
castToWords8 :: Vector Bit -> Maybe (Vector Word8)

-- | Clone an unboxed vector of bits to a new unboxed vector of
--   <a>Word8</a>. If the bits don't completely fill the bytes, the last
--   <a>Word8</a> will be zero-padded.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; cloneToWords8 [1,1,0,1,1,1,1]
--   [123]
--   </pre>
cloneToWords8 :: Vector Bit -> Vector Word8

-- | Clone a <a>ByteString</a> to a new unboxed vector of bits.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedStrings
--   
--   &gt;&gt;&gt; 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]
--   </pre>
cloneFromByteString :: ByteString -> Vector Bit

-- | Clone an unboxed vector of bits to a new <a>ByteString</a>. If the
--   bits don't completely fill the bytes, the last character will be
--   zero-padded.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; cloneToByteString [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1]
--   "ab#"
--   </pre>
cloneToByteString :: Vector Bit -> ByteString

-- | Zip two vectors with the given function. Similar to <a>zipWith</a>,
--   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, <a>zipBits</a> is
--   up to 64x faster than <a>union</a>, <a>intersection</a>, etc.
--   
--   The function passed to zipBits may only use the following <a>Bits</a>
--   methods:
--   
--   <a>.&amp;.</a>, <a>.|.</a>, <a>xor</a>, <a>complement</a>,
--   <a>zeroBits</a>, and (likely uselessly) <a>bitSizeMaybe</a> and
--   <a>isSigned</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; zipBits (.&amp;.) [1,1,0] [0,1,1] -- intersection
--   [0,1,0]
--   
--   &gt;&gt;&gt; zipBits (.|.) [1,1,0] [0,1,1] -- union
--   [1,1,1]
--   
--   &gt;&gt;&gt; zipBits (\x y -&gt; x .&amp;. complement y) [1,1,0] [0,1,1] -- difference
--   [1,0,0]
--   
--   &gt;&gt;&gt; zipBits xor [1,1,0] [0,1,1] -- symmetric difference
--   [1,0,1]
--   </pre>
zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit

-- | Map a vectors with the given function. Similar to <a>map</a>, but
--   faster.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; mapBits complement [0,1,1]
--   [1,0,0]
--   </pre>
mapBits :: (forall a. Bits a => a -> a) -> Vector Bit -> Vector Bit

-- | Invert (flip) all bits.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; invertBits [0,1,0,1,0]
--   [1,0,1,0,1]
--   </pre>
invertBits :: Vector Bit -> Vector Bit

-- | Reverse the order of bits.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; reverseBits [1,1,0,1,0]
--   [0,1,0,1,1]
--   </pre>
--   
--   Consider using the <a>vector-rotcev</a> 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 <a>elemIndex</a>, but up to 64x faster.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; bitIndex 1 [0,0,1,0,1]
--   Just 2
--   
--   &gt;&gt;&gt; bitIndex 1 [0,0,0,0,0]
--   Nothing
--   </pre>
--   
--   <pre>
--   bitIndex bit == nthBitIndex bit 1
--   </pre>
--   
--   One can also use it to reduce a vector with disjunction or
--   conjunction:
--   
--   <pre>
--   import Data.Maybe
--   isAnyBitSet   = isJust    . bitIndex 1
--   areAllBitsSet = isNothing . bitIndex 0
--   </pre>
bitIndex :: Bit -> Vector Bit -> Maybe Int

-- | Return the index of the <tt>n</tt>-th bit in the vector with the
--   specified value, if any. Here <tt>n</tt> is 1-based and the index is
--   0-based. Non-positive <tt>n</tt> results in an error.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; nthBitIndex 1 2 [0,1,0,1,1,1,0] -- 2nd occurence of 1
--   Just 3
--   
--   &gt;&gt;&gt; nthBitIndex 1 5 [0,1,0,1,1,1,0] -- 5th occurence of 1
--   Nothing
--   </pre>
--   
--   One can use <a>nthBitIndex</a> to implement to implement
--   <tt>select{0,1}</tt> queries for <a>succinct dictionaries</a>.
nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int

-- | Return the number of set bits in a vector (population count,
--   popcount).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; countBits [1,1,0,1,0,1]
--   4
--   </pre>
--   
--   One can combine <a>countBits</a> with <a>take</a> to implement
--   <tt>rank{0,1}</tt> queries for <a>succinct dictionaries</a>.
countBits :: Vector Bit -> Int

-- | Return 0-based indices of set bits in a vector.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; listBits [1,1,0,1,0,1]
--   [0,1,3,5]
--   </pre>
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 <a>parallel bit
--   extract instruction (PEXT)</a>.
--   
--   Note: If one input is larger than the other, the remaining bits will
--   be ignored.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; selectBits [0,1,0,1,1] [1,1,0,0,1]
--   [1,0,1]
--   </pre>
--   
--   Here is a reference (but slow) implementation:
--   
--   <pre>
--   import qualified Data.Vector.Unboxed as U
--   selectBits mask ws = U.map snd (U.filter (unBit . fst) (U.zip mask ws))
--   </pre>
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.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; excludeBits [0,1,0,1,1] [1,1,0,0,1]
--   [1,0]
--   </pre>
--   
--   Here is a reference (but slow) implementation:
--   
--   <pre>
--   import qualified Data.Vector.Unboxed as U
--   excludeBits mask ws = U.map snd (U.filter (not . unBit . fst) (U.zip mask ws))
--   </pre>
excludeBits :: Vector Bit -> Vector Bit -> Vector Bit

-- | Cast a vector of words to a vector of bits. Cf. <a>castFromWords</a>.
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 <a>cloneToWordsM</a> otherwise. Cf.
--   <a>castToWords</a>.
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. <a>cloneToWords</a>.
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. <a>zipBits</a>.
--   
--   Note: If one input is larger than the other, the remaining bits will
--   be ignored.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (zipInPlace (.&amp;.) [1,1,0]) [0,1,1]
--   [0,1,0]
--   </pre>
--   
--   <b>Warning</b>: if the immutable vector is shorter than the mutable
--   one, it is the caller's responsibility to trim the result:
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (zipInPlace (.&amp;.) [1,1,0]) [0,1,1,1,1,1]
--   [0,1,0,1,1,1] -- note trailing garbage
--   </pre>
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. <a>mapBits</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (mapInPlace complement) [0,1,1]
--   [1,0,0]
--   </pre>
mapInPlace :: PrimMonad m => (forall a. Bits a => a -> a) -> MVector (PrimState m) Bit -> m ()

-- | Invert (flip) all bits in-place.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify invertInPlace [0,1,0,1,0]
--   [1,0,1,0,1]
--   </pre>
invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

-- | Reverse the order of bits in-place.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify reverseInPlace [1,1,0,1,0]
--   [0,1,0,1,1]
--   </pre>
--   
--   Consider using the <a>vector-rotcev</a> package to reverse vectors in
--   O(1) time.
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

-- | Same as <a>selectBits</a>, 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.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Control.Monad.ST (runST)
--   
--   &gt;&gt;&gt; import qualified Data.Vector.Unboxed as U
--   
--   &gt;&gt;&gt; runST $ do { vec &lt;- U.unsafeThaw [1,1,0,0,1]; n &lt;- selectBitsInPlace [0,1,0,1,1] vec; U.take n &lt;$&gt; U.unsafeFreeze vec }
--   [1,0,1]
--   </pre>
selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int

-- | Same as <a>excludeBits</a>, 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.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Control.Monad.ST (runST)
--   
--   &gt;&gt;&gt; import qualified Data.Vector.Unboxed as U
--   
--   &gt;&gt;&gt; runST $ do { vec &lt;- U.unsafeThaw [1,1,0,0,1]; n &lt;- excludeBitsInPlace [0,1,0,1,1] vec; U.take n &lt;$&gt; U.unsafeFreeze vec }
--   [1,0]
--   </pre>
excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int

-- | Binary polynomials of one variable, backed by an unboxed <a>Vector</a>
--   <a>Bit</a>.
--   
--   Polynomials are stored normalized, without leading zero coefficients.
--   
--   The <a>Ord</a> instance does not make much sense mathematically, it is
--   defined only for the sake of <a>Set</a>, <a>Map</a>, etc.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XBinaryLiterals
--   
--   &gt;&gt;&gt; -- (1 + x) * (1 + x + x^2) = 1 + x^3 (mod 2)
--   
--   &gt;&gt;&gt; 0b11 * 0b111 :: F2Poly
--   0b1001
--   </pre>
data F2Poly

-- | Convert an <a>F2Poly</a> to a vector of coefficients (first element
--   corresponds to a constant term).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XBinaryLiterals
--   
--   &gt;&gt;&gt; unF2Poly 0b1101
--   [1,0,1,1]
--   </pre>
unF2Poly :: F2Poly -> Vector Bit

-- | Make an <a>F2Poly</a> from a list of coefficients (first element
--   corresponds to a constant term).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; toF2Poly [1,0,1,1,0,0]
--   0b1101
--   </pre>
toF2Poly :: Vector Bit -> F2Poly

-- | Execute the extended Euclidean algorithm. For polynomials <tt>a</tt>
--   and <tt>b</tt>, compute their unique greatest common divisor
--   <tt>g</tt> and the unique coefficient polynomial <tt>s</tt> satisfying
--   &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XBinaryLiterals
--   
--   &gt;&gt;&gt; gcdExt 0b101 0b0101
--   (0b101,0b0)
--   
--   &gt;&gt;&gt; gcdExt 0b11 0b111
--   (0b1,0b10)
--   </pre>
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 <a>Data.Bit.ThreadSafe</a>, 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
--   <a>Data.Vector.Unboxed</a>, which packs booleans as efficient as
--   possible (8 values per byte). Unboxed vectors of <a>Bit</a> use 8x
--   less memory than unboxed vectors of <a>Bool</a> (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 <a>flip</a> <a>unsafeModify</a> <a>complement</a>, but
--   up to 2x faster.
--   
--   In general there is no reason to <a>unsafeModify</a> bit vectors:
--   either you modify it with <a>id</a> (which is <a>id</a> altogether) or
--   with <a>complement</a> (which is <a>unsafeFlipBit</a>).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (`unsafeFlipBit` 2) [1,1,1,1]
--   [1,1,0,1]
--   </pre>
unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()

-- | Flip the bit at the given position. Equivalent to <a>flip</a>
--   <a>modify</a> <a>complement</a>, but up to 2x faster.
--   
--   In general there is no reason to <a>modify</a> bit vectors: either you
--   modify it with <a>id</a> (which is <a>id</a> altogether) or with
--   <a>complement</a> (which is <a>flipBit</a>).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (`flipBit` 2) [1,1,1,1]
--   [1,1,0,1]
--   </pre>
flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m ()

-- | Cast an unboxed vector of words to an unboxed vector of bits. Cf.
--   <a>castFromWordsM</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>cloneToWords</a>
--   otherwise. Cf. <a>castToWordsM</a>.
--   
--   <pre>
--   castToWords (castFromWords v) == Just v
--   </pre>
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. <a>cloneToWordsM</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; cloneToWords [1,1,0,1,1,1,1]
--   [123]
--   </pre>
cloneToWords :: Vector Bit -> Vector Word

-- | Cast an unboxed vector of <a>Word8</a> to an unboxed vector of bits.
--   
--   On big-endian architectures <a>castFromWords8</a> resorts to copying
--   instead of aliasing the underlying array.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; castFromWords8 [123]
--   [1,1,0,1,1,1,1,0]
--   </pre>
castFromWords8 :: Vector Word8 -> Vector Bit

-- | Try to cast an unboxed vector of bits to an unboxed vector of
--   <a>Word8</a>. It succeeds if the vector of bits is aligned. Use
--   <a>cloneToWords8</a> otherwise.
--   
--   <pre>
--   castToWords8 (castFromWords8 v) == Just v
--   </pre>
castToWords8 :: Vector Bit -> Maybe (Vector Word8)

-- | Clone an unboxed vector of bits to a new unboxed vector of
--   <a>Word8</a>. If the bits don't completely fill the bytes, the last
--   <a>Word8</a> will be zero-padded.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; cloneToWords8 [1,1,0,1,1,1,1]
--   [123]
--   </pre>
cloneToWords8 :: Vector Bit -> Vector Word8

-- | Clone a <a>ByteString</a> to a new unboxed vector of bits.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedStrings
--   
--   &gt;&gt;&gt; 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]
--   </pre>
cloneFromByteString :: ByteString -> Vector Bit

-- | Clone an unboxed vector of bits to a new <a>ByteString</a>. If the
--   bits don't completely fill the bytes, the last character will be
--   zero-padded.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; cloneToByteString [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1]
--   "ab#"
--   </pre>
cloneToByteString :: Vector Bit -> ByteString

-- | Zip two vectors with the given function. Similar to <a>zipWith</a>,
--   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, <a>zipBits</a> is
--   up to 64x faster than <a>union</a>, <a>intersection</a>, etc.
--   
--   The function passed to zipBits may only use the following <a>Bits</a>
--   methods:
--   
--   <a>.&amp;.</a>, <a>.|.</a>, <a>xor</a>, <a>complement</a>,
--   <a>zeroBits</a>, and (likely uselessly) <a>bitSizeMaybe</a> and
--   <a>isSigned</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; zipBits (.&amp;.) [1,1,0] [0,1,1] -- intersection
--   [0,1,0]
--   
--   &gt;&gt;&gt; zipBits (.|.) [1,1,0] [0,1,1] -- union
--   [1,1,1]
--   
--   &gt;&gt;&gt; zipBits (\x y -&gt; x .&amp;. complement y) [1,1,0] [0,1,1] -- difference
--   [1,0,0]
--   
--   &gt;&gt;&gt; zipBits xor [1,1,0] [0,1,1] -- symmetric difference
--   [1,0,1]
--   </pre>
zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit

-- | Map a vectors with the given function. Similar to <a>map</a>, but
--   faster.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; mapBits complement [0,1,1]
--   [1,0,0]
--   </pre>
mapBits :: (forall a. Bits a => a -> a) -> Vector Bit -> Vector Bit

-- | Invert (flip) all bits.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; invertBits [0,1,0,1,0]
--   [1,0,1,0,1]
--   </pre>
invertBits :: Vector Bit -> Vector Bit

-- | Reverse the order of bits.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; reverseBits [1,1,0,1,0]
--   [0,1,0,1,1]
--   </pre>
--   
--   Consider using the <a>vector-rotcev</a> 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 <a>elemIndex</a>, but up to 64x faster.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; bitIndex 1 [0,0,1,0,1]
--   Just 2
--   
--   &gt;&gt;&gt; bitIndex 1 [0,0,0,0,0]
--   Nothing
--   </pre>
--   
--   <pre>
--   bitIndex bit == nthBitIndex bit 1
--   </pre>
--   
--   One can also use it to reduce a vector with disjunction or
--   conjunction:
--   
--   <pre>
--   import Data.Maybe
--   isAnyBitSet   = isJust    . bitIndex 1
--   areAllBitsSet = isNothing . bitIndex 0
--   </pre>
bitIndex :: Bit -> Vector Bit -> Maybe Int

-- | Return the index of the <tt>n</tt>-th bit in the vector with the
--   specified value, if any. Here <tt>n</tt> is 1-based and the index is
--   0-based. Non-positive <tt>n</tt> results in an error.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; nthBitIndex 1 2 [0,1,0,1,1,1,0] -- 2nd occurence of 1
--   Just 3
--   
--   &gt;&gt;&gt; nthBitIndex 1 5 [0,1,0,1,1,1,0] -- 5th occurence of 1
--   Nothing
--   </pre>
--   
--   One can use <a>nthBitIndex</a> to implement to implement
--   <tt>select{0,1}</tt> queries for <a>succinct dictionaries</a>.
nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int

-- | Return the number of set bits in a vector (population count,
--   popcount).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; countBits [1,1,0,1,0,1]
--   4
--   </pre>
--   
--   One can combine <a>countBits</a> with <a>take</a> to implement
--   <tt>rank{0,1}</tt> queries for <a>succinct dictionaries</a>.
countBits :: Vector Bit -> Int

-- | Return 0-based indices of set bits in a vector.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; listBits [1,1,0,1,0,1]
--   [0,1,3,5]
--   </pre>
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 <a>parallel bit
--   extract instruction (PEXT)</a>.
--   
--   Note: If one input is larger than the other, the remaining bits will
--   be ignored.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; selectBits [0,1,0,1,1] [1,1,0,0,1]
--   [1,0,1]
--   </pre>
--   
--   Here is a reference (but slow) implementation:
--   
--   <pre>
--   import qualified Data.Vector.Unboxed as U
--   selectBits mask ws = U.map snd (U.filter (unBit . fst) (U.zip mask ws))
--   </pre>
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.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; excludeBits [0,1,0,1,1] [1,1,0,0,1]
--   [1,0]
--   </pre>
--   
--   Here is a reference (but slow) implementation:
--   
--   <pre>
--   import qualified Data.Vector.Unboxed as U
--   excludeBits mask ws = U.map snd (U.filter (not . unBit . fst) (U.zip mask ws))
--   </pre>
excludeBits :: Vector Bit -> Vector Bit -> Vector Bit

-- | Cast a vector of words to a vector of bits. Cf. <a>castFromWords</a>.
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 <a>cloneToWordsM</a> otherwise. Cf.
--   <a>castToWords</a>.
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. <a>cloneToWords</a>.
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. <a>zipBits</a>.
--   
--   Note: If one input is larger than the other, the remaining bits will
--   be ignored.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (zipInPlace (.&amp;.) [1,1,0]) [0,1,1]
--   [0,1,0]
--   </pre>
--   
--   <b>Warning</b>: if the immutable vector is shorter than the mutable
--   one, it is the caller's responsibility to trim the result:
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (zipInPlace (.&amp;.) [1,1,0]) [0,1,1,1,1,1]
--   [0,1,0,1,1,1] -- note trailing garbage
--   </pre>
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. <a>mapBits</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Data.Bits
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify (mapInPlace complement) [0,1,1]
--   [1,0,0]
--   </pre>
mapInPlace :: PrimMonad m => (forall a. Bits a => a -> a) -> MVector (PrimState m) Bit -> m ()

-- | Invert (flip) all bits in-place.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify invertInPlace [0,1,0,1,0]
--   [1,0,1,0,1]
--   </pre>
invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

-- | Reverse the order of bits in-place.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; Data.Vector.Unboxed.modify reverseInPlace [1,1,0,1,0]
--   [0,1,0,1,1]
--   </pre>
--   
--   Consider using the <a>vector-rotcev</a> package to reverse vectors in
--   O(1) time.
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

-- | Same as <a>selectBits</a>, 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.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Control.Monad.ST (runST)
--   
--   &gt;&gt;&gt; import qualified Data.Vector.Unboxed as U
--   
--   &gt;&gt;&gt; runST $ do { vec &lt;- U.unsafeThaw [1,1,0,0,1]; n &lt;- selectBitsInPlace [0,1,0,1,1] vec; U.take n &lt;$&gt; U.unsafeFreeze vec }
--   [1,0,1]
--   </pre>
selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int

-- | Same as <a>excludeBits</a>, 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.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; import Control.Monad.ST (runST)
--   
--   &gt;&gt;&gt; import qualified Data.Vector.Unboxed as U
--   
--   &gt;&gt;&gt; runST $ do { vec &lt;- U.unsafeThaw [1,1,0,0,1]; n &lt;- excludeBitsInPlace [0,1,0,1,1] vec; U.take n &lt;$&gt; U.unsafeFreeze vec }
--   [1,0]
--   </pre>
excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int

-- | Binary polynomials of one variable, backed by an unboxed <a>Vector</a>
--   <a>Bit</a>.
--   
--   Polynomials are stored normalized, without leading zero coefficients.
--   
--   The <a>Ord</a> instance does not make much sense mathematically, it is
--   defined only for the sake of <a>Set</a>, <a>Map</a>, etc.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XBinaryLiterals
--   
--   &gt;&gt;&gt; -- (1 + x) * (1 + x + x^2) = 1 + x^3 (mod 2)
--   
--   &gt;&gt;&gt; 0b11 * 0b111 :: F2Poly
--   0b1001
--   </pre>
data F2Poly

-- | Convert an <a>F2Poly</a> to a vector of coefficients (first element
--   corresponds to a constant term).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XBinaryLiterals
--   
--   &gt;&gt;&gt; unF2Poly 0b1101
--   [1,0,1,1]
--   </pre>
unF2Poly :: F2Poly -> Vector Bit

-- | Make an <a>F2Poly</a> from a list of coefficients (first element
--   corresponds to a constant term).
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedLists
--   
--   &gt;&gt;&gt; toF2Poly [1,0,1,1,0,0]
--   0b1101
--   </pre>
toF2Poly :: Vector Bit -> F2Poly

-- | Execute the extended Euclidean algorithm. For polynomials <tt>a</tt>
--   and <tt>b</tt>, compute their unique greatest common divisor
--   <tt>g</tt> and the unique coefficient polynomial <tt>s</tt> satisfying
--   &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XBinaryLiterals
--   
--   &gt;&gt;&gt; gcdExt 0b101 0b0101
--   (0b101,0b0)
--   
--   &gt;&gt;&gt; gcdExt 0b11 0b111
--   (0b1,0b10)
--   </pre>
gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)
