system.indexes.radix_trie module

Radix trie (compressed prefix tree) index implementation with pluggable key mapping.

class system.indexes.radix_trie.KeyMapping

Bases: ABC, Generic

Maps a key to a value

abstractmethod map(key: Key, level: int, descriptor: Descriptor = None) → int

Maps the given key to a bucket at the given level.

Parameters:

• key – The key to map.

• level – The level of the mapping.

• descriptor – The optional descriptor to use for the mapping.

Returns:

The bucket index from 0 to max_buckets of an inner_node - 1.

class system.indexes.radix_trie.RadixTrie(key_mapping: KeyMapping[Key, Value], children_per_inner_node: int, inner_node_factory: RadixTrie.InnerNodeFactory[Key, Value] = <system.indexes.radix_trie.RadixTrie.InnerNodeFactory object>, leaf_factory: RadixTrie.LeafFactory[Key, Value] = <system.indexes.radix_trie.RadixTrie.LeafFactory object>, descriptor: Descriptor = None, number_of_inner_node_levels: int = 0)

Bases: KeyValueStore, Drawable, Generic

A simple implementation of a radix trie data structure.

class AbstractNode

Bases: KeyValueStore, Drawable, ABC

Abstract node of a radix trie. A node is itself a valid key-value store: it is either an inner node that routes keys to children by radix, or a leaf node that stores the key-value pairs.

get(key: Key, level: int = 0) → Iterator[Value]

See PointQueryMixIn.get().

The extra level parameter is the current depth of this node in the trie. Overridden by concrete node types.

put(key: Key, value: Value, level: int = 0) → None | PutInfo

See Index.put().

The extra level parameter is the current depth of this node in the trie. Overridden by concrete node types.

size() → int

See Index.size().

flush(key: Key | None = None) → None

See Index.flush().

Not supported for trie nodes: always raises NotImplementedError.

delete(key: Key, value: Value = None) → None

See Index.delete().

Not supported for trie nodes: always raises NotImplementedError.

show(indent: str = '') → None

See Index.show().

The indent parameter is a prefix prepended to every printed line for nesting. Overridden by concrete node types.

draw(canvas: Canvas, canvas_height: int = 0, x_offset: int = 0, y_offset: int = 0)

Draw this instance on the given canvas.

class InnerNode(key_mapping: KeyMapping[Key, Value] = None, parent_descriptor: Descriptor = None)

Bases: AbstractNode, Generic

Inner node of a radix trie. Holds a list of children and routes each key to the matching child by computing its radix (either via the key mapping or via the child descriptors).

show(indent: str = '') → None

See Index.show().

Prints this inner node and recurses into every child, indenting each level further.

draw(canvas: Canvas, canvas_height: int = 0, x_offset: int = 0, y_offset: int = 0)

Draw this instance on the given canvas.

get(key: Key, level: int = 0) → Iterator[Value]

See PointQueryMixIn.get().

Computes the radix for the key at this level and delegates the lookup to the matching child at the next level.

put(key: Key, value: Value, level: int = 0) → None | PutInfo

See Index.put().

Computes the radix for the key at this level and delegates the insertion to the matching child at the next level.

class LeafNode(parent_descriptor: Descriptor = None, left_sibling: RadixTrie.LeafNode[Key, Value] | None = None)

Bases: AbstractNode, Generic

Leaf node of a radix trie. Stores the key-value pairs and is chained to its left sibling so that all leaves form a sequence for ISAM-style scanning.

show(indent: str = '') → None

See Index.show().

Prints the key/value pairs stored in this leaf.

draw(canvas: Canvas, canvas_height: int = 0, x_offset: int = 0, y_offset: int = 0)

Draw this instance on the given canvas. This only works if the key is of type Drawable.

put(key: Key, value: Value, level: int = 0) → None | PutInfo

See Index.put().

Appends the (key, value) pair to this leaf and increments its element count; duplicates are kept.

get(key: Key, level: int = 0) → Iterator[Value]

See PointQueryMixIn.get().

Scans this leaf and yields the value of every stored pair whose key equals the search key.

class InnerNodeFactory

Bases: Generic

A factory that creates new RadixTrie.InnerNode instances.

new_instance(key_mapping: KeyMapping[Key, Value] = None, new_descriptor: Descriptor = None) → RadixTrie.InnerNode[Key, Value]

Creates and returns a new RadixTrie.InnerNode.

Parameters:

• key_mapping – the key mapping to pass to the new inner node.

• new_descriptor – the descriptor of the region covered by the new inner node.

Returns:

the newly created inner node.

class LeafFactory

Bases: Generic

A factory that creates new RadixTrie.LeafNode instances.

new_instance(parent_descriptor, previous_leaf) → RadixTrie.LeafNode[Key, Value]

Creates and returns a new RadixTrie.LeafNode.

Parameters:

• parent_descriptor – the descriptor of the region covered by the new leaf.

• previous_leaf – the leaf to the left of the new leaf, used to chain leaves for ISAM.

Returns:

the newly created leaf node.

number_of_nodes() → int

Returns the total number of nodes (inner nodes and leaves) in the trie.

Returns:

the number of nodes in the trie.

get(key: Key) → Iterator[Value]

See PointQueryMixIn.get().

put(key: Key, value: Value) → None | PutInfo

See Index.put().

size() → int

See Index.size().

delete(key: Key, value: Value = None) → None

See Index.delete().

Not implemented yet: always raises NotImplementedError.

flush(key: Key | None = None) → None

See Index.flush().

Not supported: always raises NotImplementedError.

show() → None

See Index.show().

draw(canvas: Canvas, canvas_height: int = 0, x_offset: int = 0, y_offset: int = 0)

Draw the radix trie on the given canvas.