Struct ConstTree 

pub struct ConstTree<T> { /* private fields */ }

A persistent, immutable tree structure.

ConstTree is a handle to a tree node. Cloning a ConstTree is a cheap, constant-time operation as it only increments a reference count.

All modification methods (with_value, add_child, etc.) are non-destructive. They return a new ConstTree representing the modified version, leaving the original unchanged and sharing as much memory as possible.

Implementations

impl<T> ConstTree<T>

pub fn value(&self) -> &T

Returns a reference to the value stored at the root of the tree.

pub fn children(&self) -> &[ConstTree<T>]

Returns a slice containing the children of the root node.

pub fn ptr_eq(&self, other: &Self) -> bool

Checks if two ConstTree handles point to the same underlying Arc allocation.

This is the most efficient way to check for equality, but it only returns true if the two handles were created from the same original tree or via clone().

Examples

use deep_causality_ast::ConstTree;
let tree1 = ConstTree::new(1);
let tree2 = ConstTree::new(1); // Same value, different allocation
let tree1_clone = tree1.clone();

assert!(tree1.ptr_eq(&tree1_clone));
assert!(!tree1.ptr_eq(&tree2));

pub fn get_child(&self, index: usize) -> Option<&ConstTree<T>>

Returns a specific child by its index.

Returns

An Option containing a reference to the child ConstTree, or None if the index is out of bounds.

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(0, vec![ConstTree::new(1), ConstTree::new(2)]);
assert_eq!(*tree.get_child(0).unwrap().value(), 1);
assert!(tree.get_child(2).is_none());

pub fn get_id(&self) -> usize

Returns a unique identifier for the node pointed to by this ConstTree.

The ID is the memory address of the underlying Arc’s allocation.

pub fn is_leaf(&self) -> bool

Checks if the tree is a leaf node (i.e., has no children).

pub fn size(&self) -> usize

Returns the total number of nodes in the tree (including the root).

Complexity

This is an O(n) operation as it traverses the entire tree.

pub fn depth(&self) -> usize

Returns the maximum depth of the tree.

A leaf node has a depth of 1.

Complexity

This is an O(n) iterative operation that is robust against stack overflows for very deep trees.

pub fn find<P>(&self, predicate: P) -> Option<&ConstTree<T>>

where P: Fn(&T) -> bool,

Finds the first node that satisfies a predicate in pre-order traversal.

Arguments

• predicate: A closure that takes a reference to a value and returns true for the node being sought.

Returns

An Option containing a reference to the found ConstTree, or None.

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(10, vec![ConstTree::from(20), ConstTree::from(30)]);
let found_node = tree.find(|v| *v > 25).unwrap();
assert_eq!(*found_node.value(), 30);

pub fn find_all<P>(&self, predicate: P) -> impl Iterator<Item = &ConstTree<T>>

where P: Fn(&T) -> bool,

Returns an iterator over all nodes that satisfy a predicate in pre-order traversal.

Arguments

• predicate: A closure that takes a reference to a value and returns true for the nodes to be included in the iterator.

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(10, vec![ConstTree::new(20), ConstTree::new(30)]);
let results: Vec<_> = tree.find_all(|v| *v > 15).map(|n| *n.value()).collect();
assert_eq!(results, vec![20, 30]);

impl<T: Clone> ConstTree<T>

pub fn add_child(&self, child: ConstTree<T>) -> Self

Returns a new ConstTree with an additional child appended to the end of the children list.

This is a non-destructive operation. The original ConstTree is not modified.

Examples

use deep_causality_ast::ConstTree;
let original = ConstTree::new(1);
let with_child = original.add_child(ConstTree::new(2));

assert!(original.is_leaf());
assert_eq!(with_child.children().len(), 1);

pub fn replace_children( &self, new_children: impl IntoIterator<Item = Self>, ) -> Self

Returns a new ConstTree with the children replaced by a new set.

This is a non-destructive operation. The original ConstTree is not modified.

Examples

use deep_causality_ast::ConstTree;
let original = ConstTree::with_children(1, vec![ConstTree::new(2)]);
let replaced = original.replace_children(vec![ConstTree::new(3), ConstTree::new(4)]);

assert_eq!(original.children().len(), 1);
assert_eq!(replaced.children().len(), 2);
assert_eq!(*replaced.children()[0].value(), 3);

pub fn update_child( &self, index: usize, new_child: ConstTree<T>, ) -> Option<Self>

Returns a new ConstTree with the child at the specified index updated.

This is a non-destructive operation. The original ConstTree is not modified.

Returns

An Option containing the new ConstTree, or None if the index is out of bounds.

Examples

use deep_causality_ast::ConstTree;
let original = ConstTree::with_children(1, vec![ConstTree::new(2)]);
let updated = original.update_child(0, ConstTree::new(99)).unwrap();

assert_eq!(*original.children()[0].value(), 2);
assert_eq!(*updated.children()[0].value(), 99);
assert!(original.update_child(1, ConstTree::new(100)).is_none());

pub fn remove_child(&self, index: usize) -> Option<Self>

Returns a new ConstTree with the child at the specified index removed.

This is a non-destructive operation. The original ConstTree is not modified.

Returns

An Option containing the new ConstTree, or None if the index is out of bounds.

Examples

use deep_causality_ast::ConstTree;
let original = ConstTree::with_children(1, vec![ConstTree::new(2)]);
let removed = original.remove_child(0).unwrap();

assert_eq!(original.children().len(), 1);
assert!(removed.is_leaf());
assert!(original.remove_child(1).is_none());

impl<T: PartialEq> ConstTree<T>

pub fn contains(&self, value: &T) -> bool

