class Trie[V = Unsubscripted]
Build one with Trie.empty(), Trie.make(*entries) or
Trie.from_iterable(entries).
Functions#
__init__#
__init__(root=_EMPTY) -> None| Parameter | Type | Description |
|---|---|---|
root | _Node = _EMPTY |
def __init__(self, root: _Node = _EMPTY) -> None:
self._root = rootempty#
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]| Parameter | Type | Description |
|---|---|---|
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.
| Parameter | Type | Description |
|---|---|---|
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() -> boolReturns bool
def is_empty(self) -> bool:
return self._root.count == 0get#
get(key) -> Option[V]| Parameter | Type | Description |
|---|---|---|
key | str |
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| Parameter | Type | Description |
|---|---|---|
key | str |
Returns bool
def has(self, key: str) -> bool:
return self._node(key) is not Noneget_unsafe#
get_unsafe(key) -> VThe value for key; raises KeyError without one.
| Parameter | Type | Description |
|---|---|---|
key | str |
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.
| Parameter | Type | Description |
|---|---|---|
prefix | str |
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]| Parameter | Type | Description |
|---|---|---|
prefix | str |
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]]| Parameter | Type | Description |
|---|---|---|
prefix | str |
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]]| Parameter | Type | Description |
|---|---|---|
prefix | str |
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.
| Parameter | Type | Description |
|---|---|---|
key | str |
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) -> ZFold the entries in key order.
| Parameter | Type | Description |
|---|---|---|
zero | Z | |
f | Callable[[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 outfor_each#
for_each(f) -> None| Parameter | Type | Description |
|---|---|---|
f | Callable[[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.
| Parameter | Type | Description |
|---|---|---|
key | str | |
value | V |
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]| Parameter | Type | Description |
|---|---|---|
entries | Iterable[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 outremove#
remove(key) -> Trie[V]The trie without key; the same trie when it has no key.
| Parameter | Type | Description |
|---|---|---|
key | str |
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]| Parameter | Type | Description |
|---|---|---|
keys | Iterable[str] |
Returns Trie[V]
def remove_many(self, keys: Iterable[str]) -> Trie[V]:
out = self
for key in keys:
out = out.remove(key)
return outmodify#
modify(key, f) -> Trie[V]The trie with key's value replaced by f(value); the same
trie without key.
| Parameter | Type | Description |
|---|---|---|
key | str | |
f | Callable[[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]| Parameter | Type | Description |
|---|---|---|
f | Callable[[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]| Parameter | Type | Description |
|---|---|---|
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.
| Parameter | Type | Description |
|---|---|---|
f | Callable[[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))