node

DynamicNode

DynamicNode(parser, children=None, leaf=None, separator='/')

Bases: RadixNode

A DynamicNode is a single elements.

This class wraps a named-regex pattern which is later used to match strings.

prefix_search

prefix_search(prefix)

Searches a prefix and yields all nodes that match.

We yield inside-out, so the deepest matching node should appear first in results.

Check the PrefixSearchResult object for unmatched characters.

Note: When inserting dynamic nodes, we need some way to check that they're the same.

This is different from searching an input string using the regex. We look for a completely matching dynamic path.

search_path

search_path(path, context=None)

This method runs a regex match function and updates the context dict with any matched values.

LeafNode

LeafNode(handler)

Bases: Generic[V]

The LeafNode represents a pointer to a handler.

NodeChildSet

NodeChildSet(data=None)

Bases: MutableSet

The children of a node are two Sets: - DynamicNodes - StaticNodes

The goal of this data structure is to make it easy to iterate StaticNodes before DynamicNodes.

We keep two Sets below the surface: one for StaticNodes and one for DynamicNodes. Then, when iterating, we iterate StaticNodes first.

__contains__

__contains__(node)

Check if a node exists in children

__iter__

__iter__()

Iterate child nodes (static first!)

__len__

__len__()

The length of all children is the sum of the lengths of dynamic and static nodes

add

add(node)

Puts item into appropriate set. If key already exists in the other set, we delete it from there afterward.

Parameters:

Name	Type	Description	Default
node	RadixNode	RadixNode to add as a child	required

discard

discard(node)

Remove a child node

PrefixSearchResult

PrefixSearchResult(node, index, left_side_remaining, right_side_remaining)

A class for packaging up results for comparing strings against nodes

complete_match property

complete_match()

If this match is 'complete' then both sides will be empty afterward

RadixNode

RadixNode(path, children=None, leaf=None, separator='/')

Bases: Generic[V]

A base class for a node in our radix tree.

__bool__

__bool__()

A RadixNode is always truthy.

Without this method if node will call len which recursively iterates the entire tree!

__eq__

__eq__(other_node)

Note: this equality checks only the nodes. It does not recurse into child nodes, so the sub-trees may be different for nodes that are equal.

__len__

__len__()

Returns count of all nodes in the tree

insert

insert(path, handler=None)

Inserts a path somewhere in this tree as a new subtree

May include dynamic path parts.

prefix_search

prefix_search(prefix)

Searches a prefix and yields all nodes that match.

We yield inside-out, so the deepest matching node should appear first in results.

Note: this method doesn't guarantee a full match. It means only that there are some matching characters for this prefix.

prettyprint

prettyprint(mult=1, indent='')

Pretty printing a tree is a useful visualization tool.

Note, this calls self.tree_as_str to get a string representation of the tree.

search_path

search_path(path, context=None)

Searches for a prefix and returns only a node that is a complete match.

tree_as_str

tree_as_str(mult=1, indent='', is_leaf=False)

Representing this tree as a string is a useful visualization tool.

This can help with debugging and documentation.

StaticNode

StaticNode(path, children=None, leaf=None, separator='/')

Bases: RadixNode

A StaticNode has no dynamic elements.

prefix_search

prefix_search(prefix)

Searches a prefix and yields all nodes that match.

We yield inside-out, so the deepest matching node should appear first in results.

Note: this method doesn't guarantee a full match. It means only that there are some matching characters for this prefix.

Check the PrefixSearchResult object for unmatched characters.

search_path

search_path(path, context=None)

Searches for a prefix and returns only a node that is a complete match.

For dynamic nodes, it will use the regex parser to match the input path.

We yield inside-out, so the deepest matching node should appear first in results.

Note: this method doesn't guarantee a full match. It means only that there are some matching characters for this prefix.

merge_nodes

merge_nodes(into, merge_node)

This operation is useful when we discover overlapping paths in our radix tree

node_map

node_map(element)

Returns a DynamicNode or a StaticNode for any str or parser passed in.

path_to_tree

path_to_tree(path, handler)

Create a new tree out of this path. Because this is a new node, it should contain only simple parent.children = {child-node} relationships.

Parameters:

Name	Type	Description	Default
path	str	The path to construct a tree out of	required
handler	Any	Any associated function that we want this path to point to.	required

Returns:

Name	Type	Description
RadixNode	RadixNode	the root node of the tree