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

Safe HaskellNone
LanguageHaskell2010

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.

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.

Orphan instances

Ranked Int Source # 

Methods

lsb :: Int -> Int #

rank :: Int -> Int #

nlz :: Int -> Int #

Ranked Word Source # 

Methods

lsb :: Word -> Int #

rank :: Word -> Int #

nlz :: Word -> Int #