append_id will remove the node when the new node is the last child

[AuTa]

When I tried to sort in the tree, I used the code below which caused a panic in detach function:

use ego_tree::{tree, Tree};

fn sort<T>(tree: &mut Tree<T>)
where
    T: Ord + Clone + std::fmt::Display,
{
    let binding = tree.clone();
    let children = binding.root().children();
    let mut node_vec = children.collect::<Vec<_>>();
    node_vec.sort_by_key(|node| node.value());

    let mut root_mut = tree.root_mut();
    node_vec.iter().for_each(|node| {
        println!(
            "{:?}: {}; tree: {}",
            node.id(),
            node.value(),
            root_mut.tree()
        );
        // match root_mut.last_child() {
        //     Some(last_child) if last_child.id() != node.id() => {
        root_mut.append_id(node.id());
        //     }
        //     _ => (),
        // }
    });
}

fn main() {
    let mut tree = tree!('a' => { 'd', 'c', 'b' });
    sort(&mut tree);
    println!("{}", tree);
}

I found that every time I append, the last node disappears. After reviewing the code, it seems that when a node detaches, the previous node's next_sibling is set to None, but the parent's children still hold the original value. When only one node remains, it enters the condition first_child_id == self.id.

The simplest way to fix this is, as I commented in the match, to directly return the Node if last_child_id == new_child_id. The same logic applies to prepend_id.

BTW, Is it possible to implement a sort or sort_by_key method? By operating directly within NodeMut, it would eliminate the need for operations like clone to_vec that I'm currently using.

[adamreichold]

Thank you for reporting this and I agree with your assessment. This might also be the root cause of #35 (prepending an ID that already is the first child).

Let me try to come up with a regression test and then implement your fix...

[AuTa]

I found a way to implement sorting. However, since sorting wasn't implemented before, I'm not sure if it can be merged.

use std::cmp::Ordering;

impl<'a, T: 'a> NodeMut<'a, T> {
    pub fn sort(&mut self)
    where
        T: Ord,
    {
        if self.has_children() {
            let (unsorted, sorted) = self.sort_handler(|nodes| {
                nodes.sort_by(|(_, a), (_, b)| a.cmp(b));
            });

            self.swap(unsorted, sorted);
        }
    }

    pub fn sort_by<F>(&mut self, mut compare: F)
    where
        F: FnMut(&T, &T) -> Ordering,
    {
        if self.has_children() {
            let (unsorted, sorted) = self.sort_handler(|nodes| {
                nodes.sort_by(|(_, a), (_, b)| compare(a, b));
            });

            self.swap(unsorted, sorted);
        }
    }

    pub fn sort_by_key<K, F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
        if self.has_children() {
            let (unsorted, sorted) = self.sort_handler(|nodes| {
                nodes.sort_by_key(|(_, value)| f(value));
            });

            self.swap(unsorted, sorted);
        }
    }

    fn sort_handler<F>(&mut self, mut f: F) -> (Vec<NodeId>, Vec<NodeId>)
    where
        F: FnMut(&mut Vec<(NodeId, &T)>),
    {
        let children = unsafe { self.tree.get_unchecked(self.id()).children() };
        let (unsorted, mut nodes): (Vec<_>, Vec<_>) =
            children.map(|n| (n.id(), (n.id(), n.value()))).unzip();
        f(&mut nodes);
        let sorted = nodes.into_iter().map(|(id, _)| id).collect::<Vec<_>>();
        (unsorted, sorted)
    }

    fn swap(&mut self, unsorted: Vec<NodeId>, sorted: Vec<NodeId>) {
        let mut swap = |sorted_id: NodeId, unsorted_id: NodeId| {
            let mut node = unsafe { self.tree.get_unchecked_mut(unsorted_id) };
            node.insert_id_before(sorted_id);
        };

        let mut cache = None;
        let mut unsorted = unsorted.into_iter();
        for id in sorted {
            match cache {
                Some(cache_id) if cache_id != id => swap(id, cache_id),
                Some(_) => cache = None,
                None => match unsorted.next() {
                    Some(unsorted_id) if unsorted_id != id => {
                        swap(id, unsorted_id);
                        cache = Some(unsorted_id);
                    }
                    _ => (),
                },
            }
        }
    }
}