Request: Re-parent (move, re-root) TreeNodes

[aaronrudkin]

Is there a mechanism to re-parent or re-order TreeNodes?

Possible use cases:

• Sorting a tree by various metrics without having to remove and re-add all nodes in code
• Re-rooting a tree
• Moving a "directory" node into another directory node along with all its children

Right now, as best as I can tell, the correct way to do this is to maintain a data structure containing the source of truth for the tree, mutating that structure, calling <TreeNode>.remove(), and then re-adding recursively in the appropriate location and order. The .add() and .add_leaf() methods of the Tree class support after/before arguments. Maybe this is the preferred workflow.

Suggestions:

1. Add a .move() method to TreeNode. The caller will be the new parent. The first argument is node, a TreeNode, which is the node you wish to move. The arguments would also include after and before, which can function similarly to the .add() analogues. I think that's it for arguments. There is one edge case you need to defensively guard against: which is moving an ancestor node into a child node creates an infinite loop, but I think the check would be as simple as taking the new parent node and progressively checking its parents until you get to the root for a node match. Provided all this is clean, the .move() method is an almost straight reimplementation of .add() except that a node is not created, it just has its reference assigned.
2. (Significantly less important, and probably significantly more difficult) Add a mechanism to write to a Tree's root in order to entirely re-root the tree.

Looking at the package internals, I have a few more thoughts:

• This would maybe also involve creating an exception type MoveNodeError, or adjusting the AddNodeError exception type to have a more general name.
• I think the self._tree_nodes[node._id] flat cache for the tree nodes probably doesn't need to be updated, I imagine the node would preserve its ID even when moved.
• I don't fully understand at first blush how the rendering cache works vis-a-vis the ._updates attribute and invalidation; it looks like ._updates is just an incrementing thing and isn't used to do anything, and ._invalidate() re-renders the whole meal deal so it should be sufficient at the end of the method?
• I have not looked into DirectoryTree to see whether or not the method would need to be reimplemented there as well.

If my understanding of package internals is correct, I am not intrinsically opposed to trying to implement this myself.

[aaronrudkin]

Had a few minutes on the subway to swing at this:

    def move(
        self,
        node: int | TreeNode[TreeDataType],
        *,
        before: int | TreeNode[TreeDataType] | None = None,
        after: int | TreeNode[TreeDataType] | None = None,
    ) -> TreeNode[TreeDataType]:
        """Move a node to become a child of this node.

        Args:
            node: The node to move (either an index or TreeNode).
            before: Optional index or `TreeNode` to move the node before.
            after: Optional index or `TreeNode` to move the node after.

        Returns:
            The moved node.

        Raises:
            MoveNodeError: If there is a problem with the move request.

        Note:
            Only one of `before` or `after` can be provided. If both are
            provided a `MoveNodeError` will be raised. If `node` is an
            ancestor of this node, a `MoveNodeError` will be raised.
        """
        if before is not None and after is not None:
            raise MoveNodeError("Unable to move a node both before and after a node")

        if isinstance(node, int):
            try:
                node_to_move = self.children[node]
            except IndexError:
                raise MoveNodeError(f"Node index {node} is out of range") from None
        else:
            node_to_move = node

        current_node = self
        while current_node is not None:
            if current_node.id == node_to_move.id:
                raise MoveNodeError("Cannot move a node to be a child of itself or its descendants")
            current_node = current_node.parent

        insert_index: int = len(self.children)

        if before is not None:
            if isinstance(before, int):
                insert_index = before
            elif isinstance(before, TreeNode):
                try:
                    insert_index = self.children.index(before)
                except ValueError:
                    raise MoveNodeError(
                        "The node specified for `before` is not a child of this node"
                    ) from None
            else:
                raise TypeError(
                    "`before` argument must be an index or a TreeNode object to move before"
                )

        if after is not None:
            if isinstance(after, int):
                insert_index = after + 1
                if after < 0:
                    insert_index += len(self.children)
            elif isinstance(after, TreeNode):
                try:
                    insert_index = self.children.index(after) + 1
                except ValueError:
                    raise MoveNodeError(
                        "The node specified for `after` is not a child of this node"
                    ) from None
            else:
                raise TypeError(
                    "`after` argument must be an index or a TreeNode object to move after"
                )

        old_parent = node_to_move.parent
        if old_parent is None:
            raise MoveNodeError("Cannot move the root node")

        old_parent._children.remove(node_to_move)
        node_to_move._parent = self

        self._updates += 1
        self._children.insert(insert_index, node_to_move)
        self._tree._invalidate()

        return node_to_move

I imagine given the code reuse from add() you might prefer to abstract common elements (like processing before/after, resolving a node from an int | TreeNode input, recursing up the ancestor tree) into helper functions, but again I don't really know your style norms in this regard. I only had a second and limited connectivity so I didn't set up the test harness or anything but I figured I'd share the method anyway and only bother doing testing if you guys thought it was something you'd be happy accommodating in the design.

One thing from looking at the code: one bug is that if the node is already a child of the calling node, then the insertion index will be off by one because of the deletion -- obviously if I do a PR for this I'll fix that.

And then my sense is that the only other thing undone here is writing tests, which I imagine would be pretty similar to the tests for adding nodes. Looking over the docs there's not much on how Tree objects are handled so I don't think it'd be crazy to add without doing any doc updates beyond the docstring.

Any thoughts?