GitHub

API reference for Trie.

class Trie[V = Unsubscripted]

Build one with Trie.empty(), Trie.make(*entries) or Trie.from_iterable(entries).

Functions

__init__

__init__(root=_EMPTY) -> None
ParameterTypeDescription
root_Node = _EMPTY
def __init__(self, root: _Node = _EMPTY) -> None:
    self._root = root

empty

empty() -> Trie[V]

Spelled Trie[int].empty().

Returns Trie[V]

@classmethod
def empty(cls) -> Trie[V]:
    """Spelled ``Trie[int].empty()``."""
    return Trie()

make

make[V2](*entries: tuple[str, V2] = ()) -> Trie[V2]
make(*entries: tuple[str, V] = ()) -> Trie[V]
ParameterTypeDescription
entries= ()
@overload
@classmethod
def make[V2](cls: type[Trie[Unsubscripted]], *entries: tuple[str, V2]) -> Trie[V2]: ...
@overload
@classmethod
def make(cls, *entries: tuple[str, V]) -> Trie[V]: ...
@classmethod
def make[V2](cls, *entries: tuple[str, V2]) -> Trie[V2]:
    return Trie.from_iterable(entries)

from_iterable

from_iterable[V2](entries: list[tuple[str, V2]]) -> Trie[V2]
from_iterable[V2](entries: Iterable[tuple[str, V2]]) -> Trie[V2]
from_iterable(entries: Iterable[tuple[str, V]]) -> Trie[V]

The trie of entries; a later value for a key wins.

ParameterTypeDescription
entries
@overload
@classmethod
def from_iterable[V2](
    cls: type[Trie[Unsubscripted]], entries: list[tuple[str, V2]]
) -> Trie[V2]: ...
@overload
@classmethod
def from_iterable[V2](
    cls: type[Trie[Unsubscripted]], entries: Iterable[tuple[str, V2]]
) -> Trie[V2]: ...
@overload
@classmethod
def from_iterable(cls, entries: Iterable[tuple[str, V]]) -> Trie[V]: ...
@classmethod
def from_iterable[V2](cls, entries: Iterable[tuple[str, V2]]) -> Trie[V2]:
    """The trie of ``entries``; a later value for a key wins."""
    return Trie[V2]().insert_many(entries)

is_empty

is_empty() -> bool

Returns bool

def is_empty(self) -> bool:
    return self._root.count == 0

get

get(key) -> Option[V]
ParameterTypeDescription
keystr

Returns Option[V]

def get(self, key: str) -> Option[V]:
    node = self._node(key)
    return None if node is None else Some(self._value(node))

has

has(key) -> bool
ParameterTypeDescription
keystr

Returns bool

def has(self, key: str) -> bool:
    return self._node(key) is not None

get_unsafe

get_unsafe(key) -> V

The value for key; raises KeyError without one.

ParameterTypeDescription
keystr

Returns V

def get_unsafe(self, key: str) -> V:
    """The value for ``key``; raises ``KeyError`` without one."""
    node = self._node(key)
    if node is None:
        raise KeyError("Expected trie to contain key")
    return self._value(node)

keys

keys() -> Iterator[str]

The keys in order.

Returns Iterator[str]

def keys(self) -> Iterator[str]:
    """The keys in order."""
    return (k for k, _ in self.entries())

values

values() -> Iterator[V]

The values in key order.

Returns Iterator[V]

def values(self) -> Iterator[V]:
    """The values in key order."""
    return (v for _, v in self.entries())

entries

entries() -> Iterator[tuple[str, V]]

The (key, value) pairs in key order.

Returns Iterator[tuple[str, V]]

def entries(self) -> Iterator[tuple[str, V]]:
    """The ``(key, value)`` pairs in key order."""
    return self.entries_with_prefix("")

to_entries

to_entries() -> list[tuple[str, V]]

Returns list[tuple[str, V]]

def to_entries(self) -> list[tuple[str, V]]:
    return list(self.entries())

keys_with_prefix

keys_with_prefix(prefix) -> Iterator[str]

The keys starting with prefix, in order.

ParameterTypeDescription
prefixstr

Returns Iterator[str]

def keys_with_prefix(self, prefix: str) -> Iterator[str]:
    """The keys starting with ``prefix``, in order."""
    return (k for k, _ in self.entries_with_prefix(prefix))

values_with_prefix

values_with_prefix(prefix) -> Iterator[V]
ParameterTypeDescription
prefixstr

Returns Iterator[V]

def values_with_prefix(self, prefix: str) -> Iterator[V]:
    return (v for _, v in self.entries_with_prefix(prefix))

entries_with_prefix

entries_with_prefix(prefix) -> Iterator[tuple[str, V]]
ParameterTypeDescription
prefixstr

Returns Iterator[tuple[str, V]]

def entries_with_prefix(self, prefix: str) -> Iterator[tuple[str, V]]:
    node = _descend(self._root, prefix)
    if node is None:
        return iter(())
    return _walk(node, prefix)  # pyright: ignore[reportReturnType]

to_entries_with_prefix

to_entries_with_prefix(prefix) -> list[tuple[str, V]]
ParameterTypeDescription
prefixstr

Returns list[tuple[str, V]]

def to_entries_with_prefix(self, prefix: str) -> list[tuple[str, V]]:
    return list(self.entries_with_prefix(prefix))

