find possible paths in map : recursive function in javascript

Question

doc = {
  'a': {
    'b': {
      'c': 'hello'
    },
    'd': {
      'c': 'sup',
      'e': {
        'f': 'blah blah blah'
      }
    }
  }
}

function get(json, path) {
  var str = path.split('.');
  var temp = json;
  var arr = [];
  var keystr = "";
  for (var i = 0; i < str.length; i++) {
    if (str[i] != "*") {

      keystr += str[i] + ".";

      if (temp[str[i]] === undefined)
        break;
      else {
        temp = temp[str[i]];
        if (i == str.length - 1) {
          var nObj = {};
          nObjKey = keystr.substr(0, keystr.length - 1);
          nObj[nObjKey] = temp
            // console.log("Obj check" + JSON.stringify(nObj) + keystr)
          arr.push(nObj);
        }
      }
    } else {
      for (var key in temp) {
        var concat = key + "."
        for (var j = i + 1; j < str.length; j++)
          concat += str[j] + ".";
        if (temp[key] !== undefined && temp[key] instanceof Object) {

          var m = keystr + concat.substr(0, concat.length - 1);
          var obj = (get(temp, concat.substr(0, concat.length - 1)));

          if (obj != "") {
            // console.log("existing arr "+JSON.stringify(arr))
            obj[m] = (obj[0])[concat.substr(0, concat.length - 1)]
              //  console.log("hello "+JSON.stringify(obj) + " end hello")
            arr.push(obj);
          }
        } else if (temp[key] !== undefined && i == str.length - 1) {
          // arr.push(temp);
        }
      }
    }
  }
  return arr;
}

var result = (get(doc, 'a.*.e'))
console.log(result)

For input of 'a.*.e' the output should be {'a.d.e': {'f': 'blah blah blah'}}}. But I get all the replacement for wild card as well in the array. I am sure something is wrong but not able to detect it. Help would be appreciated.

Nina Scholz · Answer 1 · 2017-04-01T20:07:58.510

You could change the structure of the operation a little bit with a recursive approach and an exit early exit often paradigm with checking of single parts with exit options, like

length, a part result is found,
falsy or not object types,
part at index is a star, then iterate all keys from the object, or
the part at index is a key, then call the function again.

At the end, with a found path, joint the path and generate a new property with the actual value of the object.

function get(object, path) {

    function iter(o, p, i) {
        if (i === parts.length) {
            result[p.join('.')] = o;
            return;
        }
        if (!o || typeof o !== 'object') {
            return;
        }
        if (parts[i] === '*') {
            Object.keys(o).forEach(function (k) {
                iter(o[k], p.concat(k), i + 1);
            });
            return;
        }
        if (parts[i] in o) {
            iter(o[parts[i]], p.concat(parts[i]), i + 1);
        }
    }

    var result = {},
        parts = path.split('.');

    iter(object, [], 0);
    return result;
}

var doc = { a: { b: { c: 'hello' }, d: { c: 'sup', e: { f: 'blah blah blah' } } } };

console.log(get(doc, 'a.*.e'));
console.log(get(doc, 'a.*.c'));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Version with * as wildcard for any level.

function get(object, path) {

    function iter(o, p, i) {
        if (i === parts.length) {
            result[p.join('.')] = o;
            return;
        }
        if (!o || typeof o !== 'object') {
            return;
        }
        if (parts[i] === '*') {
            Object.keys(o).forEach(function (k) {
                iter(o[k], p.concat(k), i);
                iter(o[k], p.concat(k), i + 1);
            });
            return;
        }
        if (parts[i] in o) {
            iter(o[parts[i]], p.concat(parts[i]), i + 1);
        }
    }

    var result = {},
        parts = path.split('.');

    iter(object, [], 0);
    return result;
}

var doc = { a: { b: { c: 'hello' }, d: { c: 'sup', e: { f: 'blah blah blah' } } } };

console.log(get(doc, 'a.*.e'));
console.log(get(doc, 'a.*.c'));
console.log(get(doc, 'a.*.f'));

.as-console-wrapper { max-height: 100% !important; top: 0; }

doesn't work for `get(doc, 'a.*.f')` if `*` is meant to work for arbitrary depth. great answer tho, otherwise ^^ — Mulan, Apr 01 '17 at 19:37
Ha, I didn't mean to imply you had to support it! Great work tho! — Mulan, Apr 01 '17 at 20:46

trincot · Answer 2 · 2017-04-01T19:39:24.490

First of all, since your desired output {'a.d.e': {'f': 'blah blah blah'}}} does not contain any array, but only plain objects, you should not need the variable arr in your code.

