gentrie package¶

Module contents¶

Package providing a generalized trie implementation.

This package includes classes and functions to create and manipulate a generalized trie data structure. Unlike common trie implementations that only support strings as keys, this generalized trie can handle various types of tokens, as long as they are hashable.

Warning

gentrie IS NOT thread-safe

It is not designed for concurrent use. If you need a thread-safe trie, you must use an external locking mechanism to ensure that either only read-only threads are accessing the trie at the same time or that only one write thread and no read threads are accessing the trie at the same time.

One way to do this is to create TWO instances of the trie, one for read-only access and one for write access.

The read-only instance can be used by multiple threads at the same time, while the write instance can be used by only one thread at a time. After a write operation, a new read-only instance can be created from the write instance by forking it using copy.deepcopy() which can then be used by the read-only threads.

Usage¶

You can create a trie using the GeneralizedTrie class:

from gentrie import GeneralizedTrie

# Create a new trie instance
trie = GeneralizedTrie()

There are three ways to add entries:

Using the trie[key] = value syntax

This allows you to assign a value directly to a key and will create a new TrieEntry if the key does not already exist. If the key already exists, it will update the value associated with that key.

Examples of using the trie[key] = value syntax¶

# Assigns 'value' to 'key'
# (tokenized as characters 'k','e','y')
trie['key'] = 'value'

# Assigns value 'value2' to key 'another_key' (tokenized as
# 'a','n','o','t','h','e','r','_','k','e','y','2')
trie['another_key'] = 'another_value'

# Changes the value for 'key' (tokenized as 'k', 'e', 'y')
# to 'new_value'
trie['key'] = 'new_value'

# Assigns a tuple of int (tokenized as
# 128, 96, 160, 0) as a key with the value'value5'
trie[(128, 96, 160, 0)] = 'value5'

# Assigns a tuple with mixed value types (tokenized
# as 128, 'a') as a key with the value 'value5b'
trie[(128, 'a')] = 'value5b'

# Assigns a list of words (tokenized as 'hello', 'world')
# as a key with the value 'value6'
trie[['hello', 'world']] = 'value6'

Using the trie.add(key, value) method

This method adds a new entry to the trie and returns the TrieId for the new entry. If the key already exists, it will throw an error. The value argument is optional, and if not provided the entry will be created with a value of None.
Using the trie.update(key, value) method

This method adds a new entry or updates an existing entry, returning the TrieId for the entry and returns the TrieId of the entry.

This is the same as using the trie[key] = value syntax, but it is more explicit about the intention to update or add an entry and returns the TrieId of the entry.

The value argument is optional, and if not provided, the entry will be created or updated with a value of None.

You can use the in operator to check if a key exists in the trie, e.g., if key in trie:. This will return True if the key exists, and False otherwise.

There are two ways to directly retrieve entries using their keys:

Using the trie[key | TrieId] syntax.

This retrieves the TrieEntry associated with the key or TrieId. It will raise a KeyError if the key/TrieId does not exist. It will raise a TypeError if the key is not either a valid TrieId or GeneralizedKey.

The returned TrieEntry contains the key, value, and an identifier (ident - of type TrieId) that uniquely identifies the entry in the trie.
Using the trie.get(key | TrieId, [default]) method
This retrieves the TrieEntry associated with the key or TrieId, returning None if the key/TrieId does not exist. This could be preferable in cases where you want to avoid exceptions for missing keys although it cannot distinguish between a key that does not exist and a key that exists with a None value in the trie by default.

You can provide a different default value to return if the key does not exist, which can be useful for handling cases where you want to return a specific value instead of None.

You can also retrieve all entries that are prefixed by or prefixes for a given key:

trie.prefixed_by(key) returns a Generator of TrieEntry objects that are prefixed_by of the given key.
trie.prefixes(key) returns a Generator of TrieEntry objects that are prefixes of the given key.

These methods are useful for searching and retrieving entries that match a specific pattern or structure in the trie.

Example 1 - Basic Usage¶

from gentrie import GeneralizedTrie, TrieEntry