longest_prefix_of

longest_prefix_of(key) -> Option[tuple[str, V]]

The entry whose key is the longest one that key starts with.

ParameterTypeDescription
keystr

Returns Option[tuple[str, V]]

def longest_prefix_of(self, key: str) -> Option[tuple[str, V]]:
    """The entry whose key is the longest one that ``key`` starts with."""
    node = self._root
    found = (0, node) if node.has else None
    for end, c in enumerate(key, 1):
        child = node.children.get(c)
        if child is None:
            break
        node = child
        if node.has:
            found = (end, node)
    if found is None:
        return None
    return Some((key[: found[0]], self._value(found[1])))

reduce

reduce[Z](zero, f) -> Z

Fold the entries in key order.

ParameterTypeDescription
zeroZ
fCallable[[Z, V, str], Z]

Returns Z

def reduce[Z](self, zero: Z, f: Callable[[Z, V, str], Z]) -> Z:
    """Fold the entries in key order."""
    out = zero
    for k, v in self.entries():
        out = f(out, v, k)
    return out

for_each

for_each(f) -> None
ParameterTypeDescription
fCallable[[V, str], object]
def for_each(self, f: Callable[[V, str], object]) -> None:
    for k, v in self.entries():
        f(v, k)

insert

insert(key, value) -> Trie[V]

The trie with key set to value.

ParameterTypeDescription
keystr
valueV

Returns Trie[V]

def insert(self, key: str, value: V) -> Trie[V]:
    """The trie with ``key`` set to ``value``."""
    root, depth = self._root, 0
    node: _Node | None = root
    while depth < len(key) and node is not None:
        node = node.children.get(key[depth])
        depth += 1
    if node is not None:
        return Trie(_replace(root, key, _Node(True, value, node.children)))
    # ``key[:depth - 1]`` exists: grow the rest as a chain below it.
    leaf = _Node(True, value, {})
    for c in reversed(key[depth:]):
        leaf = _Node(False, None, {c: leaf})
    return Trie(_replace(root, key[:depth], leaf))

insert_many

insert_many(entries) -> Trie[V]
ParameterTypeDescription
entriesIterable[tuple[str, V]]

Returns Trie[V]

def insert_many(self, entries: Iterable[tuple[str, V]]) -> Trie[V]:
    out = self
    for key, value in entries:
        out = out.insert(key, value)
    return out

remove

remove(key) -> Trie[V]

The trie without key; the same trie when it has no key.

ParameterTypeDescription
keystr

Returns Trie[V]

def remove(self, key: str) -> Trie[V]:
    """The trie without ``key``; the same trie when it has no ``key``."""
    node = self._node(key)
    if node is None:
        return self
    leaf = _Node(False, None, node.children) if node.children else None
    return Trie(_replace(self._root, key, leaf))

remove_many

remove_many(keys) -> Trie[V]
ParameterTypeDescription
keysIterable[str]

Returns Trie[V]

def remove_many(self, keys: Iterable[str]) -> Trie[V]:
    out = self
    for key in keys:
        out = out.remove(key)
    return out

modify

modify(key, f) -> Trie[V]

The trie with key's value replaced by f(value); the same trie without key.

ParameterTypeDescription
keystr
fCallable[[V], V]

Returns Trie[V]

def modify(self, key: str, f: Callable[[V], V]) -> Trie[V]:
    """The trie with ``key``'s value replaced by ``f(value)``; the same
    trie without ``key``."""
    node = self._node(key)
    if node is None:
        return self
    return self.insert(key, f(self._value(node)))

map

map[A](f) -> Trie[A]
ParameterTypeDescription
fCallable[[V, str], A]

Returns Trie[A]

def map[A](self, f: Callable[[V, str], A]) -> Trie[A]:
    return self._rebuilt((k, f(v, k)) for k, v in self.entries())

filter

filter[B](predicate: Callable[[V, str], TypeIs[B]]) -> Trie[B]
filter(predicate: Callable[[V, str], bool]) -> Trie[V]
ParameterTypeDescription
predicate
@overload
def filter[B](self, predicate: Callable[[V, str], TypeIs[B]]) -> Trie[B]: ...
@overload
def filter(self, predicate: Callable[[V, str], bool]) -> Trie[V]: ...
def filter(self, predicate: Callable[[V, str], bool]) -> Trie[Any]:
    return self._rebuilt((k, v) for k, v in self.entries() if predicate(v, k))

filter_map

filter_map[A](f) -> Trie[A]

The entries f(value, key) keeps (Ok), with its values.

ParameterTypeDescription
fCallable[[V, str], Result[A, object]]

Returns Trie[A]

def filter_map[A](self, f: Callable[[V, str], Result[A, object]]) -> Trie[A]:
    """The entries ``f(value, key)`` keeps (``Ok``), with its values."""

    def kept() -> Iterator[tuple[str, A]]:
        for k, v in self.entries():
            result = f(v, k)
            if isinstance(result, Ok):
                yield k, result.value

    return self._rebuilt(kept())

compact

compact[A]() -> Trie[A]

The Some values, unwrapped.

Returns Trie[A]

def compact[A](self: Trie[Option[A]]) -> Trie[A]:
    """The ``Some`` values, unwrapped."""
    return self._rebuilt((k, v.value) for k, v in self.entries() if isinstance(v, Some))