Module trie

Description
Data Types
Function Index
Function Details

A trie data structure implementation.

The trie (i.e., from "retrieval") data structure was invented by Edward Fredkin (it is a form of radix sort). The implementation stores string suffixes as a list because it is a PATRICIA trie (PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric, D.R.Morrison (1968)).

Version: 2.0.5 Oct 26 2023 11:28:28 ------------------------------------------------------------------------

Authors: Michael Truog (mjtruog at protonmail dot com).

Description

A trie data structure implementation.

This Erlang trie implementation uses string (list of integers) keys and is able to get performance close to the process dictionary when doing key lookups (find or fetch, see http://okeuday.livejournal.com/16941.html). Utilizing this trie, it is possible to avoid generating dynamic atoms in various contexts. Also, an added benefit to using this trie is that the traversals preserve alphabetical ordering.

Data Types

empty_trie()

empty_trie() = []

nonempty_trie()

nonempty_trie() = {integer(), integer(), tuple()}

trie()

trie() = nonempty_trie() | empty_trie()

Function Index

append/3	Append a value as a list element in a trie instance. .
append_list/3	Append a list of values as a list element in a trie instance. .
erase/2	Erase a value in a trie. .
erase_similar/2	Erase all entries within a trie that share a common prefix. .
fetch/2	Fetch a value from a trie. .
fetch_keys/1	Fetch all the keys in a trie. .
fetch_keys_similar/2	Fetch the keys within a trie that share a common prefix. .
filter/2	Filter a trie with a predicate function. .
find/2	Find a value in a trie. .
find_match/2	Find a match with patterns held within a trie. All patterns held within the trie use a wildcard character "*" to represent a regex of ".+".
find_match2/2	Find a match with patterns (using 2 wildcard characters) held within a trie. All patterns held within the trie use the wildcard character "*" or "?" to represent a regex of ".+".
find_prefix/2	Find a value in a trie by prefix. The atom 'prefix' is returned if the string supplied is a prefix for a key that has previously been stored within the trie, but no value was found, since there was no exact match for the string supplied.
find_prefix_longest/2	Find the longest key in a trie that is a prefix to the passed string. .
find_prefixes/2	Find all the keys in a trie that are prefixes to the passed string. The entries are returned in alphabetical order.
find_similar/2	Find the first key/value pair in a trie where the key shares a common prefix. The first match is found based on alphabetical order.
fold/3	Fold a function over the trie. Traverses in alphabetical order.
fold_match/4	Fold a function over the keys within a trie that matches a pattern. Traverses in alphabetical order.
fold_similar/4	Fold a function over the keys within a trie that share a common prefix. Traverses in alphabetical order.
foldl/3	Fold a function over the trie. Traverses in alphabetical order.
foldl_similar/4	Fold a function over the keys within a trie that share a common prefix. Traverses in alphabetical order.
foldr/3	Fold a function over the trie in reverse. Traverses in reverse alphabetical order.
foldr_similar/4	Fold a function over the keys within a trie that share a common prefix in reverse. Traverses in reverse alphabetical order.
foreach/2	Call a function for each element. Traverses in alphabetical order.
from_list/1	Create a trie from a list. .
is_bytestring/1	Test if the parameter is a byte string. .
is_bytestring_nonempty/1	Test if the parameter is a nonempty byte string. .
is_key/2	Determine if a key exists in a trie. .
is_pattern/1	Test to determine if a string is a pattern. "*" is the wildcard character (equivalent to the ".+" regex).
is_pattern2/1	Test to determine if a string is a pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
is_pattern2_bytes/1	Test to determine if a byte string is a pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
is_pattern_bytes/1	Test to determine if a byte string is a pattern. "*" is the wildcard character (equivalent to the ".+" regex).
is_prefix/2	Determine if the prefix provided has existed within a trie. The function returns true if the string supplied is a prefix for a key that has previously been stored within the trie.
is_prefixed/2	Determine if the provided string has a prefix within a trie. .
is_prefixed/3	Determine if the provided string has an acceptable prefix within a trie. The prefix within the trie must match at least 1 character that is not within the excluded list of characters.
iter/2	Iterate over a trie. Traverses in alphabetical order.
itera/3	Iterate over a trie with an accumulator. Traverses in alphabetical order.
map/2	Map a function over a trie. Traverses in reverse alphabetical order.
merge/3	Merge two trie instance. Update the second trie parameter with all of the elements found within the first trie parameter.
new/0	Create a new trie instance. .
new/1	Create a new trie instance from a list. The list may contain either: strings, 2 element tuples with a string as the first tuple element, or tuples with more than 2 elements (including records) with a string as the first element (second element if it is a record).
pattern2_fill/2	Fill wildcard characters in a string. The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).
pattern2_fill/4	Fill wildcard characters in a string. The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).
pattern2_parse/2	Parse a string based on the supplied wildcard pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
pattern2_parse/3	Parse a string based on the supplied wildcard pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
pattern2_suffix/2	Parse a string based on the supplied wildcard pattern (using 2 wildcard characters) to return only the suffix after the pattern. "*" and "?" are wildcard characters (equivalent to the ".+" regex).
pattern_fill/2	Fill wildcard characters in a string. The "*" wildcard character may be used consecutively by this function to have parameters concatenated.
pattern_fill/4	Fill wildcard characters in a string. The "*" wildcard character may be used consecutively by this function to have parameters concatenated.
pattern_parse/2	Parse a string based on the supplied wildcard pattern. "*" is the wildcard character (equivalent to the ".+" regex).
pattern_parse/3	Parse a string based on the supplied wildcard pattern. "*" is the wildcard character (equivalent to the ".+" regex).
pattern_suffix/2	Parse a string based on the supplied wildcard pattern to return only the suffix after the pattern. "*" is the wildcard character (equivalent to the ".+" regex).
prefix/3	Insert a value as the first list element in a trie instance. The reverse of append/3.
size/1	Size of a trie instance. .
store/2	Store only a key in a trie instance. .
store/3	Store a key/value pair in a trie instance. .
take/2	Take a value from the trie. .
to_list/1	Convert all entries in a trie to a list. The list is in alphabetical order.
to_list_similar/2	Return a list of all entries within a trie that share a common prefix. .
update/3	Update a value in a trie. .
update/4	Update or add a value in a trie. .
update_counter/3	Update a counter in a trie. .

