DenseIntSet

DenseIntSet

data DenseIntSet

Set of integer values represented as a space-optimized dense array of booleans, where an entry only occupies 1 bit. Compared to IntSet of the "containers" library, it trades off the the ability for modification for much better lookup performance. Hence it best fits the usage patterns, where you first create the set and then only use it for lookups.

Since there's multiple ways to implement a monoid for this data-structure, the instances are provided for DenseIntSetComposition, which is open for interpretation of how to compose.

Instances

IsList DenseIntSet

Defined in DenseIntSet

Associated Types

type Item DenseIntSet :: *

Methods

fromList :: [Item DenseIntSet] -> DenseIntSet

fromListN :: Int -> [Item DenseIntSet] -> DenseIntSet

toList :: DenseIntSet -> [Item DenseIntSet]

Eq DenseIntSet

Defined in DenseIntSet

Methods

(==) :: DenseIntSet -> DenseIntSet -> Bool

(/=) :: DenseIntSet -> DenseIntSet -> Bool

Ord DenseIntSet

Defined in DenseIntSet

Methods

compare :: DenseIntSet -> DenseIntSet -> Ordering

(<) :: DenseIntSet -> DenseIntSet -> Bool

(<=) :: DenseIntSet -> DenseIntSet -> Bool

(>) :: DenseIntSet -> DenseIntSet -> Bool

(>=) :: DenseIntSet -> DenseIntSet -> Bool

max :: DenseIntSet -> DenseIntSet -> DenseIntSet

min :: DenseIntSet -> DenseIntSet -> DenseIntSet

Show DenseIntSet

Defined in DenseIntSet

Methods

showsPrec :: Int -> DenseIntSet -> ShowS

show :: DenseIntSet -> String

showList :: [DenseIntSet] -> ShowS

Generic DenseIntSet

Defined in DenseIntSet

Associated Types

type Rep DenseIntSet :: * -> *

Methods

from :: DenseIntSet -> Rep DenseIntSet x

to :: Rep DenseIntSet x -> DenseIntSet

Serialize DenseIntSet

Defined in DenseIntSet

Methods

put :: Putter DenseIntSet

get :: Get DenseIntSet

Hashable DenseIntSet

Defined in DenseIntSet

Methods

hashWithSalt :: Int -> DenseIntSet -> Int

hash :: DenseIntSet -> Int

type Rep DenseIntSet

Defined in DenseIntSet

type Rep DenseIntSet

type Item DenseIntSet

Defined in DenseIntSet

type Item DenseIntSet = Int

Constructors

foldable :: Foldable foldable => Int -> foldable Int -> DenseIntSet

Given a maximum int, construct from a foldable of ints, which are smaller or equal to it and larger than 0.

It is your responsibility to ensure that the values match this contract.

topValueIndices :: (Vector vector a, Vector vector (a, Int)) => (a -> a -> Ordering) -> Int -> vector a -> DenseIntSet

Using the provided ordering function, select the indices of the specified amount of top-ordered elements of a generic vector.

filteredIndices :: Vector vector a => (a -> Bool) -> vector a -> DenseIntSet

Select the indices of vector elements, which match the predicate.

invert :: DenseIntSet -> DenseIntSet

Invert the set.

Composition

intersections :: [DenseIntSet] -> DenseIntSet

Intersect multiple sets

unions :: [DenseIntSet] -> DenseIntSet

Unite multiple sets

Accessors

capacity :: DenseIntSet -> Int

O(1). Size of the value space.

population :: DenseIntSet -> Int

O(log n). Count the amount of present elements in the set.

lookup :: Int -> DenseIntSet -> Bool

O(1). Check whether an int is a member of the set.

Vectors

presentElementsVector :: Vector vector element => DenseIntSet -> (Int -> element) -> vector element

Extract the present elements into a vector.

indexVector :: Vector vector (Maybe index) => DenseIntSet -> (Int -> index) -> vector (Maybe index)

Construct a vector, which maps from the original ints into their indices amongst the ones present in the set.

filterVector :: Vector vector a => DenseIntSet -> vector a -> vector a

Filter a vector, leaving only the entries, under the indices, which are in the set.

It is your responsibility to ensure that the indices in the set don't exceed the original vector's bounds.

Unfoldrs

presentElementsUnfoldr :: DenseIntSet -> Unfoldr Int

Unfold the present elements.

absentElementsUnfoldr :: DenseIntSet -> Unfoldr Int

Unfold the absent elements.

vectorElementsUnfoldr :: Vector vector a => vector a -> DenseIntSet -> Unfoldr a

Unfold the elements of a vector by indices in the set.

It is your responsibility to ensure that the indices in the set don't exceed the vector's bounds.