Z-Data-0.1.7.2: Array, vector and text

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

Z.Data.Vector.FlatIntSet

Contents

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

FlatIntSet backed by sorted vector

data FlatIntSet Source #

Instances
Eq FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

Ord FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

Show FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

Semigroup FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

Monoid FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

Arbitrary FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

CoArbitrary FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

Methods

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

NFData FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

Methods

rnf :: FlatIntSet -> () #

ShowT FlatIntSet Source # 
Instance details

Defined in Z.Data.Vector.FlatIntSet

FromValue FlatIntSet Source # 
Instance details

Defined in Z.Data.JSON.Base

EncodeJSON FlatIntSet Source # 
Instance details

Defined in Z.Data.JSON.Base

ToValue FlatIntSet Source # 
Instance details

Defined in Z.Data.JSON.Base

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.

elem :: Int -> FlatIntSet -> Bool Source #

O(logN) Binary search on flat set.

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.

binary & linear search on vectors

binarySearch :: PrimVector Int -> Int -> Either Int Int Source #

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.