Safe Haskell | Safe-Inferred |
---|
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.
- data BitSet a
- (\\) :: Enum a => BitSet a -> BitSet a -> BitSet a
- null :: BitSet a -> Bool
- size :: BitSet a -> Int
- member :: Enum a => a -> BitSet a -> Bool
- notMember :: Enum a => a -> BitSet a -> Bool
- isSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool
- isProperSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool
- empty :: BitSet a
- singleton :: Enum a => a -> BitSet a
- insert :: Enum a => a -> BitSet a -> BitSet a
- delete :: Enum a => a -> BitSet a -> BitSet a
- union :: Enum a => BitSet a -> BitSet a -> BitSet a
- unions :: Enum a => [BitSet a] -> BitSet a
- difference :: Enum a => BitSet a -> BitSet a -> BitSet a
- intersection :: Enum a => BitSet a -> BitSet a -> BitSet a
- elems :: Enum a => BitSet a -> [a]
- toList :: Enum a => BitSet a -> [a]
- fromList :: Enum a => [a] -> BitSet a
- toIntegral :: Integral b => BitSet a -> b
- unsafeFromIntegral :: Integral b => b -> BitSet a
Bit set type
Operators
Query
member :: Enum a => a -> BitSet a -> BoolSource
O(testBit on Integer). Ask whether the item is in the bit set.
notMember :: Enum a => a -> BitSet a -> BoolSource
O(testBit on Integer). Ask whether the item is in the bit set.
isSubsetOf :: Enum a => BitSet a -> BitSet a -> BoolSource
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 -> BoolSource
O(max(n, m).. Is this a proper subset? (ie. a subset but not equal).
Construction
insert :: Enum a => a -> BitSet a -> BitSet aSource
O(setBit on Integer). Insert an item into the bit set.
delete :: Enum a => a -> BitSet a -> BitSet aSource
O(clearBit on Integer). Delete an item from the bit set.
Combine
difference :: Enum a => BitSet a -> BitSet a -> BitSet aSource
O(max(m, n)). Difference of two bit sets.
intersection :: Enum a => BitSet a -> BitSet a -> BitSet aSource
O(max(m, n)). The intersection of two bit sets.
Conversion
List
toList :: Enum a => BitSet a -> [a]Source
O(n * shiftR on Integer). Convert a bit set to a list of elements.
fromList :: Enum a => [a] -> BitSet aSource
O(n * setBit on Integer). Make a bit set from a list of elements.
Arbitraty integral type
toIntegral :: Integral b => BitSet a -> bSource
O(1). Project a bit set to an integral type.
unsafeFromIntegral :: Integral b => b -> BitSet aSource
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.