Portability | GHC |
---|---|
Stability | experimental |
Maintainer | superbobry@gmail.com |
Safe Haskell | Safe-Inferred |
A space-efficient implementation of set data structure for enumerated data types.
Note: Read below the synopsis for important notes on the use of this module.
This module is intended to be imported qualified
, to avoid name
clashes with Prelude functions, e.g.
import Data.BitSet.Generic (BitSet) import qualified Data.BitSet.Generic as BS
The implementation is abstract with respect to conatiner type, so any
numeric type with Bits
instance can be used as a container. However,
independent of container choice, the maximum number of elements in a
bit set is bounded by maxBound :: Int
.
- data GBitSet c a = (Enum a, Bits c, Num c) => BitSet {}
- (\\) :: GBitSet c a -> GBitSet c a -> GBitSet c a
- empty :: (Enum a, Bits c, Num c) => GBitSet c a
- singleton :: (Enum a, Bits c, Num c) => a -> GBitSet c a
- insert :: a -> GBitSet c a -> GBitSet c a
- delete :: a -> GBitSet c a -> GBitSet c a
- null :: GBitSet c a -> Bool
- size :: GBitSet c a -> Int
- member :: a -> GBitSet c a -> Bool
- notMember :: a -> GBitSet c a -> Bool
- isSubsetOf :: GBitSet c a -> GBitSet c a -> Bool
- isProperSubsetOf :: Eq c => GBitSet c a -> GBitSet c a -> Bool
- union :: GBitSet c a -> GBitSet c a -> GBitSet c a
- unions :: (Enum a, Bits c, Num c) => [GBitSet c a] -> GBitSet c a
- difference :: GBitSet c a -> GBitSet c a -> GBitSet c a
- intersection :: GBitSet c a -> GBitSet c a -> GBitSet c a
- map :: (Enum a, Enum b, Bits c, Num c) => (a -> b) -> GBitSet c a -> GBitSet c b
- filter :: (Enum a, Bits c, Num c) => (a -> Bool) -> GBitSet c a -> GBitSet c a
- toList :: Num c => GBitSet c a -> [a]
- fromList :: (Enum a, Bits c, Num c) => [a] -> GBitSet c a
Bit set type
Operators
Construction
Query
isSubsetOf :: GBitSet c a -> GBitSet c a -> BoolSource
O(max(n, m)). Is this a subset? (s1 isSubsetOf s2
) tells whether
s1
is a subset of s2
.
isProperSubsetOf :: Eq c => GBitSet c a -> GBitSet c a -> BoolSource
O(max(n, m). Is this a proper subset? (ie. a subset but not equal).
Combine
unions :: (Enum a, Bits c, Num c) => [GBitSet c a] -> GBitSet c aSource
O(max(m, n)). The union of a list of bit sets.
difference :: GBitSet c a -> GBitSet c a -> GBitSet c aSource
O(max(m, n)). Difference of two bit sets.
intersection :: GBitSet c a -> GBitSet c a -> GBitSet c aSource
O(max(m, n)). The intersection of two bit sets.
Transformations
map :: (Enum a, Enum b, Bits c, Num c) => (a -> b) -> GBitSet c a -> GBitSet c bSource
O(d * n) Transform this bit set by applying a function to every value. Resulting bit set may be smaller then the original.
Filter
filter :: (Enum a, Bits c, Num c) => (a -> Bool) -> GBitSet c a -> GBitSet c aSource
O(d * n) Filter this bit set by retaining only elements satisfying predicate.