Native pointer in the graph structure

Question

With the generous help of the rust community, I managed to get a database of the topological data structure collected using managed pointers. It came together pretty well, and I was very excited about Rust in general. Then I read this post (which looks like a reasonable plan), and it inspired me to feedback and tried to compile it using only owned pointers, if possible.

This is a working version using managed pointers:

struct Dart<T> { alpha: ~[@mut Dart<T>], embed: ~[@mut T], tagged: bool } impl<T> Dart<T> { pub fn new(dim: uint) -> @mut Dart<T> { let mut dart = @mut Dart{alpha: ~[], embed: ~[], tagged: false}; dart.alpha = vec::from_elem(dim, dart); return dart; } pub fn get_dim(&self) -> uint { return self.alpha.len(); } pub fn traverse(@mut self, invs: &[uint], f: &fn(&Dart<T>)) { let dim = self.get_dim(); for invs.each |i| {if *i >= dim {return}}; //test bounds on invs vec if invs.len() == 2 { let spread:int = int::abs(invs[1] as int - invs[0] as int); if spread == 1 { //simple loop let mut dart = self; let mut i = invs[0]; while !dart.tagged { dart.tagged = true; f(dart); dart = dart.alpha[i]; if i == invs[0] {i = invs[1];} else {i == invs[0];} } } // else if spread == 2 { // max 4 cells traversed // } } else { let mut stack = ~[self]; self.tagged = true; while !stack.is_empty() { let mut dart = stack.pop(); f(dart); for invs.each |i| { if !dart.alpha[*i].tagged { dart.alpha[*i].tagged = true; stack.push(dart); } } } } } } 

After several hours of errors in the pursuit of the life cycle, I came to the conclusion that it might not even be possible with pointers owned due to the cyclical nature (without binding the node, as I was warning ). My weak attempt at this below. My question is, is it possible to implement this structure without resorting to managed pointers? And if not, is the above code reasonable "rusty"? (idiomatic rust). Thank you

 struct GMap<'self,T> { dim: uint, darts: ~[~Dart<'self,T>] } struct Dart<'self,T> { alpha: ~[&'self mut Dart<'self, T>], embed: ~[&'self mut T], tagged: bool } impl<'self, T> GMap<'self, T> { pub fn new_dart(&'self mut self) { let mut dart = ~Dart{alpha: ~[], embed: ~[], tagged: false}; let dartRef: &'self mut Dart<'self, T> = dart; dartRef.alpha = vec::from_elem(self.dim, copy dartRef); self.darts.push(dart); } } 

Answer 1

I am sure that using &mut pointers is not possible, since there can only be one such pointer at a time, for example:

 fn main() { let mut i = 0; let a = &mut i; let b = &mut i; } 

 and-mut.rs:4:12: 4:18 error: cannot borrow `i` as mutable more than once at at a time and-mut.rs:4 let b = &mut i; ^~~~~~ and-mut.rs:3:12: 3:18 note: second borrow of `i` as mutable occurs here and-mut.rs:3 let a = &mut i; ^~~~~~ error: aborting due to previous error 

It is not possible to bypass check checks, either by storing an unsafe pointer to memory ( ptr::to_mut_unsafe_ptr ), or by indices in the darts GMap member. Essentially, storing a single memory reference (in self.darts ), and all operations must go through it.

It might look like this:

 impl<'self, T> GMap<'self, T> { pub fn new_dart(&'self mut self) { let ind = self.darts.len(); self.darts.push(~Dart{alpha: vec::from_elem(self.dim, ind), embed: ~[], tagged: false}); } } 

traverse must be changed either as a method to GMap (for example, fn(&mut self, node_ind: uint, invs: &[uint], f: &fn(&Dart<T>)) ), or at least take the GMap type.

(In a completely different note, there is support for a library of external iterators , which are much more complicated than internal iterators (those that do closure). Thus, defining one of them for traverse may (or may not) make it more enjoyable.)