| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.Bits.Ordered
Contents
Description
Efficiently enumerate the bits in data types in order of population
count. This yields, say, 000, 001, 010, 100, 011, 101, 110, 111 (or
0, 1, 2, 4, 3, 5, 6, 7). Another view is of looking at the bits as
a bitset, first enumerating the empty set, then all 1-element sets, all
2-element sets, up to the set size.
The enumerator can be inlined with unfoldr (of the vector package)
and is a good producer.
A memo-table is available, since popCntSorted is still waiting for an
efficient popCntEnumerated that does not require sorting.
- lsbZ :: Ranked t => t -> Int
- nextActiveZ :: Ranked t => Int -> t -> Int
- maybeNextActive :: Ranked t => Int -> t -> Maybe Int
- maybeLsb :: Ranked t => t -> Maybe Int
- popPermutation :: Ranked t => Int -> t -> Maybe t
- popComplement :: Ranked t => Int -> t -> t
- popCntSorted :: (Unbox n, Integral n, Bits n, Ranked n) => Int -> Vector n
- popCntMemoInt :: Int -> Vector Int
- popCntMemoWord :: Int -> Vector Word
- popShiftL :: Ranked t => t -> t -> t
- popShiftR :: Ranked t => t -> t -> t
- activeBitsL :: Ranked t => t -> [Int]
- activeBitsS :: (Ranked t, Monad m) => t -> Stream m Int
- activeBitsV :: (Ranked t, Vector v Int) => t -> v Int
Documentation
nextActiveZ :: Ranked t => Int -> t -> Int Source #
Given the currently active bit k and the set t, get the next
active bit. Return -1 if there is no next active bit.
popPermutation :: Ranked t => Int -> t -> Maybe t Source #
Enumerate all sets with the same population count. Given a population
i, this returns Just j with j>i (but same number of set bits) or
Nothing. For a population count of k, start with 2^(k+1) -1.
Note that sort permutations == sort (nub permutations) if
permutations is a set of all permutations for a given popCount
generated by popPermutation. The Data.List.permutations functions
will create duplicates.
cf http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
popComplement :: Ranked t => Int -> t -> t Source #
Given a population, get the complement. The first argument is the size of the population (say. 8 for 8 bits); the second the current population.
Examples:
>>>popComplement 5 (3 :: Int)28
>>>popComplement 6 (3 :: Int)60
popCntSorted :: (Unbox n, Integral n, Bits n, Ranked n) => Int -> Vector n Source #
The slow default implementation. We sort the vector, not the list, as sorting will walk the whole data structure anyway, and the vector requires not as much memory.
Replaced popCount &&& id as sort, which provides for a<b on equal
popCount with popCount &&& activeBitsL which sorts according to
a list of increasing bit indices. Mostly to stay in sync with the pred
/ succ functions below.
Arguments
| :: Int | size of the set we want. If larger than memo limit, will just call |
| -> Vector Int |
Memoized version of popCntSorted for Ints.
NOTE Since this uses popCntSorted for now it will still require a lot
of memory for sorting the vector!
Arguments
| :: Int | size of the set we want. If larger than memo limit, will just call |
| -> Vector Word |
Memoized version of popCntSorted for Words.
NOTE Since this uses popCntSorted for now it will still require a lot
of memory for sorting the vector!
popShiftL :: Ranked t => t -> t -> t Source #
Move a population more to the left. This, effectively, introduces 0s
in the set, whereever the mask has a 0. Only as many 1s can be
set, as the mask holds. Assume that you have a bitmask mask = 10101
and a least-significant aligned population 11, then given mask and
population you'd like to see 00101, i.e. the two lowest one bits of
the mask are set. 101 would set the lowest and third one bit.
Examples:
>>>popShiftL (21::Int) 3 -- 10101 00011 -- 001015>>>popShiftL (28::Int) 0 -- 11100 00000 -- 000000>>>popShiftL (28::Int) 1 -- 11100 00001 -- 001004>>>popShiftL (28::Int) 2 -- 11100 00010 -- 010008>>>popShiftL (28::Int) 3 -- 11100 00011 -- 0110012
popShiftR :: Ranked t => t -> t -> t Source #
Effectively compresses a bitset, given a mask. Removes set elements,
whenever the mask is 0, by moving all remaining elements one to the
right.
activeBitsL :: Ranked t => t -> [Int] Source #
List of all active bits, from lowest to highest.
activeBitsS :: (Ranked t, Monad m) => t -> Stream m Int Source #
A stream with the currently active bits, lowest to highest.
activeBitsV :: (Ranked t, Vector v Int) => t -> v Int Source #
A generic vector (specializes to the corrept type) of the active bits, lowest to highest.