use std::fmt::{Display, Formatter}; pub type ID = usize; static mut LAST_ID: usize = 0; #[derive(Clone, Debug, PartialEq)] pub struct SyntaxTree<T> { id: ID, value: T, children: Vec<SyntaxTree<T>>, } /// Simple ID provider fn next_id() -> ID { unsafe { let id = LAST_ID; LAST_ID += 1; id } } impl<T> SyntaxTree<T> { /// Create a SyntaxTree with a root node that carries the given value pub fn new(value: T) -> SyntaxTree<T>{ let tree = SyntaxTree{ id:next_id(), value, children:Vec::<SyntaxTree<T>>::new(), }; tree } /// Add another SyntaxTree as last child of this tree pub fn push_node(&mut self, new_node: SyntaxTree<T>) { (*self).children.push(new_node); } /// Create a new SyntaxTree with a root node that carries the given value. Add the created tree /// as last child of this tree. pub fn push_value(&mut self, value: T) { self.push_node(SyntaxTree::new(value)); } /// Add another SyntaxTree as first child of this tree pub fn prepend_node(&mut self, new_node: SyntaxTree<T>) { (*self).children.insert(0,new_node); } /// Create a new SyntaxTree with a root node that carries the given value. Add the created tree /// as first child of this tree. pub fn prepend_value(&mut self, value: T) { self.prepend_node(SyntaxTree::new(value)); } /// Insert the given SyntaxTree into the children of this tree at the given index pub fn insert_node(&mut self, index: usize, new_node: SyntaxTree<T>) { self.children.insert(index, new_node); } /// Create a new SyntaxTree with a root node that carries the given value. /// Insert the created SyntaxTree into the children of this tree at the given index pub fn insert_value(&mut self, index: usize, value: T) { self.insert_node(index, SyntaxTree::new(value)); } /// Perform a depth-first search with the given predicate. /// The method returns a reference to the first SyntaxTree instance for which the predicate /// return true. If no instance is found, None is returned. pub fn find_node(&self, predicate: fn(&SyntaxTree<T>) -> bool) -> Option<&SyntaxTree<T>> { if predicate(self) { return Some(self) } else { let children = (*self).children(); for child in children{ if(child.find_node(predicate).is_some()){ return child.find_node(predicate); } } }None } /// Perform a depth-first search with the given predicate. /// The method returns a mutable reference to the first SyntaxTree instance for which the predicate /// return true. If no instance is found, None is returned. pub fn find_node_mut( &mut self, predicate: fn(&SyntaxTree<T>) -> bool,) -> Option<&SyntaxTree<T>> { if predicate(self) { return Some(self) } else { let mut children = self.children_mut(); for child in children{ if(child.find_node_mut(predicate).is_some()){ return child.find_node_mut(predicate); } } None } } /// Return a reference to the value carried by the root of this tree pub fn value(&self) -> &T { &self.value } /// Return the id of the root of this tree pub fn id(&self) -> ID { self.id } /// Return a reference to the children of this tree pub fn children(&self) -> &Vec<SyntaxTree<T>> { &self.children } pub fn children_mut(&mut self) -> &mut Vec<SyntaxTree<T>> { &mut self.children } } impl<T: Display> SyntaxTree<T> { pub fn print(&self) -> String { if self.children.is_empty() { format!("{}", self.value) } else { format!( "{}\n[\n{}\n]", self.value, &self .children .iter() .map(|tn| tn.print_inner(1)) .collect::<Vec<String>>() .join(",\n") ) } } pub fn print_inner(&self, indent: usize) -> String { let mut indentation = String::new(); for _ in 0..indent { indentation.push_str(" "); } if self.children.is_empty() { format!("{}{}", &indentation, self.value) } else { format!( "{}{}\n{}[\n{}\n{}]", &indentation, self.value, &indentation, &self .children .iter() .map(|tn| tn.print_inner(indent + 1)) .collect::<Vec<String>>() .join(",\n"), indentation, ) } } } impl<T: Display> Display for SyntaxTree<T> { fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { write!(f, "({})", self.print()) } } #[cfg(test)] mod tests { use super::*; fn fill_tree_numbers() -> SyntaxTree<i32> { let mut tree = SyntaxTree::new(0); for child in 1..3 { let mut child = SyntaxTree::new(child); for grandchild in 1..3 { let id = grandchild * 10; child.prepend_node(SyntaxTree::new(id)); } tree.push_node(child); } tree } fn fill_tree_words() -> SyntaxTree<String> { let mut tree = SyntaxTree::new(to_s("root")); for (child_id, child) in ["first", "second", "third"].iter().map(to_s).enumerate() { let child_id = child_id; let mut child = SyntaxTree::new(child); if child_id == 0 { let mut descendant1 = SyntaxTree::new(to_s("A")); let mut descendant2 = SyntaxTree::new(to_s("B")); let descendant3 = SyntaxTree::new(to_s("C")); descendant2.push_node(descendant3); descendant1.push_node(descendant2); child.push_node(descendant1); } tree.push_node(child); } tree } #[test] fn number_tree() -> Result<(), String> { let tree = fill_tree_numbers(); println!("{}", tree); assert_eq!( String::from( "0\n[\n 1\n [\n 20,\n 10\n ],\n 2\n [\n 20,\n 10\n ]\n]" ), tree.print() ); Ok(()) } #[test] fn word_tree() -> Result<(), String> { let tree = fill_tree_words(); println!("{}", tree); assert_eq!( String::from("root\n[\n first\n [\n A\n [\n B\n [\n C\n ]\n ]\n ],\n second,\n third\n]"), tree.print() ); Ok(()) } #[test] fn find_node_by_value() -> Result<(), String> { let tree = fill_tree_numbers(); assert!(tree.find_node(|n| n.value == 0).is_some()); let left = tree.find_node(|n| n.value == 1).unwrap(); assert!(left.find_node(|n| n.value == 10).is_some()); assert!(left.find_node(|n| n.value == 20).is_some()); let right = tree.find_node(|n| n.value == 2).unwrap(); assert!(right.find_node(|n| n.value == 10).is_some()); assert!(right.find_node(|n| n.value == 20).is_some()); Ok(()) } fn to_s<T: Display>(value: T) -> String { format!("{}", value) } }