Safe Haskell	Safe-Inferred
Language	GHC2021

MCSP.Data.RadixTree

Contents

Data Types
Construction
Query
Modification

Description

A compressed trie of string radices.

Synopsis

type RadixTree a = RadixTreeMap a (String a)
data RadixTreeMap a v
empty :: RadixTree a
construct :: Ord a => [String a] -> RadixTree a
member :: Ord a => String a -> RadixTree a -> Bool
findMin :: RadixTree a -> Maybe (String a)
findMax :: RadixTree a -> Maybe (String a)
insert :: Ord a => String a -> RadixTree a -> RadixTree a
union :: Ord a => RadixTree a -> RadixTree a -> RadixTree a
delete :: Ord a => String a -> RadixTree a -> RadixTree a

Data Types

type RadixTree a = RadixTreeMap a (String a) Source #

A set of Strings represented by a radix tree.

This tree is implemented a RadixTreeMap where each key is associated with itself, enabling key construction in constant time (no need to concatenate radices) and some useful instances (like Foldable).

data RadixTreeMap a v Source #

A map of String keys represented by a radix tree.

The tree structure uses the maximal substring possible to label edges so that each internal node has at least two children. Even though a substrings are used, the trie property is maintained, that is, a node has at most r children, where r is the number of possible values for a. Given this property, substring are stored using a sorted Map which may improve performance.

Instances

Instances details

Foldable (RadixTreeMap s) Source #	Delegate `Foldabe` to its `Edge`s.
Instance details Defined in MCSP.Data.RadixTree.Map Methods fold :: Monoid m => RadixTreeMap s m -> m # foldMap :: Monoid m => (a -> m) -> RadixTreeMap s a -> m # foldMap' :: Monoid m => (a -> m) -> RadixTreeMap s a -> m # foldr :: (a -> b -> b) -> b -> RadixTreeMap s a -> b # foldr' :: (a -> b -> b) -> b -> RadixTreeMap s a -> b # foldl :: (b -> a -> b) -> b -> RadixTreeMap s a -> b # foldl' :: (b -> a -> b) -> b -> RadixTreeMap s a -> b # foldr1 :: (a -> a -> a) -> RadixTreeMap s a -> a # foldl1 :: (a -> a -> a) -> RadixTreeMap s a -> a # toList :: RadixTreeMap s a -> [a] # null :: RadixTreeMap s a -> Bool # length :: RadixTreeMap s a -> Int # elem :: Eq a => a -> RadixTreeMap s a -> Bool # maximum :: Ord a => RadixTreeMap s a -> a # minimum :: Ord a => RadixTreeMap s a -> a # sum :: Num a => RadixTreeMap s a -> a # product :: Num a => RadixTreeMap s a -> a #
Traversable (RadixTreeMap s) Source #
Instance details Defined in MCSP.Data.RadixTree.Map Methods traverse :: Applicative f => (a -> f b) -> RadixTreeMap s a -> f (RadixTreeMap s b) # sequenceA :: Applicative f => RadixTreeMap s (f a) -> f (RadixTreeMap s a) # mapM :: Monad m => (a -> m b) -> RadixTreeMap s a -> m (RadixTreeMap s b) # sequence :: Monad m => RadixTreeMap s (m a) -> m (RadixTreeMap s a) #
Functor (RadixTreeMap s) Source #
Instance details Defined in MCSP.Data.RadixTree.Map Methods fmap :: (a -> b) -> RadixTreeMap s a -> RadixTreeMap s b # (<$) :: a -> RadixTreeMap s b -> RadixTreeMap s a #
(ShowString a, Show v) => Show (RadixTreeMap a v) Source #
Instance details Defined in MCSP.Data.RadixTree.Map Methods showsPrec :: Int -> RadixTreeMap a v -> ShowS # show :: RadixTreeMap a v -> String # showList :: [RadixTreeMap a v] -> ShowS #
(Eq v, Eq a) => Eq (RadixTreeMap a v) Source #
Instance details Defined in MCSP.Data.RadixTree.Map Methods (==) :: RadixTreeMap a v -> RadixTreeMap a v -> Bool # (/=) :: RadixTreeMap a v -> RadixTreeMap a v -> Bool #
(Ord v, Ord a) => Ord (RadixTreeMap a v) Source #
Instance details Defined in MCSP.Data.RadixTree.Map Methods compare :: RadixTreeMap a v -> RadixTreeMap a v -> Ordering # (<) :: RadixTreeMap a v -> RadixTreeMap a v -> Bool # (<=) :: RadixTreeMap a v -> RadixTreeMap a v -> Bool # (>) :: RadixTreeMap a v -> RadixTreeMap a v -> Bool # (>=) :: RadixTreeMap a v -> RadixTreeMap a v -> Bool # max :: RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v # min :: RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v #

Construction

empty :: RadixTree a Source #

O(1) The empty tree.

>>> import Prelude (Char)
>>> empty @Char
Tree []

construct :: Ord a => [String a] -> RadixTree a Source #

O(?) Build a radix tree from a list of strings.

>>> construct ["abc", "def", "abb"]
Tree [ab :~> Tree [b :~> Tree (abb) [],c :~> Tree (abc) []],def :~> Tree (def) []]

Query

member :: Ord a => String a -> RadixTree a -> Bool Source #

O(n log r) Check if string is present in the tree.

>>> member "ab" (construct ["abc", "def", "abb"])
False

>>> member "abc" (construct ["abc", "def", "abb"])
True

findMin :: RadixTree a -> Maybe (String a) Source #

O(n log r) Extract the minimal string in the tree.

>>> findMin (construct ["abc", "def", "abb"])
Just abb

>>> import Prelude (Char)
>>> findMin @Char empty
Nothing

findMax :: RadixTree a -> Maybe (String a) Source #

O(n log r) Extract the minimal string in the tree.

>>> findMax (construct ["abc", "def", "abb"])
Just def

>>> import Prelude (Char)
>>> findMax @Char empty
Nothing

Modification

insert :: Ord a => String a -> RadixTree a -> RadixTree a Source #

O(?) Insert a string in a tree.

If the tree already contains a string equal to the given value, it is replaced with the new value.

>>> insert "xyz" (construct ["abc"])
Tree [abc :~> Tree (abc) [],xyz :~> Tree (xyz) []]

>>> insert "xyz" (construct ["abc", "xyz"])
Tree [abc :~> Tree (abc) [],xyz :~> Tree (xyz) []]

union :: Ord a => RadixTree a -> RadixTree a -> RadixTree a Source #

O(?) The union of two sets, preferring the first set when equal strings are encountered.

>>> construct ["abc"] `union` construct ["def"]
Tree [abc :~> Tree (abc) [],def :~> Tree (def) []]

>>> construct ["abc"] `union` construct []
Tree [abc :~> Tree (abc) []]

>>> construct [] `union` construct ["abc"]
Tree [abc :~> Tree (abc) []]

>>> construct ["abc"] `union` construct ["abc"]
Tree [abc :~> Tree (abc) []]

delete :: Ord a => String a -> RadixTree a -> RadixTree a Source #

O(?) Delete a string from the tree set.

>>> delete "abc" (construct ["abc", "def"])
Tree [def :~> Tree (def) []]

>>> delete "abc" (construct ["def"])
Tree [def :~> Tree (def) []]