Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.RadixTree.Word8.Lazy.Unsafe

Contents

Bit operations
Exceptions
Full-tree
- Merge

Description

Data structure internals, helper operations and unsafe functions.

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

data RadixTree a Source #

Spine-strict radix tree with byte sequences as keys.

Constructors

RadixTree
Fields !(Maybe a) Value at the empty byte sequence key. (Radix1Tree a)

Instances

Instances details

Foldable RadixTree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods fold :: Monoid m => RadixTree m -> m # foldMap :: Monoid m => (a -> m) -> RadixTree a -> m # foldMap' :: Monoid m => (a -> m) -> RadixTree a -> m # foldr :: (a -> b -> b) -> b -> RadixTree a -> b # foldr' :: (a -> b -> b) -> b -> RadixTree a -> b # foldl :: (b -> a -> b) -> b -> RadixTree a -> b # foldl' :: (b -> a -> b) -> b -> RadixTree a -> b # foldr1 :: (a -> a -> a) -> RadixTree a -> a # foldl1 :: (a -> a -> a) -> RadixTree a -> a # toList :: RadixTree a -> [a] # null :: RadixTree a -> Bool # length :: RadixTree a -> Int # elem :: Eq a => a -> RadixTree a -> Bool # maximum :: Ord a => RadixTree a -> a # minimum :: Ord a => RadixTree a -> a # sum :: Num a => RadixTree a -> a # product :: Num a => RadixTree a -> a #
Eq1 RadixTree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods liftEq :: (a -> b -> Bool) -> RadixTree a -> RadixTree b -> Bool #
Show1 RadixTree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> RadixTree a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [RadixTree a] -> ShowS #
Traversable RadixTree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods traverse :: Applicative f => (a -> f b) -> RadixTree a -> f (RadixTree b) # sequenceA :: Applicative f => RadixTree (f a) -> f (RadixTree a) # mapM :: Monad m => (a -> m b) -> RadixTree a -> m (RadixTree b) # sequence :: Monad m => RadixTree (m a) -> m (RadixTree a) #
Functor RadixTree Source #	Uses `map`.
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods fmap :: (a -> b) -> RadixTree a -> RadixTree b # (<$) :: a -> RadixTree b -> RadixTree a #
NFData1 RadixTree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods liftRnf :: (a -> ()) -> RadixTree a -> () #
Show a => Show (RadixTree a) Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods showsPrec :: Int -> RadixTree a -> ShowS # show :: RadixTree a -> String # showList :: [RadixTree a] -> ShowS #
NFData a => NFData (RadixTree a) Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods rnf :: RadixTree a -> () #
Eq a => Eq (RadixTree a) Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods (==) :: RadixTree a -> RadixTree a -> Bool # (/=) :: RadixTree a -> RadixTree a -> Bool #

data Radix1Tree a Source #

Spine-strict radix tree with non-empty byte sequences as keys.

Constructors

Bin
Fields !Prefix (Radix1Tree a) Masked bit is `0`. Invariant: not `Nil`. (Radix1Tree a) Masked bit is `1`. Invariant: not `Nil`.
Tip
Fields !ByteArray Invariant: non-empty. !(Maybe a) Invariant: can only be `Nothing` when the tree below is `Bin`. (Radix1Tree a)
Nil

Instances

Instances details

Foldable Radix1Tree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods fold :: Monoid m => Radix1Tree m -> m # foldMap :: Monoid m => (a -> m) -> Radix1Tree a -> m # foldMap' :: Monoid m => (a -> m) -> Radix1Tree a -> m # foldr :: (a -> b -> b) -> b -> Radix1Tree a -> b # foldr' :: (a -> b -> b) -> b -> Radix1Tree a -> b # foldl :: (b -> a -> b) -> b -> Radix1Tree a -> b # foldl' :: (b -> a -> b) -> b -> Radix1Tree a -> b # foldr1 :: (a -> a -> a) -> Radix1Tree a -> a # foldl1 :: (a -> a -> a) -> Radix1Tree a -> a # toList :: Radix1Tree a -> [a] # null :: Radix1Tree a -> Bool # length :: Radix1Tree a -> Int # elem :: Eq a => a -> Radix1Tree a -> Bool # maximum :: Ord a => Radix1Tree a -> a # minimum :: Ord a => Radix1Tree a -> a # sum :: Num a => Radix1Tree a -> a # product :: Num a => Radix1Tree a -> a #
Eq1 Radix1Tree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods liftEq :: (a -> b -> Bool) -> Radix1Tree a -> Radix1Tree b -> Bool #
Show1 Radix1Tree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Radix1Tree a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Radix1Tree a] -> ShowS #
Traversable Radix1Tree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods traverse :: Applicative f => (a -> f b) -> Radix1Tree a -> f (Radix1Tree b) # sequenceA :: Applicative f => Radix1Tree (f a) -> f (Radix1Tree a) # mapM :: Monad m => (a -> m b) -> Radix1Tree a -> m (Radix1Tree b) # sequence :: Monad m => Radix1Tree (m a) -> m (Radix1Tree a) #
Functor Radix1Tree Source #	Uses `map`.
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods fmap :: (a -> b) -> Radix1Tree a -> Radix1Tree b # (<$) :: a -> Radix1Tree b -> Radix1Tree a #
NFData1 Radix1Tree Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods liftRnf :: (a -> ()) -> Radix1Tree a -> () #
Show a => Show (Radix1Tree a) Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods showsPrec :: Int -> Radix1Tree a -> ShowS # show :: Radix1Tree a -> String # showList :: [Radix1Tree a] -> ShowS #
NFData a => NFData (Radix1Tree a) Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods rnf :: Radix1Tree a -> () #
Eq a => Eq (Radix1Tree a) Source #
Instance details Defined in Data.RadixNTree.Word8.Lazy Methods (==) :: Radix1Tree a -> Radix1Tree a -> Bool # (/=) :: Radix1Tree a -> Radix1Tree a -> Bool #

Bit operations

type Prefix = Word8 Source #

Part of the Key from the largest bit to the Mask bit, plus the Mask bit.

type Key = Word8 Source #

Key as stored in the data structure.

Compare

beyond :: Prefix -> Key -> Bool Source #

$\mathcal{O}(1)$. Whether the key does not match the prefix.

upper :: Prefix -> Key Source #

$\mathcal{O}(1)$. Largest key that can reside under this prefix.

lower :: Prefix -> Key Source #

$\mathcal{O}(1)$. Smallest key that can reside under this prefix.

Create

type Mask = Word8 Source #

Masking bit.

zeroBit :: Key -> Mask -> Bool Source #

Get the state of the masked bit from the Key.

mask :: Key -> Mask -> Prefix Source #

Trim the Key down to a Prefix.

branchingBit :: Prefix -> Prefix -> Mask Source #

Finds the bit the two Prefixes disagree on.

Exceptions

data MalformedTree Source #

Exception thrown by functions that need to return a value, but instead find an invariant-breaking empty node.

Constructors

MalformedTree
Fields String Module name String Function name

Instances

Instances details

Exception MalformedTree Source #
Instance details Defined in Radix.Exception Methods toException :: MalformedTree -> SomeException # fromException :: SomeException -> Maybe MalformedTree # displayException :: MalformedTree -> String #
Show MalformedTree Source #
Instance details Defined in Radix.Exception Methods showsPrec :: Int -> MalformedTree -> ShowS # show :: MalformedTree -> String # showList :: [MalformedTree] -> ShowS #

Full-tree

Merge

merge Source #

Arguments

:: (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}(1)\texttt{+}, \mathcal{O}(n_A k_A + n_B k_B)$. General merge of two trees.

Resulting Maybes and Radix1Trees in argument functions are evaluated to WHNF.

This functions inlines when all argument functions are provided.