Function Details

append/3

append(Key::nonempty_string(), Value::any(), Node::trie()) -> nonempty_trie()

Append a value as a list element in a trie instance.

append_list/3

append_list(Key::nonempty_string(), ValueList::list(), Node::trie()) -> nonempty_trie()

Append a list of values as a list element in a trie instance.

erase/2

erase(Key::nonempty_string(), Node::trie()) -> trie()

Erase a value in a trie.

erase_similar/2

erase_similar(Similar::nonempty_string(), Node::trie()) -> [nonempty_string()]

Erase all entries within a trie that share a common prefix.

fetch/2

fetch(T::nonempty_string(), Node::nonempty_trie()) -> any()

Fetch a value from a trie.

fetch_keys/1

fetch_keys(Node::trie()) -> [nonempty_string()]

Fetch all the keys in a trie.

fetch_keys_similar/2

fetch_keys_similar(Similar::nonempty_string(), Node::trie()) -> [nonempty_string()]

Fetch the keys within a trie that share a common prefix.

filter/2

filter(F::fun((nonempty_string(), any()) -> boolean()), Node::trie()) -> trie()

Filter a trie with a predicate function.

find/2

find(T::nonempty_string(), Node::trie()) -> {ok, any()} | error

Find a value in a trie.

find_match/2

find_match(Match::string(), Node::trie()) -> {ok, any(), any()} | error

Find a match with patterns held within a trie.

