A struct that holds "Something" and can iterate through potentially children of itself

I can not for the life of me figure this one out.

It feels like I'm trying to create a linked list... maybe I am, I don't know.

Kind of a flat_map too...

What I want is to have a struct that holds "something" and also children of the same, if any. The "something" can be a String for now, so we can print it and see if the logic is working.

I want to be able to hit .next() (in the future, .prev() also) directly on the root struct and it return me a reference (can be mutable) to the next element. So we can do things, such as print the String that it holds. the .next() function should be recursive however and iterate its children also.

Note, I don't need it to necessarily impl iterator. I tried many times not to though. And my strategy might be entirely wrong. So it's important that I can just get what I want

Here's where I got to:

struct Step {
    name: String,
    children: Vec<Box<Step>>,
    child_iter: Box<dyn Iterator<Item = Self>>,
}

impl Step {
    fn new(name: String) -> Self {
        let children = vec![];
        let child_iter = Box::new(children.iter());
        Self {
            name,
            children,
            child_iter,
        }
    }

    fn with_child(mut self, step: Step) -> Self {
        self.children.push(Box::new(step));
        self
    }
}

impl Iterator for Step {
    type Item = Self;
    fn next(&mut self) -> Option<Self::Item> {
        todo!()
    }
}

impl Display for Step {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "({})", self.name)
    }
}

fn main() {
    let a = Step::new("A".to_string());
    let b = Step::new("B".to_string())
        .with_child(Step::new("1".to_string()))
        .with_child(Step::new("2".to_string()))
        .with_child(Step::new("3".to_string()));
    let c = Step::new("C".to_string());

    let mut wizard = Step::new("MAIN".to_string())
        .with_child(a)
        .with_child(b)
        .with_child(c);

    for w in wizard {
        println!("{}", step);
    }
}

Thanks for your help. (i'm gonna head to bed now, I'll reply in the morning. Thanks in advance!!)

You'll probably want to make two separate types: One to store the data, and a separate one to iterate over it.

This is how all of the standard library's collection types work. For example, Vec<T> does not implement the Iterator trait, but it has methods to return iterators which do.

2 Likes

playground link

(The code I wrote really irks me.)

Yes you are making a tree-like structure.

Woah, nice! .. But just a note, the order should be: A B 1 2 3 C

Just change pop_back to pop_front or vice versa ? I think that should work. (Edit: nope of course not, it's been too long since I went to school)

Is that the "correct" order ? (edit: I vaguely prefer this, because ownership is clearer)

1 Like

If you don't want to consume the struct, you could do something like

impl Step {
    fn visit_mut<F: Copy + for<'a> Fn(&'a mut Step)>(&mut self, f: F) {
        f(self);
        for child in self.children.iter_mut() {
            child.visit_mut(f);
        }
    }
}
// ...
wizard.visit_mut(|step| println!("{}", step));

Playground.

If you need that next/prev fine control, you're going to have to maintain some sort of stack to keep track of your place in the tree. And consider how to handle or prevent[0] mutating the structure of the tree. And each step forward/backwards will be relatively slow with the not-unsafe approach of using indices. Alternatively, you could look for a tree library that has solved it for you.

[0]: E.g. StepView<'a> { name: &'a mut String, children: &'a [Box<Step>] }

2 Likes

Here is something I put together with input from others in the group. It describes how to think about iterators in relation to your collection. It also takes inventory of the approach used in the collections lib. Let me know what you think if you like.

It occured to me that if you don't need to mutate and don't mind some allocation, @jRimbault's approach could be adjusted to return a vector of references to your tree nodes in pre-traversal order. Moreover, if you do need mutation, but can do without access to the list of children within each node, a vector of mutable reference containing "view structs" could similarly be constructed. (Once you have the vector, you can iterate over it or otherwise access the members in any number of ways.)

Updated playground.

1 Like

Okay interesting stuff. But I'm kind of confused, what does 'preorder' mean, and what is a limited view as opposed to just a view?

I need to be able to stop at any step to get the data (name) and navigate via prev/next functions. rather than just iterate in one fell swoop. I don't want to consume the tree either, just get a reference (and the nodes can be 'static) because inside every note I'm hoping that the data will eventually manage it's own state and do sophisticated things. I just want a reference, because when it is time my GUI is going to ask it for GUI to display. (I think data/name will become a trait)

Let me try to explain the situation so as to avoid any xy problem.

I built a GUI wizard, that takes you prev/next along some Steps. using an enum, The wizard then displays on the left, like vertical tabs, the steps, and presents to the user prev and next buttons to navigate the state machine. the enum itself knows for which variant which UI to pull in and display on the right of the screen.

Imgur

However, eventually I realized I want to sub divide one of the steps, Let's say B now has several steps inside it. Well then I would the right side of the screen to be sub divided into another left/right. with a column on the left for steps... But use the same global prev/next buttons to navigate through them.

This is the bit I'm struggling with.

The data structure you describe is a tree, which is a kind of graph. There are many ways to traverse (≈iterate over) a graph, but the one that specifically has the order you're looking for is called preorder depth-first.

