Hello everyone, and thank you in advance for your time and help.
First I'll give a little backstory into my problem, please feel free to skip it to go directly to the issue I present.
Backstory
I started with a recursively defined struct like this:
pub struct Clade {
name: Option<String>,
branch_len: Option<f64>,
children: Option<Vec<Clade>>
}
I was able to implement immutable iterators for a preorder and postorder traversal correctly. When I tried to implement a mutable postorder iterator, I quickly ran into trouble.
After looking online, I reasoned perhaps an arena allocator might help me solve this issue. My code changed to this:
pub struct Clade {
name: Option<String>,
branch_len: Option<f64>,
children: Option<Vec<Index>> // from generational-arena crate
}
Again I tried to implement a mutable iterator, and again I couldn't get it to work. Then I read online that streaming iterators may be a possible solution to a similar problem.
Problem
I have the following tree structure with all Clades being allocated through a generational arena (courtesy of the generational-arena = "0.2" crate).
pub struct Clade {
name: Option<String>,
branch_len: Option<f64>,
children: Option<Vec<Index>> // from generational-arena crate
}
I want to be able to apply changes to subtrees, and a post-order traversal would be ideal. I want to apply these changes iteratively, as a recursive approach may not scale with the size of trees I'm expecting.
Ultimately, regardless of what approach I take I still see the same root cause of my problem: the returned mutable reference from the iterator encounters lifetime-related issues. I'm guessing Rust doesn't want me to return a mutable reference that might be a dangling one. Here is my streaming iterator, courtesy of the streaming-iterator = "0.1.5" crate:
pub struct CladePostorderMutIterator<'a> {
clade_lookup: &'a mut Arena<Clade>,
stack: Vec<CladePair<'a>>,
cursor: Option<&'a Index>,
index: usize,
next: Option<&'a mut Clade>
}
impl<'a> StreamingIterator for CladePostorderMutIterator<'a> {
type Item = &'a mut Clade;
// post-order traversal algorithm
fn advance(&mut self) {
self.next = None;
while self.cursor.is_some() || !self.stack.is_empty() {
while !self.stack.is_empty() && self.cursor.is_none() {
let CladePair(peek_ind, _) = self.stack.last().unwrap();
let peek = self.clade_lookup.get(**peek_ind).unwrap();
if let Some(children) = &peek.children() {
if self.index != children.len() - 1 { break }
} else { break }
let CladePair(next, i) = self.stack.pop().unwrap();
self.index = i;
self.next = self.clade_lookup.get_mut(*next);
return
}
if !self.stack.is_empty() {
let CladePair(peek_ind, _) = self.stack.last().unwrap();
let peek = self.clade_lookup.get(**peek_ind).unwrap();
if let Some(children) = &peek.children() {
self.index = self.index + 1;
if self.index < children.len() {
self.cursor = Some(&children[self.index]);
} else {
self.cursor = None;
}
}
}
while self.cursor.is_some() {
let clade_ind = self.cursor.unwrap();
self.stack.push(CladePair(clade_ind, self.index));
self.index = 0;
let clade = self.clade_lookup.get(*clade_ind).unwrap();
if !clade.is_leaf() {
if let Some(children) = &clade.children() {
self.cursor = Some(&children[0])
}
} else { self.cursor = None }
}
let CladePair(next, i) = self.stack.pop().unwrap();
self.index = i;
self.next = self.clade_lookup.get_mut(*next);
return
}
}
fn get(&self) -> Option<&Self::Item> {
let result = &self.next;
return Option::from(result);
}
}
Final thoughts
I'm not tied to any specific approach, whether it's a streaming iterator or not, recursively defined trees or arena-allocated. I just want to be able to mutably iterate over the tree in post-order.