| Copyright | (c) Dong Han 2017-2019 (c) Tao He 2018-2019 |
|---|---|
| License | BSD |
| Maintainer | winterland1989@gmail.com |
| Stability | experimental |
| Portability | non-portable |
| Safe Haskell | None |
| Language | Haskell2010 |
Z.Data.Vector.FlatIntSet
Description
This module provides a simple int set based on sorted vector and binary search. It's particularly suitable for small sized value collections such as deserializing intermediate representation. But can also used in various place where insertion and deletion is rare but require fast elem.
Synopsis
- data FlatIntSet
- sortedValues :: FlatIntSet -> PrimVector Int
- size :: FlatIntSet -> Int
- null :: FlatIntSet -> Bool
- empty :: FlatIntSet
- map' :: (Int -> Int) -> FlatIntSet -> FlatIntSet
- pack :: [Int] -> FlatIntSet
- packN :: Int -> [Int] -> FlatIntSet
- packR :: [Int] -> FlatIntSet
- packRN :: Int -> [Int] -> FlatIntSet
- unpack :: FlatIntSet -> [Int]
- unpackR :: FlatIntSet -> [Int]
- packVector :: PrimVector Int -> FlatIntSet
- packVectorR :: PrimVector Int -> FlatIntSet
- elem :: Int -> FlatIntSet -> Bool
- delete :: Int -> FlatIntSet -> FlatIntSet
- insert :: Int -> FlatIntSet -> FlatIntSet
- merge :: FlatIntSet -> FlatIntSet -> FlatIntSet
- binarySearch :: PrimVector Int -> Int -> Either Int Int
FlatIntSet backed by sorted vector
data FlatIntSet Source #
Instances
sortedValues :: FlatIntSet -> PrimVector Int Source #
size :: FlatIntSet -> Int Source #
null :: FlatIntSet -> Bool Source #
empty :: FlatIntSet Source #
O(1) empty flat set.
map' :: (Int -> Int) -> FlatIntSet -> FlatIntSet Source #
Mapping values of within a set, the result size may change if there're duplicated values after mapping.
pack :: [Int] -> FlatIntSet Source #
O(N*logN) Pack list of values, on duplication prefer left one.
packN :: Int -> [Int] -> FlatIntSet Source #
O(N*logN) Pack list of values with suggested size, on duplication prefer left one.
packR :: [Int] -> FlatIntSet Source #
O(N*logN) Pack list of values, on duplication prefer right one.
packRN :: Int -> [Int] -> FlatIntSet Source #
O(N*logN) Pack list of values with suggested size, on duplication prefer right one.
unpack :: FlatIntSet -> [Int] Source #
O(N) Unpack a set of values to a list s in ascending order.
This function works with foldr/build fusion in base.
unpackR :: FlatIntSet -> [Int] Source #
O(N) Unpack a set of values to a list s in descending order.
This function works with foldr/build fusion in base.
packVector :: PrimVector Int -> FlatIntSet Source #
O(N*logN) Pack vector of values, on duplication prefer left one.
packVectorR :: PrimVector Int -> FlatIntSet Source #
O(N*logN) Pack vector of values, on duplication prefer right one.
delete :: Int -> FlatIntSet -> FlatIntSet Source #
O(N) Delete a value.
insert :: Int -> FlatIntSet -> FlatIntSet Source #
O(N) Insert new value into set.
merge :: FlatIntSet -> FlatIntSet -> FlatIntSet Source #
O(n+m) Merge two FlatIntSet, prefer right value on value duplication.