Efficient function to create JSON data from a file directory structure?

Question

As in the title, I have a directory structure, I want to convert it to JSON format compatible with jsTree use . Thus, the output for this list

INPUT:

./Simple Root Node ./Root Node 2 ./Root Node 2/Child 1 ./Root Node 2/Child 2 

OUTPUT:

 treeJSON = [ { "id" : "ajson1", "parent" : "#", "text" : "Simple root node" }, { "id" : "ajson2", "parent" : "#", "text" : "Root node 2" }, { "id" : "ajson3", "parent" : "ajson2", "text" : "Child 1" }, { "id" : "ajson4", "parent" : "ajson2", "text" : "Child 2" }, ] 

My method:

I am currently taking every line from the input. Say ./Root Node 2/Child 1 , then I map the first folder, creating an array like { "id" : "ajson2", "parent" : "#", "text" : "Root node 2" } . Then go recursively for the next deletion of the first folder. Take by creating a clean array as { "id" : "ajson4", "parent" : "ajson2", "text" : "Child 2" } .

I do this for each line in the input, and then use my unique array function, as in http://jsfiddle.net/bsw5s60j/8/ , to remove all duplicate arrays that were created. For example, { "id" : "ajson2", "parent" : "#", "text" : "Root node 2" } will be created twice. Going through the 3rd line, and then the 4th line.

Obviously, this code is HIGHLY inefficient. If I have about 1.3K directories, then suppose everyone has 4 subdirectories, we have 5.2K arrays that need to be checked for duplicates.

This creates a hge problem. Is there any other efficient way I can twaek this code?

Fiddle: (only works with Chrome because of the webkit file attribute) http://jsfiddle.net/bsw5s60j/8/

Javascript

  var input = document.getElementById('files'); var narr = []; var fileICON = "file.png"; //when browse button is pressed input.onchange = function (e) { var dummyObj = []; var files = e.target.files; // FileList for (var i = 0, f; f = files[i]; ++i) { var fname = './' + files[i].webkitRelativePath; narr = $.merge(dummyObj, (cat(fname))); } treeJSON = narr.getUnique(); // getting the JSON tree after processing input console.log(JSON.stringify(treeJSON)); //creating the tree using jstree $('#tree') .jstree({ 'core': { 'check_callback': true, 'data': function (node, cb) { cb.call(this, treeJSON); } } }); var tree = $('#tree').jstree(true); tree.refresh(); }; //get unqiue array function Array.prototype.getUnique = function () { var o = {}, a = []; for (var i = 0, l = this.length; i < l; ++i) { if (o.hasOwnProperty(JSON.stringify(this[i]))) { continue; } a.push(this[i]); o[JSON.stringify(this[i])] = 1; } return a; }; // categorizing function which converts each ./Files/Root/File.jpg to a JSON var objArr = []; var folderArr = []; function cat(a) { if (!a.match(/\/(.+?)\//)) { var dummyObj = {}; var fname = a.match(/\/(.*)/)[1]; dummyObj.id = fname; dummyObj.text = fname; if (folderArr === undefined || folderArr.length == 0) { dummyObj.parent = '#'; } else { dummyObj.parent = folderArr[(folderArr.length) - 1]; dummyObj.icon = fileICON; // add extention and icon support } objArr.push(dummyObj); return objArr; } else { if (a.charAt(0) == '.') { var dummyObj = {}; var dir1 = a.match(/^.*?\/(.*?)\//)[1]; dummyObj.id = dir1; dummyObj.text = dir1; dummyObj.parent = '#'; dummyObj.state = { 'opened': true, 'selected': true }; // not working folderArr.push(dir1); objArr.push(dummyObj); var remStr = a.replace(/^[^\/]*\/[^\/]+/, ''); cat(remStr); return objArr; } else { var dummyObj = {}; var dir1 = a.match(/^.*?\/(.*?)\//)[1]; dummyObj.id = dir1; dummyObj.text = dir1; dummyObj.parent = folderArr[(folderArr.length) - 1]; folderArr.push(dir1); objArr.push(dummyObj); var remStr = a.replace(/^[^\/]*\/[^\/]+/, ''); cat(remStr); return objArr; } } } 

HTML

  <input type="file" id="files" name="files[]" multiple webkitdirectory /> <div id="tree"></div> 

Any changes or suggestions will be very helpful! Thanks

Answer 1

Here is a simple algorithm that should do quite efficiently, using a map from file paths to its identifiers:

 var idcount = 0; var treeJSON = []; var idmap = {}; function add(dirs) { if (!dirs.length) return "#"; var name = dirs.join("/"); if (name in idmap) return idmap[name]; var dir = dirs.pop(); var parent = add(dirs); var id = "ajson" + ++idcount; treeJSON.push({id: id, parent: parent, text: dir}); return idmap[name] = id; } var files = e.target.files; // FileList for (var i=0; i<files.length; ++i) { var name = files[i].webkitRelativePath; add(name.split("/")); } return treeJSON; 

( updated jsfiddle demo )

Here's how you can use it for dynamic updates:

 // initalise JStree here var idcount = 0; var treeJSON = []; var idmap = {}; function add(dirs, isfolder) { if (!dirs.length) return "#"; var name = dirs.join("/"); if (name in idmap) { if (isfolder && idmap[name].icon) delete idmap[name].icon; return idmap[name]; } var dir = dirs.pop(); var parent = add(dirs, true); var id = "ajson" + ++idcount; var item = {id: id, parent: parent, text: dir} if (parent == "#") item.state = {opened:true, selected:true}; if (!isfolder && dir.indexOf(".") > 0) item.icon = fileICON; treeJSON.push(item); return idmap[name] = id; } input.onchange = function(e) { var files = e.target.files; // FileList for (var i=0; i<files.length; ++i) { var name = files[i].webkitRelativePath; add(name.split("/"), false); } // refresh JStree };