Create a tree from a list of strings containing paths of files - javascript

Question

Let's assume I have the following array:

[
    "About.vue", 
    "Categories/Index.vue", 
    "Categories/Demo.vue", 
    "Categories/Flavors.vue"
]

We use the Index.vue in each sub-folder to act as the parent of that folder. That means the above would look like:

[
  { 
    name: "About", 
    children: [] 
  }, 
  { 
    name: "Categories", 
    children: 
    [
      {
        name: "Index.vue", 
        children: [] 
      },
      {
        name: "Demo.vue", 
        children: [] 
      },
      { 
        name: "Flavors.vue", 
        children: [] 
      }
    ]
  }
]

I was able to get it working slightly by using the following tutorial: https://joelgriffith.net/array-reduce-is-pretty-neat/

However, the thing about that is that it is a root object with a property for each file, as opposed to an array with an object for each file.

The following code produces the intended output:

let paths = [
    "About.vue", 
    "Categories/Index.vue", 
    "Categories/Demo.vue", 
    "Categories/Flavors.vue"
];


let helper = {
  index: -1,
  name: ""
};

function treeify(files) {
  var fileTree = [];

  function mergePathsIntoFileTree(prevDir, currDir, i, filePath) {

    helper.name = currDir;
    helper.index = i;
      
    if (helper.index == 0) {
      let index = prevDir.findIndex(x => x.name == helper.name);
      if (index < 0) {
        prevDir.push({
          name: helper.name,
          children: []
        });
      }
      
      return prevDir;
    }
    
    if (helper.index >= 0) {
      let obj = {
        name: currDir,
        children: []
      };
      
      prevDir[helper.index].children.push(obj);
      helper.index = i;
      helper.name = currDir;
    }
   
  }

  function parseFilePath(filePath) {
    var fileLocation = filePath.split('/');

    // If file is in root directory, eg 'index.js'
    if (fileLocation.length === 1) {
      fileTree[0] = {
        name: fileLocation[0],
        children: []
      };
    } else {
      fileLocation.reduce(mergePathsIntoFileTree, fileTree);
    }
  }

  files.forEach(parseFilePath);

  return fileTree;
}

console.log(treeify(paths));

However, it fails on the following input:

let paths = [
    "About.vue", 
    "Categories/Index.vue", 
    "Categories/Demo.vue", 
    "Categories/Flavors.vue",
    "Categories/Types/Index.vue",
    "Categories/Types/Other.vue"
];

Does anyone know a solution to get it working for further nested lists of paths?

Answer 1

My answer is inspired from @Nenad Vracar. But unlike his solution where he used for each and reduce which I think unnecessary.

let final = {result:[]};

for (const path of paths) {
  let context = final;
  
  for (const name of path.split('/')) {
    if (!context[name]) {
      context[name] = {result:[]};
      context.result.push({name, children: context[name].result});
    }
    
    context = context[name];
  }
}

console.log(final.result)

Answer 2

The following solution was derived from @nenad-vracar's answer. One shortcoming with his answer is that if a path contains "result", the code will fail. A simple workaround would be to rename "result" to "", that is, include characters that cannot appear in a path.

export interface IPathNode {
  name: string;
  children: IPathNode[];
  path: IPath | null;
}

export interface IPath {
  key: string;
  directory: boolean;
}

interface IPathLevel {
  // ["<result>"]: IPathNode[];
  [key: string]: IPathLevel | IPathNode[];
}

export const createPathTree = (paths: IPath[]): IPathNode | null => {
  const level: IPathLevel = { ["<result>"]: [] as IPathNode[] };

  paths.forEach((path) => {
    path.key.split("/").reduce(
      ((
        currentLevel: IPathLevel,
        name: string,
        index: number,
        array: string[]
      ) => {
        if (!currentLevel[name]) {
          currentLevel[name] = { ["<result>"]: [] };
          (currentLevel["<result>"] as IPathNode[]).push({
            name,
            children: (currentLevel[name] as IPathLevel)[
              "<result>"
            ] as IPathNode[],
            /* Attach the path object to the leaf node. */
            path: index === array.length - 1 ? path : null,
          });
        }

        return currentLevel[name];
      }) as any,
      level
    );
  });

  const finalArray = level["<result>"] as IPathNode[];
  return finalArray.length > 0 ? finalArray[0] : null;
};

