how to convert a flat javascript array into a nested graph structure?

Question

how would I convert this flat json structure:

[
    ["a","b","c"],
    ["a","b","d"],
    ["c","b","e"],
    ["c","b","f"]
]

Into the following graph structure using javascript?

{"uri": "a", "subItems": [
    {"uri": "b", "subItems": [
        {"uri": "c", "subItems": [
            {"uri": "b", "subItems": [
                {"uri": "e"},
                {"uri": "f"}
            ]}
        ]},
        {"uri": "d"}
    ]}
]}

Answer 1

I think this should get you REALLY close. It wraps the entire JSON result in an array, which was done to simplify the getNode function but you could easily just grab the [0] index of the array. I started out trying to conform to JSLint (hence the i = i + 1 instead of i++), but I gave up half way through so the code could be cleaned up a bit. ;)

http://jsfiddle.net/Zcyca/

var i, j, k, arr = 
[
    ["a","b","c"],
    ["a","b","d"],
    ["c","b","e"],
    ["c","b","f"]        
];

var results = [];
var last = results;

for(i = 0; i < arr.length; i = i + 1) {
    var subArr = arr[i];  
    var parentURI = subArr[0], middleURI = subArr[1], childURI = subArr[2]; 
    var parent, middle, child;

    // Find parent or create parent
    parent = getNode(results, parentURI);        
    if(parent === null) {
        results.push({"uri": parentURI, "subItems": []});
        parent = results[results.length-1];
    }        
    if(typeof parent["subItems"] === "undefined") {
        parent["subItems"] = [];
    }

    // Find middle or create middle
    middle = getNode(parent["subItems"], middleURI);
    if(middle === null) {
        parent["subItems"].push({"uri": middleURI, "subItems": []});
        middle = parent["subItems"][parent["subItems"].length-1];        
    }
    if(typeof middle["subItems"] === "undefined") {
        middle["subItems"] = [];
    }    

    // Find child or create child 
    child = getNode(middle["subItems"], childURI);
    if(child === null) {
        middle["subItems"].push({"uri": childURI});
        //child = middle["subItems"][middle["subItems"].length-1];            
    }
}

document.write(JSON.stringify(results));

function getNode(arr, uri) {
    var node = null;

    (function recurseArr(arr) {
        for(var i = 0; i < arr.length; i = i + 1) {
            var obj = arr[i];
            if(obj["uri"] === uri) {
                node = arr[i];
                break;   
            } else if(typeof obj["subItems"] !== "undefined") {  
                recurseArr(obj["subItems"]);
            }
        }
    })(arr);      

  return node;  
}

Answer 2

There is not "easy" way it seems.

I wasn't sure how to handle what to do where t needs to find another match for example if you were to add ["b", "e", "b"] where should it go? the "b" on the second level or the fourth?

http://jsfiddle.net/qVFCe/3/

var data = [
["a", "b", "c"],
["a", "b", "d"],
["c", "b", "e"],
["c", "b", "f"]
];

var group = null;

var baseStructure = {
    "uri": null,
    "subItems": []
};


function find(parent, uri) {
    for (var i = 0; parent.subItems && i < parent.subItems.length; i++) {
        if (parent.subItems[i].uri == uri) {
            return parent.subItems[i];
        }
    }
    return null;
}

function findRecursive(parent, uri) {
    var i, obj;
    //look in children
    for (i = 0; parent.subItems && i < parent.subItems.length; i++) {
        obj = find(parent.subItems[i], uri);
        if (obj !== null) {
            return obj;
        }
    }
    //look recursively in children
    for (i = 0; parent.subItems && i < parent.subItems.length; i++) {
        obj = findRecursive(parent.subItems[i], uri);
        if (obj !== null) {
            return obj;
        }
    }
    return null;
}


for (var i = 0; (group = data[i]); i++) {
    var current = baseStructure;
    for (var j = 0; j < group.length; j++) {
        var obj = find(current, group[j]);

        if (obj === null && j === 0) {
            obj = findRecursive(current, group[j]);
        }

        if (obj === null) {
            //create a new one if not found
            obj = {
                uri: group[j]
            };
            if(current.subItems === undefined)
            {
                current.subItems = [];
            }
            current.subItems.push(obj);
        }
        current = obj;
    }
}