monoids-0.1.36: Monoids, specialized containers and a general map/reduce framework Source code Contents Index

Data.Ring.Semi.BitSet Portability portable (instances use MPTCs) Stability experimental Maintainer ekmett@gmail.com

Contents BitSet Manipulation Acessors

Description

Replacement for Data.BitSet extended to handle enumerations where fromEnum can return negative values, support efficient intersection and union and allow complementing of the set with respect to the bounds of the enumeration. Treated as a Boolean semiring over .&./.|.. To get a Boolean Ring, use Boolean (BitSet a).

Synopsis

module Data.Monoid.Reducer module Data.Ring data BitSet a empty :: Enum a => BitSet a singleton :: Enum a => a -> BitSet a full :: (Enum a, Bounded a) => BitSet a union :: Enum a => BitSet a -> BitSet a -> BitSet a intersection :: Enum a => BitSet a -> BitSet a -> BitSet a complement insert :: Enum a => a -> BitSet a -> BitSet a delete :: Enum a => a -> BitSet a -> BitSet a (\\) :: Enum a => BitSet a -> BitSet a -> BitSet a fromList :: Enum a => [a] -> BitSet a fromDistinctAscList :: Enum a => [a] -> BitSet a member :: Enum a => a -> BitSet a -> Bool null :: BitSet a -> Bool size :: BitSet a -> Int isComplemented :: Enum a => BitSet a -> Bool toInteger :: BitSet a -> Integer

Documentation

module Data.Monoid.Reducer

module Data.Ring

BitSet

data BitSet a Source

Set operations optimized for tightly grouped sets or nearly universal sets with a close by group of elements missing. Stores itself like an arbitrary precision floating point number, tracking the least valued member of the set and an Integer comprised of the members. Instances Typeable1 BitSet Foldable BitSet Enum a => Reducer a (BitSet a) (Bounded a, Enum a) => Algebra Natural (BitSet a) Enum a => Bimodule Natural (BitSet a) Enum a => RightModule Natural (BitSet a) Enum a => LeftModule Natural (BitSet a) Enum a => Module Natural (BitSet a) (Enum a, Bounded a) => Bounded (BitSet a) (Enum a, Bounded a) => Enum (BitSet a) Eq (BitSet a) (Enum a, Data a) => Data (BitSet a) (Show a, Bounded a, Enum a) => Num (BitSet a) (Enum a, Read a) => Read (BitSet a) Show a => Show (BitSet a) Enum a => Monoid (BitSet a) (Show a, Bounded a, Enum a) => Bits (BitSet a) Generator (BitSet a) (Bounded a, Enum a) => Multiplicative (BitSet a) (Bounded a, Enum a) => SemiRing (BitSet a) (Bounded a, Enum a) => RightSemiNearRing (BitSet a) (Bounded a, Enum a) => LeftSemiNearRing (BitSet a) (Bounded a, Enum a) => Ringoid (BitSet a) (Bounded a, Enum a) => Algebra (BitSet a) (BitSet a) (Bounded a, Enum a) => Bimodule (BitSet a) (BitSet a) (Bounded a, Enum a) => RightModule (BitSet a) (BitSet a) (Bounded a, Enum a) => LeftModule (BitSet a) (BitSet a) (Bounded a, Enum a) => Module (BitSet a) (BitSet a)

Manipulation

empty :: Enum a => BitSet a Source

O(1) The empty set. Permits O(1) null and size.

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

O(1) Construct a BitSet with a single element. Permits O(1) null and size

full :: (Enum a, Bounded a) => BitSet a Source

O(d) A BitSet containing every member of the enumeration of a.

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

O(d).

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

O(d)

complement

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

O(d) Insert a single element of type a into the BitSet. Preserves order of null and size

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

O(d) Delete a single item from the BitSet. Preserves order of null and size

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

O(d) Infix difference

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

O(d * n) Make a BitSet from a list of items.

fromDistinctAscList :: Enum a => [a] -> BitSet a Source

O(d * n) Make a BitSet from a distinct ascending list of items

Acessors

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

O(1) Test for membership in a BitSet

null :: BitSet a -> Bool Source

O(1) amortized cost. Is the BitSet empty? May be faster than checking if size == 0.

size :: BitSet a -> Int Source

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

isComplemented :: Enum a => BitSet a -> Bool Source

O(1) Check to see if we are represented as a complemented BitSet.

toInteger :: BitSet a -> Integer Source

O(d) convert to an Integer representation. Discards negative elements

Produced by Haddock version 2.4.2