console.log(
  JSON.stringify(
    createPathTree([
      {
        key: "/components/button.tsx",
        directory: false,
      },
      {
        key: "/components/checkbox.tsx",
        directory: false,
      },
      {
        key: "/result",
        directory: true,
      },
    ]),
    null,
    4
  )
);

Output:

{
    "name": "",
    "children": [
        {
            "name": "components",
            "children": [
                {
                    "name": "button.tsx",
                    "children": [],
                    "path": {
                        "key": "/components/button.tsx",
                        "directory": false
                    }
                },
                {
                    "name": "checkbox.tsx",
                    "children": [],
                    "path": {
                        "key": "/components/checkbox.tsx",
                        "directory": false
                    }
                }
            ],
            "path": null
        },
        {
            "name": "result",
            "children": [],
            "path": {
                "key": "/result",
                "directory": true
            }
        }
    ],
    "path": null
}

Answer 3

I went with @Nenad Vracar's answer (and upvoted, thank you!), but I also had the need to allow duplicate filenames in my use case. I just wanted to share how I did that.

let paths = ["About.vue","Categories/Index.vue","Categories/Demo.vue","Categories/Flavors.vue","Categories/Types/Index.vue","Categories/Types/Other.vue","Categories/Types/Other.vue","Categories/Types/Other.vue"];

let result = [];
let level = {result};

paths.forEach(path => {
  path.split('/').reduce((r, name, i, a) => {
    if(!r[name]) {
      r[name] = {result: []};
      r.result.push({name, children: r[name].result});
    } else if (i === a.length - 1) {
      // Allow duplicate filenames.
      // Filenames should always be at the end of the array.
      r.result.push({name, children: []});
    }
    
    return r[name];
  }, level)
})

console.log(result)

Answer 4

So, first off, I am going to assume this is in Node.js, second, I am currently at home so I don't have access to node.js at the moment so I had no real way of testing the code, however the following code should work.

What you need to do is check the contents of the folder and then make a check to see if an item in the folder is a directory or not, if true, call the function again with the new path (a.k.a. recursion).

So first you start by reading the folder, add each item's name to the .name property of the object, then you check if it's a folder or not, if it is, recursive for that path. Keep returning an array of objects back (this will be added to the .children property.

var fs = require('fs');

var filetree = DirToObjectArray('path/to/folder/');

function DirToObjectArray(path) {
        var arr = [];
    var content =  fs.readdirSync(path, { withFileTypes: true });
        for (var i=0; i< content.length; i++) {
        var obj = new Object({
        name: "",
        children: []
     });

     obj.name = content[i].name;

     if (content[i].isDirectory()) {
       obj.children = DirToObjectArray(path + content[i].name + "/");
     }

            arr.push(obj);
   }
   return arr;
}

If you are not using node.js but in-browser javascript, I can't help you with that

Answer 5

You can create this structure using forEach method to loop each path and split it to array on /, then you can also use reduce method to create nested objects.

let paths = ["About.vue","Categories/Index.vue","Categories/Demo.vue","Categories/Flavors.vue","Categories/Types/Index.vue","Categories/Types/Other.vue"];

let result = [];
let level = {result};

paths.forEach(path => {
  path.split('/').reduce((r, name, i, a) => {
    if(!r[name]) {
      r[name] = {result: []};
      r.result.push({name, children: r[name].result})
    }
    
    return r[name];
  }, level)
})

console.log(result)

Answer 6

You could take an iterative approach for every found name part and get an object and return the children for the next search.

var paths = ["About.vue", "Categories/Index.vue", "Categories/Demo.vue", "Categories/Flavors.vue", "Categories/Types/Index.vue", "Categories/Types/Other.vue"],
    result = paths.reduce((r, p) => {
        var names = p.split('/');
        names.reduce((q, name) => {
            var temp = q.find(o => o.name === name);
            if (!temp) q.push(temp = { name, children: [] });
            return temp.children;
        }, r);
        return r;
    }, []);

console.log(result);

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