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

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 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.

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.

Composition

intersection :: DenseIntSetComposition -> DenseIntSet

Interpret a composition as an intersection of sets.

union :: DenseIntSetComposition -> DenseIntSet

Interpret a composition as a union of sets.

Accessors

size :: 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 Int => DenseIntSet -> vector Int

Extract the present elements into a vector.

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.

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

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

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.

Composition

data DenseIntSetComposition

Abstraction over the composition of sets, which is cheap to append and can be used for interpreted merging of sets.

Instances

Semigroup DenseIntSetComposition

Defined in DenseIntSet

Methods

(<>) :: DenseIntSetComposition -> DenseIntSetComposition -> DenseIntSetComposition

sconcat :: NonEmpty DenseIntSetComposition -> DenseIntSetComposition

stimes :: Integral b => b -> DenseIntSetComposition -> DenseIntSetComposition

Monoid DenseIntSetComposition

Defined in DenseIntSet

Methods

mempty :: DenseIntSetComposition

mappend :: DenseIntSetComposition -> DenseIntSetComposition -> DenseIntSetComposition

mconcat :: [DenseIntSetComposition] -> DenseIntSetComposition

compose :: DenseIntSet -> DenseIntSetComposition

Lift a set into composition.

composeList :: [DenseIntSet] -> DenseIntSetComposition

Lift a list of sets into composition.