stdio-0.2.0.0: A simple and high performance IO toolkit for Haskell

Copyright(c) Dong Han 2017-2019
(c) Tao He 2018-2019
LicenseBSD
Maintainerwinterland1989@gmail.com
Stabilityexperimental
Portabilitynon-portable
Safe HaskellNone
LanguageHaskell2010

Std.Data.Vector.FlatSet

Contents

Description

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.

Synopsis

FlatSet backed by sorted vector

data FlatSet v Source #

Instances
Foldable FlatSet Source # 
Instance details

Defined in Std.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) Source # 
Instance details

Defined in Std.Data.Vector.FlatSet

Methods

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

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

Ord v => Ord (FlatSet v) Source # 
Instance details

Defined in Std.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) Source # 
Instance details

Defined in Std.Data.Vector.FlatSet

Methods

showsPrec :: Int -> FlatSet v -> ShowS #

show :: FlatSet v -> String #

showList :: [FlatSet v] -> ShowS #

Ord v => Semigroup (FlatSet v) Source # 
Instance details

Defined in Std.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) Source # 
Instance details

Defined in Std.Data.Vector.FlatSet

Methods

mempty :: FlatSet v #

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

mconcat :: [FlatSet v] -> FlatSet v #

NFData v => NFData (FlatSet v) Source # 
Instance details

Defined in Std.Data.Vector.FlatSet

Methods

rnf :: FlatSet v -> () #

(Ord v, Arbitrary v) => Arbitrary (FlatSet v) Source # 
Instance details

Defined in Std.Data.Vector.FlatSet

Methods

arbitrary :: Gen (FlatSet v)

shrink :: FlatSet v -> [FlatSet v]

CoArbitrary v => CoArbitrary (FlatSet v) Source # 
Instance details

Defined in Std.Data.Vector.FlatSet

Methods

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

ToText v => ToText (FlatSet v) Source # 
Instance details

Defined in Std.Data.Vector.FlatSet

(Ord a, FromValue a) => FromValue (FlatSet a) Source # 
Instance details

Defined in Std.Data.JSON.Base

EncodeJSON a => EncodeJSON (FlatSet a) Source # 
Instance details

Defined in Std.Data.JSON.Base

Methods

encodeJSON :: FlatSet a -> Builder () Source #

ToValue a => ToValue (FlatSet a) Source # 
Instance details

Defined in Std.Data.JSON.Base

Methods

toValue :: FlatSet a -> Value Source #

empty :: FlatSet v Source #

O(1) empty flat map.

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

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

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

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

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

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

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

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

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

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

unpack :: FlatSet v -> [v] 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 :: FlatSet v -> [v] 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 :: Ord v => Vector v -> FlatSet v Source #

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

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

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

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

O(logN) Binary search on flat map.

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

O(N) Delete a key value pair by key.

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

O(N) Insert new key value into map, replace old one if key exists.

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

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

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

This function only works on ascending sorted vectors.