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
- invert :: DenseIntSet -> DenseIntSet
- intersections :: [DenseIntSet] -> DenseIntSet
- unions :: [DenseIntSet] -> DenseIntSet
- capacity :: DenseIntSet -> Int
- population :: DenseIntSet -> Int
- lookup :: Int -> DenseIntSet -> Bool
- presentElementsVector :: Vector vector element => DenseIntSet -> (Int -> element) -> vector element
- indexVector :: Vector vector (Maybe index) => DenseIntSet -> (Int -> index) -> vector (Maybe index)
- filterVector :: Vector vector a => DenseIntSet -> vector a -> vector a
- presentElementsUnfoldr :: DenseIntSet -> Unfoldr Int
- absentElementsUnfoldr :: DenseIntSet -> Unfoldr Int
- vectorElementsUnfoldr :: Vector vector a => vector a -> DenseIntSet -> Unfoldr a

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

invert :: DenseIntSet -> DenseIntSet Source #

Invert the set.

### Composition

intersections :: [DenseIntSet] -> DenseIntSet Source #

Intersect multiple sets

unions :: [DenseIntSet] -> DenseIntSet Source #

Unite multiple sets

## Accessors

capacity :: DenseIntSet -> Int Source #

*O(1)*. Size of the value space.

population :: DenseIntSet -> Int Source #

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

### Vectors

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

Extract the present elements into a vector.

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

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

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