10
\$\begingroup\$

The following function takes an object of items in the format of

{
  'complex-key': 'value',
  // Repeat
}

where complex-key is a key delimited by dots, and returns an object in the form of a tree, where you can access the value by traversing the parts of the complex keys as keys in the object (see examples below).

The function

function createMessages(items) {
    var result = {};
    Object.keys(items).forEach(function(key) {
        var keyParts = key.split('.');
        var currentObj = result;
        while (keyParts.length > 0) {
            var currentKey = keyParts.shift();
            if (keyParts.length === 0) {
                var currentItems = {};
                if (currentObj[currentKey]) {
                    currentItems = currentObj[currentKey];
                }
                currentObj[currentKey] = function() { return items[key]; };
                Object.keys(currentItems).forEach(function(currentItemKey) {
                    currentObj[currentKey][currentItemKey] = currentItems[currentItemKey];
                });
            }
            else if (!currentObj[currentKey]) { currentObj[currentKey] = {}; }
            currentObj = currentObj[currentKey];
        }
    });
    return result;
}

Examples

var message1 = createMessages({'a.b.c.d': 42});
console.log(message1.a.b.c.d() === 42); // true

var message2 = createMessages({'a.b.c.d': 42, 'a.b.c.e': 43});
console.log(message2.a.b.c.d() === 42); // true
console.log(message2.a.b.c.e() === 43); // true

var message3 = createMessages({'a.b.c.d': 42, 'a.b.c': 43});
console.log(message3.a.b.c() === 43); // true
console.log(message3.a.b.c.d() === 42); // true (properties on the functions)

The current function looks overly bloated and inefficient (with \$O(n\times m)\$ at best, and \$O(n\times m^2)\$ at worst). While this is going to be used for test code only, and to small objects only (no more than 10 keys), I would still want to find a way to make it prettier and more efficient. Would appreciate any and all help.

\$\endgroup\$
8
\$\begingroup\$

Here is what I'd do. I'd split it into two actions - adding a single property and assigning them all.

Adding a single property is just adding a function if it's something like "a", and it's adding a property to a sub-object if it's something like "a....". So let's use recursion and break it up into those two use cases:

  • If it's at length one , create the function (but keep all the keys for the third example).
  • If it's more, call it recursively and create a property.

This translates to the following JS:

function walkTheChain(arr, val, obj){
  if(arr.length === 1) return obj[arr[0]] = Object.assign(() => val, obj[arr[0]]);
  if(!(arr[0] in obj)) obj[arr[0]] = {};
  walkTheChain(arr.slice(1), val, obj[arr[0]]);
}

Now, creating the whole object is just a matter of applying it to all the keys passed in:

function createMessages(map){
  var obj = {};
  for(var key in map) walkTheChain(key.split("."), map[key], obj);
  return obj;
}
\$\endgroup\$
2
\$\begingroup\$

I really like @BenjaminGruenbaum's answer, but I'm going to post a non-recursive alternative that might be a little easier to digest.

You can get to a shorter, easier-to-understand function by avoiding unneeded control statements

It's unnecessary to keep checking whether keyParts is down to a length of 0, when in fact it's quite predictable when this will happen. You can structure your code to take advantage of this predictability with a for loop rather than a while loop. This along with corresponding structural changes and the nifty Object.assign(()=>val... technique I saw in @BenjaminGruenbaum's post took the function from 22 to 13 lines. These changes make the structure of the method easier to follow, in my opinion.

function createMessages(items) {
    var result = {};
    Object.keys(items).forEach(function(key) {
        var keyParts = key.split('.');
        currentObj = result;
         for(i = 0; i < (keyParts.length-1); i++){
            if(!currentObj[keyParts[i]]) currentObj[keyParts[i]] = {} ;
            currentObj = currentObj[keyParts[i]] ;
         }
        currentObj[ keyParts[keyParts.length - 1] ]  = Object.assign( () => items[key], currentObj)
    })
    return result;
}

Optimize the data structure (if you can) before optimizing your algorithm

You can simplify your function by 4 lines already if you change your data formatting requirements. Specifically, if you could change the formatting requirements of this 'flat' data so that all data has to be stored in a 'leaf', at the end of a unique path not fully contained in another path, you could eliminate this portion of your code:

            Object.keys(currentItems).forEach(function(currentItemKey) {
                currentObj[currentKey][currentItemKey] = currentItems[currentItemKey];
            });

This would improve the readability and efficiency of your code substantially, and also, in my opinion, make the code make more sense.

Additional points

  • In any case your function was probably too long, particularly given that it's not just a bunch of HTML manipulation. You could have broken your two cases (keyParts.length === 0 and otherwise) into two function calls and moved the work to these two function calls, say function addFinalPathComponent and addIntermediatePathComponent.
  • Personally I'd prefer shortening the current prefixes in your variable names to cur but I may be out of the mainstream on this one.
  • Your use of currentItems and items was a bit confusing to me. I might change the parameter name to flatObject and result into treeObject for easier understanding.
\$\endgroup\$
  • \$\begingroup\$ Nice answer, note that that programmers.se post is wrong, modern JavaScript does support tail recursion - the code in my answer will likely compile to a tail call since the last thing it does is a single recursion (you can see for yourself babel transform it to tail recursion to ES5 here: goo.gl/o1OE6X ). \$\endgroup\$ – Benjamin Gruenbaum Sep 30 '15 at 18:02
  • \$\begingroup\$ @BenjaminGruenbaum thanks for the update. Will delete that note about the recursive-iterable comparison in that case. How outdated is this? There's a not on that SE-programmers post from early 2014 saying recursion still seems to have a performance penalty. Or are you just saying the stack overflow problem is unlikely? \$\endgroup\$ – sunny Sep 30 '15 at 18:07
  • 1
    \$\begingroup\$ Well, it's an ES2015 thing, ES2015 has only been out for 2-3 months and not all browsers implement tail recursion. Transpilers do, and I think chrome does (at least in a branch) but it's far from "everywhere". That said, as a language JS does have tail recursion and since OP is writing that code for testing I assume the environment they run also supports it - that said, that is mostly relevant with big stacks (say - over 1000 depth), with stacks of depth 4-5 it shouldn't make a difference anyway. \$\endgroup\$ – Benjamin Gruenbaum Sep 30 '15 at 18:09
  • \$\begingroup\$ Yeah, JavaScript folks have such a high tolerance for uncertainty vis a vis the standards! Thanks for this info. \$\endgroup\$ – sunny Sep 30 '15 at 18:10
  • \$\begingroup\$ I can't change the result data format. It's meant to mock a (very ugly) part of our code for unit testing. Thanks for your answer! +1. I'll look into it in-depth later. \$\endgroup\$ – Madara Uchiha Sep 30 '15 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.