JavaScript function to generate tree object from flat object

Question

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.

Answer 1

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;
}

Answer 2

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.

• Benjamin Gruenbaum: 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: babeljs.io/repl ).
• sunny: @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?
• Benjamin Gruenbaum: 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.
• sunny: Yeah, JavaScript folks have such a high tolerance for uncertainty vis a vis the standards! Thanks for this info.
• Madara's Ghost: 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.