trie = GeneralizedTrie()
trie.add(['ape', 'green', 'apple'])
trie.add(['ape', 'green'])
matches: set[TrieEntry] = set(trie.prefixes(['ape', 'green']))
print(matches)

Value of ‘matches’:

{TrieEntry(ident=2, key=['ape', 'green'], value=None)}

Example 2 - Trie of URLs¶

from gentrie import GeneralizedTrie, TrieEntry

# Create a trie to store website URLs
url_trie = GeneralizedTrie()

# Add some URLs with different components (protocol, domain, path)
url_trie.add(["https", "com", "example", "www", "/", "products", "clothing"], value="Clothing Store")
url_trie.add(["http", "org", "example", "blog", "/", "2023", "10", "best-laptops"], value="Best Laptops 2023")
url_trie.add(["ftp", "net", "example", "ftp", "/", "data", "images"], value="FTP Data Images")

# Find all https URLs with "example.com" domain
prefixed_by: set[TrieEntry] = set(url_trie.prefixed_by(["https", "com", "example"]))
print(prefixed_by)

Value of ‘prefixed_by’:

{
    TrieEntry(
        ident=1,
        key=['https', 'com', 'example', 'www', '/', 'products', 'clothing'],
        value='Clothing Store')
}

Example 3 - Entries prefixed by a key¶

from gentrie import GeneralizedTrie, TrieEntry

trie = GeneralizedTrie()
trie.add('abcdef')
trie.add('abc')
trie.add('qrf')
matches: set[TrieEntry] = set(trie.prefixed_by('ab'))
print(matches)

Value of ‘matches’:

{
    TrieEntry(ident=2, key='abc', value=None),
    TrieEntry(ident=1, key='abcdef', value=None)
}

exception gentrie.DuplicateKeyError¶

Bases: KeyError

Raised when an attempt is made to add a key that is already in the trie with a different associated value.

This is a sub-class of KeyError.

gentrie.GeneralizedKey¶

A GeneralizedKey is an object of any class that is a Sequence and that when iterated returns tokens conforming to the TrieKeyToken protocol.

Warning

Keys Must Be Immutable

Once a key is added to the trie, neither the key sequence itself nor any of its constituent tokens should be mutated. Modifying a key after it has been added can corrupt the internal state of the trie, leading to unpredictable behavior and making entries unreachable. The trie does not create a deep copy of keys for performance reasons.

If you need to modify a key, you should remove the old key and add a new one with the modified value.

Examples of valid :class:`GeneralizedKey` types

str
bytes
list[bool]
list[int]
list[bytes]
list[str]
list[Optional[str]]
tuple[int, int, str]

class gentrie.GeneralizedTrie¶

Bases: object

A general purpose trie.

Unlike many trie implementations which only support strings as keys and token match only at the character level, it is agnostic as to the types of tokens used to key it and thus far more general purpose.

It requires only that the indexed tokens be hashable. This is verified at runtime using the gentrie.TrieKeyToken protocol.

Tokens in a key do NOT have to all be the same type as long as they can be compared for equality.

It can handle a Sequence of TrieKeyToken conforming objects as keys for the trie out of the box.

You can ‘mix and match’ types of objects used as token in a key as long as they all conform to the TrieKeyToken protocol.

The code emphasizes robustness and correctness.

Warning

GOTCHA: Using User Defined Classes As Tokens In Keys

Objects of user-defined classes are conformant with the TrieKeyToken protocol by default, but this will not work as naively expected. The hash value of an object is based on its memory address by default. This results in the hash value of an object changing every time the object is created and means that the object will not be found in the trie unless you have a reference to the original object.

If you want to use a user-defined class as a token in a key to look up by value instead of the instance, you must implement the __eq__() and __hash__() dunder methods in a content aware way (the hash and eq values must depend on the content of the object).

Tip

Using `dataclasses.dataclass` For Content-Aware User Defined Classes

A simple way to implement a user-defined class that is content aware hashable is to use the dataclasses.dataclass decorator using the frozen=True and eq=True options . This will automatically implement appropriate __eq__() and __hash__() methods for you.

Example of a content-aware user-defined class¶

from dataclasses import dataclass

from gentrie import TrieKeyToken

