Trying to make a variable-sized tree


#1

I’m new to Rust, and I’m trying to use it for a project which requires a tree structure where each node of the tree has a number of children to be determined at runtime. I keep running into errors having to do with lifetimes, arrays, and/or references.

Here’s what I’m starting with that won’t compile:

use std::cmp::PartialEq;
use std::cmp::Eq;

struct Tree {
    thisnode: usize,
    children: [Tree],
}

impl PartialEq for Tree {
    fn eq(&self, other: &Tree) -> bool {
        if self.thisnode != other.thisnode || self.children.len() != other.children.len() {
            return false;         
        }
        for i in 0..self.children.len() {
            if self.children[i] != other.children[i] {
                return false;
            }
        }
        true
    }
}

impl Eq for Tree {}

fn main() {
}

Since I don’t want any tree to be able to change after it’s initially created I thought it would be better to store the actual array of children instead of a reference to it, and I intended on implementing Copy instead of using move semantics, but I can’t even get that far since I can’t get equality testing to work (when I try to #[derive(PartialEq)] it tells me that it can’t compare [Tree]s using == or !=).
When I change children to &[Tree] it demands a lifetime for the reference and when I include that it tells me that it can’t derive lifetimes for self.children and other.children in the eq function.
The code I provided above fails to compile since it says that self.children and other.children don’t have len methods and can’t be indexed.

I would really rather not make one version of Tree for each possible number of children, and I think I’m probably missing something basic. Anybody feel like helping?


#2

I think Vec may be your best bet. Its size is determined at runtime.


#3

I think when you want the Tree to own its children, you should use Vec<Tree> for the children. [Tree] is an unsized type which can only be put into a struct behind a e.g. reference or a Box.


#4

Thank you for your help, I’ve implemented it with Vecs now, but I’ve hit another weird snag which appears to need more details fixed and I can’t understand the errors I’m getting.
Here’s my full code for this structure so far:

use operation::OperationSymbol;
use std::fmt;
use std::cmp::Eq;
use std::cmp::PartialEq;

trait Term: Eq + fmt::Display {
    fn get_variables(&self) -> Vec<&Variable>;
}

#[derive(Eq, PartialEq)]
struct Variable {
    name: String,
}

impl Term for Variable {
    fn get_variables(&self) -> Vec<&Variable> {
        vec![&self]
    }
}

impl fmt::Display for Variable {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(),fmt::Error> {
        f.write_str(self.name.as_ref())
    }
}

#[derive(Eq, PartialEq)]
struct CompositeTerm {
    symbol: OperationSymbol,
    children: Vec<Box<Term>>,
}

impl Term for CompositeTerm {
    fn get_variables(&self) -> Vec<&Variable> {
        let ans: Vec<&Variable> = vec![];
        for x in self.children {
            for y in x.get_variables() {
                if !ans.contains(&y) {
                    ans.push(y);
                }
            }
        }
        ans
    }
}

impl fmt::Display for CompositeTerm {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(),fmt::Error> {
        let mut ans = String::new();
        ans.push_str(self.symbol.name.as_ref());
        if self.symbol.arity > 0 {
            ans.push_str("(");
            ans.push_str(self.children[0].to_string().as_ref());
            for q in self.children.split_at(1).1 {
                ans.push_str(",");
                ans.push_str(q.to_string().as_ref());
            }
            ans.push_str(")");
        }
        f.write_str(ans.as_ref())
    }
}

As you can probably tell, I’m trying to parse out an arbitrary composition of functions with variables in such a way as to distinguish variables from constants. OperationSymbol is nothing special - it’s just a struct with a name field of type String and an arity field of type u8.
Anyway, the compiler keeps telling me that Term doesn’t implement Eq and that Term doesn’t implement Term. I assume this refers to the fact that I’m using methods without default implementations, but I don’t know what to do to fix that other than to provide useless default implementations which don’t distinguish Variables from CompositeTerms.

I should say that I’ve managed to get a similar structure almost working by defining Term as an enum with values Variable and CompositeTerm, but that seems really inelegant to me as I need to wrap every method’s implementation with match *self.


#5

Your problem seems to be that you have no implementation of Eq for trait objects of the type Term, meaning that you can’t do a == b where a and b has the type Box<Term>. There is a difference between requiring that anything implementing Term must implement Eq and implementing Eq for Term itself, which is what you really seem to want. This can easily be done with a few code changes (playpen with a couple of fixes):

trait Term {
    fn get_variables(&self) -> Vec<&Variable>;
}

impl PartialEq for Term {
    fn eq(&self, other: &Term) -> bool {
        self.get_variables() == other.get_variables()
    }
}

impl Eq for Term {}

impl fmt::Display for Term {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let variables = self.get_variables()
            .into_iter()
            .map(|var| &*var.name)
            .collect::<Vec<_>>()
            .connect(", ");
        write!(f, "Term with [{}]", variables)
    }
}

The problem with this approach is that you have no idea of what the original type of the Term trait object is, so you will have to establish a concept of equality for the trait object, itself, using only its methods. I used the variables in this example, but it’s maybe not what you really want, since it would cause a CompositeTerm containing one variable to be equal to an identical variable. You could add a method that returns some kind of tag, but then it would not be far from using an enum for everything.