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;  
}