Data.RadixTree.Word8.Lazy.Unsafe

Data structure internals, helper operations and unsafe functions.

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

Defined in Data.RadixNTree.Word8.Lazy

Methods

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

Show1 RadixTree

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

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

Uses map.

Defined in Data.RadixNTree.Word8.Lazy

Methods

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

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

NFData1 RadixTree

Defined in Data.RadixNTree.Word8.Lazy

Methods

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

Show a => Show (RadixTree a)

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)

Defined in Data.RadixNTree.Word8.Lazy

Methods

rnf :: RadixTree a -> ()

Eq a => Eq (RadixTree a)

Defined in Data.RadixNTree.Word8.Lazy

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

Defined in Data.RadixNTree.Word8.Lazy

Methods

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

Show1 Radix1Tree

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

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

Uses map.

Defined in Data.RadixNTree.Word8.Lazy

Methods

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

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

NFData1 Radix1Tree

Defined in Data.RadixNTree.Word8.Lazy

Methods

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

Show a => Show (Radix1Tree a)

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)

Defined in Data.RadixNTree.Word8.Lazy

Methods

rnf :: Radix1Tree a -> ()

Eq a => Eq (Radix1Tree a)

Defined in Data.RadixNTree.Word8.Lazy

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