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


-- | Unboxed bit vectors
--   
--   Bit vectors library for Haskell. The current <tt>vector</tt> package
--   represents unboxed arrays of <tt>Bool</tt> allocating one byte per
--   boolean, which might be considered wasteful. This library provides a
--   newtype wrapper <tt>Bit</tt> and a custom instance of unboxed
--   <tt>Vector</tt>, which packs booleans densely. It is a time-memory
--   tradeoff: 8x less memory footprint at the price of moderate
--   performance penalty (mostly, for random writes).
@package bitvec
@version 0.2.0.1

module Data.Bit

-- | A newtype wrapper with a custom instance of
--   <a>Data.Vector.Unboxed</a>, which packs booleans as efficient as
--   possible (8 values per byte). Vectors of <a>Bit</a> use 8x less memory
--   than vectors of <a>Bool</a> (which stores one value per byte), but
--   random writes are slightly slower.
--   
--   In addition to <a>Data.Vector.Unboxed</a> interface, one can also find
--   assorted utilities from <a>Data.Vector.Unboxed.Bit</a> and
--   <a>Data.Vector.Unboxed.Mutable.Bit</a>.
newtype Bit
Bit :: Bool -> Bit
[unBit] :: Bit -> Bool

module Data.Vector.Unboxed.Mutable.Bit

-- | The number of <a>Bit</a>s in a <a>Word</a>. A handy constant to have
--   around when defining <a>Word</a>-based bulk operations on bit vectors.
wordSize :: Int

-- | Get the length of the vector that would be created by
--   <a>cloneToWords</a>
wordLength :: MVector s Bit -> Int

-- | Clone a specified number of bits from a vector of words into a new
--   vector of bits (interpreting the words in little-endian order, as
--   described at <a>indexWord</a>). If there are not enough words for the
--   number of bits requested, the vector will be zero-padded.
cloneFromWords :: PrimMonad m => Int -> MVector (PrimState m) Word -> m (MVector (PrimState m) Bit)

-- | 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.
cloneToWords :: PrimMonad m => MVector (PrimState m) Bit -> m (MVector (PrimState m) Word)

-- | read a word at the given bit offset in little-endian order (i.e., the
--   LSB will correspond to the bit at the given address, the 2's bit will
--   correspond to the address + 1, etc.). If the offset is such that the
--   word extends past the end of the vector, the result is zero-padded.
readWord :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m Word

-- | write a word at the given bit offset in little-endian order (i.e., the
--   LSB will correspond to the bit at the given address, the 2's bit will
--   correspond to the address + 1, etc.). If the offset is such that the
--   word extends past the end of the vector, the word is truncated and as
--   many low-order bits as possible are written.
writeWord :: PrimMonad m => MVector (PrimState m) Bit -> Int -> Word -> m ()

-- | Map a function over a bit vector one <a>Word</a> at a time
--   (<a>wordSize</a> bits at a time). The function will be passed the bit
--   index (which will always be <a>wordSize</a>-aligned) and the current
--   value of the corresponding word. The returned word will be written
--   back to the vector. If there is a partial word at the end of the
--   vector, it will be zero-padded when passed to the function and
--   truncated when the result is written back to the array.
mapMInPlaceWithIndex :: PrimMonad m => (Int -> Word -> m Word) -> MVector (PrimState m) Bit -> m ()
mapInPlaceWithIndex :: PrimMonad m => (Int -> Word -> Word) -> MVector (PrimState m) Bit -> m ()

-- | Same as <a>mapMInPlaceWithIndex</a> but without the index.
mapMInPlace :: PrimMonad m => (Word -> m Word) -> MVector (PrimState m) Bit -> m ()
mapInPlace :: PrimMonad m => (Word -> Word) -> MVector (PrimState m) Bit -> m ()
zipInPlace :: PrimMonad m => (Word -> Word -> Word) -> MVector (PrimState m) Bit -> Vector Bit -> m ()
unionInPlace :: PrimMonad m => MVector (PrimState m) Bit -> Vector Bit -> m ()
intersectionInPlace :: PrimMonad m => MVector (PrimState m) Bit -> Vector Bit -> m ()
differenceInPlace :: PrimMonad m => MVector (PrimState m) Bit -> Vector Bit -> m ()
symDiffInPlace :: PrimMonad m => MVector (PrimState m) Bit -> Vector Bit -> m ()

-- | Flip every bit in the given vector
invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()
selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int
excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int