All patterns held within the trie use a wildcard character "*" to represent a regex of ".+". "**" within the trie will result in undefined behavior (the pattern is malformed). The function will search for the most specific match possible, given the input string and the trie contents. The input string must not contain wildcard characters, otherwise a badarg exit exception will occur. If you instead want to supply a pattern string to match the contents of the trie, see fold_match/4.

find_match2/2

find_match2(Match::string(), Node::trie()) -> {ok, any(), any()} | error

Find a match with patterns (using 2 wildcard characters) held within a trie.

All patterns held within the trie use the wildcard character "*" or "?" to represent a regex of ".+". "**", "??", "*?", or "?*" within the trie will result in undefined behavior (the pattern is malformed). The function will search for the most specific match possible, given the input string and the trie contents. The input string must not contain wildcard characters, otherwise a badarg exit exception will occur. The "?" wildcard character consumes the shortest match to the next character and must not be the the last character in the string (the pattern would be malformed).

find_prefix/2

find_prefix(T::nonempty_string(), X2::trie()) -> {ok, any()} | prefix | error

Find a value in a trie by prefix.

The atom 'prefix' is returned if the string supplied is a prefix for a key that has previously been stored within the trie, but no value was found, since there was no exact match for the string supplied.

find_prefix_longest/2

find_prefix_longest(Match::nonempty_string(), Node::trie()) -> {ok, nonempty_string(), any()} | error

Find the longest key in a trie that is a prefix to the passed string.

find_prefixes/2

find_prefixes(Match::nonempty_string(), Node::trie()) -> [{nonempty_string(), any()}]

Find all the keys in a trie that are prefixes to the passed string.

The entries are returned in alphabetical order.

find_similar/2

find_similar(Similar::string(), Node::trie()) -> {ok, string(), any()} | error

Find the first key/value pair in a trie where the key shares a common prefix.

The first match is found based on alphabetical order.

fold/3

