Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Data structure internals, helper operations and unsafe functions.
Implementation
The tree is an altered Patricia
tree.
Each Tip
in the radix tree represents a continuous non-empty chunk of the key,
at the end of which there either exists a value or the rest of the key branches.
The first byte of the chunk corresponds to a Key
in a
Patricia
tree, hence the definitions of
Bin
and Nil
remain unchanged.
The only state the resulting Radix1Tree
is unable to represent is the
value at the root of the tree (for which the key is an empty byte sequence),
as such that value is prepended with a special 2-tuple named RadixTree
.
Synopsis
- data RadixTree a = RadixTree !(Maybe a) !(Radix1Tree a)
- data Radix1Tree a
- = Bin !Prefix !(Radix1Tree a) !(Radix1Tree a)
- | Tip !ByteArray !(Maybe a) !(Radix1Tree a)
- | Nil
- type Prefix = Word8
- type Key = Word8
- beyond :: Prefix -> Key -> Bool
- upper :: Prefix -> Key
- lower :: Prefix -> Key
- type Mask = Word8
- zeroBit :: Key -> Mask -> Bool
- mask :: Key -> Mask -> Prefix
- branchingBit :: Prefix -> Prefix -> Mask
- data MalformedTree = MalformedTree String String
- merge :: (Build -> a -> b -> Maybe c) -> (Build -> a -> Maybe c) -> (Build -> Radix1Tree a -> Radix1Tree c) -> (Build -> b -> Maybe c) -> (Build -> Radix1Tree b -> Radix1Tree c) -> RadixTree a -> RadixTree b -> RadixTree c
Documentation
Spine-strict radix tree with byte sequences as keys.
RadixTree | |
|
Instances
data Radix1Tree a Source #
Spine-strict radix tree with non-empty byte sequences as keys.
Bin | |
| |
Tip | |
| |
Nil |
Instances
Bit operations
Compare
beyond :: Prefix -> Key -> Bool Source #
\(\mathcal{O}(1)\). Whether the key does not match the prefix.
Create
Exceptions
data MalformedTree Source #
Exception thrown by functions that need to return a value, but instead find an invariant-breaking empty node.
Instances
Exception MalformedTree Source # | |
Defined in Radix.Exception | |
Show MalformedTree Source # | |
Defined in Radix.Exception showsPrec :: Int -> MalformedTree -> ShowS # show :: MalformedTree -> String # showList :: [MalformedTree] -> ShowS # |
Full-tree
Merge
:: (Build -> a -> b -> Maybe c) | Single value collision |
-> (Build -> a -> Maybe c) | Single left value |
-> (Build -> Radix1Tree a -> Radix1Tree c) | Left subtree |
-> (Build -> b -> Maybe c) | Single right value |
-> (Build -> Radix1Tree b -> Radix1Tree c) | Right subtree |
-> RadixTree a | |
-> RadixTree b | |
-> RadixTree c |
\(\mathcal{O}(n_A k_A + n_B k_B)\). General merge of two trees.
Resulting Maybe
s and Radix1Tree
s in argument functions are evaluated to WHNF.
This functions inlines when all argument functions are provided.