pure_radix package

Module contents

pure_radix: a generic [radix tree](https://en.wikipedia.org/wiki/Radix_tree) implementation in pure Python.

A radix tree (also known as a compressed trie or PATRICIA trie) is a tree data structure in which each edge is labeled with a sequence (a “prefix”) of elements, rather than a single element. It is a space-efficient way to store many sequences that share common prefixes.

The tree is fully generic: it works with any sequence of hashable elements (ints, strings, tuples, …). What each node stores is up to you: subclass Node to customize it, or use one of the ready-made subclasses such as SetNode.

Example

Create a tree in which each node holds a set of strings:

>>> from pure_radix import SetNode
>>> t = SetNode()
>>> # ``node_force`` creates the node (and any missing intermediate nodes) and returns it.
>>> n1 = t.node_force((10, 11, 12))
>>> n2 = t.node_force((10, 11, 30))
>>> n1.add("cat")
>>> n2.add("dog")
>>> # (10, 11) is a common prefix, so it lives in its own node, holding no data of its own.
>>> t.node_get((10, 11)) is not None
True
>>> t.node_get((10,)) is None
True
>>> print(t.node_debug_string())
[]
  [10, 11]
    [30] {'dog'}
    [12] {'cat'}
>>> # It works with any sequence type, including strings!
>>> s = SetNode()
>>> s.node_force("category").add(1)
>>> s.node_force("catalogue").add(2)
>>> s.node_get("cat") is not None
True
>>> s.node_get("car") is None
True

class pure_radix.ANode

Bases: Generic[T]

Abstract class implementing a node. You probably want to subclass the concrete class Node.

You must subclass this to customize the information stored in a Node. Avoid using the prefixes “node_” and “_node_” for methods or attributes in your subclass as it may lead to future name clashes.

Don’t forget to use @attr.s(slots=True, eq=False)

static _node_match_prefix(key, child_prefix, key_start=0)

Return type:

int

_node_new(parent, prefix)

Return type:

ANode[TypeVar(T, bound= Hashable)]

_node_replace_with_child()

node_children: dict[TypeVar(T, bound= Hashable), ANode[TypeVar(T, bound= Hashable)]]

node_debug_string(indent='  ', initial_indent='')

Return type:

str

node_debug_string_data()

node_debug_string_prefix()

node_find(has_data=True)

Recursively iterate through every child node. By default, only yield nodes that have data (where Node.node_should_prune is false).

Return type:

Iterator[ANode[TypeVar(T, bound= Hashable)]]

node_find_closest_nodes(sequence)

Yield pairs (longest_common_prefix, node) in descending order.

Return type:

Iterator[tuple[int, ANode[TypeVar(T, bound= Hashable)]]]

node_force(sequence, **kw)

Alias for get() with create=True.

Return type:

ANode[TypeVar(T, bound= Hashable)]

node_get(sequence, *, create=False, remove=0)

Return type:

Optional[ANode[TypeVar(T, bound= Hashable)]]

node_parent: Optional[ANode[TypeVar(T, bound= Hashable)]]

property node_parents

Yield parents, starting with node_parent and ending in the radix tree’s root.

property node_path

Like node_parents but includes the current node.

node_prefix: tuple[TypeVar(T, bound= Hashable), ...]

node_prune(enter=<function default_enter>)

Recursively prune the tree.

Return type:

None

node_prune_maybe()

Try to prune this node if possible and if node_should_prune is true.

Return type:

None

node_reparent(parent)

Change the parent of this node. If you need to add a hook that runs before or after a change of parent, a great way is to override this method and use super().node_reparent.

Return type:

None

property node_sequence: tuple[T, ...]

property node_sequence_offset: int

property node_should_prune

Should this node be pruned whenever possible? Default implementation always returns false.

node_traverse(sequence, sequence_start_index=0)

Mostly internal method. Starting at node, follow the path of sequence by looking at children and their children’s children and so on.

Return type:

TraverseResult

node_visit(enter=<function default_enter>, exit=<function default_exit>, frame_class=<class 'pure_radix.VisitFrame'>)

Visit nodes recursively. Call enter(stack, frame) before recursing down a node’s children, and call exit(stack, frame) after the node and its children have all been visited.

The enter function must modify VisitFrame.children (initially an empty list) and add to it the subset of child nodes that should be visited. The helper method VisitFrame.set_children() helps. If unset, then all children will be traversed.

Both enter and exit must return an iterable. The values from this iterable will be yielded from this generator.

Example:

def _enter(stack, frame):
    frame.set_children()
    # equivalent: frame.children = list(frame.node.node_children.values())

    yield ("enter", frame.node)

def _exit(stack, frame):
    yield ("exit", frame.node)

for action, node in t.node_visit(enter=_enter, exit=_exit):
    print(action, node)

Return type:

Iterator[TypeVar(S)]

class pure_radix.Node(node_prefix=(), node_children=NOTHING)

Bases: ANode, Generic[T]

You must subclass this to customize the information stored in a Node. Avoid using the prefixes “node_” and “_node_” for methods or attributes in your subclass as it may lead to future name clashes.

Don’t forget to use @attr.s(slots=True, eq=False)

static _node_match_prefix(key, child_prefix, key_start=0)

Return type:

int

_node_new(parent, prefix)

Return type:

ANode[TypeVar(T, bound= Hashable)]

_node_replace_with_child()

node_children: dict[TypeVar(T, bound= Hashable), ANode[TypeVar(T, bound= Hashable)]]

node_debug_string(indent='  ', initial_indent='')

Return type:

str

node_debug_string_data()

node_debug_string_prefix()

node_find(has_data=True)

Recursively iterate through every child node. By default, only yield nodes that have data (where Node.node_should_prune is false).

Return type:

Iterator[ANode[TypeVar(T, bound= Hashable)]]

node_find_closest_nodes(sequence)

Yield pairs (longest_common_prefix, node) in descending order.

Return type:

Iterator[tuple[int, ANode[TypeVar(T, bound= Hashable)]]]

node_force(sequence, **kw)

Alias for get() with create=True.

Return type:

ANode[TypeVar(T, bound= Hashable)]

node_get(sequence, *, create=False, remove=0)

Return type:

Optional[ANode[TypeVar(T, bound= Hashable)]]

node_parent: Optional[ANode[TypeVar(T, bound= Hashable)]]

property node_parents

Yield parents, starting with node_parent and ending in the radix tree’s root.

property node_path

Like node_parents but includes the current node.

node_prefix: tuple[TypeVar(T, bound= Hashable), ...]

node_prune(enter=<function default_enter>)

Recursively prune the tree.

Return type:

None

node_prune_maybe()

Try to prune this node if possible and if node_should_prune is true.

Return type:

None

node_reparent(parent)

Change the parent of this node. If you need to add a hook that runs before or after a change of parent, a great way is to override this method and use super().node_reparent.

Return type:

None

property node_sequence: tuple[T, ...]

property node_sequence_offset: int

property node_should_prune

Should this node be pruned whenever possible? Default implementation always returns false.

node_traverse(sequence, sequence_start_index=0)

Mostly internal method. Starting at node, follow the path of sequence by looking at children and their children’s children and so on.

Return type:

TraverseResult

node_visit(enter=<function default_enter>, exit=<function default_exit>, frame_class=<class 'pure_radix.VisitFrame'>)

Visit nodes recursively. Call enter(stack, frame) before recursing down a node’s children, and call exit(stack, frame) after the node and its children have all been visited.

The enter function must modify VisitFrame.children (initially an empty list) and add to it the subset of child nodes that should be visited. The helper method VisitFrame.set_children() helps. If unset, then all children will be traversed.

Both enter and exit must return an iterable. The values from this iterable will be yielded from this generator.

Example:

def _enter(stack, frame):
    frame.set_children()
    # equivalent: frame.children = list(frame.node.node_children.values())

    yield ("enter", frame.node)

def _exit(stack, frame):
    yield ("exit", frame.node)

for action, node in t.node_visit(enter=_enter, exit=_exit):
    print(action, node)

Return type:

Iterator[TypeVar(S)]

class pure_radix.RawDataNode(node_prefix=(), node_children=NOTHING, raw_data=None)

Bases: Node

static _node_match_prefix(key, child_prefix, key_start=0)

Return type:

int

_node_new(parent, prefix)

Return type:

ANode[TypeVar(T, bound= Hashable)]

_node_replace_with_child()

node_children: dict[TypeVar(T, bound= Hashable), ANode[TypeVar(T, bound= Hashable)]]

node_debug_string(indent='  ', initial_indent='')

Return type:

str

node_debug_string_data()

node_debug_string_prefix()

node_find(has_data=True)

Recursively iterate through every child node. By default, only yield nodes that have data (where Node.node_should_prune is false).

Return type:

Iterator[ANode[TypeVar(T, bound= Hashable)]]

node_find_closest_nodes(sequence)

Yield pairs (longest_common_prefix, node) in descending order.

Return type:

Iterator[tuple[int, ANode[TypeVar(T, bound= Hashable)]]]

node_force(sequence, **kw)

Alias for get() with create=True.

Return type:

ANode[TypeVar(T, bound= Hashable)]

node_get(sequence, *, create=False, remove=0)

Return type:

Optional[ANode[TypeVar(T, bound= Hashable)]]

node_parent: Optional[ANode[TypeVar(T, bound= Hashable)]]

property node_parents

Yield parents, starting with node_parent and ending in the radix tree’s root.

property node_path

Like node_parents but includes the current node.

node_prefix: tuple[TypeVar(T, bound= Hashable), ...]

node_prune(enter=<function default_enter>)

Recursively prune the tree.

Return type:

None

node_prune_maybe()

Try to prune this node if possible and if node_should_prune is true.

Return type:

None

node_reparent(parent)

Change the parent of this node. If you need to add a hook that runs before or after a change of parent, a great way is to override this method and use super().node_reparent.

Return type:

None

property node_sequence: tuple[T, ...]

property node_sequence_offset: int

property node_should_prune: bool

Should this node be pruned whenever possible? Default implementation always returns false.

node_traverse(sequence, sequence_start_index=0)

Mostly internal method. Starting at node, follow the path of sequence by looking at children and their children’s children and so on.

Return type:

TraverseResult

node_visit(enter=<function default_enter>, exit=<function default_exit>, frame_class=<class 'pure_radix.VisitFrame'>)

Visit nodes recursively. Call enter(stack, frame) before recursing down a node’s children, and call exit(stack, frame) after the node and its children have all been visited.

The enter function must modify VisitFrame.children (initially an empty list) and add to it the subset of child nodes that should be visited. The helper method VisitFrame.set_children() helps. If unset, then all children will be traversed.

Both enter and exit must return an iterable. The values from this iterable will be yielded from this generator.

Example:

def _enter(stack, frame):
    frame.set_children()
    # equivalent: frame.children = list(frame.node.node_children.values())

    yield ("enter", frame.node)

def _exit(stack, frame):
    yield ("exit", frame.node)

for action, node in t.node_visit(enter=_enter, exit=_exit):
    print(action, node)

Return type:

Iterator[TypeVar(S)]

raw_data

class pure_radix.SetNode(node_prefix=(), node_children=NOTHING, raw_data=None)

Bases: RawDataNode

Node which holds a set in data. This attribute is initialized lazily.

static _node_match_prefix(key, child_prefix, key_start=0)

Return type:

int

_node_new(parent, prefix)

Return type:

ANode[TypeVar(T, bound= Hashable)]

_node_replace_with_child()

add(x)

clear()

property data

discard(x)

node_children: dict[TypeVar(T, bound= Hashable), ANode[TypeVar(T, bound= Hashable)]]

node_debug_string(indent='  ', initial_indent='')

Return type:

str

node_debug_string_data()

node_debug_string_prefix()

node_find(has_data=True)

Recursively iterate through every child node. By default, only yield nodes that have data (where Node.node_should_prune is false).

Return type:

Iterator[ANode[TypeVar(T, bound= Hashable)]]

node_find_closest_nodes(sequence)

Yield pairs (longest_common_prefix, node) in descending order.

Return type:

Iterator[tuple[int, ANode[TypeVar(T, bound= Hashable)]]]

node_force(sequence, **kw)

Alias for get() with create=True.

Return type:

ANode[TypeVar(T, bound= Hashable)]

node_get(sequence, *, create=False, remove=0)

Return type:

Optional[ANode[TypeVar(T, bound= Hashable)]]

node_parent: Optional[ANode[TypeVar(T, bound= Hashable)]]

property node_parents

Yield parents, starting with node_parent and ending in the radix tree’s root.

property node_path

Like node_parents but includes the current node.

node_prefix: tuple[TypeVar(T, bound= Hashable), ...]

node_prune(enter=<function default_enter>)

Recursively prune the tree.

Return type:

None

node_prune_maybe()

Try to prune this node if possible and if node_should_prune is true.

Return type:

None

node_reparent(parent)

Change the parent of this node. If you need to add a hook that runs before or after a change of parent, a great way is to override this method and use super().node_reparent.

Return type:

None

property node_sequence: tuple[T, ...]

property node_sequence_offset: int

property node_should_prune: bool

Should this node be pruned whenever possible? Default implementation always returns false.

node_traverse(sequence, sequence_start_index=0)

Mostly internal method. Starting at node, follow the path of sequence by looking at children and their children’s children and so on.

Return type:

TraverseResult

node_visit(enter=<function default_enter>, exit=<function default_exit>, frame_class=<class 'pure_radix.VisitFrame'>)

Visit nodes recursively. Call enter(stack, frame) before recursing down a node’s children, and call exit(stack, frame) after the node and its children have all been visited.

The enter function must modify VisitFrame.children (initially an empty list) and add to it the subset of child nodes that should be visited. The helper method VisitFrame.set_children() helps. If unset, then all children will be traversed.

Both enter and exit must return an iterable. The values from this iterable will be yielded from this generator.

Example:

def _enter(stack, frame):
    frame.set_children()
    # equivalent: frame.children = list(frame.node.node_children.values())

    yield ("enter", frame.node)

def _exit(stack, frame):
    yield ("exit", frame.node)

for action, node in t.node_visit(enter=_enter, exit=_exit):
    print(action, node)

Return type:

Iterator[TypeVar(S)]

raw_data

remove(x)

update(xs)

class pure_radix.TraverseResult(sequence_index, node, node_prefix_index)

Bases: object

Attributes

sequence_index: int | None

Number of matching sequence elements. None if it’s the whole sequence.

node: Node

Node.

node_prefix_index: int | None

Number of matching elements in the Node.node_prefix. None if the entire prefix matched.

node: ANode

node_prefix_index: int | None

sequence_index: int | None

class pure_radix.VisitFrame(node, children=None, iterator=None)

Bases: Generic[T]

children: tuple[ANode[TypeVar(T, bound= Hashable)], ...] | None

iterator

node: ANode[TypeVar(T, bound= Hashable)]

set_children(filter=<function VisitFrame.<lambda>>)

Helper method to add the direct children of node to children. If the filter predicate callable is provided, then call it for each child and only keep the children for which it returns True.

pure_radix.default_enter(stack, frame)

pure_radix.default_exit(stack, frame)