@dataclass(frozen=True, eq=True)
class MyTokenClass:
    name: str
    value: int

# Create an instance of the token class
token = MyTokenClass(name="example", value=42)

# Check if the token is hashable
if isinstance(token, TrieKeyToken):
    print("token is usable as a TrieKeyToken")
else:
    print("token is not usable as a TrieKeyToken")

add(key: Sequence[TrieKeyToken | str], value: Any | None = None) → TrieId¶

Adds the key to the trie.

Warning

Keys Must Be Immutable

If you need to modify a key, you should remove the old key and add a new one with the modified value.

Parameters:

key (GeneralizedKey) – Must be an object that can be iterated and that when iterated returns elements conforming to the TrieKeyToken protocol.
value (Optional[Any], default=None) – Optional value to associate with the key.

Raises:

InvalidGeneralizedKeyError ([GTU001]) – If key is not a valid GeneralizedKey.
DuplicateKeyError ([GTU002]) – If the key is already in the trie.

Returns:

Id of the inserted key. If the key was not in the trie, it returns the id of the new entry. If the key was already in the trie, it raises a DuplicateKeyError.

Return type:

TrieId

clear() → None¶

Clears all keys from the trie.

Usage:

trie_obj.clear()

Returns the TrieEntry for the ident or key with the passed identifier.

The identifier can be either the TrieId (ident) or the GeneralizedKey (key) for the entry.

If the key is not found, it returns the default value if provided or None if not provided.

Example

trie = GeneralizedTrie() ident: TrieId = trie.add([‘ape’, ‘green’, ‘apple’])

entry: TrieEntry = trie.get(ident) print(entry) # Output: TrieEntry(ident=1, key=[‘ape’, ‘green’, ‘apple’], value=None)

trie[[‘ape’, ‘green’, ‘apple’]] = “A green apple” entry = trie.get([‘ape’, ‘green’, ‘apple’]) print(entry) # Output: TrieEntry(ident=1, key=[‘ape’, ‘green’, ‘apple’], value=”A green apple”)

entry = trie.get([‘non’, ‘existent’, ‘key’], default=”Not Found”) print(entry) # Output: “Not Found”

Parameters:

key (TrieId | GeneralizedKey) – the identifier to retrieve.
default (Optional[TrieEntry | Any], default=None) – The default value to return if the key is not found.

Returns: TrieEntry: TrieEntry for the key with the passed identifier or the default value if not found.

Raises:: TypeError ([GTG002]) – if the key arg is neither a TrieId or a valid GeneralizedKey.

items() → Generator[tuple[TrieId, TrieEntry], None, None]¶

Returns an iterator for the trie.

The keys are the TrieIds and the values are the TrieEntry instances.

The generator yields the TrieId and TrieEntry for each key in the trie.

Returns:: Generator for the trie.
Return type:: Generator[tuple[TrieId, TrieEntry], None, None]

keys() → Generator[TrieId, None, None]¶

Returns an iterator for all the TrieIds in the trie.

The generator yields the TrieId for each key in the trie.

It returns TrieIds instead of GeneralizedKeys because TrieIds are

Faster: Lookups using TrieIds are O(1) for time regardless of the length of the GeneralizedKey they are associated with vs O(n) to the length of keys for operations using GeneralizedKeys to look up entries.
More efficient memory usage: TrieIds are typically smaller in size compared to GeneralizedKeys, leading to reduced memory overhead when storing and processing keys in the trie.
Guaranteed stable even with key modifications: TrieIds remain consistent even if the underlying GeneralizedKey changes, making them more reliable for long-term storage and retrieval.

Returns:: Generator for the trie.
Return type:: Generator[TrieId, None, None]

prefixed_by(key: Sequence[TrieKeyToken | str], depth: int = -1) → Generator[TrieEntry, None, None]¶

Yields all entries in the trie that are prefixed by the given key, up to a specified depth.

Searches the trie for all keys that start with the provided key and yields their TrieEntry instances.

Note

The prefixed_by method finds all keys that start with the given prefix. For example, trie.prefixed_by(‘app’) will find entries for keys like ‘apple’ and ‘application’.