-- | return the number of ones in a bit vector
countBits :: PrimMonad m => MVector (PrimState m) Bit -> m Int
listBits :: PrimMonad m => MVector (PrimState m) Bit -> m [Int]

-- | Returns <a>True</a> if all bits in the vector are set
and :: PrimMonad m => MVector (PrimState m) Bit -> m Bool

-- | Returns <a>True</a> if any bit in the vector is set
or :: PrimMonad m => MVector (PrimState m) Bit -> m Bool
any :: PrimMonad m => (Bit -> Bool) -> MVector (PrimState m) Bit -> m Bool
anyBits :: PrimMonad m => Bit -> MVector (PrimState m) Bit -> m Bool
all :: PrimMonad m => (Bit -> Bool) -> MVector (PrimState m) Bit -> m Bool
allBits :: PrimMonad m => Bit -> MVector (PrimState m) Bit -> m Bool
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m ()

module Data.Vector.Unboxed.Bit

-- | The number of <a>Bit</a>s in a <a>Word</a>. A handy constant to have
--   around when defining <a>Word</a>-based bulk operations on bit vectors.
wordSize :: Int
wordLength :: Vector Bit -> Int

-- | Given a number of bits and a vector of words, concatenate them to a
--   vector of bits (interpreting the words in little-endian order, as
--   described at <a>indexWord</a>). If there are not enough words for the
--   number of bits requested, the vector will be zero-padded.
fromWords :: Int -> Vector Word -> Vector Bit

-- | Given a vector of bits, extract an unboxed vector of words. If the
--   bits don't completely fill the words, the last word will be
--   zero-padded.
toWords :: Vector Bit -> Vector Word

-- | read a word at the given bit offset in little-endian order (i.e., the
--   LSB will correspond to the bit at the given address, the 2's bit will
--   correspond to the address + 1, etc.). If the offset is such that the
--   word extends past the end of the vector, the result is zero-padded.
indexWord :: Vector Bit -> Int -> Word
pad :: Int -> Vector Bit -> Vector Bit
padWith :: Bit -> Int -> Vector Bit -> Vector Bit

-- | <tt>zipWords f xs ys</tt> = <tt>fromWords (min (length xs) (length
--   ys)) (zipWith f (toWords xs) (toWords ys))</tt>
zipWords :: (Word -> Word -> Word) -> Vector Bit -> Vector Bit -> Vector Bit
union :: Vector Bit -> Vector Bit -> Vector Bit
unions :: Int -> [Vector Bit] -> Vector Bit
intersection :: Vector Bit -> Vector Bit -> Vector Bit
intersections :: Int -> [Vector Bit] -> Vector Bit
difference :: Vector Bit -> Vector Bit -> Vector Bit
symDiff :: Vector Bit -> Vector Bit -> Vector Bit

-- | Flip every bit in the given vector
invert :: Vector Bit -> Vector Bit

-- | Given a vector of bits and a vector of things, extract those things
--   for which the corresponding bit is set.
--   
--   For example, <tt>select (V.map (fromBool . p) x) x == V.filter p
--   x</tt>.
select :: (Vector v1 Bit, Vector v2 t) => v1 Bit -> v2 t -> [t]
selectBits :: Vector Bit -> Vector Bit -> Vector Bit

-- | Given a vector of bits and a vector of things, extract those things
--   for which the corresponding bit is unset.
--   
--   For example, <tt>exclude (V.map (fromBool . p) x) x == V.filter (not .
--   p) x</tt>.
exclude :: (Vector v1 Bit, Vector v2 t) => v1 Bit -> v2 t -> [t]
excludeBits :: Vector Bit -> Vector Bit -> Vector Bit

-- | return the number of ones in a bit vector
countBits :: Vector Bit -> Int
listBits :: Vector Bit -> [Int]

-- | <a>True</a> if all bits in the vector are set
and :: Vector Bit -> Bool

-- | <a>True</a> if any bit in the vector is set
or :: Vector Bit -> Bool
any :: (Bit -> Bool) -> Vector Bit -> Bool
anyBits :: Bit -> Vector Bit -> Bool
all :: (Bit -> Bool) -> Vector Bit -> Bool
allBits :: Bit -> Vector Bit -> Bool
reverse :: Vector Bit -> Vector Bit

-- | Return the address of the first bit in the vector with the specified
--   value, if any
first :: Bit -> Vector Bit -> Maybe Int
findIndex :: (Bit -> Bool) -> Vector Bit -> Maybe Int