Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Data.Patricia.Word.Strict.Unsafe
Description
Data structure internals, helper operations and unsafe functions.
Synopsis
- data Patricia a
- type Prefix = Word
- type Key = Word
- beyond :: Prefix -> Key -> Bool
- upper :: Prefix -> Key
- lower :: Prefix -> Key
- type Mask = Word
- zeroBit :: Key -> Mask -> Bool
- mask :: Key -> Mask -> Word
- branchingBit :: Prefix -> Prefix -> Mask
- data MalformedTree = MalformedTree String String
- data Range where
- unsafeAdjustRange :: (a -> a) -> Word -> Word -> Patricia a -> Patricia a
- unsafeAdjustRange' :: (a -> a) -> Word -> Word -> Patricia a -> Patricia a
- unsafeAdjustRangeWithKey :: (Word -> a -> a) -> Word -> Word -> Patricia a -> Patricia a
- unsafeAdjustRangeWithKey' :: (Word -> a -> a) -> Word -> Word -> Patricia a -> Patricia a
- unsafeDeleteRange :: Word -> Word -> Patricia a -> Patricia a
- unsafeUpdateRange :: (a -> Maybe a) -> Word -> Word -> Patricia a -> Patricia a
- unsafeUpdateRangeWithKey :: (Word -> a -> Maybe a) -> Word -> Word -> Patricia a -> Patricia a
- unsafeTakeRange :: Word -> Word -> Patricia a -> Patricia a
- data Lookup a = Lookup !Word a
- unsafeLookupMin :: Patricia a -> (# a #)
- unsafeLookupMinWithKey :: Patricia a -> Lookup a
- unsafeLookupMax :: Patricia a -> (# a #)
- unsafeLookupMaxWithKey :: Patricia a -> Lookup a
- data ViewL a = ViewL !(Lookup a) !(Patricia a)
- unsafeMinView :: Patricia a -> ViewL a
- data ViewR a = ViewR !(Patricia a) !(Lookup a)
- unsafeMaxView :: Patricia a -> ViewR a
- merge :: (Key -> a -> b -> Patricia c) -> (Key -> a -> Patricia c) -> (Prefix -> Patricia a -> Patricia a -> Patricia c) -> (Key -> b -> Patricia c) -> (Prefix -> Patricia b -> Patricia b -> Patricia c) -> Patricia a -> Patricia b -> Patricia c
Documentation
Spine-strict PATRICIA tree.
Instances
Bit operations
Compare
Create
branchingBit :: Prefix -> Prefix -> Mask Source #
O(1).
Find the bit two Prefix
es disagree on.
Note that using this function on two equal integers yields 1 << (-1)
,
which results in undefined behavior.
Exceptions
data MalformedTree Source #
Exception thrown by functions that need to return a value, but instead find an invariant-breaking empty node.
Constructors
MalformedTree | |
Instances
Exception MalformedTree Source # | |
Defined in Radix.Exception Methods toException :: MalformedTree -> SomeException # fromException :: SomeException -> Maybe MalformedTree # displayException :: MalformedTree -> String # | |
Show MalformedTree Source # | |
Defined in Radix.Exception Methods showsPrec :: Int -> MalformedTree -> ShowS # show :: MalformedTree -> String # showList :: [MalformedTree] -> ShowS # |
Range
A closed interval between two keys.
Constructors
UnsafeRange | Invariant: kL≤kR. |
Bundled Patterns
pattern Range | Reorders endpoints to fit mathematical notation: [12,3] will be converted to [3,12]. Pattern matching guarantees k1≤k2. |
Map
O(min. Apply a function to every value for which the key is in the given range.
k_R must be greater than k_L.
\mathcal{O}(\min(n,W) + n_I). Apply a function to every value for which the key is in the given range.
New value is evaluated to WHNF.
k_R must be greater than k_L.
unsafeAdjustRangeWithKey Source #
\mathcal{O}(\min(n,W) + n_I). Apply a function to every value for which the key is in the given range.
k_R must be greater than k_L.
unsafeAdjustRangeWithKey' Source #
\mathcal{O}(\min(n,W) + n_I). Apply a function to every value for which the key is in the given range.
New value is evaluated to WHNF.
k_R must be greater than k_L.
Delete
\mathcal{O}(\min(n,W)). Delete values for which keys are in the given range.
k_R must be greater than k_L.
Update
\mathcal{O}(\min(n,W) + n_I). Update every value for which the key is in the given range.
The Maybe
is evaluated to WHNF.
k_R must be greater than k_L.
unsafeUpdateRangeWithKey Source #
\mathcal{O}(\min(n,W) + n_I). Update every value for which the key is in the given range.
The Maybe
is evaluated to WHNF.
k_R must be greater than k_L.
Take
\mathcal{O}(\min(n,W)). Take values for which keys are in the given range.
k_R must be greater than k_L.
Edges
Lookup
Key together with the value.
Min
unsafeLookupMin :: Patricia a -> (# a #) Source #
\mathcal{O}(\min(n,W)). Look up a value at the leftmost key in the tree.
Throws MalformedTree
if the tree is empty.
unsafeLookupMinWithKey :: Patricia a -> Lookup a Source #
\mathcal{O}(\min(n,W)). Look up a value at the leftmost key in the tree.
Throws MalformedTree
if the tree is empty.
Max
unsafeLookupMax :: Patricia a -> (# a #) Source #
\mathcal{O}(\min(n,W)). Look up a value at the rightmost key in the tree.
Throws MalformedTree
if the tree is empty.
unsafeLookupMaxWithKey :: Patricia a -> Lookup a Source #
\mathcal{O}(\min(n,W)). Look up a value at the rightmost key in the tree.
Throws MalformedTree
if the tree is empty.
View
Min
The leftmost value with its key and the rest of the tree.
unsafeMinView :: Patricia a -> ViewL a Source #
\mathcal{O}(\min(n,W)). Look up the leftmost value and return it alongside the tree without it.
Throws MalformedTree
if the tree is empty.
Max
The rightmost value with its key and the rest of the tree.
unsafeMaxView :: Patricia a -> ViewR a Source #
\mathcal{O}(\min(n,W)). Look up the rightmost value and return it alongside the tree without it.
Throws MalformedTree
if the tree is empty.
Full-tree
Merge
Arguments
:: (Key -> a -> b -> Patricia c) | Single value collision |
-> (Key -> a -> Patricia c) | Single left value |
-> (Prefix -> Patricia a -> Patricia a -> Patricia c) | Left subtree |
-> (Key -> b -> Patricia c) | Single right value |
-> (Prefix -> Patricia b -> Patricia b -> Patricia c) | Right subtree |
-> Patricia a | |
-> Patricia b | |
-> Patricia c |
\mathcal{O}(n_A + n_B). General merge of two trees.
Collision and single value functions must return either
Tip
with the respective key, or Nil
.
Subtree argument functions may return any tree, however the shape of said tree must be compatible with the prefix passed to the function.
Resulting Patricia
trees in argument functions are evaluated to WHNF.
This functions inlines when all argument functions are provided.