vcti-tree

Tree protocols and generic algorithms for the vcti ecosystem. Zero-dependency abstractions; pluggable backings.

Overview

vcti-tree defines what a tree is in the vcti ecosystem: three Protocols (ReadOnlyTree, MutableTree, LockableTree) parameterized in payload type T and handle type H, plus generic algorithms — DFS and BFS walks, ancestor/depth/path queries, locking guards — written against those Protocols. The Protocols specify semantics (what a tree must support); they do not prescribe storage. Any backing — numpy-array, pointer-based, dict-based — that satisfies the Protocols gets the algorithms for free. The package has no numpy or other heavy dependency; it is a pure-Python abstraction layer that downstream tree packages depend on.

Why this exists

Tree code in the Python ecosystem typically bundles storage, mutation, and traversal into a single class — every new tree implementation re-implements its own walker, its own navigation helpers, its own delete semantics. This package brings across a pattern that's well-established in C++: a small abstract interface defining what a tree is, multiple concrete implementations choosing their own storage, and generic algorithms written once against the interface and reused across every backing. The result is that adding a new tree implementation (numpy-backed, pointer-backed, persistent, …) doesn't mean rewriting walkers and guards — it means satisfying three small Protocols and inheriting the entire algorithm library. See docs/design.md for the full background and the design decisions.

Installation

pip install vcti-tree

In requirements.txt

vcti-tree>=2.1.0

In pyproject.toml dependencies

dependencies = [
    "vcti-tree>=2.1.0",
]

Quick Start

The protocols and algorithms are the API; you bring (or import) a backing. DictTree is the bundled dict-backed reference implementation — enough to build a tree and run the generic algorithms against it:

from vcti.tree.core import DictTree, dfs_preorder, ancestors, depth

tree = DictTree[str]("root")            # every tree has a root from the start
a = tree.create_child(tree.root_handle, "a")
b = tree.create_child(tree.root_handle, "b")
tree.create_child(a, "a1")

# Generic walks/queries work against any tree that satisfies the protocols.
print([tree.payload(h) for h in dfs_preorder(tree)])   # ['root', 'a', 'a1', 'b']
print([tree.payload(h) for h in ancestors(tree, a)])   # ['root']
print(depth(tree, a))                                  # 1

The protocols (ReadOnlyTree, MutableTree, LockableTree) and the rest of the algorithm set are importable from the same package root:

from vcti.tree.core import ReadOnlyTree, MutableTree, LockableTree
from vcti.tree.core import dfs_preorder, dfs_postorder, bfs
from vcti.tree.core import ancestors, depth, path, descendants

Dependencies

None. Standard library only.