Warning

GOTCHA: Generators

Because generators are not executed until the first iteration, they may not behave as expected if not consumed properly. For example, exceptions will not be raised until the generator is iterated over.

Parameters:

key (GeneralizedKey) – Key for matching.
depth (int, default=-1) – Depth starting from the matched key to include. The depth determines how many ‘layers’ deeper into the trie to look for prefixed_by.: * A depth of -1 (the default) includes ALL entries for the exact match and all children nodes. * A depth of 0 only includes the entries for the exact match for the key. * A depth of 1 includes entries for the exact match and the next layer down. * A depth of 2 includes entries for the exact match and the next two layers down.

Yields:

TrieEntry – The next matching TrieEntry instance.

Raises:

InvalidGeneralizedKeyError ([GTS001]) – If key arg is not a GeneralizedKey.
TypeError ([GTS002]) – If depth arg is not an int.
ValueError ([GTS003]) – If depth arg is less than -1.
InvalidGeneralizedKeyError ([GTS004]) – If a token in the key arg does not conform to the TrieKeyToken protocol.

Usage:

from gentrie import GeneralizedTrie, TrieEntry

trie = GeneralizedTrie()
keys: list[str] = ['abcdef', 'abc', 'a', 'abcd', 'qrs']
for entry in keys:
    trie.add(entry)
matches_generator = trie.prefixed_by('abcd')

for trie_entry in sorted(list(matches_generator)):
    print(f'{trie_entry.ident}: {trie_entry.key}')

# 1: abcdef
# 4: abcd

prefixes(key: Sequence[TrieKeyToken | str]) → Generator[TrieEntry, None, None]¶

Yields TrieEntry instances for all keys in the trie that are a prefix of the passed key.

Searches the trie for all keys that are prefix matches for the key and yields their TrieEntry instances.

Note

The prefixes method finds all keys that are prefixes of the passed key. For example, trie.prefixes(‘apple’) will find entries for keys like ‘a’, ‘apple’ and ‘app’.

Warning

GOTCHA: Generators

Parameters:: key (GeneralizedKey) – Key for matching.
Yields:: TrieEntry – The next matching TrieEntry instance.
Raises:: InvalidGeneralizedKeyError ([GTM001]) – If key is not a valid GeneralizedKey (is not a Sequence of TrieKeyToken objects).

Usage:

from gentrie import GeneralizedTrie, TrieEntry

trie: GeneralizedTrie = GeneralizedTrie()
keys: list[str] = ['abcdef', 'abc', 'a', 'abcd', 'qrs']
for entry in keys:
    trie.add(entry)
matches_generator: Generator[TrieEntry, None, None] = trie.prefixes('abcd')
for trie_entry in sorted(list(matches_generator)):
    print(f'{trie_entry.ident}: {trie_entry.key}')

# 2: abc
# 3: a
# 4: abcd

remove(key: TrieId | Sequence[TrieKeyToken | str]) → None¶

Remove the specified key from the trie.

Removes the key from the trie. If the key is not found, it raises a KeyError. The key can be specified either as a TrieId or as a GeneralizedKey.

Parameters:

key (TrieId | GeneralizedKey) – identifier for key to remove.

Raises:

TypeError ([GTR001]) – if the key arg is not a TrieId or a valid GeneralizedKey.
KeyError ([GTR002]) – if the key arg does not match the id or trie key of any entries in the trie.

update(key: Sequence[TrieKeyToken | str], value: Any | None = None) → TrieId¶

Updates the key/value pair in the trie.

Warning

Keys Must Be Immutable

If you need to modify a key, you should remove the old key and add a new one with the modified value.

Parameters:

key (GeneralizedKey) – Must be an object that can be iterated and that when iterated returns elements conforming to the TrieKeyToken protocol.
value (Optional[Any], default=None) – Optional value to associate with the key.

Raises:

InvalidGeneralizedKeyError ([GTSE001]) – If key is not a valid GeneralizedKey.

Returns:

Id of the inserted key. If the key was already in the trie with the same value it returns the id for the already existing entry. If the key was not already in the trie, it returns the id for a new entry.

Return type:

TrieId

values() → Generator[TrieEntry, None, None]¶

Returns an iterator for all the TrieEntry entries in the trie.

The generator yields the TrieEntry for each key in the trie.

Returns:: Generator for the trie.
Return type:: Generator[TrieEntry, None, None]

class gentrie.Hashable(*args, **kwargs)¶

Bases: TrieKeyToken, Protocol

The Hashable protocol is deprecated and will be removed in a future version.

This protocol is a sub-class of TrieKeyToken and is only provided for backward compatibility.

Use TrieKeyToken instead.

exception gentrie.InvalidGeneralizedKeyError¶

Bases: TypeError

Raised when a key is not a valid GeneralizedKey object.

This is a sub-class of TypeError.

exception gentrie.InvalidTrieKeyTokenError¶

Bases: TypeError

Raised when a token in a key is not a valid TrieKeyToken object.

This is a sub-class of TypeError.

gentrie.TRIE_IDENT: int = 0¶: Alias for field number 0 (ident) in TrieEntry. It is faster to use this than accessing the field by name.

gentrie.TRIE_KEY: int = 1¶: Alias for field number 1 (key) in TrieEntry. It is faster to use this than accessing the field by name.

gentrie.TRIE_VALUE: int = 2¶: Alias for field number 2 (value) in TrieEntry. It is faster to use this than accessing the field by name.

class gentrie.TrieEntry(ident: TrieId, key: Sequence[TrieKeyToken | str], value: Any | None = None)¶

Bases: NamedTuple

A TrieEntry is a NamedTuple containing the unique identifer and key for an entry in the trie.

ident: TrieId¶: TrieId Unique identifier for a key in the trie. Alias for field number 0.

key: Sequence[TrieKeyToken | str]¶: GeneralizedKey Key for an entry in the trie. Alias for field number 1.

value: Any | None¶: Optional value for the entry in the trie. Alias for field number 2.

class gentrie.TrieId(value: int)¶

Bases: int

Unique identifier for a key in a trie.

class gentrie.TrieKeyToken(*args, **kwargs)¶

Bases: Protocol

TrieKeyToken is a protocol that defines key tokens that are usable with a GeneralizedTrie.

The protocol requires that a token object be hashable. This means that it implements both an __eq__() method and a __hash__() method.

Some examples of built-in types that are suitable for use as tokens in a key:

Note: frozensets and tuples are only hashable if their contents are hashable.

Usage:

from gentrie import TrieKeyToken

token = SomeTokenClass()
if isinstance(token, TrieKeyToken):
    print("supports the TrieKeyToken protocol")
else:
    print("does not support the TrieKeyToken protocol")

Warning

Using User Defined Classes As Tokens In Keys

User-defined classes are hashable by default, but you should implement the __eq__() and __hash__() dunder methods in a content-aware way (the hash and eq values must depend on the content of the object) if you want to use them as tokens in a key. The default implementation of __eq__() and __hash__() uses the memory address of the object, which means that two different instances of the same class will not be considered equal.

gentrie.is_generalizedkey(key: Sequence[TrieKeyToken | str]) → bool¶

Tests key for whether it is a valid GeneralizedKey.

A valid GeneralizedKey is a Sequence that returns TrieKeyToken protocol conformant objects when iterated. It must have at least one token.

Parameters:: key (GeneralizedKey) – Key for testing.
Returns:: True if a valid GeneralizedKey, False otherwise.
Return type:: bool

gentrie.is_hashable(token: TrieKeyToken) → bool¶

is_hashable is deprecated and will be removed in a future version.

This function is a wrapper for is_triekeytoken() and is only provided for backward compatibility.

Use is_triekeytoken() instead.

gentrie.is_triekeytoken(token: TrieKeyToken) → bool¶

Tests token for whether it is a valid TrieKeyToken.

A valid TrieKeyToken is a hashable object (implements both __eq__() and __hash__() methods).

Examples: bool, bytes, float, frozenset, int, str, None, tuple.

Parameters:: token (GeneralizedKey) – Object for testing.
Returns:: True if a valid TrieKeyToken, False otherwise.
Return type:: bool