current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

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"}
    ]}
]}
share|improve this question
2  
Could you explain the structure you want returned? The example isn't quite doing it for me. –  Casey Chu Jun 9 '11 at 22:39
    
Is your data guaranteed not to have circular references? What have you got so far? –  Mr E Jun 9 '11 at 22:39
    
So if the "c" name already exists anywhere in the structure, use it; otherwise create a new top-level name? –  Šime Vidas Jun 9 '11 at 22:42
    
It won't have circular references and there would only be one top node. I'm essentially serializing structured data into flat data, and need to be able to format it back to the structured data somehow on the client. Haven't gotten too far with this :( –  Devin McQueeney Jun 9 '11 at 22:45
2  
Is there any reason you can't serialize it to JSON? It'll make your life a lot easier... –  Mr E Jun 9 '11 at 22:48

2 Answers 2

up vote 0 down vote accepted

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;  
}
share|improve this answer
up vote 0 down vote

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;
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.