How to deal with "cannot move out of borrowed content"

help
1

I am learining rust and as an exercise i wanted to implement simple graph dfs and bfs. However i completly stucked with "cannot move out of borrowed content" error.
This is what i already have, it failes inside Iterator implementation

struct Node<T> {
  value: T,
  neighbors: Vec<Node<T>>,
}

impl <T> Node<T> {
  fn new(value: T) -> Node<T> {
    Node { value, neighbors: Vec::new() }
  }

  fn add_neighbor(&mut self, node: Node<T>) {
    self.neighbors.push(node)
  }
}

struct Dfs<T> {
  root: Node<T>,
  queue: Vec<Node<T>>
}

impl <T> Dfs<T> {
  fn new(root: Node<T>) -> Dfs<T> {
    Dfs { root, queue: Vec::new() }
  }
}

impl <T> Iterator for Dfs<T> {
  type Item = T;

  fn next(&mut self) -> Option<T> {
    let current = &mut self.root;
    match current.neighbors.split_first_mut() {
      Some((head, _tail)) => {
        self.root = *head;
        Some(current.value)
      }
      _ => None
    }
  }
}

fn main() {
  let mut a = Node::new(1);
  let mut b = Node::new(2);
  let mut c = Node::new(3);
  let d = Node::new(4);
  let e = Node::new(5);
  let f = Node::new(6);

  b.add_neighbor(d);
  a.add_neighbor(b);

  c.add_neighbor(e);
  c.add_neighbor(f);
  a.add_neighbor(c);

  let mut dfs = Dfs::new(a);

  while let Some(value) = dfs.next() {
    println!("{}", value);
  }
}
2

With split_first_mut you are getting two slices of the Vec. Therefore, current.neighbours still owns both head and (the unused) tail. You are trying to steal the ownership, and you could only do that for things like Vec<Option<T>>, using Option::take.

The main problem here is that Dfs is your container object, but you are trying to making it work as Iterator. Generally you need a different struct to handle the iterator behaviour.

IMHO, something like Windows is a good example of how to do that: you have a slice and you need to iterate across it, using a sliding windows of given size. Try to give a look at the code, maybe it makes things a bit clearer on how you should write the code :smiley:

3

As @dodomorandi mentioned, Dfs should be borrowing the Node; its definition is likely more like:

struct Dfs<'a, T: 'a> {
  root: &'a Node<T>,
  queue: Vec<&'a Node<T>>,
}
4

Stackoverflow is your friend :wink:

https://stackoverflow.com/questions/28158738/cannot-move-out-of-borrowed-content
https://stackoverflow.com/questions/23969191/using-the-same-iterator-multiple-times-in-rust
https://stackoverflow.com/questions/34530567/cannot-move-out-of-borrowed-content-when-using-skip-while
https://stackoverflow.com/questions/39935158/cannot-use-moved-bufreader-after-for-loop-with-bufreader-lines