Trait needs reference to children of tree node - conflicts with one tree implementation

help
2

Your tree version doesn't work, unless I apply the suggestion.

 pub trait Tree<T>: Sized {
-    fn children(&self) -> Box<dyn Iterator<Item = &Self>>;
+    fn children(&self) -> Box<dyn Iterator<Item = &Self> + '_>;

As for your actual question, I think this is basically the same restruction that Index has: it assumes that you contain your target type, so you can get a &Target out from &Self. But your (&Hash<T>, usize) doesn't contain any (&Hash<T>, usize) tuples.

But if we look at the methods, everything in this trait is dealing with some form of a borrowed tree. You just need to abstract over what that borrow looks like.

  • &Node<T> aka &Self for Node-based trees
  • (&Hash<T>, usize) aka Self for Heap-based trees

And one way to do this is to have the trait be designed for implementation on the borrowed form, and not the owned form.

pub trait BorrowedTree<'a, T>: Sized + Copy + 'a {
    fn children(self) -> Box<dyn Iterator<Item = Self> + 'a>;
    fn dfs_pre_order(self) -> Vec<Self> { /* ... */ }
    // ...
    fn value(self) -> &'a T;
}

impl<'a, T: Ord> BorrowedTree<'a, T> for &'a Node<T> { /* ... */ }
impl<'a, T: Ord> BorrowedTree<'a, T> for (&'a Heap<T>, usize) { /* ... */ }

Playground.

More generally, you might want to try and make everything an iterator (BorrowedTree<'a, T>::DfsPreIter etc), though that would probably end up being a whole lot of boilerplate for the sake of optimization.

3 Likes