| Copyright | (c) Alex Washburn 2018 |
|---|---|
| License | BSD-style |
| Maintainer | github@recursion.ninja |
| Stability | provisional |
| Portability | portable |
| Safe Haskell | Trustworthy |
| Language | Haskell2010 |
Data.BitVector.LittleEndian
Description
A bit vector similar to Data.BitVector from the
bv, however the endianness is
reversed. This module defines little-endian pseudo–size-polymorphic
bit vectors.
Little-endian bit vectors are isomorphic to a [Bool] with the least
significant bit at the head of the list and the most significant bit at the
end of the list. Consequently, the endianness of a bit vector affects the semantics of the
following typeclasses:
BitsFiniteBitsSemigroupMonoidMonoAdjustableMonoIndexableMonoKeyedMonoLookupMonoFoldableMonoFoldableWithKeyMonoTraversableMonoTraversableWithKeyMonoZipWithKey
For an implementation of bit vectors which are isomorphic to a [Bool] with the most
significant bit at the head of the list and the least significant bit at the
end of the list, use the
bv package.
This module does not define numeric instances for BitVector. This is
intentional! To interact with a bit vector as an Integral value,
convert the BitVector using either toSignedNumber or toUnsignedNumber.
This module defines rank and select operations for BitVector as a
succinct data structure.
These operations are not o(1) so BitVector is not a true succinct data
structure. However, it could potentially be extend to support this in the
future.
Synopsis
- data BitVector
- fromBits :: Foldable f => f Bool -> BitVector
- toBits :: BitVector -> [Bool]
- fromNumber :: Integral v => Word -> v -> BitVector
- toSignedNumber :: Num a => BitVector -> a
- toUnsignedNumber :: Num a => BitVector -> a
- dimension :: BitVector -> Word
- isZeroVector :: BitVector -> Bool
- subRange :: (Word, Word) -> BitVector -> BitVector
- rank :: BitVector -> Word -> Word
- select :: BitVector -> Word -> Maybe Word
Documentation
A little-endian bit vector of non-negative dimension.
Instances
Bit-stream conversion
fromBits :: Foldable f => f Bool -> BitVector Source #
Create a bit vector from a little-endian list of bits.
The following will hold:
length . takeWhile not === countLeadingZeros . fromBits length . takeWhile not . reverse === countTrailingZeros . fromBits
Time: \(\, \mathcal{O} \left( n \right) \)
Since: 0.1.0
Examples
>>>fromBits [True, False, False][3]1
toBits :: BitVector -> [Bool] Source #
Create a little-endian list of bits from a bit vector.
The following will hold:
length . takeWhile not . toBits === countLeadingZeros length . takeWhile not . reverse . toBits === countTrailingZeros
Time: \(\, \mathcal{O} \left( n \right) \)
Since: 0.1.0
Examples
>>>toBits [4]11[True, True, False, True]
Numeric conversion
Arguments
| :: Integral v | |
| => Word | dimension of bit vector |
| -> v | signed, little-endian integral value |
| -> BitVector |
Create a bit vector of non-negative dimension from an integral value.
The integral value will be treated as an signed number and the resulting bit vector will contain the two's complement bit representation of the number.
The integral value will be interpreted as little-endian so that the least
significant bit of the integral value will be the value of the 0th index of
the resulting bit vector and the most significant bit of the integral value
will be at index dimension − 1.
Note that if the bit representation of the integral value exceeds the supplied dimension, then the most significant bits will be truncated in the resulting bit vector.
Time: \(\, \mathcal{O} \left( 1 \right) \)
Since: 0.1.0
Examples
>>>fromNumber 8 96[8]96
>>>fromNumber 8 -96[8]160
>>>fromNumber 6 96[6]32
toSignedNumber :: Num a => BitVector -> a Source #
Two's complement value of a bit vector.
Time: \(\, \mathcal{O} \left( 1 \right) \)
Since: 0.1.0
Examples
>>>toSignedNumber [4]00
>>>toSignedNumber [4]33
>>>toSignedNumber [4]77
>>>toSignedNumber [4]8-8
>>>toSignedNumber [4]12-4
>>>toSignedNumber [4]15-1
toUnsignedNumber :: Num a => BitVector -> a Source #
Unsigned value of a bit vector.
Time: \(\, \mathcal{O} \left( 1 \right) \)
Since: 0.1.0
Examples
>>>toSignedNumber [4]00
>>>toSignedNumber [4]33
>>>toSignedNumber [4]77
>>>toSignedNumber [4]88
>>>toSignedNumber [4]1212
>>>toSignedNumber [4]1515
Queries
dimension :: BitVector -> Word Source #
Get the dimension of a BitVector. Preferable to finiteBitSize as it
returns a type which cannot represent a non-negative value and a BitVector
must have a non-negative dimension.
Time: \(\, \mathcal{O} \left( 1 \right) \)
Since: 0.1.0
Examples
>>>dimension [2]32
>>>dimension [4]124
isZeroVector :: BitVector -> Bool Source #
Determine if any bits are set in the BitVector.
Faster than (0 ==) . popCount.
Time: \(\, \mathcal{O} \left( 1 \right) \)
Since: 0.1.0
Examples
>>>isZeroVector [2]3False
>>>isZeroVector [4]0True
subRange :: (Word, Word) -> BitVector -> BitVector Source #
Get the inclusive range of bits in BitVector as a new BitVector.
If either of the bounds of the subrange exceed the bit vector's dimension, the resulting subrange will append an infinite number of zeroes to the end of the bit vector in order to satisfy the subrange request.
Time: \(\, \mathcal{O} \left( 1 \right) \)
Since: 0.1.0
Examples
>>>subRange (0,2) [4]7[3]7
>>>subRange (1, 3) [4]7[3]3
>>>subRange (2, 4) [4]7[3]1
>>>subRange (3, 5) [4]7[3]0
>>>subRange (10, 20) [4]7[10]0
Rank / Select
Determine the number of set bits in the BitVector up to, but not including, index k.
To determine the number of unset bits in the BitVector, use k - rank bv k.
Uses "broadword programming." Efficient on small BitVectors (10^3).
Time: \(\, \mathcal{O} \left( \frac{n}{w} \right) \), where \(w\) is the number of bits in a Word.
Since: 1.1.0
Examples
>>>let bv = fromNumber 128 0 `setBit` 0 `setBit` 65
>>>rank bv 0 -- Count how many ones in the first 0 bits (always returns 0)0
>>>rank bv 1 -- Count how many ones in the first 1 bits1
>>>rank bv 2 -- Count how many ones in the first 2 bits1
>>>rank bv 65 -- Count how many ones in the first 65 bits1
>>>rank bv 66 -- Count how many ones in the first 66 bits1
>>>rank bv 128 -- Count how many ones in all 128 bits2
>>>rank bv 129 -- Out-of-bounds, fails gracefully2
Find the index of the k-th set bit in the BitVector.
To find the index of the k-th unset bit in the BitVector, use select (complement bv) k.
Uses "broadword programming." Efficient on small BitVectors (10^3).
Time: \(\, \mathcal{O} \left( \frac{n}{w} \right) \), where \(w\) is the number of bits in a Word.
Since: 1.1.0
Examples
>>>let bv = fromNumber 128 0 `setBit` 0 `setBit` 65
>>>select bv 0 -- Find the 0-indexed position of the first one bitJust 0
>>>select bv 1 -- Find the 0-indexed position of the second one bitJust 65
>>>select bv 2 -- There is no 3rd set bit, `select` failsNothing