2

I’m writing code to iteratively search a recursive data structure such as the following:

struct Tree {
    payload: i32,
    children: Vec<Box<Tree>>
}

Suppose that I want to walk down every left branch of the tree and modify every node encountered. For simplicity, I won't include any termination conditions. The following code is not permitted by Rust’s borrow checking rules:

fn traverse(mut n: &mut Tree) {
    loop {
        n.payload += 1;
        n = n.children[0].as_mut();
    }
}

The only way I have found of expressing this logic so far is the following:

fn traverse(n: &mut Tree) {
    let mut stack: Vec<&mut Tree> = vec![n];
    while let Some(x) = stack.pop() {
        x.payload += 1;
        stack.push(x.children[0].as_mut())
    }
}

This works, but the unnecessary pushing/popping isn't very elegant.

Is there a better way of expressing this pattern in safe Rust without using recursion?

foldl
  • 725
  • 1
  • 7
  • 23
  • Just as a side-note -- I believe you're allowed to declare your `Tree` struct as containing a `Vec` rather than a `Vec>`. I'm unsure why...I guess it's since a `Vec`'s size isn't dependent on the size of its generic argument (since it holds only a pointer?) – user1935361 Apr 10 '17 at 16:35
  • Ah yes, my actual code had an array of children rather than a vector, so using Box was necessary, but you're right, there's actually no need for the Box in my example code. – foldl Apr 10 '17 at 16:43
  • Could you explain why this isn't a duplicate of http://stackoverflow.com/q/37986640 or http://stackoverflow.com/q/37904071 or http://stackoverflow.com/q/29711348 or http://stackoverflow.com/q/36167160 or http://stackoverflow.com/q/28767108 or http://stackoverflow.com/q/26563762? As you can see, **many people** have asked similar questions; all of these were found with the search terms "rust mutable reference tree". You are [expected to show a lot of effort](https://meta.stackoverflow.com/q/261592/155423) when asking a question, and looking at existing questions is the *bare minimum* effort. – Shepmaster Apr 10 '17 at 17:18
  • @Shepmaster. I obviously can't insert an explanation for every one of the questions in that long list, but I have looked at all of them and verified that my question is not a duplicate. (Most of them focus on the problem of having pointers to both parent and child nodes.) Also, you should not presume that I have not made an effort or looked at existing questions. – foldl Apr 10 '17 at 17:19
  • Ok. As described in the 3 linked duplicates: `n = {n}.children[0].as_mut();` – Shepmaster Apr 10 '17 at 17:24
  • And, FWIW, I'm encouraging you to **put in your original question** related things that you've already tried and *why they don't work*. Linking to other SO questions is ideal. Putting it in the question is the only way to *demonstrate* that you've done the research and aren't just asking for us to write your code for you. It also shows us what you do and don't understand so that part can be clarified, potentially adding value. Unfortunately for you, we do presume that every asker has put no effort... because it's true for the vast majority of people. – Shepmaster Apr 10 '17 at 17:29
  • @Shepmaster: This is clearly inapplicable in my case, as my original post contained working (but inelegant) code. Either put your answer as the answer or don't. There is no point in haranguing me in this manner in the comments. – foldl Apr 10 '17 at 17:30
  • You are right; in this case it's obviously not just a "write my code for me". I'm combining general advice on how to ask questions on Stack Overflow with advice on this specific question and not being very clear about the difference. The point I'm trying to make is that based on history of a vast number of posters, we (I?) tend to assume that a general poster hasn't done the initial legwork. You can prevent that by showing us your work up-front. Explaining why other solutions doesn't work also tends to allow for a better answer as the misconception can be cleared up. – Shepmaster Apr 10 '17 at 17:36
  • Also, if you are angry at me, you'll find yourself in good company. Most people where I have this much back-and-forth with tend to find me a troll or worse. This is why the vast majority of people who participate in Stack Overflow refrain from commenting. :-( – Shepmaster Apr 10 '17 at 17:38
  • Not really angry with you Shepmaster, but if I might offer your some advice in return, why not just mark the question as a dupe without the copypasta SO advice? I hate posting on SO precisely because of exchanges like this, so you can be sure that I only do it when I've failed to find an existing answer (whether because there isn't one or because I've made a mistake). – foldl Apr 10 '17 at 17:42

0 Answers0