Add api get index of child and to insert child at given index.

[causal-agent]

Children form a linked list, so "index" isn't really a concept that should apply to them. The crate documentation claims that all methods are constant time and all iterators are linear time, and I'd like to maintain that API. The "correct" solution here would be to have mutable iterators, but of course Rust makes that quite difficult.

[jessegrosjean]

I understand not wanting "index" in the API, I'm just not sure how to do what I want without it.

The "correct" solution here would be to have mutable iterators, but of course Rust makes that quite difficult.

Is this something that's possible now with existing ego-tree? If so can you give me a hint in how I would use?

My goal is:

1. I have a NodeMut
2. I want to insert a new child value at a given index.

I couldn't figure out how to do this using existing high level API no matter what I tried. (I'm new to Rust, so quite possibly just missing something). The only way that I could get it to work was with low level id manipulation, and so that's why I though it was a good candidate for the crate.

[SimonSapin]

Would something like this work?

fn insert_at<T>(parent: NodeMut<T>, index: usize, new_child: T) -> NodeMut<T> {
    if index == 0 {
        return parent.prepend(new_child)  // covers the `first_child().is_none()` case
    }
    let mut child = parent.first_child().unwrap();
    for _ in 1..index {
        child = child.next_sibling().unwrap()
    }
    child.insert_after(new_child)
}

[LoZack19]

Would something like this work?

fn insert_at<T>(parent: NodeMut<T>, index: usize, new_child: T) -> NodeMut<T> {
    if index == 0 {
        return parent.prepend(new_child)  // covers the `first_child().is_none()` case
    }
    let mut child = parent.first_child().unwrap();
    for _ in 1..index {
        child = child.next_sibling().unwrap()
    }
    child.insert_after(new_child)
}

This tries to implement a mutable iterator, but it doesn't quite work. The BC won't let you reassing child, since it was borrowed mutably by next_sibling()

[LoZack19]

I still would not implement this into master, because of what said previously here. We could maybe isolate the new non-constant time funtions, for making sure that whoever uses them is fully aware of the time complexity they require.

[adamreichold]

I think an API organized around a type derived from std's Cursor might be appropriate. We would provide only efficient methods to produce cursor (e.g. to insert before the first child) and user code would have to advance the cursor N times to insert before "index N" making the asymptotics more explicit in the code.

EDIT: Of course, for insertion CursorMut is the relevant role model.

[adamreichold]

Thinking about this some more, NodeMut basically already is a cursor but the signature of methods like next_sibling is too restrictive. I wonder if we can just provide an alternative signature like

impl<'a, T: 'a> NodeMut<'a, T> {
    pub fn into_next_sibling(self) -> Option<Self> {
        let id = self.node().next_sibling;
        id.map(move |id| unsafe { self.tree.get_unchecked_mut(id) })
    }
}

to make code like that proposed in https://github.com/rust-scraper/ego-tree/pull/15#issuecomment-443786983 work?

[adamreichold]

I wonder if we can just provide an alternative signature like

Opened #33 as an alternative approach.

[LoZack19]

I really like the approach in https://github.com/rust-scraper/ego-tree/pull/15#issuecomment-2310091848, into_* functions are very much needed in NodeMut

[cfvescovo]

Superseded by #33