-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A space-efficient set data structure.
--
-- A bit set is a compact data structure, which maintains a set of
-- members from a type that can be enumerated (i. e. has an Enum
-- instance).
@package bitset
@version 1.3.0
-- | 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.
module Data.BitSet.Generic
-- | A bit set with unspecified container type.
data GBitSet c a
BitSet :: Int -> c -> GBitSet c a
-- | Number of elements in the bit set.
_n :: GBitSet c a -> Int
-- | Bit container.
_bits :: GBitSet c a -> c
-- | O(max(m, n)). See difference.
(\\) :: GBitSet c a -> GBitSet c a -> GBitSet c a
-- | The empty bit set.
empty :: (Enum a, Bits c, Num c) => GBitSet c a
-- | O(1). Create a singleton set.
singleton :: (Enum a, Bits c, Num c) => a -> GBitSet c a
-- | O(d). Insert an item into the bit set.
insert :: a -> GBitSet c a -> GBitSet c a
-- | O(d). Delete an item from the bit set.
delete :: a -> GBitSet c a -> GBitSet c a
-- | O(1). Is the bit set empty?
null :: GBitSet c a -> Bool
-- | O(1). The number of elements in the bit set.
size :: GBitSet c a -> Int
-- | O(d). Ask whether the item is in the bit set.
member :: a -> GBitSet c a -> Bool
-- | O(d). Ask whether the item is in the bit set.
notMember :: a -> GBitSet c a -> Bool
-- | O(max(n, m)). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: GBitSet c a -> GBitSet c a -> Bool
-- | O(max(n, m). Is this a proper subset? (ie. a subset but not
-- equal).
isProperSubsetOf :: Eq c => GBitSet c a -> GBitSet c a -> Bool
-- | O(max(m, n)). The union of two bit sets.
union :: GBitSet c a -> GBitSet c a -> GBitSet c a
-- | O(max(m, n)). The union of a list of bit sets.
unions :: (Enum a, Bits c, Num c) => [GBitSet c a] -> GBitSet c a
-- | O(max(m, n)). Difference of two bit sets.
difference :: GBitSet c a -> GBitSet c a -> GBitSet c a
-- | O(max(m, n)). The intersection of two bit sets.
intersection :: GBitSet c a -> GBitSet c a -> GBitSet c a
-- | O(d * n) Transform this bit set by applying a function to every
-- value. Resulting bit set may be smaller then the original.
map :: (Enum a, Enum b, Bits c, Num c) => (a -> b) -> GBitSet c a -> GBitSet c b
-- | O(d * n) Filter this bit set by retaining only elements
-- satisfying predicate.
filter :: (Enum a, Bits c, Num c) => (a -> Bool) -> GBitSet c a -> GBitSet c a
-- | O(d * n). Convert the bit set set to a list of elements.
toList :: Num c => GBitSet c a -> [a]
-- | O(d * n). Make a bit set from a list of elements.
fromList :: (Enum a, Bits c, Num c) => [a] -> GBitSet c a
instance Typeable2 GBitSet
instance Num c => Foldable (GBitSet c)
instance NFData c => NFData (GBitSet c a)
instance (Enum a, Bits c, Num c) => Monoid (GBitSet c a)
instance (Show a, Num c) => Show (GBitSet c a)
instance (Enum a, Read a, Bits c, Num c) => Read (GBitSet c a)
instance Ord (GBitSet c a)
instance Eq (GBitSet c a)
-- | A space-efficient implementation of set data structure 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.Dynamic (BitSet)
-- import qualified Data.BitSet.Dynamic as BS
--
--
-- The implementation uses Integer as underlying container, thus
-- it grows automatically when more elements are inserted into the bit
-- set.
module Data.BitSet.Dynamic
-- | A wrapper around Integer which provides faster bit-level
-- operations.
data FasterInteger
type BitSet = GBitSet FasterInteger
-- | O(max(m, n)). See difference.
(\\) :: BitSet a -> BitSet a -> BitSet a
-- | The empty bit set.
empty :: Enum a => BitSet a
-- | O(1). Create a singleton set.
singleton :: Enum a => a -> BitSet a
-- | O(1). Insert an item into the bit set.
insert :: a -> BitSet a -> BitSet a
-- | O(1). Delete an item from the bit set.
delete :: a -> BitSet a -> BitSet a
-- | O(1). Is the bit set empty?
null :: BitSet a -> Bool
-- | O(1). The number of elements in the bit set.
size :: BitSet a -> Int
-- | O(1). Ask whether the item is in the bit set.
member :: a -> BitSet a -> Bool
-- | O(1). Ask whether the item is in the bit set.
notMember :: a -> BitSet a -> Bool
-- | O(max(n, m)). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: BitSet a -> BitSet a -> Bool
-- | O(max(n, m). Is this a proper subset? (ie. a subset but not
-- equal).
isProperSubsetOf :: BitSet a -> BitSet a -> Bool
-- | O(max(m, n)). The union of two bit sets.
union :: BitSet a -> BitSet a -> BitSet a
-- | O(max(m, n)). The union of a list of bit sets.
unions :: Enum a => [BitSet a] -> BitSet a
-- | O(max(m, n)). Difference of two bit sets.
difference :: BitSet a -> BitSet a -> BitSet a
-- | O(max(m, n)). The intersection of two bit sets.
intersection :: BitSet a -> BitSet a -> BitSet a
-- | O(n) Transform this bit set by applying a function to every
-- value. Resulting bit set may be smaller then the original.
map :: (Enum a, Enum b) => (a -> b) -> BitSet a -> BitSet b
-- | O(n) Filter this bit set by retaining only elements satisfying
-- a predicate.
filter :: Enum a => (a -> Bool) -> BitSet a -> BitSet a
-- | O(n). Convert the bit set set to a list of elements.
toList :: BitSet a -> [a]
-- | O(n). Make a bit set from a list of elements.
fromList :: Enum a => [a] -> BitSet a
instance Read FasterInteger
instance Show FasterInteger
instance Eq FasterInteger
instance Ord FasterInteger
instance Enum FasterInteger
instance Integral FasterInteger
instance Num FasterInteger
instance Real FasterInteger
instance NFData FasterInteger
instance Bits FasterInteger
-- | A space-efficient implementation of set data structure 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 (BitSet)
-- import qualified Data.BitSet as BS
--
--
-- This module re-exports Dynamic implementation that uses
-- Integer as underlying container.
module Data.BitSet