Metadata-Version: 2.4 Name: AlgoTree Version: 3.0.0 Summary: Immutable-by-default tree manipulation library with functional programming patterns and composable transformations Home-page: https://github.com/queelius/AlgoTree Author: Alex Towell Author-email: lex@metafunctor.com Project-URL: Documentation, https://queelius.github.io/AlgoTree/ Project-URL: Source Code, https://github.com/queelius/AlgoTree Project-URL: Issue Tracker, https://github.com/queelius/AlgoTree/issues Project-URL: Changelog, https://github.com/queelius/AlgoTree/blob/main/CHANGELOG.md Keywords: tree data-structure algorithms pattern-matching transformation fluent-api Classifier: Development Status :: 4 - Beta Classifier: Intended Audience :: Developers Classifier: Topic :: Software Development :: Libraries :: Python Modules Classifier: Topic :: Software Development :: Libraries Classifier: License :: OSI Approved :: MIT License Classifier: Programming Language :: Python :: 3 Classifier: Programming Language :: Python :: 3.8 Classifier: Programming Language :: Python :: 3.9 Classifier: Programming Language :: Python :: 3.10 Classifier: Programming Language :: Python :: 3.11 Classifier: Programming Language :: Python :: 3.12 Classifier: Operating System :: OS Independent Requires-Python: >=3.8 Description-Content-Type: text/x-rst License-File: LICENSE Provides-Extra: dev Requires-Dist: sphinx; extra == "dev" Requires-Dist: sphinx-rtd-theme; extra == "dev" Requires-Dist: sphinxcontrib-napoleon; extra == "dev" Requires-Dist: coverage; extra == "dev" Requires-Dist: pytest; extra == "dev" Requires-Dist: flake8; extra == "dev" Provides-Extra: analytics Requires-Dist: pandas>=1.3.0; extra == "analytics" Requires-Dist: pyarrow>=6.0.0; extra == "analytics" Provides-Extra: jupyter Requires-Dist: ipywidgets>=7.6.0; extra == "jupyter" Requires-Dist: IPython>=7.0.0; extra == "jupyter" Dynamic: author Dynamic: author-email Dynamic: classifier Dynamic: description Dynamic: description-content-type Dynamic: home-page Dynamic: keywords Dynamic: license-file Dynamic: project-url Dynamic: provides-extra Dynamic: requires-python Dynamic: summary AlgoTree ======== .. image:: https://img.shields.io/pypi/v/AlgoTree.svg :target: https://pypi.org/project/AlgoTree/ .. image:: https://img.shields.io/pypi/l/AlgoTree.svg :target: https://pypi.org/project/AlgoTree/ .. image:: https://img.shields.io/badge/coverage-86%25-brightgreen.svg :target: https://github.com/queelius/AlgoTree A powerful, immutable-by-default tree manipulation library for Python with functional programming patterns, composable transformations, and advanced pattern matching. ⚠️ **BREAKING CHANGES in v2.0.0** ⚠️ -------------------------------------- **Version 2.0.0 is a complete redesign with NO backward compatibility.** - **Immutable-by-default API** - All operations return new trees - **Functional programming style** - map, filter, reduce, fold operations - **Composable transformations** - Selectors and transformers compose with operators - **Type-safe with full type hints** - Complete IDE support - **86% test coverage** - 197 passing tests across comprehensive test suite **Upgrading from v1.x:** The v1.x API has been completely removed. See the `Migration Guide <#migration-from-v1x>`_ below. **If you need the old API:** .. code-block:: shell pip install "AlgoTree<2.0.0" Introduction ------------ AlgoTree v2.0 provides a modern, functional approach to working with tree structures in Python. Built on immutable-by-default principles, it offers: - **Immutable trees** - Safe, predictable transformations without side effects - **Functional operations** - map, filter, reduce, fold, and more - **Pattern matching** - Powerful selectors with wildcards and composition - **Composable transformers** - Build complex pipelines with simple operators - **Multiple construction styles** - Fluent builders, DSL parsing, factory methods - **Rich export formats** - JSON, GraphViz, Mermaid, paths, and more - **Interactive shell** - Terminal-based exploration and quick operations **For Scripting & Automation:** Use the fluent Python API (recommended) **For Interactive Exploration:** Use the shell/CLI tools Installation ------------ .. code-block:: shell pip install AlgoTree Quick Start ----------- Building Trees ^^^^^^^^^^^^^^ .. code-block:: python from AlgoTree import Node, node # Simple construction with Node tree = Node("root", Node("child1", attrs={"value": 1}), Node("child2", attrs={"value": 2}) ) # Convenience function (auto-converts strings) tree = node("root", node("child1", value=1), "child2", # Strings auto-convert to nodes node("child3", "grandchild1", "grandchild2" ) ) # From paths tree = Node.from_paths([ "root/src/main.py", "root/src/utils.py", "root/docs/README.md", ]) Immutable Transformations ^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: python # All operations return new trees tree2 = tree.with_name("new_root") tree3 = tree.with_attrs(status="active") tree4 = tree.with_child(Node("new_child")) # Functional tree-wide operations doubled = tree.map(lambda n: n.with_attrs( value=n.get("value", 0) * 2 )) filtered = tree.filter(lambda n: n.get("value", 0) > 5) nodes = tree.find_all(lambda n: n.is_leaf) Composable Selectors ^^^^^^^^^^^^^^^^^^^^ .. code-block:: python from AlgoTree import name, attrs, leaf, type_ # Pattern matching with wildcards selector = name("*.txt") # Attribute matching with predicates selector = attrs(size=lambda s: s > 1000) # Logical composition with operators selector = type_("file") & ~leaf() # Structural selectors selector = type_("file").child_of(name("src")) selector = leaf().at_depth(2) # Use selectors with trees matching_nodes = list(selector.select(tree)) Composable Transformers ^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: python from AlgoTree import map_, filter_, prune, normalize, extract # Build transformation pipelines with >> operator pipeline = ( map_(lambda n: {"processed": True}) >> filter_(lambda n: n.get("active")) >> normalize(sort_children=True) >> extract(lambda n: n.name) ) # Apply to tree result = pipeline(tree) # Or use Tree's fluent API result = (Tree(tree) .map(lambda n: {"processed": True}) .filter(lambda n: n.get("active")) .prune(lambda n: n.name == "temp")) DSL Parsing ^^^^^^^^^^^ .. code-block:: python from AlgoTree import parse_tree # Visual ASCII format tree = parse_tree(""" root ├── child1 │ ├── grandchild1 │ └── grandchild2 └── child2 """) # Indented format tree = parse_tree(""" root child1 grandchild1 grandchild2 child2 """) # S-expression format tree = parse_tree("(root (child1 (grandchild1) (grandchild2)) (child2))") Export & Serialization ^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: python from AlgoTree import export_tree, save, load # Export to various formats json_str = export_tree(tree, "json") dot_str = export_tree(tree, "graphviz") mermaid_str = export_tree(tree, "mermaid") # File operations save(tree, "tree.json") loaded = load("tree.json") # Export to dictionary data = Tree(tree).to_dict() # Export to paths paths = Tree(tree).to_paths() # ['root/child1', 'root/child2', ...] Core API -------- Node (Immutable) ^^^^^^^^^^^^^^^^ The ``Node`` class is the foundation of AlgoTree v2.0. It's immutable by default, making trees safe to share and transform. **Properties:** - ``name`` - Node name (immutable) - ``attrs`` - Node attributes dictionary (returns copy) - ``children`` - Tuple of child nodes (immutable) - ``parent`` - Parent node (weak reference) - ``is_root`` - True if node has no parent - ``is_leaf`` - True if node has no children - ``depth`` - Distance from root (root has depth 0) - ``height`` - Height of subtree rooted at this node - ``size`` - Total number of nodes in subtree - ``path`` - Path from root as string (e.g., "root/child/grandchild") **Immutable transformations:** .. code-block:: python new_node = node.with_name("new_name") new_node = node.with_attrs(key="value") new_node = node.without_attrs("key1", "key2") new_node = node.with_child(Node("child")) new_node = node.with_children(Node("a"), Node("b")) new_node = node.without_child("child_name") new_node = node.map_children(lambda c: c.with_attrs(tagged=True)) new_node = node.filter_children(lambda c: c.get("active")) **Tree-wide transformations:** .. code-block:: python new_tree = node.map(lambda n: n.with_attrs(processed=True)) filtered = node.filter(lambda n: n.get("value") > 0) found = node.find(lambda n: n.name == "target") all_matches = node.find_all(lambda n: n.is_leaf) **Iteration:** .. code-block:: python for n in node.walk("preorder"): # or "postorder", "levelorder" print(n.name) for descendant in node.descendants(): print(descendant.name) for ancestor in node.ancestors(): print(ancestor.name) for leaf in node.leaves(): print(leaf.name) Tree (Wrapper) ^^^^^^^^^^^^^^ The ``Tree`` class wraps a root node and provides a consistent fluent API. **Factory methods:** .. code-block:: python tree = Tree.from_dict({ "name": "root", "value": 1, "children": [ {"name": "child1", "value": 2}, {"name": "child2", "value": 3} ] }) tree = Tree.from_paths([ "root/a/b", "root/a/c", "root/d" ]) **Functional operations:** .. code-block:: python # Map over all nodes result = tree.map(lambda n: {"processed": True}) # Filter nodes (preserves structure) result = tree.filter(lambda n: n.get("active")) # Reduce to single value total = tree.reduce( lambda acc, n: acc + n.get("value", 0), 0 ) # Fold bottom-up result = tree.fold( lambda node, child_results: sum(child_results) + 1 ) **Structure operations:** .. code-block:: python pruned = tree.prune(lambda n: n.name == "temp") grafted = tree.graft(lambda n: n.is_leaf, Node("new_child")) flattened = tree.flatten(max_depth=2) **Query operations:** .. code-block:: python node = tree.find(lambda n: n.name == "target") nodes = tree.find_all(lambda n: n.is_leaf) exists = tree.exists(lambda n: n.get("error")) count = tree.count(lambda n: n.get("active")) **Properties:** - ``root`` - Root node - ``size`` - Total number of nodes - ``height`` - Height of tree - ``leaves`` - List of all leaf nodes - ``is_empty`` - True if tree is empty Selectors ^^^^^^^^^ Selectors provide composable pattern matching for tree nodes. **Basic selectors:** .. code-block:: python from AlgoTree import name, attrs, type_, predicate, depth, leaf, root # Name matching with wildcards sel = name("*.txt") sel = name("file_*") # Attribute matching sel = attrs(type="file") sel = attrs(size=lambda s: s > 1000) # With predicate sel = attrs(type="file", active=True) # Multiple attrs # Type matching sel = type_("directory") # Custom predicate sel = predicate(lambda n: n.name.startswith("test_")) # Depth matching sel = depth(2) # Nodes at depth 2 # Leaf/root selectors sel = leaf() sel = root() **Logical composition:** .. code-block:: python # AND sel = name("*.py") & type_("file") # OR sel = name("*.py") | name("*.txt") # NOT sel = ~leaf() # XOR sel = type_("file") ^ leaf() **Structural composition:** .. code-block:: python # Child of sel = name("*.py").child_of(name("src")) # Parent of sel = type_("directory").parent_of(name("main.py")) # Descendant of sel = name("*.txt").descendant_of(name("docs")) # Ancestor of sel = type_("directory").ancestor_of(leaf()) # Sibling of sel = name("config.json").sibling_of(name("main.py")) # At specific depth sel = type_("file").at_depth(3) **Using selectors:** .. code-block:: python # Select all matching nodes for node in selector.select(tree): print(node.name) # Get first match first = selector.first(tree) # Count matches count = selector.count(tree) # Check existence exists = selector.exists(tree) Transformers ^^^^^^^^^^^^ Transformers provide composable tree transformations. **Tree -> Tree transformers:** .. code-block:: python from AlgoTree import map_, filter_, prune, graft, flatten, normalize, annotate # Map over nodes t = map_(lambda n: {"processed": True}) t = map_(lambda n: n.with_attrs(value=n.get("value", 0) * 2)) # Filter nodes t = filter_(lambda n: n.get("active")) t = filter_(name("*.txt")) # Can use selectors # Prune (remove) nodes t = prune(lambda n: n.name == "temp") t = prune(name("test_*")) # Graft (add) subtrees t = graft(leaf(), Node("new_child")) # Flatten to depth t = flatten(max_depth=2) # Normalize (sort, deduplicate) t = normalize(sort_children=True, dedup=True) # Annotate (add metadata) t = annotate(lambda n: {"depth": n.depth, "size": n.size}) **Tree -> Any transformers (shapers):** .. code-block:: python from AlgoTree import reduce_, fold, extract, to_dict, to_paths # Reduce to single value t = reduce_(lambda acc, n: acc + n.get("value", 0), initial=0) # Fold bottom-up t = fold(lambda node, child_results: sum(child_results) + 1) # Extract values t = extract(lambda n: n.name) # Convert to dictionary t = to_dict(children_key="children") # Convert to paths t = to_paths(to_leaves_only=True) **Composition:** .. code-block:: python # Sequential composition with >> pipeline = map_(fn1) >> filter_(pred) >> prune(sel) # Parallel composition with & both = map_(fn1) & annotate(fn2) # Conditional application conditional = map_(fn).when(lambda t: t.size > 10) # Repeated application repeated = normalize().repeat(3) # Debug intermediate results debug = pipeline.debug("after_filter") Tree Construction ^^^^^^^^^^^^^^^^^ AlgoTree provides several ways to construct trees (the ``builders.py`` module was removed in v2.0; use these approaches instead). **Direct construction:** .. code-block:: python from AlgoTree import Node, node tree = Node("root", attrs={"type": "container", "version": "1.0"}, *(Node(name, attrs={"type": "directory"}) for name in ("src", "tests"))) # Or with the node() convenience function my_tree = node("root", node("child1", node("grandchild1", value=1), node("grandchild2", value=2) ), node("child2", node("grandchild3", value=3) ) ) **Path-based construction:** .. code-block:: python from AlgoTree import Node tree = Node.from_paths([ "project/src/main.py", "project/src/utils.py", "project/tests/test_main.py", "project/docs/README.md", ]) **From a dict:** .. code-block:: python from AlgoTree import Node tree = Node.from_dict({ "name": "root", "type": "container", "children": [ {"name": "src", "children": [ {"name": "main.py", "type": "file", "size": 1024}, {"name": "utils.py", "type": "file", "size": 512} ]}, {"name": "tests", "children": [ {"name": "test_main.py", "type": "file"} ]} ] }) Examples -------- File System Tree ^^^^^^^^^^^^^^^^ .. code-block:: python from AlgoTree import Node, node, name, export_tree # Build file system tree fs = node("home", node("user", node("documents", type="dir", *[node("report.pdf", type="file", size=1024), node("notes.txt", type="file", size=256)] ), node("code", type="dir", *[node("main.py", type="file", size=512), node("test.py", type="file", size=128)] ) ) ) # Find all Python files py_files = fs.find_all(name("*.py")) for f in py_files: print(f.path, f.get("size")) # Calculate total size of all files total_size = fs.reduce( lambda acc, n: acc + n.get("size", 0), 0 ) print(f"Total size: {total_size} bytes") # Export to GraphViz dot = export_tree(fs, "graphviz") print(dot) Organization Hierarchy ^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: python from AlgoTree import node, attrs, map_, normalize # Build organization tree company = node("TechCorp", node("Engineering", node("Frontend", team_size=10, budget=500000), node("Backend", team_size=15, budget=750000), node("DevOps", team_size=5, budget=300000) ), node("Sales", node("Enterprise", team_size=8, budget=400000), node("SMB", team_size=12, budget=350000) ), node("Marketing", node("Digital", team_size=6, budget=250000), node("Content", team_size=4, budget=150000) ) ) # Calculate department budgets result = company.map(lambda n: { "total_budget": sum( child.get("budget", 0) for child in n.children ) if n.children else n.get("budget", 0) }) # Find high-budget teams high_budget = result.find_all( lambda n: n.get("budget", 0) > 400000 ) for team in high_budget: print(f"{team.path}: ${team.get('budget'):,}") Data Processing Pipeline ^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: python from AlgoTree import Tree, map_, filter_, normalize, extract # Create data tree data = Tree.from_dict({ "name": "dataset", "children": [ {"name": "record_1", "value": 10, "valid": True}, {"name": "record_2", "value": 5, "valid": False}, {"name": "record_3", "value": 15, "valid": True}, {"name": "record_4", "value": 8, "valid": True}, ] }) # Build processing pipeline pipeline = ( filter_(lambda n: n.get("valid", False)) >> map_(lambda n: {"value": n.get("value", 0) * 2}) >> normalize(sort_children=True) >> extract(lambda n: n.get("value")) ) # Process data result = pipeline(data) print("Processed values:", result) When to Use Python API vs Shell -------------------------------- AlgoTree provides two interfaces for different use cases: **Use the Python API (Recommended for Scripting):** .. code-block:: python from AlgoTree import Node, Tree, node from AlgoTree.transformers import map_, filter_, prune # Fluent, composable, type-safe tree = Tree(node('root', node('child1', value=1), node('child2', value=2) )) # Powerful transformations with full Python result = tree.map(lambda n: n.with_attrs(doubled=n.get('value', 0) * 2)) filtered = tree.filter(lambda n: n.get('value', 0) > 1) # Integration with Python ecosystem import pandas as pd df = pd.DataFrame([{'name': n.name, 'value': n.get('value')} for n in tree.root.descendants()]) **Use the Shell/CLI (For Interactive Exploration):** .. code-block:: bash # Quick exploration algotree shell tree.json # In the shell: > cd root > ls > find "child.*" > select "n.get('value', 0) > 1" > tree # One-off terminal operations algotree tree tree.json algotree select 'n.depth > 2' tree.json **Decision Matrix:** ===================== ==================== ================== Use Case Python API Shell/CLI ===================== ==================== ================== Automation **Recommended** Not ideal Scripts/Programs **Recommended** Not ideal Complex logic **Recommended** Not ideal Type safety **Recommended** No type checking IDE support **Recommended** N/A Testing **Recommended** Limited Integration **Recommended** Limited Quick exploration Possible **Recommended** Terminal workflows Possible **Recommended** Learning structure Possible **Recommended** Human interaction Possible **Recommended** ===================== ==================== ================== **Example: Automation with Python API** .. code-block:: python # Production-ready script from AlgoTree import Tree, map_, filter_, save # Load, transform, save tree = Tree.from_dict(load_data()) processed = tree.filter(validate).map(enrich).prune(cleanup) save(processed.root, 'output.json') # Full error handling, logging, etc. **Example: Quick Exploration with Shell** .. code-block:: bash # Quick terminal session $ algotree shell data.json > tree > cd interesting_node > stat > find "pattern.*" > exit Migration from v1.x ------------------- AlgoTree v2.0 is a complete redesign. Here's how to migrate: **Old v1.x API:** .. code-block:: python # v1.x - mutable operations (no longer works in v2.0+) # TreeBuilder, FlatForest, FlatForestNode, TreeNode are all removed. **New v2.0 API:** .. code-block:: python from AlgoTree import node, Node, Tree # v2.0 - functional construction tree = node("company", node("engineering", node("frontend"), node("backend") ), node("sales") ) # Immutable operations tree2 = tree.with_child(Node("marketing")) **Key changes:** 1. **TreeBuilder removed** - use ``node()``, ``Node()``, ``Node.from_dict()``, ``Node.from_paths()``, or ``parse_tree()`` 2. **All operations are immutable** - return new trees instead of mutating 3. **Node is immutable** - use ``.with_*()`` methods instead of property setters 4. **No FlatForest, FlatForestNode, TreeNode** - removed entirely 5. **Tree wrapper** provides functional API (map, filter, reduce, fold) 6. **Selectors** replace string-based pattern matching 7. **Transformers** provide composable pipelines Advanced Features ----------------- Lazy Evaluation ^^^^^^^^^^^^^^^ Transformers support lazy evaluation for large trees: .. code-block:: python # Create lazy pipeline pipeline = map_(expensive_fn) >> filter_(predicate) # Only evaluated when called result = pipeline(tree) Structural Sharing ^^^^^^^^^^^^^^^^^^ Immutable operations use structural sharing for efficiency: .. code-block:: python tree1 = Node("root", Node("a"), Node("b")) tree2 = tree1.with_child(Node("c")) # tree1 and tree2 share "a" and "b" nodes # Only "c" and new root are created Custom Selectors ^^^^^^^^^^^^^^^^ Create custom selectors by subclassing: .. code-block:: python from AlgoTree import Selector class ExtensionSelector(Selector): def __init__(self, ext): self.ext = ext def matches(self, node): return node.name.endswith(self.ext) # Use it py_files = ExtensionSelector(".py") for node in py_files.select(tree): print(node.name) Custom Transformers ^^^^^^^^^^^^^^^^^^^ Create custom transformers: .. code-block:: python from AlgoTree import TreeTransformer class CapitalizeNames(TreeTransformer): def __call__(self, tree): return tree.map(lambda n: n.with_name(n.name.upper())) # Use it uppercase_tree = CapitalizeNames()(tree) # Or compose it pipeline = CapitalizeNames() >> normalize() Testing ------- AlgoTree v2.0 has 86% test coverage with 197 passing tests: .. code-block:: shell # Run tests python -m pytest # Run with coverage python -m pytest --cov=AlgoTree --cov-report=html # Run specific test python -m pytest test/test_node.py::TestNode::test_immutability Contributing ------------ Contributions are welcome! Please: 1. Fork the repository 2. Create a feature branch 3. Add tests for new functionality 4. Ensure all tests pass 5. Submit a pull request License ------- MIT License - see LICENSE file for details. Links ----- - **Documentation:** https://queelius.github.io/AlgoTree/ - **Source Code:** https://github.com/queelius/AlgoTree - **Issue Tracker:** https://github.com/queelius/AlgoTree/issues - **PyPI:** https://pypi.org/project/AlgoTree/ - **Changelog:** https://github.com/queelius/AlgoTree/blob/master/CHANGELOG.md