I'm trying to learn Rust, and for that I decided to implement Depth First Search algorithm.
So far I have the following Node struct:
#[derive(Debug)]
pub struct Node<'a> {
parent: Option<&'a Node<'a>>,
position: crate::entities::Position,
}
As you can see every time I create a node there is a reference to its parent.
Now, I have the dfs algorithm:
pub fn dfs<'a>(maze: &crate::entities::Maze) -> Node<'static> {
let mut traversed = Vec::new();
let mut frontier = Vec::new();
let mut seen: HashSet<crate::entities::Position> = HashSet::new();
let parent = Node {
parent: None,
position: maze.start // position is just a holder for row and column
};
frontier.push(parent);
loop {
if frontier.is_empty() {
panic!("No solution found!")
}
let current: Node<'static> = frontier.pop().expect("There must be a node here");
let position = current.position;
if current.position == maze.exit {
break current;
} else {
if !seen.contains(¤t.position) {
let neighbours = maze.get_neighbours(current.position).iter().map(|pos| Node {
parent: Some(¤t), // this line is not compiling
position: *pos
}).collect::<Vec<Node>>();
frontier.append(&mut neighbours);
traversed.push(current);
}
}
seen.insert(position);
}
}
But I am getting a compile error:
27 | parent: Some(¤t),
| ^^^^^^^ borrowed value does not live long enough
How can I fix that?