Z.Data.Vector.FlatIntSet

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.

FlatIntSet backed by sorted vector

data FlatIntSet

Instances

Eq FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

(==) :: FlatIntSet -> FlatIntSet -> Bool

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

Ord FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

compare :: FlatIntSet -> FlatIntSet -> Ordering

(<) :: FlatIntSet -> FlatIntSet -> Bool

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

(>) :: FlatIntSet -> FlatIntSet -> Bool

(>=) :: FlatIntSet -> FlatIntSet -> Bool

max :: FlatIntSet -> FlatIntSet -> FlatIntSet

min :: FlatIntSet -> FlatIntSet -> FlatIntSet

Show FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

showsPrec :: Int -> FlatIntSet -> ShowS

show :: FlatIntSet -> String

showList :: [FlatIntSet] -> ShowS

Semigroup FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

(<>) :: FlatIntSet -> FlatIntSet -> FlatIntSet

sconcat :: NonEmpty FlatIntSet -> FlatIntSet

stimes :: Integral b => b -> FlatIntSet -> FlatIntSet

Monoid FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

mempty :: FlatIntSet

mappend :: FlatIntSet -> FlatIntSet -> FlatIntSet

mconcat :: [FlatIntSet] -> FlatIntSet

Arbitrary FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

arbitrary :: Gen FlatIntSet

shrink :: FlatIntSet -> [FlatIntSet]

CoArbitrary FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

coarbitrary :: FlatIntSet -> Gen b -> Gen b

NFData FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

rnf :: FlatIntSet -> ()

Print FlatIntSet

Defined in Z.Data.Vector.FlatIntSet

Methods

toUTF8BuilderP :: Int -> FlatIntSet -> Builder ()

JSON FlatIntSet

Defined in Z.Data.JSON.Base

Methods

fromValue :: Value -> Converter FlatIntSet

toValue :: FlatIntSet -> Value

encodeJSON :: FlatIntSet -> Builder ()

sortedValues :: FlatIntSet -> PrimVector Int

size :: FlatIntSet -> Int

null :: FlatIntSet -> Bool

empty :: FlatIntSet

O(1) empty flat set.

map' :: (Int -> Int) -> FlatIntSet -> FlatIntSet

Mapping values of within a set, the result size may change if there're duplicated values after mapping.

pack :: [Int] -> FlatIntSet

O(N*logN) Pack list of values, on duplication prefer left one.

packN :: Int -> [Int] -> FlatIntSet

O(N*logN) Pack list of values with suggested size, on duplication prefer left one.

packR :: [Int] -> FlatIntSet

O(N*logN) Pack list of values, on duplication prefer right one.

packRN :: Int -> [Int] -> FlatIntSet

O(N*logN) Pack list of values with suggested size, on duplication prefer right one.

unpack :: FlatIntSet -> [Int]

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]

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

O(N*logN) Pack vector of values, on duplication prefer left one.

packVectorR :: PrimVector Int -> FlatIntSet

O(N*logN) Pack vector of values, on duplication prefer right one.

elem :: Int -> FlatIntSet -> Bool

O(logN) Binary search on flat set.

delete :: Int -> FlatIntSet -> FlatIntSet

O(N) Delete a value.

insert :: Int -> FlatIntSet -> FlatIntSet

O(N) Insert new value into set.

merge :: FlatIntSet -> FlatIntSet -> FlatIntSet

O(n+m) Merge two FlatIntSet, prefer right value on value duplication.

search on vectors

binarySearch :: PrimVector Int -> Int -> Either Int Int

Find the value's index in the vector slice, if value exists return Right, otherwise Left, i.e. the insert index

This function only works on ascending sorted vectors.