Data.BitSet

A bit set maintains a record of members from a type that can be enumerated (i. e. has and Enum instance). The maximum number of elements that can be stored is maxBound :: Int.

To use this library, define a Enum instance for your data type or have it derived. It is important that the values you intend to store in a bit set start from 0 and go up. A value for which fromEnum x is n corresponds to bit location n in an Integer, and thus requires that Integer to have at least n bits.

Note: The idea of using Integer as bit storage for a bit set was borrowed from an unsupported BitSet implementation by Denis Bueno.

Bit set type

data BitSet a

Instances

Typeable1 BitSet

Eq (BitSet a)

Data a => Data (BitSet a)

Ord (BitSet a)

(Enum a, Show a) => Show (BitSet a)

Enum a => Monoid (BitSet a)

NFData (BitSet a)

Operators

(\\) :: Enum a => BitSet a -> BitSet a -> BitSet a

O(max(m, n)). See difference.

Query

null :: BitSet a -> Bool

O(1). Is the bit set empty?

size :: BitSet a -> Int

O(1). The number of elements in the bit set.

member :: Enum a => a -> BitSet a -> Bool

O(testBit on Integer). Ask whether the item is in the bit set.

notMember :: Enum a => a -> BitSet a -> Bool

O(testBit on Integer). Ask whether the item is in the bit set.

isSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool

O(max(n, m)).. Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.

isProperSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool

O(max(n, m).. Is this a proper subset? (ie. a subset but not equal).

Construction

empty :: BitSet a

The empty bit set.

singleton :: Enum a => a -> BitSet a

O(setBit on Integer). Create a singleton set.

insert :: Enum a => a -> BitSet a -> BitSet a

O(setBit on Integer). Insert an item into the bit set.

delete :: Enum a => a -> BitSet a -> BitSet a

O(clearBit on Integer). Delete an item from the bit set.

Combine

union :: Enum a => BitSet a -> BitSet a -> BitSet a

O(max(m, n)). The union of two bit sets.

unions :: Enum a => [BitSet a] -> BitSet a

O(max(m, n)). The union of a list of bit sets.

difference :: Enum a => BitSet a -> BitSet a -> BitSet a

O(max(m, n)). Difference of two bit sets.

intersection :: Enum a => BitSet a -> BitSet a -> BitSet a

O(max(m, n)). The intersection of two bit sets.

Conversion

List

elems :: Enum a => BitSet a -> [a]

O(n * shiftR on Integer). An alias to toList.

toList :: Enum a => BitSet a -> [a]

O(n * shiftR on Integer). Convert a bit set to a list of elements.

fromList :: Enum a => [a] -> BitSet a

O(n * setBit on Integer). Make a bit set from a list of elements.

Arbitraty integral type

toIntegral :: Integral b => BitSet a -> b

O(1). Project a bit set to an integral type.

unsafeFromIntegral :: Integral b => b -> BitSet a

O(n). Make a bit set from an integral. Unsafe because we don't checked whether the bits set in a given value correspond to values of type a. This is only useful as a more efficient alternative to fromList.