Data.Bits.Ordered

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.

Documentation

lsbZ :: Ranked t => t -> Int

Get the lowest active bit. Returns -1 if no bit is set.

nextActiveZ :: Ranked t => Int -> t -> Int

Given the currently active bit k and the set t, get the next active bit. Return -1 if there is no next active bit.

maybeNextActive :: Ranked t => Int -> t -> Maybe Int

Return next active bit, using Maybe.

maybeLsb :: Ranked t => t -> Maybe Int

Maybe the lowest active bit.

popPermutation :: Ranked t => Int -> t -> Maybe t

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

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

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.

popCntMemoInt

Arguments

:: Int

size of the set we want. If larger than memo limit, will just call popCntSorted

-> 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!

popCntMemoWord

Arguments

:: Int

size of the set we want. If larger than memo limit, will just call popCntSorted

-> 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

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  -- 00101
5
>>> popShiftL (28::Int) 0 -- 11100 00000  -- 00000
0
>>> popShiftL (28::Int) 1 -- 11100 00001  -- 00100
4
>>> popShiftL (28::Int) 2 -- 11100 00010  -- 01000
8
>>> popShiftL (28::Int) 3 -- 11100 00011  -- 01100
12

popShiftR :: Ranked t => t -> t -> t

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]

List of all active bits, from lowest to highest.

activeBitsS :: (Ranked t, Monad m) => t -> Stream m Int

A stream with the currently active bits, lowest to highest.

activeBitsV :: (Ranked t, Vector v Int) => t -> v Int

A generic vector (specializes to the corrept type) of the active bits, lowest to highest.

Orphan instances

Ranked Int

Methods

lsb :: Int -> Int

rank :: Int -> Int

nlz :: Int -> Int

Ranked Word

Methods

lsb :: Word -> Int

rank :: Word -> Int

nlz :: Word -> Int