Transform comma separated input to JSON

Question

I'm hoping you guys can help me figure out how to separate the values at the root level. The expected output is shown below but what I'm getting is all the values get placed under the "ABC" item when there should be two objects at the root level in this example.

Note: there can be 1 or many different root level values that can have n levels separated by '|' character.

Input

            "values": [
                "ABC|A Type 1",
                "ABC|A Type 2|B Type 1",
                "ABC|A Type 2|B Type 2",
                "XYZ|X Type 1",
                "XYZ|X Type 2",
                "XYZ|X Type 3|Y Type 1",
            ]

Expected Output

[
    {
      "value": "ABC",
      "label": "ABC",
      "children": [
        {
          "value": "A Type 1",
          "label": "A Type 1",
        },
        {
          "value": "A Type 2",
          "label": "A Type 2",
          "children": [
            {
              "value": "B Type 1",
              "label": "B Type 1",
            },
            {
              "value": "B Type 2",
              "label": "B Type 2",
            }
          ]
        }
      ]
    },
    {
      "value": "XYZ",
      "label": "XYZ",
      "children": [
        {
          "value": "X Type 1",
          "label": "X Type 1",
        },
        {
          "value": "X Type 2",
          "label": "X Type 2",
        },
        {
          "value": "X Type 3",
          "label": "X Type 3",
          "children": [
            {
              "value": "Y Type 1",
              "label": "Y Type 1",
            }
          ]
        }
      ]
    }
  ]

What I have tried so far:

const input = {
  "values": [
    "ABC|A Type 1",
    "ABC|A Type 2|B Type 1",
    "ABC|A Type 2|B Type 2",
    "XYZ|X Type 1",
    "XYZ|X Type 2",
    "XYZ|X Type 3|Y Type 1",
  ]
};
let tree = {};
function fillTree(steps) {
  let current = null,
    existing = null,
    i = 0;

  for (let y = 0; y < steps.length; y++) {
    if (y === 0) {
      if (!tree.children || typeof tree.children == 'undefined') {
        tree = { label: steps[y], value: steps[y], children: [] };
      }
      current = tree.children;
    } else {
      existing = null;
      for (i = 0; i < current.length; i++) {
        if (current[i].label === steps[y]) {
          existing = current[i];
          break;
        }
      }
      if (existing) {
        current = existing.children;
      } else {
        if (y === steps.length - 1) {
          current.push({ label: steps[y], value: steps[y] });
        } else {
          current.push({ label: steps[y], value: steps[y], children: [] });
        }
        current = current[current.length - 1].children;
      }
    }
  }
}

for (let x = 0; x < input.values.length; x++) {
  let steps = input.values[x].split('|');
  fillTree(steps);
}
console.log('tree', JSON.stringify(tree));

Answer 1

Kind of a fun problem.

When building a nested tree-like data structure, it's helpful to build the tree with objects, as opposed to arrays, to quickly determine if a child key exists when building the tree. As in, this is easier to build:

{ ABC: children: [{ "A Type 2": { "B Type 1": {} }] }

Than this:

{ ABC: [{ name: "A Type 2", children: [{ name: "B Type 1": }] ] }

It's because when you're recursively building, with the first way (objects only) you can easily check if a child key exists, when looping over the elements and juggling the current node in a loop.

In general I think about breaking this problem down into a series of steps.

1. Parse the input data, as in split each row on |
2. Build the tree structure using objects
3. Iterate over the tree structure to build your desired new data structure shape.

If the desired output was nested objects rather than arrays with children, I would combine the second two steps.

The code below takes advantage of Javascript shorthand and fat arrow functions.

const values = [
    "ABC|A Type 1",
    "ABC|A Type 2|B Type 1",
    "ABC|A Type 2|B Type 2",
    "XYZ|X Type 1",
    "XYZ|X Type 2",
    "XYZ|X Type 3|Y Type 1",
];

const buildTree = values => values
  .map(v => v.split('|'))
  // For each row, build the nested tree structure
  .reduce((tree, [root, ...children]) => {
    // Start at the root, like "ABC". If this node doesn't already
    // exist in the tree we're building, add it
    let node = tree[root] = tree[root] || {};

    // Juggle the current child, like "X Type 1", and progressively
    // add children to the tree if they don't exist
    for(let childKey of children) {
      if(!(childKey in node)) {
        node[childKey] = {};
      }
      node = node[childKey];
    }

    return tree;
  }, {}); // The {} here represents our starting tree

// Recursively map over each node and its children to "expand" the
// object values into full nodes.
const expandTree = values =>
  Object.entries(values).map(([key, value]) => ({
    value: key,
    label: key,
    children: expandTree(value)
  }));

console.log(expandTree(buildTree(values)));

The last function, if you aren't familiar, takes advantage of the fact arrow function behavior where you can return an object literal without a return statement, if you wrap the object in ( and ).

The above code mixes two paradigms. It first does a loop based nested tree building, where you juggle the current node. Then it does a recursive process to iterate over the tree structure. Here's another option that makes both operations recursive. It makes a shallow copy of each node every time it builds the tree, which isn't as performant, but for shallow tree depths this isn't a worry.

const buildNode = (tree, [key, ...rest]) =>
  key
    ? {
        ...tree,
        [key]: buildNode(tree[key] || {}, rest)
      }
    : tree;

const buildTree = (values) =>
  values.map((v) => v.split("|")).reduce(buildNode, {});