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.

A labelled edge.

A simple pair (label :~> subtree) representing an edge of a RadixTreeMap.

Note that the subtre pointed by an edge must never be empty!

A collection of uniquely labelled edges.

This could be Map (String a) (Edge a v), using the entire label as key, but the trie property ensures that the first character of the label must also be unique. This enables us to use a faster implementation and also helps to ensure the trie property.

Show RadixTreeMap in a readable, idented format.

O(1) The empty map.

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

O(?) Build a map from a list of key/value pairs.

>>> import Prelude (Char, Int)
>>> construct [("abc", 1), ("def", 3), ("abb", 5)]
Tree [ab :~> Tree [b :~> Tree (5) [],c :~> Tree (1) []],def :~> Tree (3) []]

O(n log r) Lookup the value at a key in the map.

>>> import Prelude (Int)
>>> lookup "abc" (construct [("abc", 1), ("def", 3), ("abb", 5)])
Just 1

>>> lookup "xyz" (construct [("abc", 1), ("def", 3), ("abb", 5)])
Nothing

>>> lookupMax (construct [("abc", 1), ("def", 3), ("abb", 5)])
Just 3

O(n log r) Extract the value associated with the minimal key in the map.

>>> lookupMin @Char @Int (construct [("abc", 1), ("def", 3), ("abb", 5)])
Just 5

>>> lookupMin @Char @Int empty
Nothing

O(n log r) Extract the minimal key in the map.

>>> lookupMinWithKey (construct [("abc", 1), ("def", 3), ("abb", 5)])
Just (abb,5)

>>> lookupMinWithKey @Char @Int empty
Nothing

O(n log r) Extract the value associated with the maximal key in the map.

>>> lookupMax @Char @Int (construct [("abc", 1), ("def", 3), ("abb", 5)])
Just 3

>>> lookupMax @Char @Int empty
Nothing

O(n log r) Extract the maximal key in the map.

>>> lookupMaxWithKey (construct [("abc", 1), ("def", 3), ("abb", 5)])
Just (def,3)

>>> lookupMaxWithKey @Char @Int empty
Nothing

O(n log r) Check if there is an associated value for the key.

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

>>> member "xyz" (construct [("abc", 1), ("def", 3), ("abb", 5)])
False

O(?) Insert a new key and value in the map.

If the key is already present in the map, the associated value is replaced with the supplied value.

Insert with a function, combining new value and old value.

insertWith f key value tree will insert the pair (key, value) into tree if key does not exist in the map. If the key does exist, the function will insert the pair (key, f new_value old_value).

O(?) The expression union t1 t2 takes the left-biased union of t1 and t2.

It prefers t1 when duplicate keys are encountered.

O(?) Union with a combining function.

O(?) Delete a key and its value from the map.

When the key is not a member of the map, the original map is returned.

O(n log r) Update values for all prefixes of key in the map, present or not.