-- 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.4.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 container 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
-- | 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 :: (Enum a, Bits c) => a -> GBitSet c a -> Bool
-- | O(d). Ask whether the item is in the bit set.
notMember :: (Enum a, Bits c) => 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)). 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) Reduce this bit set by applying a binary function to
-- all elements, using the given starting value. Each application of the
-- operator is evaluated before before using the result in the next
-- application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> GBitSet c a -> b
-- | O(d * n) Reduce this bit set by applying a binary function to
-- all elements, using the given starting value.
foldr :: (a -> b -> b) -> b -> GBitSet c a -> 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 this 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
-- | O(1). Internal function, which extracts the underlying
-- container from the bit set.
toBits :: GBitSet c a -> c
-- | O(1). Internal function, which constructs a bit set, using a
-- given container value. Highly unsafe, because we don't check if bits
-- in the given value correspond to valid instances of type a.
unsafeFromBits :: (Enum a, Bits c, Num c) => c -> GBitSet c a
instance Typeable2 GBitSet
instance Num c => Foldable (GBitSet c)
instance (Bits c, Enum a, Num c, Storable c) => Storable (GBitSet c a)
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 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.Word (BitSet)
-- import qualified Data.BitSet.Word as BS
--
--
-- The implementation uses Word as underlying container, thus the
-- maximum number of elements you can store in this bit set is bounded by
-- the number of bits in Word data type. However, due to native
-- bitwise operations Data.BitSet.Word is significantly faster
-- then Data.Set on all operations.
module Data.BitSet.Word
type BitSet = GBitSet Word
-- | O(1). 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 :: Enum a => a -> BitSet a -> Bool
-- | O(1). Ask whether the item is in the bit set.
notMember :: Enum a => a -> BitSet a -> Bool
-- | O(1). Is this a subset? (s1 isSubsetOf s2) tells
-- whether s1 is a subset of s2.
isSubsetOf :: BitSet a -> BitSet a -> Bool
-- | O(1). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: BitSet a -> BitSet a -> Bool
-- | O(1). The union of two bit sets.
union :: BitSet a -> BitSet a -> BitSet a
-- | O(1). Difference of two bit sets.
difference :: BitSet a -> BitSet a -> BitSet a
-- | O(1). 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) Reduce this bit set by applying a binary function to all
-- elements, using the given starting value. Each application of the
-- operator is evaluated before before using the result in the next
-- application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> BitSet a -> b
-- | O(n) Reduce this bit set by applying a binary function to all
-- elements, using the given starting value.
foldr :: (a -> b -> b) -> b -> BitSet a -> 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
-- | 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.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(1). 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 :: Enum a => a -> BitSet a -> Bool
-- | O(1). Ask whether the item is in the bit set.
notMember :: Enum a => 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(1). Difference of two bit sets.
difference :: BitSet a -> BitSet a -> BitSet a
-- | O(1). 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) Reduce this bit set by applying a binary function to all
-- elements, using the given starting value. Each application of the
-- operator is evaluated before before using the result in the next
-- application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> BitSet a -> b
-- | O(n) Reduce this bit set by applying a binary function to all
-- elements, using the given starting value.
foldr :: (a -> b -> b) -> b -> BitSet a -> 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.
module Data.BitSet