Manipulate a recursive array

Question

I have a hierarchical data structure such as this:

var tree = [ {foo: 1, children:[
    {foo: 2, children:[
        {foo: 13, children:[]},
        {foo: 14, children:[]}
    ]}, 
    {foo: 3, children:[]}, 
    {foo: 4, children:[]}
]}, 

{foo: 5, children:[
    {foo: 6, children:[]}, 
    {foo: 8, children:[]}
]}, 

{foo: 9, children:[
    {foo: 10, children:[]}, 
    {foo: 11, children:[]}, 
    {foo: 12, children:[]}
]} ];

The tree can be of any depth.

In order to reposition a specific object in the tree (including its children), I can trivially write:

// Move object from [0, 0, 1] to [2, 1]
var obj = tree[0]['children'][0]['children'][1];
tree[0]['children'][0]['children'].splice(1, 1);
tree[2]['children'].splice(1, 0, obj);

But I am not able to program the general case:

Given two sets of coordinates, reposition an object from [i1, i2, ..., im] to [j1, j2, ..., jn].

I would like some hints about how to construct this recursive algorithm. Although this is a pure Javascript question, I should note that my application uses AngularJS and jQuery. Perhaps these libraries provide array manipulation functions that I could use?

My answer here may be of interest (with some subtle modifications i.e. adding setValue and getValue functions) - stackoverflow.com/questions/12163160/… — Pebbl
– Pebbl, Commented Jan 2, 2013 at 11:10

Stuart Wakefield · Accepted Answer · 2013-01-02 11:09:46Z

One way to do this tree traversal is to use a variable to store the reference to the part of the tree you have navigated to, navigating a layer at a time. We could write a traversal function as follows:

var traverseTree = function(tree, coord) {

  var current = tree;

  // Loop through the coordinates moving one at a time, no error handling
  // what happens if the node doesn't exist?
  for(var i = 0; i < coord.length; ++i) {
    current = current[coord[i]].children;
  }      

  // Return the node
  return current;
}

Then we could write the functionality described as two functions a method that extracts the node and a method that inserts the node:

var extractNodeFromTree = function(tree, coord) {

  // We don't want to traverse the whole way
  var last = coord.pop();

  // Traverse to the parent
  var parent = traverseTree(tree, coord);

  // Extract the element using the last coordinate
  return parent.splice(last, 1)[0];
}

var insertNodeIntoTree = function(tree, coord, node) {

  // Same as last method
  var last = coord.pop();
  var parent = traverseTree(tree, coord);

  // Insert node to the specified position
  current.splice(last, 0, node);

}

You could use the functions as follows:

var node = extractNodeFromTree(tree, [0, 0, 1]);
insertNodeIntoTree(tree, [2, 1], node);

A fiddle to show it in action

pimvdb · Accepted Answer · 2013-01-02 13:06:02Z

3

The main issue is that you have to access properties to an arbitrary depth. What you can use for this is a loop which is recursive in a sense:

// a is the input set

var arr = tree;  // start at the root
for(var i = 0; i < a.length - 1; i++) {  // stop one too early
  arr = arr[ a[i] ].children;
}
// now, arr is the array you want to splice, so
// you can splice the object and store it in a temporary
// place

With the same logic, you can traverse to the output array and add the value there.

edited Jan 2, 2013 at 13:06

answered Jan 2, 2013 at 10:50

pimvdb

155k80 gold badges313 silver badges357 bronze badges

1 Comment

user1942447 Over a year ago

Thanks. I picked the other answer, because it also includes a POC; but this one is equally correct.

Collectives™ on Stack Overflow

Manipulate a recursive array

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related