fold(F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the trie.

Traverses in alphabetical order.

fold_match/4

fold_match(Match::string(), F::fun((string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the keys within a trie that matches a pattern.

Traverses in alphabetical order. Uses "*" as a wildcard character within the pattern (it acts like a ".+" regex, and "**" is forbidden). The trie keys must not contain wildcard characters, otherwise a badarg exit exception will occur. If you want to match a specific string without wildcards on trie values that contain wildcard characters, see find_match/2.

fold_similar/4

fold_similar(Similar::nonempty_string(), F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the keys within a trie that share a common prefix.

Traverses in alphabetical order.

foldl/3

foldl(F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the trie.

Traverses in alphabetical order.

foldl_similar/4

foldl_similar(Similar::nonempty_string(), F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the keys within a trie that share a common prefix.

Traverses in alphabetical order.

foldr/3

foldr(F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the trie in reverse.

Traverses in reverse alphabetical order.

foldr_similar/4

foldr_similar(Similar::nonempty_string(), F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the keys within a trie that share a common prefix in reverse.

Traverses in reverse alphabetical order.

foreach/2

foreach(F::fun((nonempty_string(), any()) -> any()), Node::trie()) -> any()

Call a function for each element.

Traverses in alphabetical order.

from_list/1

from_list(L::[nonempty_string() | tuple()]) -> trie()

Create a trie from a list.

is_bytestring/1

is_bytestring(L::[byte()]) -> true | false

Test if the parameter is a byte string.

is_bytestring_nonempty/1

is_bytestring_nonempty(L::[byte(), ...]) -> true | false

Test if the parameter is a nonempty byte string.

is_key/2

is_key(T::nonempty_string(), Node::trie()) -> boolean()

Determine if a key exists in a trie.

is_pattern/1

is_pattern(Pattern::string()) -> true | false

Test to determine if a string is a pattern.

"*" is the wildcard character (equivalent to the ".+" regex). "**" is forbidden.

is_pattern2/1

is_pattern2(Pattern::string()) -> true | false

Test to determine if a string is a pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

is_pattern2_bytes/1

is_pattern2_bytes(Pattern::[byte()]) -> true | false

Test to determine if a byte string is a pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

is_pattern_bytes/1

is_pattern_bytes(Pattern::[byte()]) -> true | false

Test to determine if a byte string is a pattern.

"*" is the wildcard character (equivalent to the ".+" regex). "**" is forbidden.

is_prefix/2

is_prefix(T::string(), X2::trie()) -> true | false

Determine if the prefix provided has existed within a trie.

The function returns true if the string supplied is a prefix for a key that has previously been stored within the trie. If no values with the prefix matching key(s) were removed from the trie, then the prefix currently exists within the trie.

is_prefixed/2

is_prefixed(T::string(), X2::trie()) -> true | false

Determine if the provided string has a prefix within a trie.

is_prefixed/3

is_prefixed(Key::string(), Exclude::string(), Node::trie()) -> true | false

Determine if the provided string has an acceptable prefix within a trie.

The prefix within the trie must match at least 1 character that is not within the excluded list of characters.

iter/2

iter(F::fun((string(), any(), fun(() -> any())) -> any()), Node::trie()) -> ok

Iterate over a trie.

Traverses in alphabetical order.

itera/3

itera(F::fun((string(), any(), any(), fun((any()) -> any())) -> any()), A::any(), Node::trie()) -> any()

Iterate over a trie with an accumulator.

Traverses in alphabetical order.

map/2

map(F::fun((nonempty_string(), any()) -> any()), Node::trie()) -> trie()

Map a function over a trie.

Traverses in reverse alphabetical order.

merge/3

merge(F::fun((nonempty_string(), any(), any()) -> any()), Node1::trie(), Node2::trie()) -> trie()

Merge two trie instance.

Update the second trie parameter with all of the elements found within the first trie parameter.

new/0

new() -> empty_trie()

Create a new trie instance.

new/1

new(L::[nonempty_string() | tuple()]) -> trie()

Create a new trie instance from a list.

The list may contain either: strings, 2 element tuples with a string as the first tuple element, or tuples with more than 2 elements (including records) with a string as the first element (second element if it is a record). If a list of records (or tuples larger than 2 elements) is provided, the whole record/tuple is stored as the value.

pattern2_fill/2

pattern2_fill(FillPattern::string(), Parameters::[string()]) -> {ok, string()} | {error, parameters_ignored | parameter_missing}

Fill wildcard characters in a string.

The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).

pattern2_fill/4

pattern2_fill(FillPattern::string(), Parameters::[string()], ParametersSelected::[pos_integer()], ParametersStrictMatching::boolean()) -> {ok, string()} | {error, parameters_ignored | parameter_missing | parameters_selected_empty | {parameters_selected_ignored, [pos_integer()]} | {parameters_selected_missing, pos_integer()}}

Fill wildcard characters in a string.

The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).

pattern2_parse/2

pattern2_parse(Pattern::string(), L::string()) -> [string()] | error

Parse a string based on the supplied wildcard pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

pattern2_parse/3

pattern2_parse(Pattern::string(), L::string(), Option::default | with_suffix | expanded) -> [string()] | {[string()], string()} | [string() | {exact, string()}] | error

Parse a string based on the supplied wildcard pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

pattern2_suffix/2

pattern2_suffix(Pattern::string(), L::string()) -> string() | error

Parse a string based on the supplied wildcard pattern (using 2 wildcard characters) to return only the suffix after the pattern.

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

pattern_fill/2

pattern_fill(FillPattern::string(), Parameters::[string()]) -> {ok, string()} | {error, parameters_ignored | parameter_missing}

Fill wildcard characters in a string.

The "*" wildcard character may be used consecutively by this function to have parameters concatenated.

pattern_fill/4

pattern_fill(FillPattern::string(), Parameters::[string()], ParametersSelected::[pos_integer()], ParametersStrictMatching::boolean()) -> {ok, string()} | {error, parameters_ignored | parameter_missing | parameters_selected_empty | {parameters_selected_ignored, [pos_integer()]} | {parameters_selected_missing, pos_integer()}}