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

help
1

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?

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
3

Oh, follow up: Maybe have a separate trait for the owned version.

// Unchecked, on the fly
pub trait Tree<T> {
    type Borrowed<'a> where Self: 'a: BorrowedTree<'a, T>;
    fn borrow(&self) -> Self::Borrowed<'_>;
}

impl<T> Tree<T> for Node<T> {
    type Borrowed<'a> = &'a Self where Self: 'a;
    fn borrow(&self) -> Self::Borrowed<'_> {
        self
    }
}    

impl<T> Tree<T> for Heap<T> {
    type Borrowed<'a> = (&'a Heap<T>, usize) where Self: 'a;
    fn borrow(&self) -> Self::Borrowed<'_> {
        (self, 0)
    }
}
2 Likes
4

Oop, I was trying to undo some of the changes I had made to try to solve this and think I got a bit overzealous

Why must Trees implement Copy?

This is giving me a syntax error. I thought the 'a: BorrowedTree was supposed to be a 'a + BorrowedTree, but when I try to implement Tree rustc gives me "The trait bound btree::Node: tree::BorrowedTree<'_, T> is not satisfied. The trait tree::BorrowedTree<'a, T> is implemented for &'a btree::Node". What's the correct syntax here?

5

Because the default functions recursively call other methods multiple times (try removing the Copy bound). It could be Clone with the addition of a lot of .clone() but I'm lazy :slight_smile:

I got the where clause and trait bound order mixed. You also need T: Ord bounds on the implementations since you put those bounds on your struct itself.

pub trait Tree<T> {
    type Borrowed<'a>: BorrowedTree<'a, T> where Self: 'a;
    fn borrow(&self) -> Self::Borrowed<'_>;
}

impl<T: Ord> Tree<T> for Node<T> {
    type Borrowed<'a> = &'a Self where Self: 'a;
    fn borrow(&self) -> Self::Borrowed<'_> {
        self
    }
}    

impl<T: Ord> Tree<T> for Heap<T> {
    type Borrowed<'a> = (&'a Heap<T>, usize) where Self: 'a;
    fn borrow(&self) -> Self::Borrowed<'_> {
        (self, 0)
    }
}

Playground.

3 Likes
6

Thank you! This works perfectly

7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.