Checks if the tree contains a given value by traversing in pre-order.

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(1, vec![ConstTree::new(2), ConstTree::new(3)]);
assert!(tree.contains(&2));
assert!(!tree.contains(&4));

impl<T> ConstTree<T>

pub fn iter_pre_order(&self) -> PreOrderIter<'_, T>

Returns an iterator that traverses the tree’s values in pre-order (root, then children).

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(1, vec![ConstTree::new(2), ConstTree::new(3)]);
let values: Vec<_> = tree.iter_pre_order().copied().collect();
assert_eq!(values, vec![1, 2, 3]);

pub fn iter_nodes_pre_order(&self) -> PreOrderNodeIter<'_, T>

Returns an iterator that traverses the tree’s nodes (ConstTree handles) in pre-order.

This is useful for finding nodes or performing operations on the tree structure itself.

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(1, vec![ConstTree::new(2)]);
let nodes: Vec<_> = tree.iter_nodes_pre_order().collect();
assert!(nodes[0].ptr_eq(&tree));
assert_eq!(*nodes[1].value(), 2);

pub fn iter_post_order(&self) -> PostOrderIter<'_, T>

Returns an iterator that traverses the tree’s values in post-order (children, then root).

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(1, vec![ConstTree::new(2), ConstTree::new(3)]);
let values: Vec<_> = tree.iter_post_order().copied().collect();
assert_eq!(values, vec![2, 3, 1]);

pub fn iter_level_order(&self) -> LevelOrderIter<'_, T>

Returns an iterator that traverses the tree’s values in level-order (breadth-first).

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(1, vec![ConstTree::with_children(2, vec![ConstTree::new(4)]), ConstTree::new(3)]);
let values: Vec<_> = tree.iter_level_order().copied().collect();
assert_eq!(values, vec![1, 2, 3, 4]);

impl<T: Clone> ConstTree<ConstTree<T>>

pub fn join(self) -> ConstTree<T>

Flattens a tree of trees into a single tree.

This is the join operation of a Monad. It takes a ConstTree where each node’s value is another ConstTree, and collapses it into a single ConstTree.

Examples

use deep_causality_ast::ConstTree;
// Create a tree of trees: ConstTree<ConstTree<i32>>
let inner_tree = ConstTree::with_children(1, vec![ConstTree::new(2)]);
let tree_of_trees = ConstTree::new(inner_tree);

let joined = tree_of_trees.join();

assert_eq!(*joined.value(), 1);
assert_eq!(joined.children().len(), 1);
assert_eq!(*joined.children()[0].value(), 2);

impl<T: Clone> ConstTree<T>

pub fn into_map<F, U>(self, f: F) -> ConstTree<U>

where F: FnMut(T) -> U, U: Clone,

Consumes the tree and creates a new tree by applying a function to each value.

This is the consuming equivalent of map(), analogous to into_iter(). Because this method consumes the tree, it can yield owned values T to the closure.

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(1, vec![ConstTree::new(2)]);
// The original tree is moved here.
let mapped_tree = tree.into_map(|v| v.to_string());

assert_eq!(*mapped_tree.value(), "1");
assert_eq!(*mapped_tree.children()[0].value(), "2");

impl<T> ConstTree<T>

pub fn map<F, U>(&self, f: &mut F) -> ConstTree<U>

where F: FnMut(&T) -> U, U: Clone,

Creates a new tree by applying a function to a reference of each value.

This is a non-destructive operation that returns a new ConstTree. The closure receives a reference &T.

Examples

use deep_causality_ast::ConstTree;
let tree = ConstTree::with_children(1, vec![ConstTree::new(2)]);
let mapped_tree = tree.map(&mut |v| v * 2);

assert_eq!(*tree.value(), 1); // Original is unchanged
assert_eq!(*mapped_tree.value(), 2);
assert_eq!(*mapped_tree.children()[0].value(), 4);

impl<T> ConstTree<T>

pub fn new(value: T) -> Self

Creates a new ConstTree with a single root node and no children (a leaf).

Example

use deep_causality_ast::ConstTree;
let leaf = ConstTree::new(10);
assert_eq!(*leaf.value(), 10);
assert!(leaf.is_leaf());

pub fn with_children(value: T, children: impl IntoIterator<Item = Self>) -> Self

Creates a new ConstTree with a root node and a given set of children.

The children argument can be any type that can be converted into an iterator over ConstTree<T>, such as a Vec<ConstTree<T>> or a slice &[ConstTree<T>].

Example

use deep_causality_ast::ConstTree;
let leaf1 = ConstTree::new(1);
let leaf2 = ConstTree::new(2);
let tree = ConstTree::with_children(0, vec![leaf1, leaf2]);
assert_eq!(tree.children().len(), 2);

pub fn with_value<V: Into<T>>(&self, new_value: V) -> Self

Returns a new ConstTree with the root value replaced.

This is a non-destructive, O(1) operation. The children of the new tree are shared with the original tree, avoiding a deep copy.

Examples

use deep_causality_ast::ConstTree;
let original = ConstTree::with_children(1, vec![ConstTree::new(2)]);
let with_new_value = original.with_value(99);

assert_eq!(*original.value(), 1);
assert_eq!(*with_new_value.value(), 99);
// The children are shared between the two trees.
assert!(original.children()[0].ptr_eq(&with_new_value.children()[0]));

Trait Implementations

impl<T> Clone for ConstTree<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for ConstTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default> Default for ConstTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Display> Display for ConstTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Clone> From<&T> for ConstTree<T>

fn from(value: &T) -> Self

Creates a new leaf ConstTree by cloning the provided value.

impl<T> From<T> for ConstTree<T>

fn from(value: T) -> Self

Converts to this type from the input type.

impl<T: Clone> IntoIterator for ConstTree<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for ConstTree<T>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for ConstTree<T>