| Copyright | (c) Sergey Vinokurov 2018 |
|---|---|
| License | BSD3-style (see LICENSE) |
| Maintainer | serg.foo@gmail.com |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Data.RadixTree.Internal
Description
This is an internal module that exposes innards of the RadixTree
data structure. This API may change in any new release, even in a
patch release - depend on it at your own risk.
Synopsis
- data RadixTree a
- empty :: RadixTree a
- null :: RadixTree a -> Bool
- size :: RadixTree a -> Int
- insert :: forall a. ShortByteString -> a -> RadixTree a -> RadixTree a
- insertWith :: forall a. (a -> a -> a) -> ShortByteString -> a -> RadixTree a -> RadixTree a
- lookup :: forall a. ShortByteString -> RadixTree a -> Maybe a
- fromList :: [(ShortByteString, a)] -> RadixTree a
- toList :: RadixTree a -> [(ShortByteString, a)]
- toAscList :: forall a. RadixTree a -> [(ShortByteString, a)]
- keys :: RadixTree a -> [ShortByteString]
- keysSet :: RadixTree a -> Set ShortByteString
- elems :: RadixTree a -> [a]
- mapMaybe :: forall a b. (a -> Maybe b) -> RadixTree a -> RadixTree b
- union :: RadixTree a -> RadixTree a -> RadixTree a
- unionWith :: forall a. (a -> a -> a) -> RadixTree a -> RadixTree a -> RadixTree a
Documentation
A tree data structure that efficiently indexes values by string keys.
This type can be more memory-efficient than Map because it combines
common prefixes of all keys. Specific savings will vary depending on
concrete data set.
Constructors
| RadixNode !(Maybe a) !(IntMap (RadixTree a)) | Either has 0 or 2 or more children, never 1. |
| RadixStr | |
Fields
| |
Instances
insert :: forall a. ShortByteString -> a -> RadixTree a -> RadixTree a Source #
Add new element to a radix tree.
insertWith :: forall a. (a -> a -> a) -> ShortByteString -> a -> RadixTree a -> RadixTree a Source #
Add new element to a radix tree. If an element was already present for
the given key, use supplied funciton f to produce a new value. The
function will be called like this f newValue oldValue.
lookup :: forall a. ShortByteString -> RadixTree a -> Maybe a Source #
O(length(key)) Try to find a value associated with the given key.
fromList :: [(ShortByteString, a)] -> RadixTree a Source #
Construct a radix tree from list of key-value pairs. If some key appears twice in the input list, later occurrences will override earlier ones.
toList :: RadixTree a -> [(ShortByteString, a)] Source #
O(n) Convert a radix tree to a list of key-value pairs.
toAscList :: forall a. RadixTree a -> [(ShortByteString, a)] Source #
O(n) Convert a radix tree to an ascending list of key-value pairs.
keys :: RadixTree a -> [ShortByteString] Source #
O(n) Get all keys stored in a radix tree.
keysSet :: RadixTree a -> Set ShortByteString Source #
O(n) Get set of all keys stored in a radix tree.
mapMaybe :: forall a b. (a -> Maybe b) -> RadixTree a -> RadixTree b Source #
O(n) Map a function that can remove some existing elements over a radix tree.