OrderedBits-0.0.0.1: Efficient ordered (by popcount) enumeration of bits

Safe HaskellNone
LanguageHaskell2010

Data.Bits.Ordered

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.

Synopsis

Documentation

lsbZ :: Ranked t => t -> Int Source

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

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.

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

Return next active bit, using Maybe.

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

Maybe the lowest 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.

popCntMemoInt Source

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 Source

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