Skip to content

Instantly share code, notes, and snippets.

@mitsos1os
Last active May 29, 2024 14:02
Show Gist options
  • Save mitsos1os/fa11f49281c525a1bf351f939605a176 to your computer and use it in GitHub Desktop.
Save mitsos1os/fa11f49281c525a1bf351f939605a176 to your computer and use it in GitHub Desktop.
flatten deep nested JSON object without recursion
const assert = require('assert').strict;
/**
* Pretty basic implementation to showcase non recursiveness.
* It would need to check for things such as Circular References in objects
*/
function flatten(source) {
const result = {};
// create an array that will hold depth-first keys as we encounter them during iteration
let keysArr = Object.keys(source);
// hold processed object stack that will be used as a guide on what object we are now processing and its ancestors
const objArr = [source];
// keep path hierarchy to easily produce flattened keys
const pathArray = [];
// as long as we have keys to process
while (keysArr.length) {
const key = keysArr.shift(); // take first key
let currentObject = objArr[0]; // take top object from processing stack
/*
rough check for object finished browsing. If object does not have property it
should mean that we finished iterating its properties and current property is
from previous object in stack
*/
if (!Object.hasOwn(currentObject, key)) {
// we have finished iterating this object
objArr.shift(); // remove from stack
currentObject = objArr[0]; // update current object variable
pathArray.pop(); // also remove path added for nested object that we were browsing
}
pathArray.push(key); // add current key in helper path array
const value = currentObject[key];
if (value == null || typeof value !== 'object') {
// leaf value
result[pathArray.join('.')] = value;
pathArray.pop(); // end of processing of leaf value, remove from helper path
} else {
// object, add to browsing items
keysArr = Object.keys(value).concat(keysArr); // add the keys of the object to be processed
objArr.unshift(value); // since its an object, add it in object stack, since its keys will be picked up next
}
}
return result;
}
assert.deepStrictEqual(
flatten({
one: 1,
middle: { middle: 'a' },
two: 2,
b: [1,2,3],
a: null
}),
{
one: 1,
'middle.middle': 'a',
two: 2,
'b.0': 1,
'b.1': 2,
'b.2': 3,
a: null
}
);
assert.deepStrictEqual(
flatten({
a: [{b: 1}, {c: 2}]
}),
{
'a.0.b': 1,
'a.1.c': 2
}
);
@mitsos1os
Copy link
Author

Could make even better by keeping an object stack of structure:

{
  obj: object, // the current object in stack entry
  keys: string[], // the keys array of what remains to be visited for the current object,
  prefix: string, // the prefix of the currently browsed object in case it is a deeper than start level
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment