I'm trying to implement different kinds of Trees in a few different ways and create a Tree
trait that can abstract over them. Tree
currently requires children(&self) -> Box<dyn Iterator<Item = &Self>>
, which takes a given node and should produce its children.
use core::fmt;
use std::fmt::Display;
pub mod trie;
pub mod heap;
pub mod btree;
pub trait Tree<T> : Sized {
fn children(&self) -> Box<dyn Iterator<Item = &Self>>;
fn dfs_pre_order(&self) -> Vec<&Self> {
let mut vec = vec![];
vec.push(self);
for i in self.children() {
vec.extend(i.dfs_pre_order());
}
vec
}
fn dfs_post_order(&self) -> Vec<&Self> {
let mut vec = vec![];
for i in self.children() {
vec.extend(i.dfs_post_order());
}
vec.push(self);
vec
}
fn dfs_in_order(&self) -> Vec<&Self> {
let mut vec = vec![];
let mut children = self.children().peekable();
while let Some(child) = children.next() {
if children.peek().is_none() {
vec.push(self);
}
vec.extend(child.dfs_in_order());
}
vec
}
fn bfs(&self) -> Vec<&Self> {
let mut vec = vec![];
let mut nodes = vec![self];
loop {
let temp = nodes.iter().map(|x| x.children()).flatten();
// vec = nodes;
// nodes = temp.collect();
if nodes.is_empty() {break};
}
vec
}
fn value(&self) -> &T;
}
For my binary tree implementation, this works fine. It has fields for left
and right
and produces an iterator over a reference to each.
use crate::tree::Tree;
type BTree<T> = Node<T>;
pub struct Node<T>
where T: std::cmp::Ord {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
impl<T: std::cmp::Ord> Node<T> {
}
impl<T: std::cmp::Ord> Tree<T> for Node<T> {
fn children(&self) -> Box<dyn Iterator<Item = &Self>> {
Box::from(vec![&self.left, &self.right].into_iter().filter_map(|x| x.as_ref()).map(|x| x.as_ref()))
}
fn value(&self) -> &T {
&self.value
}
}
I've also made a Heap
, which is done with a vector. I was planning on, for the purposes of implementing Tree
, having each node be a tuple of the Heap
and the index of the vector that represents the node.
use std::{cmp::Ordering, ops::{Index, IndexMut}, marker::PhantomData};
use super::Tree;
pub struct Heap<T>
where T: Ord {
ordering: Ordering,
list: Vec<T>,
}
...
impl<T: Ord> Tree<T> for (&Heap<T>, usize) {
fn children(&self) -> Box<dyn Iterator<Item = &Self>> {
let left = (self.0, left(self.1));
let right = (self.0, right(self.1));
Box::new(vec![left, right].iter())
}
fn value(&self) -> &T {
&self.0.list[self.1]
}
}
Obviously, this doesn't work as it's returning a reference to a temporary value. How can I change the implementation/trait to allow this same abstraction to work?