Data.RadixTree.Word8.Strict.Unsafe

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.

Documentation

data RadixTree a

Spine-strict radix tree with byte sequences as keys.

Constructors

RadixTree

Fields

• !(Maybe a)

  Value at the empty byte sequence key.

• !(Radix1Tree a)

Instances

Foldable RadixTree

Defined in Data.RadixNTree.Word8.Strict

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

Defined in Data.RadixNTree.Word8.Strict

Methods

liftEq :: (a -> b -> Bool) -> RadixTree a -> RadixTree b -> Bool

Show1 RadixTree

Defined in Data.RadixNTree.Word8.Strict

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> RadixTree a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [RadixTree a] -> ShowS

Traversable RadixTree

Defined in Data.RadixNTree.Word8.Strict

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

Uses map.

Defined in Data.RadixNTree.Word8.Strict

Methods

fmap :: (a -> b) -> RadixTree a -> RadixTree b

(<$) :: a -> RadixTree b -> RadixTree a

NFData1 RadixTree

Defined in Data.RadixNTree.Word8.Strict

Methods

liftRnf :: (a -> ()) -> RadixTree a -> ()

Show a => Show (RadixTree a)

Defined in Data.RadixNTree.Word8.Strict

Methods

showsPrec :: Int -> RadixTree a -> ShowS

show :: RadixTree a -> String

showList :: [RadixTree a] -> ShowS

NFData a => NFData (RadixTree a)

Defined in Data.RadixNTree.Word8.Strict

Methods

rnf :: RadixTree a -> ()

Eq a => Eq (RadixTree a)

Defined in Data.RadixNTree.Word8.Strict

Methods

(==) :: RadixTree a -> RadixTree a -> Bool

(/=) :: RadixTree a -> RadixTree a -> Bool

data Radix1Tree a

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

Foldable Radix1Tree

Defined in Data.RadixNTree.Word8.Strict

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

Defined in Data.RadixNTree.Word8.Strict

Methods

liftEq :: (a -> b -> Bool) -> Radix1Tree a -> Radix1Tree b -> Bool

Show1 Radix1Tree

Defined in Data.RadixNTree.Word8.Strict

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Radix1Tree a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Radix1Tree a] -> ShowS

Traversable Radix1Tree

Defined in Data.RadixNTree.Word8.Strict

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

Uses map.

Defined in Data.RadixNTree.Word8.Strict

Methods

fmap :: (a -> b) -> Radix1Tree a -> Radix1Tree b

(<$) :: a -> Radix1Tree b -> Radix1Tree a

NFData1 Radix1Tree

Defined in Data.RadixNTree.Word8.Strict

Methods

liftRnf :: (a -> ()) -> Radix1Tree a -> ()

Show a => Show (Radix1Tree a)

Defined in Data.RadixNTree.Word8.Strict

Methods

showsPrec :: Int -> Radix1Tree a -> ShowS

show :: Radix1Tree a -> String

showList :: [Radix1Tree a] -> ShowS

NFData a => NFData (Radix1Tree a)

Defined in Data.RadixNTree.Word8.Strict

Methods

rnf :: Radix1Tree a -> ()

Eq a => Eq (Radix1Tree a)

Defined in Data.RadixNTree.Word8.Strict

Methods

(==) :: Radix1Tree a -> Radix1Tree a -> Bool

(/=) :: Radix1Tree a -> Radix1Tree a -> Bool

Bit operations

type Prefix = Word8

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

type Key = Word8

Key as stored in the data structure.

Compare

beyond :: Prefix -> Key -> Bool

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

upper :: Prefix -> Key

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

lower :: Prefix -> Key

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

Create

type Mask = Word8

Masking bit.

zeroBit :: Key -> Mask -> Bool

Get the state of the masked bit from the Key.

mask :: Key -> Mask -> Prefix

Trim the Key down to a Prefix.

branchingBit :: Prefix -> Prefix -> Mask

Finds the bit the two Prefixes disagree on.

Exceptions

data MalformedTree

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

Exception MalformedTree

Defined in Radix.Exception

Methods

toException :: MalformedTree -> SomeException

fromException :: SomeException -> Maybe MalformedTree

displayException :: MalformedTree -> String

Show MalformedTree

Defined in Radix.Exception

Methods

showsPrec :: Int -> MalformedTree -> ShowS

show :: MalformedTree -> String

showList :: [MalformedTree] -> ShowS

Full-tree

Merge

merge

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}(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.