This is (what I'd call) a cursor, which is a somewhat different and lower-level abstraction than (what Rust and most other languages call) an iterator. The simplest kind of cursor is just an index into an vector: you can move it back and forth by adding or subtracting 1, and "dereference" it by using it to index the vector.

Tree cursors are more complicated, and there's different ways of approaching that problem, but one easy way is to simply flatten the tree into a vector and use an index. How you traverse the tree while flattening it determines the final order of the nodes, which brings us back to preorder depth-first. If, after creating the tree structure, you do a preorder traversal and push the nodes to a vector in the order you visit them, you end up with a flat vector of nodes which is easy to index with a cursor that goes both backwards and forwards.

You can flatten the tree either by value or by (shared) reference: neither should really pose a problem from a borrowing standpoint.

As I mentioned, there are other approaches to tree traversal with a cursor. You can have your cursor type contain a vector of references, or of indices, to the position of this node at each "level". So if you are at step B.2.iv (nested three levels in) you keep a reference to node B.2.iv, to node B.2, to node B, and to the top level / root node. That seems workable here, but it's probably more complex. Another way is to put parent links inside the tree itself, but that is pretty hard to achieve with meaningful ownership semantics, and I don't think it really solves your problem, anyway.

I would try flattening the tree first and seeing how far that can get you.

4 Likes

FYI, there's the petgraph library which types provides various iteration methods.

First let me spell out the motivation for such a thing.

Within a single function, you can do something like:

let child = &mut parent.children[0];
// do stuff with child...
// do stuff with parent...

And as long as you don't try to do things with child after doing things with parent, the compiler can figure out that this is ok. But it wouldn't be ok to modify parent and then child, because modifying the parent could invalidate the reference to the child[0]. Maybe you said parent.children =Vec::new().

So for the compiler to reason about this, it needs to remember that child is a sub-borrow of parent. That's not information that gets tracked across function boundaries. Because of this, there is no sound way to write a function that does something like this:

// n.b. if only one of the return values is &mut this is still an error
fn parent_and_child(parent: &mut Step) -> (&mut Step, &mut Step) {
    let child = &mut parent.children[0];
    (parent, child)
}

So there's no way to return a Vec<&mut Step> like you can a Vec<&Step>. That's the motivation -- I wanted to return a vector of things-you-can-mutate-the-data-with, and that couldn't be &mut Step. Instead I used a "view struct":

struct LimitedStepView<'a> {
    name: &'a mut String,
    children_count: usize,
}

Which gives you mutable access to the data, but doesn't contain the children (or any references to the children)[1], so we avoid the borrow checker violations.

You can read more about the pattern here. I am abusing the term a bit since I replaced the children field entirely instead of having a &[Box<Step>] or the like (as that would still have borrow checker violations). It's even more limited than a normal view, if you will.

[0]: That's one of the reasons it's not okay. The restrictions are actually a bit deeper than that, because Rust guarantees there are no ways to observe data behind a &mut except through the &mut -- no aliasing.

[1]: It's still possible to figure out the parent-child relationships via the children_count, with some amount of tedium.

So much amazing content in here, thank you everyone. I'm gonna need a few days to consume it and get back to you.

Also, I would use petgraph, but I think you already have to really understand graphs to be able to make use of that library. I'd need someone to show me exactly which functions to use in the petgraph lib to use.

Thanks again!

Here is a tree representation I’m using now to represent how to render my React components. It does not rely on refs. It just uses an id. You can climb up and down the tree. Hosting instances of what follows in a Map keyed by id worked well for my dynamic GUI.

{
    id, 
    parent, // Option<Id> where None means root
    children, // array of id (not refs)
    depth, // optional property
    data, // Option<MyData>
}

I did it!!!!!!!!!!! And couldn't have done it without your help

Now we have a flattened array that can be prev'ed/next'ed easily, where each node knows its siblings (I wonder if I'm going to need it to to know its entire root structure...? And it will need to repaint the entire tree again every time we progress to the next or previous step.)

Anyways, here's the code. I wonder if you can see how I could easily move any of the processing into compile time?

type Generation = Vec<Box<Step>>;

#[derive(Debug)]
pub struct Step {
    widget: String,
    children: Generation,
}

impl Step {
    pub fn new(widget: &str) -> Self {
        let children = vec![];
        Self {
            widget: widget.into(),
            children,
        }
    }

    pub fn with_child(mut self, step: impl Into<Self>) -> Self {
        self.children.push(Box::new(step.into()));
        self
    }

    pub fn build(&self) -> Vec<StepView> {
        let mut views: Vec<StepView> = Vec::new();

        fn walk_generation<'a>(views: &mut Vec<StepView<'a>>, generation: &'a Generation) {
            for current in generation {
                match current.children.is_empty() {
                    true => {
                        let view = StepView {
                            widget: &current.widget,
                            siblings: generation,
                        };
                        views.push(view);
                    }
                    false => walk_generation(views, &current.children),
                }
            }
        };

        walk_generation(&mut views, &self.children);

        views
    }
}

impl From<&str> for Step {
    fn from(item: &str) -> Self {
        Step::new(item)
    }
}

#[derive(Debug)]
pub struct StepView<'a> {
    pub widget: &'a String,
    pub siblings: &'a Generation,
}

fn main() {
    let steps = Step::new("Root")
        .with_child("A")
        .with_child("B")
        .with_child(
            Step::new("C")
                .with_child("One")
                .with_child("Two")
                .with_child("Three"),
        )
        .with_child("D");

    let wizard = steps.build();

    for w in wizard {
        let siblings: Vec<_> = w.siblings.iter().map(|x| x.widget.clone()).collect();
        println!("step {}, has siblings {:?}", w.widget, siblings);
    }
}