Recursion through JavaScript Object

Question

Trying to dust off the pipes on recursion here. Can anyone give me a hand?

I have a JavaScript object of keys that contain an array of other keys in their values. Using JavaScript I am trying to normalize the list so I can see which keys belong as dependencies to the key in question. Let me explain visually:

Here is the object (itemDepsMap):

{
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
}

So the key four depends on three, which depends on one and two, which depend on one and zero

I need a function called checkDeps(id) which will return as follows"

checkDeps('four') => [three, two, one, zero] checkDeps('two') => [one, zero]

I believe this is called a closure. I also believe that this is to be done recursively.

Here's what I have:

  this.checkDeps = function(id) {
    var closure = [];
    if(this.itemDepsMap[id] !== ''){
      for(var dep in this.itemDepsMap[id]) {
        console.log(this.itemDepsMap[id][dep]);
        closure = this.checkDeps(this.itemDepsMap[id][dep]);
      }
    }
    return closure;
  }

I would really appreciate some help here! Duplicates are not important, but bonus points if the solution doesn't add duplicates (elegantly..)

order also important? or `[three, two, one, zero]` is same as `[three, one, two, zero]` — Grundy, Oct 23 '15 at 08:34
no order doesn't matter. As long as there is a normalized array, task accomplished. — bneigher, Oct 23 '15 at 08:43
No, this has absolutely nothing to do with [closures](http://stackoverflow.com/q/111102/1048572) — Bergi, Oct 23 '15 at 09:11

score 0 · Answer 1 · answered Oct 23 '15 at 08:54

I make a very simple approach. You may take it as reference. It would return a unique array

var itemDepsMap =
{
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
};

function makeUnique(value, index, self) { 
    return self.indexOf(value) === index;
}

var closure = [];
var checkDeps = function(id) {
    if(itemDepsMap[id] !== ''){
      for(var dep in itemDepsMap[id]) {
        console.log(itemDepsMap[id][dep]);
        closure.push(itemDepsMap[id][dep]);
        checkDeps(itemDepsMap[id][dep]);
      }
    }
    closure = closure.filter( makeUnique );
};

checkDeps('four');
console.log(closure);

score 0 · Accepted Answer · answered Oct 23 '15 at 09:23

you can use two functions here is my code

var itemDepsMap = {
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
}

var closure = [];

function checkDeps(id){

    var dep = itemDepsMap[id];

    if(dep == '') return;

    for(var i = 0; i < dep.length; i++){

        if(closure.indexOf(dep[i]) == -1){
            closure.push(dep[i]);
            checkDeps(dep[i]);
        }       
    }
}


function test(){

    checkDeps('two');
    console.log(closure);

}

function test used for testing

score 0 · Answer 3 · answered Oct 23 '15 at 10:28

Yet another way without reqursion:

function f(id, obj) {
  if (obj[id] == '') return [];//if not dependencies return at once

  var path = obj[id],//save dependecies to check
    p = {},//result dependencies
    cur;//pointer to current 
  while (path.length) {
    do {
      cur = path.shift();//get first dependency that not checked
    } while (cur && p[cur]);

    if (!cur) break;//if nothing current break loop

    p[cur] = true; //mark dependency as checked
    if (obj[cur] != '') {//if current field have dependency
      path = path.concat(obj[cur]);//add to saved dependecies
    }
  }

  return Object.keys(p);
}

function f(id, obj) {
  if (obj[id] == '') return [];

  var path = obj[id],
    p = {},
    cur;
  while (path.length) {
    do {
      cur = path.shift();
    } while (cur && p[cur]);

    if (!cur) break;
    p[cur] = true;
    if (obj[cur] != '') {
      path = path.concat(obj[cur]);
    }
  }

  return Object.keys(p);
}

t={
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
};

document.getElementById('r').innerHTML = JSON.stringify(t)
+ '<br /><br />' + JSON.stringify(f('four',t))
+ '<br />' + JSON.stringify(f('two',t));

<div id="r"></div>

Abhitalks · Answer 4 · 2015-10-23T10:21:29.337

Just plain recursion, using only one completely self-contained function:

var omap = {
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
};

function tracer(key, logger) {
  obj = omap[key] ? omap[key] : obj[key];
  if (!obj || obj == 'undefined') { return logger; }
  obj.forEach(function(elem) { 
    if (logger.indexOf(elem) < 0) { 
      tracer(elem, logger); logger.unshift(elem);         
    }
  });
  return logger;
}

snippet.log('four - ' + tracer('four', [])); 
snippet.log('three - ' + tracer('three', [])); 
snippet.log('two - ' + tracer('two', []));

<script src="//tjcrowder.github.io/simple-snippets-console/snippet.js"></script>

Just call tracer with the key and an empty array.

e.g. tracer('four', []) to run the trace on the key four.

@bneigher: Updated the answer, it now gives you a trace of unique and ordered path. — Abhitalks, Oct 23 '15 at 09:50

Recursion through JavaScript Object

4 Answers4