Copyright | (c) Dong Han 2017-2019 (c) Tao He 2018-2019 |
---|---|
License | BSD |
Maintainer | winterland1989@gmail.com |
Stability | experimental |
Portability | non-portable |
Safe Haskell | None |
Language | Haskell2010 |
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
- data FlatSet v
- sortedValues :: FlatSet v -> Vector v
- size :: FlatSet v -> Int
- null :: FlatSet v -> Bool
- empty :: FlatSet v
- map' :: forall v. Ord v => (v -> v) -> FlatSet v -> FlatSet v
- pack :: Ord v => [v] -> FlatSet v
- packN :: Ord v => Int -> [v] -> FlatSet v
- packR :: Ord v => [v] -> FlatSet v
- packRN :: Ord v => Int -> [v] -> FlatSet v
- unpack :: FlatSet v -> [v]
- unpackR :: FlatSet v -> [v]
- packVector :: Ord v => Vector v -> FlatSet v
- packVectorR :: Ord v => Vector v -> FlatSet v
- elem :: Ord v => v -> FlatSet v -> Bool
- delete :: Ord v => v -> FlatSet v -> FlatSet v
- insert :: Ord v => v -> FlatSet v -> FlatSet v
- merge :: forall v. Ord v => FlatSet v -> FlatSet v -> FlatSet v
- binarySearch :: Ord v => Vector v -> v -> Either Int Int
FlatSet backed by sorted vector
Instances
sortedValues :: FlatSet v -> Vector v Source #
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.
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.