Created
July 3, 2025 02:53
-
-
Save allwefantasy/9bebf25a332d97c93299824f3d7c7657 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// Tree traversal module for MoonBit | |
| /// Provides functionality to traverse and transform tree structures | |
| /// Generic tree node structure | |
| pub struct TreeNode[T] { | |
| data : T | |
| children : Array[TreeNode[T]] | |
| } | |
| /// Create a new tree node with data and children | |
| pub fn[T] TreeNode::new(data : T, children : Array[TreeNode[T]]) -> TreeNode[T] { | |
| { data, children } | |
| } | |
| /// Create a leaf node (no children) | |
| pub fn[T] TreeNode::leaf(data : T) -> TreeNode[T] { | |
| { data, children: [] } | |
| } | |
| /// Tree traversal using preorder traversal with mapping function | |
| /// @param tree - the tree to traverse | |
| /// @param map_function - function to apply to each node (data, index, parent_data?) | |
| /// @returns new transformed tree | |
| pub fn[T, U] util_tree_traverse( | |
| tree : TreeNode[T], | |
| map_function : (T, Int?, T?) -> U | |
| ) -> TreeNode[U] { | |
| fn preorder(node : TreeNode[T], index : Int?, parent : T?) -> TreeNode[U] { | |
| let new_data = map_function(node.data, index, parent) | |
| let new_children = [] | |
| for i = 0; i < node.children.length(); i = i + 1 { | |
| let child = node.children[i] | |
| let transformed_child = preorder(child, Some(i), Some(node.data)) | |
| new_children.push(transformed_child) | |
| } | |
| TreeNode::new(new_data, new_children) | |
| } | |
| preorder(tree, None, None) | |
| } | |
| /// Simpler version that only maps the data without index/parent info | |
| pub fn[T, U] tree_map(tree : TreeNode[T], map_function : (T) -> U) -> TreeNode[U] { | |
| util_tree_traverse(tree, fn(data, _index, _parent) { map_function(data) }) | |
| } | |
| /// Helper function to convert tree to string for debugging | |
| pub fn[T : Show] TreeNode::to_string(self : TreeNode[T]) -> String { | |
| let children_str = if self.children.length() == 0 { | |
| "" | |
| } else { | |
| let parts = [] | |
| for child in self.children { | |
| parts.push(child.to_string()) | |
| } | |
| ", children: [" + parts.join(", ") + "]" | |
| } | |
| "TreeNode(data: \{self.data}\{children_str})" | |
| } | |
| /// Pretty print tree structure | |
| pub fn[T : Show] print_tree(tree : TreeNode[T], indent~ : Int = 0) -> Unit { | |
| let prefix = " ".repeat(indent * 2) | |
| println("\{prefix}\{tree.data}") | |
| for child in tree.children { | |
| print_tree(child, indent=indent + 1) | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// Tests for tree traversal functionality | |
| test "create tree node" { | |
| let leaf = TreeNode::leaf(1) | |
| inspect(leaf.data, content="1") | |
| inspect(leaf.children.length(), content="0") | |
| let node = TreeNode::new(5, [TreeNode::leaf(2), TreeNode::leaf(3)]) | |
| inspect(node.data, content="5") | |
| inspect(node.children.length(), content="2") | |
| inspect(node.children[0].data, content="2") | |
| inspect(node.children[1].data, content="3") | |
| } | |
| test "simple tree mapping" { | |
| // Create a simple tree: 1 -> [2, 3] | |
| let tree = TreeNode::new(1, [TreeNode::leaf(2), TreeNode::leaf(3)]) | |
| // Map each value to double it | |
| let doubled_tree = tree_map(tree, fn(x) { x * 2 }) | |
| inspect(doubled_tree.data, content="2") | |
| inspect(doubled_tree.children.length(), content="2") | |
| inspect(doubled_tree.children[0].data, content="4") | |
| inspect(doubled_tree.children[1].data, content="6") | |
| } | |
| test "complex tree traversal" { | |
| // Create a more complex tree structure | |
| // 1 | |
| // / \ | |
| // 2 3 | |
| // / / \ | |
| // 4 5 6 | |
| let tree = TreeNode::new(1, [ | |
| TreeNode::new(2, [TreeNode::leaf(4)]), | |
| TreeNode::new(3, [TreeNode::leaf(5), TreeNode::leaf(6)]) | |
| ]) | |
| // Transform to string with parent info | |
| let string_tree = util_tree_traverse(tree, fn(data, _index, parent) { | |
| match parent { | |
| None => "root:\{data}" | |
| Some(p) => "child:\{data}(parent:\{p})" | |
| } | |
| }) | |
| inspect(string_tree.data, content="root:1") | |
| inspect(string_tree.children[0].data, content="child:2(parent:1)") | |
| inspect(string_tree.children[1].data, content="child:3(parent:1)") | |
| inspect(string_tree.children[0].children[0].data, content="child:4(parent:2)") | |
| inspect(string_tree.children[1].children[0].data, content="child:5(parent:3)") | |
| inspect(string_tree.children[1].children[1].data, content="child:6(parent:3)") | |
| } | |
| test "tree with index information" { | |
| let tree = TreeNode::new("root", [ | |
| TreeNode::leaf("first"), | |
| TreeNode::leaf("second"), | |
| TreeNode::leaf("third") | |
| ]) | |
| let indexed_tree = util_tree_traverse(tree, fn(data, index, _parent) { | |
| match index { | |
| None => data + "(root)" | |
| Some(i) => data + "(\{i})" | |
| } | |
| }) | |
| inspect(indexed_tree.data, content="root(root)") | |
| inspect(indexed_tree.children[0].data, content="first(0)") | |
| inspect(indexed_tree.children[1].data, content="second(1)") | |
| inspect(indexed_tree.children[2].data, content="third(2)") | |
| } | |
| test "empty tree and single node" { | |
| let single_node = TreeNode::leaf(42) | |
| let mapped = tree_map(single_node, fn(x) { x.to_string() }) | |
| inspect(mapped.data, content="42") | |
| inspect(mapped.children.length(), content="0") | |
| } | |
| test "tree transformation preserves structure" { | |
| let original = TreeNode::new(1, [ | |
| TreeNode::new(2, [TreeNode::leaf(4), TreeNode::leaf(5)]), | |
| TreeNode::leaf(3) | |
| ]) | |
| let transformed = tree_map(original, fn(x) { x + 10 }) | |
| // Check structure is preserved | |
| inspect(transformed.data, content="11") | |
| inspect(transformed.children.length(), content="2") | |
| inspect(transformed.children[0].data, content="12") | |
| inspect(transformed.children[0].children.length(), content="2") | |
| inspect(transformed.children[0].children[0].data, content="14") | |
| inspect(transformed.children[0].children[1].data, content="15") | |
| inspect(transformed.children[1].data, content="13") | |
| inspect(transformed.children[1].children.length(), content="0") | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment