Algorithm for tracking the movement of nodes in a directed adjacency list
I have a directed adjacency list of node's. The structure of a node is
Node { id: integer; order: integer; parentId: integer | null; }
and the following nodes for the sake of example. [ {id: 1, order: 1, parentId: null}, {id: 2, order: 1, parentId: 1}, {id: 3, order: 2, parentId: 1}, {id: 4, order: 1, parentId: 2}, {id: 5, order: 2, parentId: 2}, {id: 6, order: 3, parentId: 2}, {id: 7, order: 4, parentId: 2}, {id: 8, order: 1, parentId: 3}, {id: 9, order: 5, parentId: 2}, {id: 10, order: 3, parentId: 1} ]
I need an algorithm that can - reorder node(s) within the same level on the hierarchy - move node(s) to a different level and inserted into an arbitrary order.
algorithm moveNodes
input
number[] nodes: Array of 1 to n node IDs.
integer destinationParentId: The new parent for each node
in the nodes array.
integer position: The starting order the nodes will be
inserted into.
Output
An array of operations describing the updates required
to move the nodes in the
nodes input param to be a child of destinationParentId
starting at position. Nodes are inserted
in the order they appear in the nodes param.
Assume the node IDs passed to the moveNodes nodes param all have the same parentId, so nodes from different levels won't be moved in the same operation.
Also, assume that the function won't be called in a way that would nest a node inside itself or one of its descendant nodes.
Other requirements
* No nodes can have both the same parentId and order.
* There can't be any gaps in the order for siblings.
Examples
(Assume changes are independent / don't persist between function runs)
moveNodes(nodes: [6, 7], destinationParentId: 2, order: 1)
should return [ {id: 4, nextOrder: 3}, {id: 5, nextOrder: 4}, {id: 6, nextOrder: 1}, {id: 7, nextOrder: 2} ] (so we are going [4, 5, 6, 7, 9] -> [6, 7, 4, 5, 9])
moveNodes(nodes: [2,3], destinationParentId: 2, order: 1)
should return [ {id: 2, nextParentId: 2}, {id: 3, nextParentId: 2}, {id: 10, nextOrder: 1}, {id: 4, nextOrder: 3}, {id: 5, nextOrder: 4}, {id: 6, nextOrder: 5}, {id: 7, nextOrder: 6}, {id: 9, nextOrder: 7} ] (so we are going [2, 3, 10] -> [10] and [4, 5, 6, 7, 9] -> [2,3, 4, 5, 6, 7, 9]) 839