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.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 Std.Data.Vector.FlatIntSet

Ord FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

Show FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

Semigroup FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

Monoid FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

NFData FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

Methods

rnf :: FlatIntSet -> () #

Arbitrary FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

CoArbitrary FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

Methods

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

ToText FlatIntSet Source # 
Instance details

Defined in Std.Data.Vector.FlatIntSet

FromValue FlatIntSet Source # 
Instance details

Defined in Std.Data.JSON.Base

EncodeJSON FlatIntSet Source # 
Instance details

Defined in Std.Data.JSON.Base

ToValue FlatIntSet Source # 
Instance details

Defined in Std.Data.JSON.Base

empty :: FlatIntSet Source #

O(1) empty flat map.

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 key values, on key duplication prefer left one.

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

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

packR :: [Int] -> FlatIntSet Source #

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

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

O(N*logN) Pack list of key values with suggested size, on key 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 key values, on key duplication prefer left one.

packVectorR :: PrimVector Int -> FlatIntSet Source #

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

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

O(logN) Binary search on flat map.

delete :: Int -> FlatIntSet -> FlatIntSet Source #

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

insert :: Int -> FlatIntSet -> FlatIntSet Source #

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

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 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.