Z.Data.Vector.FlatSet

This module provides a simple value 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.

FlatSet backed by sorted vector

data FlatSet v

Instances

Foldable FlatSet

Defined in Z.Data.Vector.FlatSet

Methods

fold :: Monoid m => FlatSet m -> m

foldMap :: Monoid m => (a -> m) -> FlatSet a -> m

foldr :: (a -> b -> b) -> b -> FlatSet a -> b

foldr' :: (a -> b -> b) -> b -> FlatSet a -> b

foldl :: (b -> a -> b) -> b -> FlatSet a -> b

foldl' :: (b -> a -> b) -> b -> FlatSet a -> b

foldr1 :: (a -> a -> a) -> FlatSet a -> a

foldl1 :: (a -> a -> a) -> FlatSet a -> a

toList :: FlatSet a -> [a]

null :: FlatSet a -> Bool

length :: FlatSet a -> Int

elem :: Eq a => a -> FlatSet a -> Bool

maximum :: Ord a => FlatSet a -> a

minimum :: Ord a => FlatSet a -> a

sum :: Num a => FlatSet a -> a

product :: Num a => FlatSet a -> a

Eq v => Eq (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

(==) :: FlatSet v -> FlatSet v -> Bool

(/=) :: FlatSet v -> FlatSet v -> Bool

Ord v => Ord (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

compare :: FlatSet v -> FlatSet v -> Ordering

(<) :: FlatSet v -> FlatSet v -> Bool

(<=) :: FlatSet v -> FlatSet v -> Bool

(>) :: FlatSet v -> FlatSet v -> Bool

(>=) :: FlatSet v -> FlatSet v -> Bool

max :: FlatSet v -> FlatSet v -> FlatSet v

min :: FlatSet v -> FlatSet v -> FlatSet v

Show v => Show (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

showsPrec :: Int -> FlatSet v -> ShowS

show :: FlatSet v -> String

showList :: [FlatSet v] -> ShowS

Ord v => Semigroup (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

(<>) :: FlatSet v -> FlatSet v -> FlatSet v

sconcat :: NonEmpty (FlatSet v) -> FlatSet v

stimes :: Integral b => b -> FlatSet v -> FlatSet v

Ord v => Monoid (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

mempty :: FlatSet v

mappend :: FlatSet v -> FlatSet v -> FlatSet v

mconcat :: [FlatSet v] -> FlatSet v

(Ord v, Arbitrary v) => Arbitrary (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

arbitrary :: Gen (FlatSet v)

shrink :: FlatSet v -> [FlatSet v]

CoArbitrary v => CoArbitrary (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

coarbitrary :: FlatSet v -> Gen b -> Gen b

NFData v => NFData (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

rnf :: FlatSet v -> ()

ShowT v => ShowT (FlatSet v)

Defined in Z.Data.Vector.FlatSet

Methods

toTextBuilder :: Int -> FlatSet v -> TextBuilder ()

(Ord a, FromValue a) => FromValue (FlatSet a)

Defined in Z.Data.JSON.Base

Methods

fromValue :: Value -> Converter (FlatSet a)

EncodeJSON a => EncodeJSON (FlatSet a)

Defined in Z.Data.JSON.Base

Methods

encodeJSON :: FlatSet a -> Builder ()

ToValue a => ToValue (FlatSet a)

Defined in Z.Data.JSON.Base

Methods

toValue :: FlatSet a -> Value

sortedValues :: FlatSet v -> Vector v

size :: FlatSet v -> Int

null :: FlatSet v -> Bool

empty :: FlatSet v

O(1) empty flat set.

map' :: forall v. Ord v => (v -> v) -> FlatSet v -> FlatSet v

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

pack :: Ord v => [v] -> FlatSet v

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

packN :: Ord v => Int -> [v] -> FlatSet v

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

packR :: Ord v => [v] -> FlatSet v

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

packRN :: Ord v => Int -> [v] -> FlatSet v

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

unpack :: FlatSet v -> [v]

O(N) Unpack a set of values to a list s in ascending order.

This function works with foldr/build fusion in base.

unpackR :: FlatSet v -> [v]

O(N) Unpack a set of values to a list s in descending order.

This function works with foldr/build fusion in base.

packVector :: Ord v => Vector v -> FlatSet v

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

packVectorR :: Ord v => Vector v -> FlatSet v

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

elem :: Ord v => v -> FlatSet v -> Bool

O(logN) Binary search on flat set.

delete :: Ord v => v -> FlatSet v -> FlatSet v

O(N) Delete a value from set.

insert :: Ord v => v -> FlatSet v -> FlatSet v

O(N) Insert new value into set.

merge :: forall v. Ord v => FlatSet v -> FlatSet v -> FlatSet v

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

binary & linear search on vectors

binarySearch :: Ord v => Vector v -> v -> 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.