Instead, return nObj as function result, and declare it at the start, never clearing it.

Secondly, when you come back from the recursive call, the results need to be copied while prefixing the paths with what you already had. Note that checking for an empty array should not be done with != "", but anyway, you don't need that any more.

You could write this from scratch in different ways (see solution at end of answer), but I have first adapted your code to only change the bare minimum, with comments where I made the changes to make it work:

function get(json, path) {
  var str = path.split('.');
  var temp = json;
  var arr = [];
  var keystr = "";
  // *** Define here the object to return
  var nObj = {};
          
  for (var i = 0; i < str.length; i++) {
    if (str[i] != "*") {
      keystr += str[i] + ".";
      if (temp[str[i]] === undefined)
        break;
      else {
        temp = temp[str[i]];
        if (i == str.length - 1) {
          // *** Move this to start of the function
          //var nObj = {}; 
          nObjKey = keystr.substr(0, keystr.length - 1);
          nObj[nObjKey] = temp
        }
      }
    } else {
      for (var key in temp) {
        var concat = key + "."
        for (var j = i + 1; j < str.length; j++)
          concat += str[j] + ".";
        if (temp[key] !== undefined && temp[key] instanceof Object) {

          var m = keystr + concat.substr(0, concat.length - 1);
          var obj = get(temp, concat.substr(0, concat.length - 1));
          // *** Return value is object with path(s) as keys
          // *** Don't compare array with string
          //if (arr != "") { 
            // *** Iterate over the returned object properties, and prefix them 
            for (var deepKey in obj) {
                nObj[keystr + deepKey] = obj[deepKey];
            }
            //*** No need for array; we already have the object properties
            //arr.push(obj);
          //}
        // *** No need for array
        //} else if (temp[key] !== undefined && i == str.length - 1) {
          // arr.push(temp);
        }
      }
    }
  }
  // *** Return object 
  return nObj;
}

var doc = {
  'a': {
    'b': {
      'c': 'hello'
    },
    'd': {
      'c': 'sup',
      'e': {
        'f': 'blah blah blah'
      },
    },
    'g': {
      'e': {
        'also': 1
      }
    }
  }
}

var result = (get(doc, 'a.*.e'));
console.log(result);

Please also consider not name objects json when they are not: JSON is a text format, JavaScript object variables are not the same thing as JSON.

Compact ES6 solution

When you are used to array functions like reduce and a functional programming style, the following compact ES6 solution might appeal to you:

function get(obj, path) {
    if (typeof path === 'string') path = path.split('.');
    return !path.length ? { '': obj } // Match
        : obj !== Object(obj) ? {} // No match
        : (path[0] === '*' ? Object.keys(obj) : [path[0]]) // Candidates
            .reduce( (acc, key) => {
                const match = get(obj[key], path.slice(1)); // Recurse
                return Object.assign(acc, ...Object.keys(match).map( dotKey => 
                    ({ [key + (dotKey ? '.'  + dotKey : '')]: match[dotKey] })
                ));
            }, {});
}

const doc = {
  'a': {
    'b': {
      'c': 'hello'
    },
    'd': {
      'c': 'sup',
      'e': {
        'f': 'blah blah blah'
      },
    },
    'g': {
      'e': {
        'also': 1
      }
    }
  }
};

const result = get(doc, 'a.*.e');
console.log(result);

Excellent work adapting the author's original code; that's usually the hardest thing to do – as an aside, I noticed that your answer fails for `get(doc, 'a.b.c')`. It also fails for `get(doc, 'a.*.f')` but I'm not sure if the `*` is only meant to be a wildcard for *one* level of nesting, or multiple levels. — Mulan, Apr 01 '17 at 19:35
Thanks @naomik, corrected for `get(doc, 'a.b.c')`. Indeed, I had understood the `*` was for one level. — trincot, Apr 01 '17 at 19:41

Mulan · Answer 3 · 2017-10-05T01:05:38.517

List monad

Here's a solution which borrows ideas from the List monad to represent a computation which may have 0, 1, or more results. I'm not going to cover it in detail and I've only included enough of the List type to get a working solution. If you're interested in this sort of approach, you can do some more research on the topic or ask me a follow-up question.

I'm also using an auxiliary find function which is the recursive helper for get which operates the array of keys that get prepares

If you like this solution, I've written about the list monad in some other answers; you might find them helpful ^_^

const List = xs =>
  ({
    value:
      xs,
    bind: f =>
      List (xs.reduce ((acc, x) =>
        acc.concat (f (x) .value), []))
  })

