# TinyTrie
A minimal and type-safe trie (prefix tree) implementation for Python 2+.
## Features
- **Typed**: Works with arbitrary key and value types (`Generic[K, V]`)
- **Minimal**: Only essential functionalities
- **Efficient**: Memory-efficient with `__slots__`
- **Iterable**: Easily traverse and list all stored sequences
- **No external dependencies** (except `typing` on Python <3.5)
## Basic Operations
```python
from tinytrie import *
# Create a trie with character (`str`) keys and integer values
root = TrieNode[str, int]()
# Insert some words with values
update(root, 'apple', 1)
update(root, 'app', 2)
update(root, 'banana', 3)
update(root, 'band', 4)
# Search for existing words
assert search(root, 'apple').value == 1
assert search(root, 'app').value == 2
assert search(root, 'banana').value == 3
# Search for non-existent words
assert search(root, 'orange') is None
assert search(root, 'appetizer') is None
update(root, 'apple', 10)
assert search(root, 'apple').value == 10 # Value updated
# Insert a new word
update(root, 'orange', 5)
assert search(root, 'orange').value == 5
# Delete 'apple', 'app' remains
assert delete(root, 'apple') is True
assert search(root, 'apple') is None
assert delete(root, 'apple') is False
assert search(root, 'app') is not None
# Add back 'apple', delete 'app', 'apple' remains
update(root, 'apple', 10)
assert delete(root, 'app') is True
assert search(root, 'app') is None
assert delete(root, 'app') is False
assert search(root, 'apple') is not None
# Try to delete non-existent words
assert delete(root, 'ban') is False
assert delete(root, 'appetizer') is False
# Get common prefix from root (no common prefix)
prefix, _ = longest_common_prefix(root)
assert prefix == [] # No common prefix among all words
# Get common prefix from 'b' subtrie
subtrie_prefix = ['b']
b_subtrie_root = get_subtrie_root(root, subtrie_prefix)
prefix, _ = longest_common_prefix(b_subtrie_root)
assert prefix == ['a', 'n'] # Common between 'banana' and 'band' after 'b'
# Get all words in the trie
words = {''.join(s) for s, _ in collect_sequences(root)}
assert words == {'apple', 'banana', 'band', 'orange'}
# Get all words in the 'ba' subtrie
subtrie_prefix = ['b', 'a']
ba_subtrie_root = get_subtrie_root(root, subtrie_prefix)
words_starting_with_ba = {''.join(s) for s, _ in collect_sequences(ba_subtrie_root, prefix=subtrie_prefix)}
assert words_starting_with_ba == {'banana', 'band'}
```
## Non-String Keys Example
```python
from tinytrie import *
# Create a trie with tuple keys
trajectory_trie = TrieNode[Tuple[int, int], str]()
update(trajectory_trie, [(1, 2), (3, 4)], 'traj1')
update(trajectory_trie, [(1, 2), (5, 6)], 'traj2')
assert search(trajectory_trie, [(1, 2), (3, 4)]).value == 'traj1'
assert search(trajectory_trie, [(1, 2), (5, 6)]).value == 'traj2'
assert search(trajectory_trie, [(1, 2)]) is None # Partial path
prefix, _ = longest_common_prefix(trajectory_trie)
assert prefix == [(1, 2)]
```
## API Reference
| Function | Purpose | Time Complexity |
|-------------------------------------------------------------------------------------------------------------------------| --- | --- |
| `traverse(root: TrieNode[K, V], path: Iterable[K]) -> Iterator[Tuple[Optional[TrieNode[K, V]], K]]` | Yields nodes and keys along a path of keys (even if it diverges) | O(n) |
| `get_subtrie_root(root: TrieNode[K, V], path: Iterable[K]) -> Optional[TrieNode[K, V]]` | Gets the root node of a subtrie at the end of a path of keys if it exists | O(n) |
| `search(root: TrieNode[K, V], sequence: Iterable[K]) -> Optional[TrieNode[K, V]]` | Returns terminal node if sequence is stored in the trie | O(n) |
| `update(root: TrieNode[K, V], sequence: Iterable[K], value: Optional[V] = None) -> TrieNode[K, V]` | Inserts or updates a sequence and sets its value | O(n) |
| `delete(root: TrieNode[K, V], sequence: Sequence[K]) -> bool` | Removes a sequence and prunes dead nodes | O(n) |
| `longest_common_prefix(root: TrieNode[K, V]) -> Tuple[Sequence[K], TrieNode[K, V]]` | Finds the longest common prefix of all sequences and its terminal node | O(m) |
| `collect_sequences(root: TrieNode[K, V], prefix: Optional[List[K]] = None) -> Iterator[Tuple[List[K], TrieNode[K, V]]]` | Yields all stored sequences and their terminal nodes | O(n) per sequence |
## Contributing
Contributions are welcome! Please submit pull requests or open issues on the GitHub repository.
## License
This project is licensed under the [MIT License](LICENSE).
Raw data
{
"_id": null,
"home_page": null,
"name": "tinytrie",
"maintainer": null,
"docs_url": null,
"requires_python": ">=2",
"maintainer_email": null,
"keywords": "trie, prefix tree, data structure, python",
"author": null,
"author_email": "Jifeng Wu <jifengwu2k@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/ba/73/cffed2b469bab274d00eb1f2edd4be969cd7555ceb0df786ed9ec0a6ae77/tinytrie-0.1.0a5.tar.gz",
"platform": null,
"description": "# TinyTrie\n\nA minimal and type-safe trie (prefix tree) implementation for Python 2+.\n\n## Features\n\n- **Typed**: Works with arbitrary key and value types (`Generic[K, V]`)\n- **Minimal**: Only essential functionalities\n- **Efficient**: Memory-efficient with `__slots__`\n- **Iterable**: Easily traverse and list all stored sequences\n- **No external dependencies** (except `typing` on Python <3.5)\n\n## Basic Operations\n\n```python \nfrom tinytrie import *\n\n# Create a trie with character (`str`) keys and integer values\nroot = TrieNode[str, int]()\n\n# Insert some words with values\nupdate(root, 'apple', 1)\nupdate(root, 'app', 2)\nupdate(root, 'banana', 3)\nupdate(root, 'band', 4)\n\n# Search for existing words\nassert search(root, 'apple').value == 1\nassert search(root, 'app').value == 2\nassert search(root, 'banana').value == 3\n\n# Search for non-existent words\nassert search(root, 'orange') is None\nassert search(root, 'appetizer') is None\n\nupdate(root, 'apple', 10)\nassert search(root, 'apple').value == 10 # Value updated\n\n# Insert a new word\nupdate(root, 'orange', 5)\nassert search(root, 'orange').value == 5\n\n# Delete 'apple', 'app' remains\nassert delete(root, 'apple') is True\nassert search(root, 'apple') is None\nassert delete(root, 'apple') is False\nassert search(root, 'app') is not None\n\n# Add back 'apple', delete 'app', 'apple' remains\nupdate(root, 'apple', 10)\nassert delete(root, 'app') is True\nassert search(root, 'app') is None\nassert delete(root, 'app') is False\nassert search(root, 'apple') is not None\n\n# Try to delete non-existent words\nassert delete(root, 'ban') is False\nassert delete(root, 'appetizer') is False\n\n# Get common prefix from root (no common prefix)\nprefix, _ = longest_common_prefix(root)\nassert prefix == [] # No common prefix among all words\n\n# Get common prefix from 'b' subtrie\nsubtrie_prefix = ['b']\nb_subtrie_root = get_subtrie_root(root, subtrie_prefix)\nprefix, _ = longest_common_prefix(b_subtrie_root)\nassert prefix == ['a', 'n'] # Common between 'banana' and 'band' after 'b'\n\n# Get all words in the trie\nwords = {''.join(s) for s, _ in collect_sequences(root)}\nassert words == {'apple', 'banana', 'band', 'orange'}\n\n# Get all words in the 'ba' subtrie\nsubtrie_prefix = ['b', 'a']\nba_subtrie_root = get_subtrie_root(root, subtrie_prefix)\nwords_starting_with_ba = {''.join(s) for s, _ in collect_sequences(ba_subtrie_root, prefix=subtrie_prefix)}\nassert words_starting_with_ba == {'banana', 'band'}\n```\n\n## Non-String Keys Example\n\n```python\nfrom tinytrie import *\n\n# Create a trie with tuple keys\ntrajectory_trie = TrieNode[Tuple[int, int], str]()\nupdate(trajectory_trie, [(1, 2), (3, 4)], 'traj1')\nupdate(trajectory_trie, [(1, 2), (5, 6)], 'traj2')\n\nassert search(trajectory_trie, [(1, 2), (3, 4)]).value == 'traj1'\nassert search(trajectory_trie, [(1, 2), (5, 6)]).value == 'traj2'\nassert search(trajectory_trie, [(1, 2)]) is None # Partial path\n\nprefix, _ = longest_common_prefix(trajectory_trie)\nassert prefix == [(1, 2)]\n```\n\n## API Reference\n\n| Function | Purpose | Time Complexity |\n|-------------------------------------------------------------------------------------------------------------------------| --- | --- |\n| `traverse(root: TrieNode[K, V], path: Iterable[K]) -> Iterator[Tuple[Optional[TrieNode[K, V]], K]]` | Yields nodes and keys along a path of keys (even if it diverges) | O(n) |\n| `get_subtrie_root(root: TrieNode[K, V], path: Iterable[K]) -> Optional[TrieNode[K, V]]` | Gets the root node of a subtrie at the end of a path of keys if it exists | O(n) |\n| `search(root: TrieNode[K, V], sequence: Iterable[K]) -> Optional[TrieNode[K, V]]` | Returns terminal node if sequence is stored in the trie | O(n) |\n| `update(root: TrieNode[K, V], sequence: Iterable[K], value: Optional[V] = None) -> TrieNode[K, V]` | Inserts or updates a sequence and sets its value | O(n) |\n| `delete(root: TrieNode[K, V], sequence: Sequence[K]) -> bool` | Removes a sequence and prunes dead nodes | O(n) |\n| `longest_common_prefix(root: TrieNode[K, V]) -> Tuple[Sequence[K], TrieNode[K, V]]` | Finds the longest common prefix of all sequences and its terminal node | O(m) |\n| `collect_sequences(root: TrieNode[K, V], prefix: Optional[List[K]] = None) -> Iterator[Tuple[List[K], TrieNode[K, V]]]` | Yields all stored sequences and their terminal nodes | O(n) per sequence |\n\n## Contributing\n\nContributions are welcome! Please submit pull requests or open issues on the GitHub repository.\n\n## License\n\nThis project is licensed under the [MIT License](LICENSE).\n",
"bugtrack_url": null,
"license": null,
"summary": "A minimal type-safe trie (prefix tree) implementation in Python.",
"version": "0.1.0a5",
"project_urls": {
"Bug Tracker": "https://github.com/jifengwu2k/tinytrie/issues",
"Homepage": "https://github.com/jifengwu2k/tinytrie"
},
"split_keywords": [
"trie",
" prefix tree",
" data structure",
" python"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "dd0399386a513f74d1d177ff347a14f65a67fe3672338f6c061b9dc13ff34c70",
"md5": "1b5009e464a1b6e9daa68c0ca52f65c0",
"sha256": "4fc10356d67ad6f41e9080630959057fbeec048dcfc61ae6e83232931007561b"
},
"downloads": -1,
"filename": "tinytrie-0.1.0a5-py2.py3-none-any.whl",
"has_sig": false,
"md5_digest": "1b5009e464a1b6e9daa68c0ca52f65c0",
"packagetype": "bdist_wheel",
"python_version": "py2.py3",
"requires_python": ">=2",
"size": 6004,
"upload_time": "2025-07-23T15:22:57",
"upload_time_iso_8601": "2025-07-23T15:22:57.892272Z",
"url": "https://files.pythonhosted.org/packages/dd/03/99386a513f74d1d177ff347a14f65a67fe3672338f6c061b9dc13ff34c70/tinytrie-0.1.0a5-py2.py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "ba73cffed2b469bab274d00eb1f2edd4be969cd7555ceb0df786ed9ec0a6ae77",
"md5": "387f083b64de656e80b59dfd0a88e90a",
"sha256": "cfe68c4286f41baf0e7fb0758b352b638e90acccd2235a4f824ca1747eac5b41"
},
"downloads": -1,
"filename": "tinytrie-0.1.0a5.tar.gz",
"has_sig": false,
"md5_digest": "387f083b64de656e80b59dfd0a88e90a",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=2",
"size": 5652,
"upload_time": "2025-07-23T15:22:59",
"upload_time_iso_8601": "2025-07-23T15:22:59.304864Z",
"url": "https://files.pythonhosted.org/packages/ba/73/cffed2b469bab274d00eb1f2edd4be969cd7555ceb0df786ed9ec0a6ae77/tinytrie-0.1.0a5.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-07-23 15:22:59",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "jifengwu2k",
"github_project": "tinytrie",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [
{
"name": "typing",
"specs": []
}
],
"lcname": "tinytrie"
}
JSON
