Convert paths with items to tree object

Question

I'm trying to convert an array of object contains paths with item to tree of data so I wrote a function path loop on the path:

From this array:

[
  { userName: "1", tags: ["A;B"] },
  { userName: "2", tags: ["A;B"] },
  { userName: "3", tags: ["A;"] },
  { userName: "4", tags: ["A;B;C"] },
  { userName: "5", tags: ["A;B"] },
  { userName: "6", tags: ["A;B;C;D"] } 
]

to this structure:

[{
    name: "A",
    families: [{
        name: "B",
        families: [{
            name: "C",
            families: [{
                name: "D",
                families: [],
                items: ["6"]
            }],
            items: ["4"]
        }],
        items: ["1", "2", "5"]
    }],
    items: ["3"]
}]

function convertListToTree(associationList) {
    let tree = [];
    for (let i = 0; i < associationList.length; i++) {
        let path = associationList[i].tags[0].split(';');
        let assetName = associationList[i].userName;
        let currentLevel = tree;
        for (let j = 0; j < path.length; j++) {
            let familyName = path[j];
            let existingPath = findWhere(currentLevel, 'name', familyName);
            if (existingPath) {
                if (j === path.length - 1) {
                    existingPath.items.push(assetName);
                }
                currentLevel = existingPath.families;
            } else {
                let assets = [];
                if (j === path.length - 1) {
                    assets.push(assetName)
                }
                let newPart = {
                    name: familyName,
                    families: [],
                    items: assets,
                };
                currentLevel.push(newPart);
                currentLevel = newPart.families;
            }
        }
    }
    return tree;
}

function findWhere(array, key, value) {
    let t = 0;
    while (t < array.length && array[t][key] !== value) {
        t++;
    }
    if (t < array.length) {
        return array[t]
    } else {
        return false;
    }
}

But I have some issue here that the expected output is not like I want

[
  {
    "name": "A",
    "families": [
      {
        "name": "B",
        "families": [
          {
            "name": "C",
            "families": [
              {
                "name": "D",
                "families": [],
                "items": [
                  "6"
                ]
              }
            ],
            "items": [
              "4"
            ]
          }
        ],
        "items": [
          "1",
          "2",
          "5"
        ]
      },
      {
        "name": "",
        "families": [],
        "items": [
          "3"
        ]
      }
    ],
    "items": []
  }
]

Can someone please help me to fix that

Answer 1

Allow me to make two small changes, and ramda's mergeDeepWithKey will do most of the work for you.

---

Changes, before we start:

• Make tags an array rather than an array containing one string (i.e. tags[0].split(";"))
• Allow families to be a dictionary-like object rather than an array (if you ever need your array format, it's Object.values(dict))

---

Solution:

1. Transform every entry to a path of the desired format using reduce
2. Merge all paths with custom logic:
   • When merging name entries, don't change the name
   • When merging items entries, concatenate

const inp = [
  { userName: "1", tags: ["A","B"] },
  { userName: "2", tags: ["A","B"] },
  { userName: "3", tags: ["A"] },
  { userName: "4", tags: ["A","B","C"] },
  { userName: "5", tags: ["A","B"] },
  { userName: "6", tags: ["A","B","C","D"] } 
];

// Transform an input element to a nested path of the right format
const Path = ({ userName, tags }) => tags
  .slice(0, -1)
  .reduceRight(
    (families, name) => ({ name, families: { [families.name]: families },
      items: []
    }),
    ({ name: last(tags), families: {}, items: [userName] })
  );
    
// When merging path entries, use this custom logic
const mergePathEntry = (k, v1, v2) => 
  k === "name" ? v1 :
  k === "items" ? v1.concat(v2) :
  null;


const result = inp
  .map(Path)
  // Watch out for inp.length < 2
  .reduce(
    mergeDeepWithKey(mergePathEntry)
  )

console.log(JSON.stringify(result, null, 2));

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>
<script>const { mergeDeepWithKey, last } = R;</script>

Answer 2

The idea here is to iterate the data (the reduce loop), and whenever a node is missing from the Map (nodesMap), use createBranch to recursively create the node, create the parent (if needed...), and then assign the node to the parent, and so on. The last step is to get a unique list of root paths (A in your data), and extract them from the Map (tree) to an array.

const createBranch = ([name, ...tagsList], nodesMap, node) => {
  if(!nodesMap.has(name)) { // create node if not in the Map
    const node = { name, families: [], items: [] };
    
    nodesMap.set(name, node);
    
    // if not root of branch create the parent...
    if(tagsList.length) createBranch(tagsList, nodesMap, node);
  };

  // if a parent assign the child to the parent's families
  if(node) nodesMap.get(name).families.push(node);
};

const createTree = data => { 
  const tree = data.reduce((nodesMap, { userName: item, tags: [tags] }) => {
    const tagsList = tags.match(/[^;]+/g).reverse(); // get all nodes in branch and reverse
    const name = tagsList[0]; // get the leaf
    
    if(!nodesMap.has(name)) createBranch(tagsList, nodesMap); // if the leaf doesn't exist create the entire branch
    
    nodesMap.get(name).items.push(item); // assign the item to the leaf's items
  
    return nodesMap;
  }, new Map());
  
    // get a list of uniqnue roots 
  const roots = [...new Set(data.map(({ tags: [tags] }) => tags.split(';')[0]))];
  
  return roots.map(root => tree.get(root)); // get an array of root nodes
}

const data = [{"userName":"1","tags":["A;B"]},{"userName":"2","tags":["A;B"]},{"userName":"3","tags":["A;"]},{"userName":"4","tags":["A;B;C"]},{"userName":"5","tags":["A;B"]},{"userName":"6","tags":["A;B;C;D"]}];

const result = createTree(data);

console.log(result);

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

Answer 3

You should be able to use recursion to achieve this, using getFamilies and getUsers functions called at each level:

const allTags = ["A", "B", "C", "D"];

let a = [ { "userName": "1", "tags": ["A;B"] }, { "userName": "2", "tags": ["A;B"] }, { "userName": "3", "tags": ["A;"] }, { "userName": "4", "tags": ["A;B;C"] }, { "userName": "5", "tags": ["A;B"] }, { "userName": "6", "tags": ["A;B;C;D"] } ];

// This function assumes order is not important, if it is, remove the sort() calls.
function arraysEqual(a1, a2) {
    return a1.length === a2.length && a1.sort().every(function(value, index) { return value === a2.sort()[index]});
}

function getUserNames(tags, arr) {
    return arr.filter(v => arraysEqual(v.tags[0].split(';').filter(a => a),tags)).map(({userName}) => userName);
}

function getFamilies(tags) {
    if (tags.length >= allTags.length) return [];
    const name = allTags[tags.length];
    const path = [...tags, name];
    return [{ name, families: getFamilies(path), items: getUserNames(path, a)}];
}

let res = getFamilies([]);
console.log('Result:', JSON.stringify(res, null, 4));