const find = (path, [key, ...keys], data) =>
  {
    if (key === undefined)
      return List([{ [path.join('.')]: data }])
    else if (key === '*')
      return List (Object.keys (data)) .bind (k =>
        find ([...path, k], keys, data[k]))
    else if (data[key] === undefined)
      return List ([])
    else
      return find ([...path, key], keys, data[key])
  }

const get = (path, doc) =>
  find ([], path.split ('.'), doc) .value

const doc =
  {a: {b: {c: 'hello'},d: {c: 'sup',e: {f: 'blah blah blah'}}}}
  
console.log (get ('a.b.c', doc))
// [ { 'a.b.c': 'hello' } ]
   
console.log (get ('a.*.c', doc))
// [ { 'a.b.c': 'hello' }, { 'a.d.c': 'sup' } ]

console.log (get ('a.*', doc))
// [ { 'a.b': { c: 'hello' } },
//   { 'a.d': { c: 'sup', e: { f: 'blah blah blah' } } } ]

console.log (get ('*.b', doc))
// [ { 'a.b': { c: 'hello' } } ]

Native arrays only

We don't have to do fancy List abstraction in order to achieve the same results. In this version of the code, I'll show you how to do it using nothing but native Arrays. The only disadvantage of this code is the '*'-key branch gets a little complicated by embedding the flatmap code inline with our function

const find = (path, [key, ...keys], data) =>
  {
    if (key === undefined)
      return [{ [path.join ('.')]: data }]
    else if (key === '*')
      return Object.keys (data) .reduce ((acc, k) =>
        acc.concat (find ([...path, k], keys, data[k])), [])
    else if (data[key] === undefined)
      return []
    else
      return find ([...path, key], keys, data[key])
  }

const get = (path, doc) =>
  find([], path.split('.'), doc)

const doc =
  {a: {b: {c: 'hello'},d: {c: 'sup',e: {f: 'blah blah blah'}}}}

console.log (get ('a.b.c', doc))
// [ { 'a.b.c': 'hello' } ]

console.log (get ('a.*.c', doc))
// [ { 'a.b.c': 'hello' }, { 'a.d.c': 'sup' } ]

console.log (get ('a.*', doc))
// [ { 'a.b': { c: 'hello' } },
//   { 'a.d': { c: 'sup', e: { f: 'blah blah blah' } } } ]

console.log (get ('*.b', doc))
// [ { 'a.b': { c: 'hello' } } ]

Why I recommend the List monad

I do personally recommend the List monad approach as it keeps the body of the find function most clean. It also encompasses the concept of ambiguous computation and allows you to reuse that wherever you might require such a behaviour. Without using the List monad, you would rewrite the necessary code each time which adds a lot of cognitive load on the understanding of the code.

Adjust the shape of your result

The return type of your function is pretty weird. We're returning an Array of objects that only have one key/value pair. The key is the path we found the data on, and the value is the matched data.

In general, we shouldn't be using Object keys this way. How would we display the results of our match?

// get ('a.*', doc) returns
let result =
  [ { 'a.b': { c: 'hello' } },
    { 'a.d': { c: 'sup', e: { f: 'blah blah blah' } } } ]

result.forEach (match =>
  Object.keys (match) .forEach (path =>
    console.log ('path:', path, 'value:', match[path])))
    
// path: a.b value: { c: 'hello' }
// path: a.d value: { c: 'sup', e: { f: 'blah blah blah' } }

What if we returned [<key>, <value>] instead of {<key>: <value>}? It's much more comfortable to work with a result in this shape. Other reasons to support this is a better shape for your data is something like Array#entries or Map#entries()

// get ('a.*', doc) returns proposed
let result =
  [ [ 'a.b', { c: 'hello' } ],
    [ 'a.d', { c: 'sup', e: { f: 'blah blah blah' } } ] ]

for (let [path, value] of result)
  console.log ('path:', path, 'value:', value)

// path: a.b value: { c: 'hello' }
// path: a.d value: { c: 'sup', e: { f: 'blah blah blah' } }

If you agree this is a better shape, updating the code is simple (changes in bold)

// List monad version
const find = (path, [key, ...keys], data) => {
  if (key === undefined)
    return List ([[path.join ('.'), data]])
  ...
}

// native arrays version
const find = (path, [key, ...keys], data) => {
  if (key === undefined)
    return [[path.join ('.'), data]]
  ...
}

find possible paths in map : recursive function in javascript

3 Answers3

Compact ES6 solution

Linked

Related