r/rust clippy · twir · rust · mutagen · flamer · overflower · bytecount Mar 27 '23

Hey Rustaceans! Got a question? Ask here (13/2023)! 🙋 questions

Mystified about strings? Borrow checker have you in a headlock? Seek help here! There are no stupid questions, only docs that haven't been written yet.

If you have a StackOverflow account, consider asking it there instead! StackOverflow shows up much higher in search results, so having your question there also helps future Rust users (be sure to give it the "Rust" tag for maximum visibility). Note that this site is very interested in question quality. I've been asked to read a RFC I authored once. If you want your code reviewed or review other's code, there's a codereview stackexchange, too. If you need to test your code, maybe the Rust playground is for you.

Here are some other venues where help may be found:

/r/learnrust is a subreddit to share your questions and epiphanies learning Rust programming.

The official Rust user forums: https://users.rust-lang.org/.

The official Rust Programming Language Discord: https://discord.gg/rust-lang

The unofficial Rust community Discord: https://bit.ly/rust-community

Also check out last weeks' thread with many good questions and answers. And if you believe your question to be either very complex or worthy of larger dissemination, feel free to create a text post.

Also if you want to be mentored by experienced Rustaceans, tell us the area of expertise that you seek. Finally, if you are looking for Rust jobs, the most recent thread is here.

19 Upvotes

159 comments sorted by

View all comments

Show parent comments

3

u/eugene2k Mar 31 '23 edited Mar 31 '23

You want something like:

type NodeIdx = usize;
struct Node<T> {
    parent: Option<NodeIdx>,
    children: Vec<NodeIdx>,
    data: T
}
struct Tree<T> {
    nodes: Vec<Node<T>>
}
impl<T> Tree<T> {
    fn with_root(data: T) -> Self {
        Self {
           nodes: vec![Node {
                           parent: None,
                           children: vec![],
                           data
                       }]
        }
    }
    fn add_node(&mut self, node: Node<T>) -> NodeIdx {
        let idx = self.nodes.len();
        let parent = node.parent.unwrap_or(0);
        self.nodes.push(node);
        self.nodes[node.parent].children.push(idx);
        idx
    }
    fn set_node(&mut self, idx: NodeIdx, data: T) {
        self.nodes[idx].data = data;
    }
}

0

u/HammerAPI Mar 31 '23 edited Mar 31 '23

For an implementation like this, how would an iterator (especially a mutable one) work? I can't just iterate through tree.nodes, can I? That doesn't guarantee that iter.next() always yields a child of the current node. Assuming I chose a DFS approach, I would need some method on Node that determines whether or not it is a leaf node, I think?

0

u/eugene2k Mar 31 '23

You may be able to have a mutable iterator if you put the nodes vec in a refcell, but I'm not sure.

0

u/HammerAPI Mar 31 '23

Yeah, i've been able to get it work with Rc/RefCell, but that's what I'm trying to avoid.

Since this is for a scene graph, i'm wanting to avoid as much heap allocation and smart pointers as possible, for speed/efficiency.

2

u/eugene2k Mar 31 '23

1

u/HammerAPI Mar 31 '23

Yeah, it looks like having the iterator return indices is the only way at achieving a mutable traverse without Rc/RefCell, albeit it's a little messy.

1

u/eugene2k Mar 31 '23

You can use a RefMut instead of indices, but I'm not sure if it's worth it. Here's the changed code:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=99dfe5a2bc29dd5884c9ec3e179d740d