Safe Haskell | None |
---|---|
Language | Haskell2010 |
Synopsis
- data DenseIntSet
- foldable :: Foldable foldable => Int -> foldable Int -> DenseIntSet
- topValueIndices :: (Vector vector a, Vector vector (a, Int)) => (a -> a -> Ordering) -> Int -> vector a -> DenseIntSet
- filteredIndices :: Vector vector a => (a -> Bool) -> vector a -> DenseIntSet
- intersection :: DenseIntSetComposition -> DenseIntSet
- union :: DenseIntSetComposition -> DenseIntSet
- size :: DenseIntSet -> Int
- lookup :: Int -> DenseIntSet -> Bool
- presentElementsVector :: Vector vector Int => DenseIntSet -> vector Int
- filterVector :: Vector vector a => DenseIntSet -> vector a -> vector a
- indexVector :: Vector vector (Maybe Int) => DenseIntSet -> vector (Maybe Int)
- presentElementsUnfoldr :: DenseIntSet -> Unfoldr Int
- absentElementsUnfoldr :: DenseIntSet -> Unfoldr Int
- vectorElementsUnfoldr :: Vector vector a => vector a -> DenseIntSet -> Unfoldr a
- data DenseIntSetComposition
- compose :: DenseIntSet -> DenseIntSetComposition
- composeList :: [DenseIntSet] -> DenseIntSetComposition
DenseIntSet
data DenseIntSet Source #
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
Constructors
foldable :: Foldable foldable => Int -> foldable Int -> DenseIntSet Source #
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 Source #
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 Source #
Select the indices of vector elements, which match the predicate.
Composition
intersection :: DenseIntSetComposition -> DenseIntSet Source #
Interpret a composition as an intersection of sets.
union :: DenseIntSetComposition -> DenseIntSet Source #
Interpret a composition as a union of sets.
Accessors
size :: DenseIntSet -> Int Source #
O(log n). Count the amount of present elements in the set.
Vectors
presentElementsVector :: Vector vector Int => DenseIntSet -> vector Int Source #
Extract the present elements into a vector.
filterVector :: Vector vector a => DenseIntSet -> vector a -> vector a Source #
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) Source #
Construct a vector, which maps from the original ints into their indices amongst the ones present in the set.
Unfoldrs
presentElementsUnfoldr :: DenseIntSet -> Unfoldr Int Source #
Unfold the present elements.
absentElementsUnfoldr :: DenseIntSet -> Unfoldr Int Source #
Unfold the absent elements.
vectorElementsUnfoldr :: Vector vector a => vector a -> DenseIntSet -> Unfoldr a Source #
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 Source #
Abstraction over the composition of sets, which is cheap to append and can be used for interpreted merging of sets.
Instances
Semigroup DenseIntSetComposition Source # | |
Defined in DenseIntSet | |
Monoid DenseIntSetComposition Source # | |
compose :: DenseIntSet -> DenseIntSetComposition Source #
Lift a set into composition.
composeList :: [DenseIntSet] -> DenseIntSetComposition Source #
Lift a list of sets into composition.