Trait and struct with cyclical associations


#1

I’ve sort of run into a snag with implementing a struct that makes use of a trait I made. The struct not only has this trait as a generic constraint, but the trait, in turn, declares methods that use the struct as the return value type. Knowing Rust is merciless when it comes to oddballness, I’m not sure if this’ll work or not, as a trivial example:

trait Action
{
    // type assoc. needed?
    fn does_something() -> Thing<Action>
}

struct Thing<T>
{
    data: T,
}

impl<T> Thing<T> where T: Action
{
    // ...
}

#2

I’m guessing you want something like this:

struct Thing<T: ?Sized> {...}
impl<T: Action + ?Sized> Thing<T> {...}

trait Action {
  fn does_something() -> Thing<Self>;
}

But, it’s hard to say for sure without knowing what you intend to do with this.


#3

Well, my real situation is that I’m trying to code a quad tree that has some flexibility as far as its contents go. Thus, I thought to make a QuadTreeItem trait that can be implemented by other types. (ie. 3D map objects). The QuadTreeNode struct itself has a generic constraint (generic type T has to implement trait QuadTreeItem). The QuadTreeItem trait itself has two particular methods which deal with QuadTreeNode (node() and set_node()) for accessing the referenced QuadTreeNode that owns it, or to change owners.

I think my code should better explain, but it likely won’t compile… yet.

pub trait QuadTreeItem
{
	type Item; // is this necessary?
	
	fn position(&self) -> Vector3;
	fn node(&self) -> Option<&QuadTreeNode<Item>>; // may be unowned
	fn set_node(&self, node: Option<&QuadTreeNode<Item>>);
}

#[derive(Debug, Clone)]
pub struct QuadTreeNode<'a, T: 'a>
{
	bounds: BoundingBox, 
	center: Vector3,
	children: Vec<Box<QuadTreeNode<'a, T>>>,
	items: Vec<Rc<QuadTreeItem<T>>>,
	root: Option<&'a QuadTreeNode<'a, T>>,
	depth: i32,
	size: f32,
	max_depth: i32,
}

impl<'a, T> QuadTreeNode<'a, T> where T: QuadTreeItem
{
    // ... most methods need not be shown here ...

    // posting this method as an example for trait obj. use
	pub fn push(&mut self, mut item: Rc<QuadTreeItem<T>>) -> bool
	{
		if self.bounds.contains_vec(item.position()) // rather new with Rc so this may not be correct
		{
			if self.children.len() == 0
			{
				if self.depth < self.max_depth { self.subdiv(); }
				else
				{
					*Rc::getmut(&mut item).unwrap().node = Some(&*self);
					self.items.push(item.clone());
					return true;
				}
			}
			for c in self.children.iter_mut()
			{
				if c.push(item.clone()) { return true; }
			}
		}
		if self.is_root { return false; }
		
		self.root.unwrap().push(item.clone())
	}
}

#4

Figured it out.:

pub trait QuadTreeItem
{
	type Item;
	
	fn node(&self) -> Option<&QuadTreeNode<Self::Item>>;
	fn set_node(&self, node: Option<&QuadTreeNode<Self::Item>>);
}

impl<'a, T> QuadTreeNode<'a, T> where T: QuadTreeItem
{
    // ....
}

#5

Have you looked at some existing quadtree rust crates? They may shed some light on best way to model them.


#6

I actually found one via google, but I’m guessing it’s outdated, as it uses a “uint” type I’m guessing Rust did away with.